《语义分析I》PPT课件.ppt

编译原理和技术,大连理工软件学院 胡 彦 ,LR(1)分析练习总结,课堂练习中的情况 不会构造识别活前缀DFA 知道构造识别活前缀DFA，但是项目集里的项目构建不完全，遗漏加点项 不会构造分析表,LR(1)分析练习题目,基于LR(1)项目来构造识别G活前缀的DFA，并基于DFA构建分析表.,S V = E S E V * E V id E V,LR(1)分析练习解答过程,答： Step 1. 对原文法进行拓广 (添加产生式S-S),S V = E S E V * E V id E V,S S S V = E S E V * E V id E V,LR(1)分析练习解答过程,Step 2: 构建识别（拓广）文法活前缀的DFA,I0: S-S, $ S-V=E, $ S-E, $ V-*E, =/$ V-id, =/$ E-V, $,I1: S-S, $,S,I2: S-V=E, $ E-V, $,V,E,I3: S-E, $,*,I4: V-*E, =/$ E-V, =/$ V-*E, =/$ V-id, =/$,id,I5: V-id, =/$,=,I6: S-V=E, $ E-V, $ V-*E, $ V-id, $,E,I8: S-*E, =/$,V,I9: E-V, =/$,*,id,指向I5,E,I10: S-V=E, $,*,I12 : V-*E, $ E-V, $ V-*E, $ V-id, $,V,I7: E-V, $,V,指向I7,id,I11: V-id, $,E,I13: S-*E, $,V,指向I7,*,id,指向I11,LR(1)分析练习解答过程,构建分析表 首先，为表达式编号 然后，计算action表和goto表,0 S S 1 S V = E 2 S E 3 V * E 4 V id 5 E V,LR(1)分析练习解答过程,构建分析表 Action(0,*)=s4, action(0,id)=s5 Goto(0,S)=1, goto(0,V)=2, goto(0,E)=3 Action(1,$)=acc Action(2,=)=s6 Goto(2,V)=7 Action(3,$)=r2 Action(4,*)=s4, action(4,id)=s5 Goto(4,E)=8, goto(4,V)=9 ,语义分析简介,编译程序的目标：将源程序翻译成为语义等价的目标程序 源程序与目标程序具有不同的语法结构，表达的结果却是相同的,语义分析简介,语义分析的功能 审查每个语法结构的静态语义 例：类型、运算、维数、越界 在验证完静态语义后，才执行真正的翻译 例：变量的存储分配 例：表达式的求值 例：语句的翻译（中间代码的生成）,语义分析简介,语义信息是上下文有关的 例如：变量使用前要先定义 文法定义可以写成：L=wcw|w是任意的a和b的串 其中第一个w代表标识符的声明 后一个w表示对标识符的引用 问题：这个文法不是上下文无关的,怎么办呢？,语义分析简介,目前情况 上下文无关文法 能够有效描述语言语法结构 具有有效的分析方法，如LR(1)、LALR等 程序语义 编译器进行翻译的时候所必须的信息 无法用上下文无关文法表示 这两者之间怎么衔接？,属性文法,属性文法,由Knuth在1968年提出 基本思想 为文法G描述的语法结构添加语义属性 通常是为每个语法树结点添加所需的属性描述 添加一系列的语义规则附加在文法G的产生式上 如果添加的语义规则是有副作用的，那么这种属性文法又称为语法制导定义,属性文法,表达式文法,E E + T | E T T T * F | T E F (E ) | F digit,为了计算表达式的值，首先为这个文法的非终结符添加val属性,4.1 语法制导的定义,例 简单台式计算器的语法制导定义,F.val := digit.lexval,T.val := F.val,T.val := T1.val * F.val,E.val := T.val,E.val := E1 .val + T.val,F.val := E.val,print (E.val),4.1 语法制导的定义,4.1.1 语法制导定义的形式 基础文法 每个文法符号有一组属性 每个文法产生式A 有一组形式为b := f(c1, c2, , ck )的语义规则，其中f 是函数，b和c1, c2, , ck 是该产生式文法符号的属性 综合属性：如果b是A的属性，c1 , c2 , , ck 是产生式右部文法符号的属性或A的其它属性。 继承属性：如果b是产生式右部某个文法符号X的属性， c1 , c2 , , ck 是产生式右部文法符号的属性或A的其它属性。,属性值由分析树中它的子结点的属性值来计算,属性值由结点的兄弟结点及父结点的属性值来计算。,4.1 语法制导的定义,关于属性的一些常识 终结符只有综合属性，并且这些综合属性通常由词法分析器提供 开始符号没有任何继承属性,因为开始符号没有任何的兄弟结点或者父结点。,4.1 语法制导的定义,4.1.2 综合属性 S属性定义：仅仅使用综合属性的语法制导定义,4.1 语法制导的定义,8+5*2 n的注释分析树,每个结点的属性值都标注出来的分析树，称为。,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,8+5*2 n,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,8+5*2 n,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,8+5*2 n,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,8+5*2 n,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,8+5*2 n,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,8+5*2 n,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,8+5*2 n,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,8+5*2 n,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,8+5*2 n,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,8+5*2 n,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,8+5*2 n,4.1 语法制导的定义,注释分析树:结点的属性值都标注出来的分析树,8+5*2 n,4.1 语法制导的定义,4.1.3 继承属性 int id, id, id,L.in := T.type,T. type := integer,T. type := real,L1.in := L.in;,addtype (id.entry, L.in ),addtype (id.entry, L.in ),综合属性计算,4.1 语法制导的定义,int id1, id2, id3的注释分析树,4.1 语法制导的定义,4.1.4