LR分析器
维基百科,自由的 encyclopedia
LR分析器是一种自底向上(bottom-up)的上下文无关语法分析器。LR意指由左(Left)至右处理输入字符串,并以最右边优先派生(Right derivation)的推导顺序(相对于LL分析器)建构语法树。能以此方式分析的语法称为LR语法。而在LR(k)这样的名称中,k代表的是分析时所需前瞻符号(lookahead symbol)的数量,也就是除了目前处理到的输入符号之外,还得再向右引用几个符号之意;省略 (k)时即视为LR(1),而非LR(0)。
由于LR分析器尝试由分析树的叶节点开始,向上一层层透过文法规则的化简,最后规约回到树的根部(起始符号),所以它是一种自底向上的分析方法。许多编程语言使用LR(1)描述文法,因此许多编译器都使用LR分析器分析原始码的文法结构[来源请求]。LR分析的优点如下:
- 众多的编程语言都可以用某种LR分析器(或其变形)分析文法。(C++是个著名的例外)
- LR分析器可以很有效率的建置。
- 对所有“由左而右”扫描原始码的分析器而言,LR分析器可以在最短的时间内侦测到文法错误(这是指文法无法描述的字符串)。
然而LR分析器很难以人工的方式设计,一般使用“分析产生器(parser generator)”或“编译器的编译器(compiler-compiler,产生编译器的工具)”来建构它。LR分析器可根据分析表(parsing table)的建构方式,分类为“简单LR分析器(SLR, Simple LR parser)”、“前瞻LR分析器(LALR, Look-ahead LR parser)”以及“正统LR分析器 (Canonical LR parser)”。这些解析器都可以处理大量的文法规则,其中LALR分析器较SLR分析器强大,而正统LR分析器又比LALR分析器能处理更多的文法。著名的Yacc即是用来产生LALR分析器的工具。