一个lr分析器实质上是一个带有先进后出存储栈的( )

Question

如题所述

Answer 1

一个lr分析器实质上是一个带有先进后出存储栈的DFA。

简介

LR意指由左（Left）至右处理输入字符串，并以最右边优先派生（Right derivation）的推导顺序（相对于LL分析器）建构语法树。能以此方式分析的语法称为LR语法。

而在LR(k)这样的名称中，k代表的是分析时所需前瞻符号（lookahead symbol）的数量，也就是除了目前处理到的输入符号之外，还得再向右引用几个符号之意；省略（k）时即视为LR(1)，而非LR(0)。

由于LR分析器尝试由分析树的叶节点开始，向上一层层透过文法规则的化简，最后规约回到树的根部（起始符号），所以它是一种由下而上的分析方法。许多编程语言使用LR(1)描述文法，因此许多编译器都使用LR分析器分析源代码的文法结构。LR分析的优点如下：

1.众多的编程语言都可以用某种LR分析器（或其变形）分析文法。（C++是个著名的例外）

2.LR分析器可以很有效率的建置。

3.对所有“由左而右”扫描源代码的分析器而言，LR分析器可以在最短的时间内侦测到文法错误（这是指文法无法描述的字符串）。

LR分析器的结构

1.一个输入缓冲器，输入的源代码存储于此，分析将由第一个符号开始依序向后扫描。

2.一座堆栈，存储过去的状态与化简中的符号。

3.一张状态转移表（goto table），决定状态的移转规则。

4.一张动作表（action table），决定目前的状态碰到输入符号时应采取的文法规则，输入符号指的是终端符号（Terminals）与非终端符号（Non-terminals）。