《语法与语义分析讲义》由会员分享，可在线阅读，更多相关《语法与语义分析讲义（36页珍藏版）》请在金锄头文库上搜索。
1、(四) 语法与语义分析 常用的终结符号集 自顶向下分析 自底向上分析 虚拟机 递归子程序方法 逆波兰表达式 2 语法与语义分析 1.编译程序逻辑图 表 格 管 理 错误处理 源 程 序 词 法 分 析 语 法 分 析 中 间 代 码 生 成 中 间 代 码 优 化 目 标 代 码 生 成 目 标 程 序 3 一、常用的终结符号集 文法 定义：文法G是一个四元组，G=（VT，VN，S，P），其中 VT为终结符号集，这是个非空有限集。 VN为非终结符号集合，它也是非空有限集。 S为一文法开始符，是一个特殊的非终结符。S VN P是产生式的非空有限集，其中每个产生式（或称规则） 是一序偶（U，x）通
2、常写作Ux或U:=x; （ 或:= ）意为“由组成”或“产生”； 字汇表: V=(VT VN) VT VN= 4 1、首符号集 定义：设有文法G=（VT，VN，S，P），字汇表为V，则符号串 的首符号集定义为 First（）=| y， VT ， y V* 特别，若为空串，则有 First（ ）= 例如：文法：G=(i，+，*，(，)，T，E，F，E，P) 一、常用的终结符号集（续一） * 5 P： E:=E+T|T T:=T*F|F F:=i|(E) 则 First（E）=i,(; First(T*F)=I,(; First(i)=(; First(i+i)=i; 一、常用的终结符号集（续二）
3、 6 2、向前看集 定义：设有文法G=（VT，VN，S，P），非终结符号U的向 前看集定义为 Follow（U）=a|S Ua,a VTU# #:非终结符号U后面的符号串为空,则将U后的符号记作特殊 符号#; Follow(U)=所有含有U的句型中紧跟U之后的终结符U# 例如：文法：G=(i，+，*，(，)，T，E，F，E，P) 一、常用的终结符号集（续三 ） * 7 P： E:=E+T|T T:=T*F|F F:=i|(E) 则因: E E; E E+T; E (E) Follow（E）=#,+,); 一、常用的终结符号集（续四） * * * 8 P： E:=E+T|T T:=T*F|F F
4、:=i|(E) 则因: E F; E T*F +T; E F*F; E (F) Follow（E）=#,+,*,); 一、常用的终结符号集（续五） * * * * 9 一、常用的终结符号集（续六） 3、可选集 定义：设有文法G=（VT，VN，S，P），规则P中 A=:a,则该规则的可选集定义为: First(a), 当a不为空 Follow(A), 当a为空 Select(A=:a)= 10 一、常用的终结符号集（续七） 例如：文法：G=(a,b,c,d, ，S,B,S,P)其中 P: S=:aBc|bB B=:bB|d| Select(S=:aBc)=First(aBc)=a Select(
5、S=:bB)=First(bB)=b Select(B=:bB)=First(bB)=b Select(B=:d)=First(d)=d Select(B=: )=Follow(B)=c,#, 11 二、自顶向下分析 自顶向下分析的思路： 对于文法 G=（VT，VN，S，P），待分析的句子 （符号串）a，分析思路就是从 S出发，试图推导出符 号串 a. 从推导角度看，分析思路即为从文法的开始符开 始根据规则试图建立一个推导序列，若得到所给 的字符串则字符串得到识别，其结构符合文法， 否则不符合文法。（参见第二章） 12 二、自顶向下分析（续一） 例：文法：G=(i，+，-，/，*，(，)，T，
6、E，F，E，P) P： E:=T|E+T|E-T(1) T:=F|T*F|T/F(2) F:=i|(E) (3) 分析句子(i+i)-i是否符合文法： 符合文法 E E-T E-F E-i T-i F-i (E)-i (E+T)-i (E+F)-i (E+i)-i (T+i)-i (F+i)-i (i+i)-i 13 二、自顶向下分析（续二 ） 自顶向下分析的难点： 如果规则中含有一条或者多条类似（1）的 规则，则在推导过程中很难确定到底选用 那一条规则，如果采用遍历全部规则的方 法则最明显的缺点就是效率低。 E:=T1| T2 | T3 | T4 | .| Tn (1) 14 二、自顶向下分
7、析（续二 ） 难点解决： 候选式： 如有规则A:=T1| T2 | T3 | T4 | .| Tn ， 则Ti称为A的后选式。 思路：通过当前的输入字符a来决定对后选式的选择。 First(), 当不为空 Follow(A), 当为空 Select(A=: )= 方法： 1、首先对文法的每个规则A=: 求可选集。 15 二、自顶向下分析（续三 ） 3、如果非终结符有n个后选式，即A:=T1| T2 | T3 | T4 | .| Tn ，则要分（I）(II)两种情况： (I)首符号不相同 对于文法中有规则A:=T1| T2 | T3 | T4 | .| Tn ，若n个后选 式的首符号均不相同即F
8、irst(Ti) First(Tj)= (ij) 对于待分析的符号串，如果其第一个符号（即当前的输入 符号）为a，且有a First(Tk),则选择规则A:= Tk进行推导 ， 即选择后选式Tk。 2、 当不等于,则对当前输入的符号a，若有 a First() 则可以选用规则A=: 进行推导，即采用后选式。 16 二、自顶向下分析（续四 ） (II)首符号相同 对于文法中有规则A:=T1| T2 | T3 | T4 | .| Tn ，若 First(Ti) First(Tj) (ij) a:试探法回溯现象 b:左提左因子法修改文法，将问题转化到（I） 左提左因子: 文法中有规则 A:=aT1|
9、 aT2 | T3 | T4 | .| Tn且 First(Ti) First(Tj) = (i,j3,ij), First(Ti) a, (I=3,4,5) 改写文法规则为: A:= aV | T3 | T4 | .| Tn V:=T1|T2 17 二、自顶向下分析（续五） 例：文法：G=(a,b,x，Z，V，Z，P) P： Z:=aV|bZ (1) V:=baZ|x (2) 待分析符号串：bbabaax. 自顶向下分析： Z bZ bbZ bbaV bbabaZ bbabaaV bbabaax 18 推导与归约 begin if n1 then rfact:=n*rfact(n-1) el
10、se rfact:=1 end; 25 五、递归子程序方法(续二) 递归子程序出口和入口工作： 一）递归入口工作 二）递归出口工作 26 六、逆波兰表达式 简单表达式的表示法 中缀表达式 前缀表达式（波兰表示法） 后缀表达式（逆波兰表示法 ） 27 六、逆波兰表达式（续一） a + b 运算符运算分量 运算分量 28 中缀、前缀、后缀表示法功能等价 共同点： 1、运算符的个数不变； 2、运算分量的次序不变； 后缀表示法的好处： a:无括号，形式简洁； b:运算符的顺序与运算的次序完全相同。 六、逆波兰表达式（续一） 29 六、逆波兰表达式（续二） 逆波兰表达式中缀表达式 ab+c*(a+b)*
11、c abc+*a*(b+c) ab * c +a*b+c abc+d-*ef/+g-a*(b+c-d)+e/f-g 1.运算符出现的先后顺序即代表计算的先后顺序。 2.每次遇到运算符，取左端紧邻的两个（一个）运算分 量作为该运算符号的两个（一个）运算分量 30 六、逆波兰表达式（续三） 1、定义运算符号的优先级 用自然数来表示运算符的优先级。故也称优先数 中缀表达式逆波兰表达式 1.1常用运算符的优先数关系： Priority()Priority()Priority(*、/) Priority(+、-) :表示单目减（负号） (的优先数小于其右边运算符的优先数； (的优先数大于其左边运算符的优
12、先数； ）的优先数最低，其不进运算栈，也不进输出区。 31 六、逆波兰表达式（续四） 中缀表达式逆波兰表达式 2、具体步骤（参P131） 1.2运算符栈：存放暂时不能处理的运算符。 3、框图（参见下页） 32 开始 输入运算符的优先关系 由左至右扫描中缀表达式 运算分量 运算符 左括号( 右括号) 栈为空 栈为空 栈顶为（ 栈顶为（ 当前运算符优 先级大于栈顶 运算符优先级 结束 N Y 输 出 入 栈 退栈输出 Y YY 入 栈 N Y 入 栈 N Y Y Y 退栈 N 栈为空 Y error N 退栈输出Y error 退栈输出 N N N N N 33 六、逆波兰表达式 实例1 ： 34 实例2 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。
