天津大学编译原理讲义-Part6属性文法和语法制导翻译ppt课件.ppt

《天津大学编译原理讲义-Part6属性文法和语法制导翻译ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、属性文法和语法制导翻译授课：胡静语义分析——面向语法的定义所处位置分析技术LL分析方法计算最左推导自顶向下的构造推导LL的分析表指出要对最左边的非终结符进行扩展时，所选的产生式。LR分析方法计算最右推导自底向上的构造推导使用LR的状态集合和符号栈LR分析表指出针对每一个状态，采用何种动作（移进/归约），并且下一个转入的状态是什么。我们可以使用这些技术来构造ASTAST复习推导：使用的产生式的序列S⇒E+S⇒1+S⇒1+E⇒1+2分析树：描述推导的图并不能表示产生式使用的顺序抽象语法树(AST)：从分

2、析树中去掉了那些不必要的信息。AST的数据结构潜在的AST构造LL/LR分析技术都潜在的构造出了AST分析树在推导过程中可以得到LLparsing:应用产生式的序列潜在的描述了ASTLRparsing：应用归约的序列潜在的描述了AST我们希望从分析过程中明确的创建AST：在分析器中添加一定的代码来明确的创建ASTAST的构造LL分析:对非终结符进行扩展•Example:AST的构造LR分析我们也需要添加一些代码使得AST可以明确的被构造出来。LR分析中AST的构造方法：将树的一部分存放在堆栈里对每个

3、在堆栈中的非终结符B，将以B作为根节点的自树也存放在堆栈里当分析器使用产生式B→γ实施一个归约操作时，为B构造一个AST的结点LR分析中AST的构造问题代码的结构混乱：进行语法分析的代码和构造AST的代码混在一起语法分析器的生成器：产生的语法分析器需要包含AST的构造代码如何使用语法分析器的自动生成器构造不同的AST数据结构？我们需要在分析阶段同时的进行其他的动作。比如，语义检查Syntax-DirectedDefinition解决方法:syntax-directeddefinition扩展每个文法

4、的产生式，使得每个产生式都和语义动作（代码）相关联：S→E+S{action}语法分析器的生成器将这些代码加入到生成的语法分析器中。当使用产生式进行归约时，对应的动作就会被执行。语义动作动作：用程序设计语言编写的代码和语法分析器的生成器的程序设计语言相同例如：Yacc=actionswritteninCCUP=actionswritteninJava动作需要访问语法分析栈！语法分析器的生成器将状态栈进行扩展，用那些用户定义的结构（分析树）去替换原先的符号动作代码应该可以引用状态需要一套命名机制命名机

5、制我们需要对那些在语义动作代码中可能用到的文法的符号进行命名。需要分别引用出现在不同地方的同一个非终结符号E→E1+E2需要对左边/右边的符号进行区别E0→E+E命名机制：YaccYacc:使用关键字:$1引用右边的第一个符号，$2引用右边的第二个符号，以此类推关键字$$引用左边的非终结符Yacc的例子expr::=exprPLUSexpr{$$=$1+$3;}构造AST使用语义动作构造ASTAST在分析过程中自底向上的构造例子分析栈保存了每个非终结符的值AST的设计保证AST的抽象性并不是对每个分

6、析树中的结点都要引入一个AST的结点。AST的设计不要使用一个单一的类AST_node例如对于像if,while,+,*,ID,NUM：classAST_node{intnode_type;AST_node[]children;Stringname;intvalue;…etc…}问题：必须要为每个不同的结点保留不同fields来保存其特性。不可扩展，对Java的类型检查没有帮助使用类的继承使用子类解决问题对每一个“感兴趣的”文法中非终结符的集合使用一个抽象类，(例如，产生式)E→E+E

7、E*E

8、-E

9、

10、(E)另一个例子可以使用syntax-directed定义在语法分析的时候进行语义检查例如，类型检查好处：有效率一个简单的编译过程可以完成多个任务坏处：代码结构混乱将语法分析和语义检查过程混在一起当AST结构改变的时候进行检查只能是自底向上的过程中类型声明的例子值的传递当创建AST的时候，也要把值属性进行传递。另一个例子值的传递值要两个方向传递：自顶向下和自底向上构造方法从语义检查阶段可以单独的构造AST反复检查AST并且进行语义检查(或其他动作)只有当树被建立起来并且他的结构是稳定的时候才能做。

11、这个过程有更多的灵活性，不容易出现错误属性文法目录虽然形式语义学的研究已经取得了许多重大进展，但目前在实际应用中比较流行的语义描述和语义处理的方法主要还是属性文法和语法制导翻译。本章研究内容：上下文无关文法所产生的语言的翻译。把属性附加到代表语法结构的文法符号上，可以将语义信息和程序设计语言的结构联系起来。属性的值是用与文法产生式相关联的“语义规则”来计算的。涉及的概念属性文法：关于语言翻译的高层次规格说明，隐蔽了具体实现细节，不显式的说明翻译发生的顺序(属性文法)语