编译原理chapter4课件.ppt

第四章 抽象语法Abstract Syntax 计算机科学与技术学院 刘 慧 Abstract：从所有具体实例中提取出来的。 编译器的工作不仅是识别一个句子是否是属于某一文法的语言，它还必须对那个句子做更多的事情。 语法分析器中的语义动作(semantic action)能够对所分析的短语做一些有用的事情。 在递归下降分析器中，语义动作代码分散在实现语法分析的控制流中。 4.1 semantic actions 每个终结符和非终结符都可关联一个语义值类型。例如文法3.35 当然，与单词关联的类型必须与词法分析器随同这个单词一起返回的类型相匹配。 4.2 Abstract Parse Tree 为了有利于模块化，最好将语法分析与语义问题（类型检查和翻译成机器代码）分开处理。 达到此目的一种方法是由语法分析器生成语法分析树(Parse Tree)，每一个输入单词对应着树中的一个叶子结点，分析期间被规约的每一个语法规则对应着树中的一个内部结点——concrete parse tree。 具体分析树不便于在语义分析阶段直接使用： 标点符号单词中有许多是冗余的，而且不传递信息； 语法树的结构对文法的依赖程度太高！ 4.2 Abstract Parse Tree 抽象语法(Abstract Syntax)起到了在语法分析器和编译器的较后阶段之间建立一个清晰接口的作用。 抽象语法树传递源程序的短语结构，其中已解决了所有语法分析问题，但不带任何语义解释。 该文法无法分析：文法具有二义性，因为没有指明操作符的优先级，并且缺少起分隔作用的标点符号。 但是，该文法并不用于语法分析： 语法分析器使用具体语法来建立该抽象语法的语法树； 语义分析阶段使用该抽象语法树，它不会受文法二义性的困扰，因为它已经有了一棵语法树。 POSITIONS 在只有一遍的编译器中，词法分析、语法分析和语义分析都是同时进行的。 如果出现了一个必须向用户报告的类型错误，词法分析器的当前位置就应是最接近错误源的位置。 在这种编译器中，词法分析器保存着一个表示“当前位置”的全局变量，错误处理程序将随同每个错误消息一起输出这个变量的值。 POSITIONS 使用抽象语法树数据结构的编译器不必在一遍中完成所有的语法分析和语义分析。 它在许多方面简化了处理过程，但却稍微增加了产生语义错误信息的难度。 在语义分析还未开始前，词法分析器就已到达了文件尾，因此，如果在遍历抽象语法树期间检测到了一个语义错误，则不能用词法分析器的当前位置（文件结尾）来报告错误。 因此，应记住抽象语法树的每个节点在源文件中对应的位置，以防该节点发生语义错误。 POSITIONS 为了记住准确的位置，抽象语法数据结构必须带有pos域，用来指明导出抽象语法树的字符在源程序中的位置。 词法分析器必须向语法分析器报告每个单词在源文件的开始位置和结束位置。 * * 举例：对于规则A→BCD，语义动作返回的值的类型 必须是与非终结符A关联的类型。但它可以由所匹配 的终结符和非终结符B、C、D的相关值来建立这个返 回值。 Grammar 4.5 Abstract syntax of straight-line programs S→S;S L→ε S→id:=E L→L E S→print L E→id B→+ E→num B→- E→E B E B→× E→S, E B→ /