读入记号再归成结构

移进把输入记号及相应状态推进分析过程,归约则把已识别的产生式右部视为一个左部非终结符。分析器反复选择这些动作,逐步把输入归为开始符号所描述的结构。

LR的R指最右推导的逆向构造,并不是从右到左读取源文件。方法可以保留足够状态,在看过一部分输入后再决定较大结构,而不像简单预测式方法那样总须先选上层规则。

参考:[1]

状态与前瞻决定动作

状态可概括当前可能完成的产生式位置。动作表根据栈顶状态及前瞻记号选择移进、归约、接受或错误;归约后再利用转移表,确定归并到非终结符后的新状态。

因此一个分析器不只是找出字符后缀像哪条规则。栈记录此前路径,状态限制哪些规则此刻可用,前瞻又帮助决定是否应继续读取;忽略其中一层,可能在错误位置作出归约。

参考:[1]

冲突需要结合表构造解释

同一情形既可移进又可归约,称为移进—归约冲突;有多条归约可选,则是归约—归约冲突。它们可能来自文法歧义,也可能来自特定表构造丢失了作决定所需的信息。

LR家族有不同的状态与前瞻组织方式,生成器还可能使用优先级或更一般的分析策略。能否成功生成一张表,不等于语言含义已经正确;应核对冲突处理是否保留设计者期望的结构。

参考:[1] [2]