parsing - S属性定义自下而上求值中栈上文法符号表示状态的意义

Question

我正在阅读文本：编译器：Ullman 等人的原则、技术和工具。al (Red Dragon Book) 在那里我遇到了使用解析器对S-attributed语法进行自下而上评估的概念。LR现在我从本书的前几章中学到的是，LR解析器使用堆栈来跟踪 DFA（LR项目的规范集合）的状态来模拟 DFA。但是在下面给出的摘录中，他们似乎没有将状态编号（例如1or 2...）推入堆栈，而是使用某种unique grammar symbol which covers the state. 我不太明白这种新方法如何保留通常的行为。

解析器堆栈上的综合属性

S 属性定义的翻译器通常可以在LR-parser 生成器的帮助下实现。根据S-attributed定义，解析器生成器可以构造一个翻译器，在解析输入时评估属性。

自底向上解析器使用堆栈来保存有关已解析的子树的信息。我们可以使用解析器堆栈中的额外字段来保存合成属性的值。图 5.15 显示了一个解析器堆栈的示例，其中一个属性值具有空间。让我们假设，如图所示，堆栈是由一对数组state和实现的val。每个状态条目都是指向LR(1)解析表的指针（或索引）。（注意，语法符号隐含在状态中，不需要存储在堆栈中。）然而，通过放置在解析堆栈上时覆盖的唯一语法符号来引用状态是很方便的。如果第ith 个状态符号是A，那么val[i]将保存与 this 对应的解析树节点关联的属性的值A。

堆栈的当前顶部由指针顶部指示。我们假设在每次归约之前对合成属性进行评估。假设语义规则A.a := f(X.x, Y.y, Z.z)与产生式相关联A -> XYZ。BeforeXYZ归结为A，属性的值Z.z是 in val[top]，Y.yin的值val[top-1]，X.xin的值val[top-2]。如果符号没有属性，则val数组中的相应条目是未定义的。归约后，top减2，状态覆盖A放入state[top]（即 where Xwas），合成属性的值A.a放入val[top]。

标签： parsingcompiler-construction