《编译原理语法制导翻译》由会员分享，可在线阅读，更多相关《编译原理语法制导翻译（71页珍藏版）》请在金锄头文库上搜索。
1、第8章 语法制导翻译和 中间代码生成数计学院宋彩芳语义分析基础l编译程序的任务 将汇编语言或高级语言书写成的源程序转换成 等价的目标代码程序。其中要求目标代码程序和 源程序的语义（Semantics）必须相同。l语义分析的执行方式l语法分析程序直接调用相应的语义子程序进行处理l先生成语法树，再进行语义分析语义分析基础l语法与语义的关系l语法是指语言的结构、即语言的“样子”；l语义是指附着于语言结构上的实际含意 ，即语言的“ 意义”。l对于语法和语义：l语义不能离开语法独立存在；l语义远比语法复杂；l同一语言结构可以包含多种含意，不同语言结构表示相 同含意；l语法与语义之间没有明确的界线。语义分
2、析基础l语义分析的任务包括两方面l静态语义分析或静态审查（验证语法结构合格的程序是 否真正有意义）；l动态语义的解释执行（计算并生成中间代码）。l代码的生成方式l语义分析直接生成目标代码（快速编译）l语义分析生成中间代码（进一步进行优化）源语言程序中间代码汇编代码词法分析语义分析语法分析中间代码生成代码生成在编译中的逻辑阶段前端处理后端处理语义处理语义分析基础源语言程序汇编代码词法分析语义分析语法分析代码生成前端处理后端处理语义处理语义处理语义分析基础l语义处理的实现（第八章）l属性文法：描述语义规则。l语法制导翻译：在语法分析的同时，执行语义规则描述 的动作：检查静态语义生成中间代码/目标代
3、码l语义处理的环境（第九章）符号表l为语义分析提供类型、作用域等信息。l为代码生成提供类型、作用域、存储类别、存储（相对 ）位置等信息。主要内容l属性文法l语法制导翻译概论l计算语义规则lS-属性文法和自下而上翻译lL-属性文法和自上而下翻译lL-属性文法和自下而上翻译l中间代码生成l简单赋值语句的翻译l布尔表达式的翻译l控制结构的翻译l说明语句的翻译l数组和结构的翻译语义形式化形式语义学的研究已取得了许多重大的进展l文法模型- 属性文法l命令式或操作式模型 - 操作语义学l应用式模型-指称语义学l公理式模型-公理语义学语义形式化l采用属性文法和语法制导翻译对语义处理工进行 比较规范和抽象的描
4、述；l属性文法：包含一个上下文无关文法和一系列附在文法 产生式上的语义规则；l语法制导翻译：在语法分析过程中，完成附加在所使用 的产生式上的语义规则描述的动作。语法制导翻译l属性文法l语法制导翻译概论l计算语义规则lS-属性文法和自下而上翻译lL-属性文法和自上而下翻译lL-属性文法和自下而上翻译属性文法l属性文法的形式化定义 属性文法是一个三元组:A=(G,V,F),其中 G:是一个上下文无关文法。 V:有穷的属性集,每个属性与文法的一个终结 符或非终结符相连。 F:关于属性的断言或谓词集。每个断言与一个 产生式相联。属性文法l属性的抽象表示 例如：E.val（值） E.type（类型）E.
5、code（代码序列）E.place（存储空间）属性文法l文法G：lET1+T2|T1 or T2lTnum|true|falseETT+34ET1.t=T2.tTT2.t=intTT1.t=int+34ET1+T2 T1.t=int AND T2.t=int ET1orT2 T1.t=bool AND T2.t=bool Tnum T.t=int Ttrue T.t=bool Tfalse T.t=bool属性文法l属性文法是一个三元组:A=(G,V,F),其中 lG：基础文法lV：每个文法符号有一组属性lF：每个文法产生式A 有一组形式为b = f(c1, c2, , ck )的语义规则，其
6、中f 是函数，b和c1, c2, , ck 是 该产生式文法符号的属性l语义规则中的属性存在下述性质与关系 (1) 若b是A的属性，c1, c2, ., ck是中文法符号的属性 ，或者A的其它属性，则称b是A的综合属性。 (2) 若b是中某文法符号X的属性，c1, c2, ., ck是A的属 性，或者是中其它文法符号的属性，则称b是X的继承 属性属性文法l属性文法是一个三元组:A=(G,V,F),其中 lG：基础文法lV：每个文法符号有一组属性lF：每个文法产生式A 有一组形式为b = f(c1, c2, , ck )的语义规则，其中f 是函数，b和c1, c2, , ck 是该产生式 文法符
7、号的属性l语义规则中的属性存在下述性质与关系 (3) 称属性b依赖于属性c1, c2, ., ck。实质上反映了属性计 算的先后次序，即所有属性ci被计算之后才能计算属性b。 (4) 若语义规则的形式如下，则可将其想像为产生式左部文法 符号A的一个虚拟属性。属性之间的依赖关系，在虚拟属 性上依然存在。 f(c1, c2, ., ck) 属性文法l属性的特点：l一个结点的综合属性的值通过分析树中它的子结点的属 性值和自己的属性值计算的；l继承属性的值由结点的父结点、兄弟结点来计算的；l非终结符号即可有综合属性也可有继承属性，但文法开 始符号没有继承属性；l终结符号只有综合属性，由词法分析器提供，
8、即记号的 属性。l每个文法符号的综合属性和继承属性的交集为空；属性文法l属性文法的表示 属性文法是一种接近形式化的语义描述方法。 属性文法的表示分两部分：l先针对语义为文法符号设置属性，l然后为每个产生式设置语义规则，来描述各属性间的关 系。 一般将属性文法写成表格形式，每个文法规则用 相应规则的语义规则列出。 属性文法l文法规则 语义规则规则1 相关的属性规则 . . . .规则n 相关的属性规则属性文法 Production Semantic RulesL E print(E.val) E E1 + TE.val: = E1.val + T.val E TE.val := T.val T
9、T1 * FT.val := T1.val * F.val T FT.val := F.val F ( E ) F.val := E.val F digit F.val: = digit.lexval综合属性 S属性定义：仅仅使用综合属性的语法制导定义产 生 式 语 义 规 则 L E print (E.val) E E1 + T E.val = E1 .val + T.val E T E.val = T.val T T1 F T.val = T1.val F.val T F T.val = F.val F (E) F.val = E.val F digit F.val = digit.lex
10、val综合属性l将属性附着在分析树对应文法符号上，形成注释分 析树。（属性作为分析树的注释）l 8+5*2的分析树digitLE TETFdigitT+ FFdigit综合属性l将属性附着在分析树对应文法符号上，形成注释分 析树。（属性作为分析树的注释）l 8+5*2的注释分析树digit.lexvalLE.valT.valE.valT.valF.valdigit.lexvalT.val+F.valF.valdigit.lexval综合属性l将属性附着在分析树对应文法符号上，形成注释分 析树。（属性作为分析树的注释）l 8+5*2的注释分析树digit.lexval = 2LE.val = 1
11、8T.val = 10E.val = 8T.val = 8F.val = 8digit.lexval = 8T.val = 5+F.val = 5F.val = 2digit.lexval = 5综合属性 分析树各结点属性的计算可以自下而上地完成digit.lexval = 2LE.val = 18T.val = 10E.val = 8T.val = 8F.val = 8digit.lexval = 8T.val = 5+F.val = 5F.val = 2digit.lexval = 5继承属性 由父节点、兄弟结点的属性来定义的属性。 例：int id, id, id 产 生 式 语 义 规
12、 则 D TL L.in = T.type T int T. type = integer T real T. type = real L L1, id L1.in = L.in;addType(id.entry, L.in) L id addType(id.entry, L.in) 继承属性 int id1, id2, id3的注释分析树DintT.type = integer,id3L.in = integerL.in = integerL.in = integerid2id1,属性文法l基于属性文法的处理过程（语法制导翻译）l注释分析树上看继承属性与综合属性 l继承属性是自上而下计算的l
13、综合属性是自下而上计算的语法制导翻译l属性文法l语法制导翻译概论l计算语义规则lS-属性文法和自下而上翻译lL-属性文法和自上而下翻译lL-属性文法和自下而上翻译语法制导翻译l语法制导翻译过程：l对单词符号串进行语法分析，构造语法分析树；l根据需要构造属性依赖图；l遍历语法树，并在语法树各结点处按语义规则进行计算；计算语义规则l构造属性依赖图： for 分析树中每一结点n do for 结点n的文法符号的每一个属性a do为a在依赖图中建立一个结点； for 分析树中每一个结点n dofor 结点n所用产生式对应的每一条语义规则 b:f（c1，c2，ck ) dofor （i=1;i k;i+
14、) do从结点ci到结点b构造一条有向边；属性依赖图 real id1, id2, id3的分析树的依赖图产 生 式 语 义 规 则 D TL L.in = T.type T int T. type = integer T real T. type = real L L1, id L1.in = L.in;addType(id.entry, L.in) L id addType(id.entry, L.in) 属性依赖图 第一步：画语法树DrealT,id3LLLid2id1,产 生 式 语 义 规 则 D TL L.in = T.type T int T. type = integer T
15、real T. type = real L L1, id L1.in = L.in;addType(id.entry, L.in) L id addType(id.entry, L.in) 属性依赖图 第二步：每一属性建立 一结点；DrealT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 type产 生 式 语 义 规 则 D TL L.in = T.type T int T. type = integer T real T. type = real L L1, id L1.in = L.in;addType(id.entry, L.
16、in) L id addType(id.entry, L.in) 属性依赖图 第三步：为每一产生式 构造有向边；DrealT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 type产 生 式 语 义 规 则 D TL L.in = T.type T int T. type = integer T real T. type = real L L1, id L1.in = L.in;addType(id.entry, L.in) L id addType(id.entry, L.in) 属性依赖图 第三步：为每一产生式 构造有向边；DrealT,id3LLLid2id1,1 en
