编译原理第5章-语义分析

5.4 中间代码
四元式的特点: 1. 四元式出现的顺序和语法成份的计值 顺序相一致. 2. 四元式之间的联系是通过临时变量实 现的,这样易于调整和变动四元式. 3. 便于优化处理.
5.4 中间代码
编译系统中,有时将四元式表示成另一 种更直观,更易理解的形式——三地址代 码或三地址语句. 三地址代码形式定义为: result := arg1 OP arg2 三地址语句:语句中是三个量的赋值语句, 三地址语句 每个量占一个地址.
5.5 自下而上的语法制导翻译
例3 简单算术表达式翻译到四元式的 语义描述 例如,设有简单算术表达式的文法: E→E+E | E*E | (E) | i
T R / S T
c S a c
c R S
输入是bR / bTc / bSc /ac 输出为: 1 4 5 314 24 31 给出相应语义动作(翻 译方案) S→bTc { print "1"} { print "2"} S→a R T→R { print "3"} R→R/S { print "4"} R→S { print "5"}
5.1 概述
例如: 表达式 A+B*C 对运算对象进行类型检查, 对变 量进行先定义后使用检查 执行真正的翻译 如果静态语义正确, 语义处理则要执 行真正的翻译, 即生成程序的某种中间 代码的形式或直接生成目标代码.
5.1 概述
目前多数编译程序进行语义分析的方 法是采用语法制导翻译法 .它不是一种 采用语法制导翻译法 形式系统, 但它比较接近形式化. 语法制导翻译法使用属性文法为工具 来描述程序设计语言的语义.
5.4 中间代码

编译原理之语法分析与语义分析
语法分析（英语：syntactic analysis，也叫 parsing）是根据某种给定的对由单词序列（如英语单词序列）构成的输⼊⽂本进⾏分析并确定其语法结构的⼀种过程。

语法分析器使⽤由词法分析器⽣成的各个词法单元的第⼀个分量来创建树形的中间表⽰。

语义分析是审查源程序有⽆语义错误，为代码⽣成阶段收集类型信息。

语义分析器（semantic analyzer）使⽤语法树和符号表中的信息来检查源程序是否和语⾔定义的语义⼀致。

它同时也收集类型信息，并把这些信息存放在语法树或符号表中，以便在随后的中间代码⽣成过程中使⽤。

编译原理A1.简要说明语义分析的基本功能。

2. 考虑文法 G[S]:S → (T) | a+S | aT → T,S | S消除文法的左递归及提取公共左因子。

3试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。

4. 按照三种基本控制结构文法将下面的语句翻译成四元式序列：while (A<C ∧ B<D){if (A ≥ 1) C=C+1;else while (A ≤ D)A=A+2;}。

5. 已知文法 G[S] 为S → aSb|Sb|b，试证明文法 G[S] 为二义文法。

A答案1答：语义分析的基本功能包括: 确定类型、类型检查、语义处理和某些静态语义检查。

2解：消除文法G[S]的左递归：S→(T) | a+S | aT→ST′T′→,ST′| ε提取公共左因子：S→(T) | aS′S′→+S | εT→ST′T′→,ST′| ε3答：w a b + c d e 10 - / + 8 + * +4答：该语句的四元式序列如下(其中E1、E2和E3分别对应A＜C∧B＜D、A≥1和A≤D，并且关系运算符优先级高)：100 (j<,A,C,102)101 (j,_,_,113)102 (j<,B,D,104)103 (j,_,_,113)104 (j=,A,1,106)105 (j,_,_,108)106 (+, C, 1, C)107 (j,_,_,112)108 (j≤,A,D,110) 109 (j,_,_,112)110 (+, A, 2, A)111 (j,_,_,108)112 (j,_,_,100)1135答：证明：由文法G[S]：S→aSb|Sb|b，对句子aabbbb对应的两棵语法树为：因此，文法G[S]为二义文法。

编译原理B1.什么是句子？什么是语言 ?2. 写一文法，使其语言是偶正整数的集合,要求：(1)允许0打头；(2) 不允许0打头。

属性和文法符号相关联 规则和产生式相关联

根据需要，将文法符号和某些属性相关联， 并通过语义规则来描述如何计算属性的值


E→E1+T E.code=E1.code || T.code || ‘+’ code表示了我们关心的表达式的逆波兰表示，规则说明 加法表达式的逆波兰表示由两个分量的逆波兰表示并置， 然后加上‘+’得到。
digitlexval=3
18
适用于自顶向下分析的SDD


前面的表达式文法存在直接左递归，因 此无法直接用自顶向下方法处理。 消除左递归之后，无法直接使用属性val 进行处理：


比如规则：T→FT’ T’→*FT’ T对应的项中，第一个因子对应于F， 而运算符在T’中。
19
相同表达式的不同文法的比较
38
例5.15 分析栈实现的例子

假设语法分析栈存放在一个被称为stack 的记录数组中，下标top指向栈顶；


stack[top]指向这个栈的栈顶；stack[top-1] 指向栈顶下一个位置； 如果不同的文法符号有不同的属性集合，我 们可以使用union来保存这些属性值。（归 约时，我们知道栈顶向下的各个符号分别是 什么）
语义翻译的流程
输 入 符 号 串 分 析 树 依 赖 图
语
义
规
则
的 计
实际上，编译中语义翻译的实现并不是 按图中的流程处理的；而是随语法分析 的进展，识别出一个语法结构，就对它 的语义进行分析和翻译。
算
9
5.1 语法制导定义

4.什么是语法制导定义（SDD） 上下文无关文法和属性/规则的结合；