LR 分析

定义

LR 分析是一类自底向上的语法分析方法,名称含义为「从左到右扫描输入(L),构造最右推导的逆过程(R)」。由 Donald Knuth 于 1965 年提出。

原理

分析器维护一个状态栈,依据分析表在「移进」(把记号压栈)与「归约」(按产生式把栈顶符号串替换为非终结符)之间决策,直至归约出起始符号。分析表由文法的项目集自动机构造。

变体

按分析表构造精度分为 LR(0)、SLR、LALR(1)、规范 LR(1)。LALR(1) 在表大小与能力之间取得平衡,被 Yacc、Bison 采用;GLR 进一步支持歧义文法。

评价

LR 能识别几乎所有无歧义的上下文无关语言,能力强于 LL;但分析表由工具生成、难以手工推理,冲突(移进-归约冲突等)的排查也较为晦涩。