《大连理工大学编译原理习题课》由会员分享，可在线阅读，更多相关《大连理工大学编译原理习题课（36页珍藏版）》请在金锄头文库上搜索。
1、编译原理习题课（第三章起 ）LL文法套路总结 1. 计算FIRST集合（第一个终结符，或者 ） 2. 计算FOLLOW集合（三个要点，0. 开始记号的FOLLOW包含$；1. 句型中非终结符后面有内容；2. 产生式右部末尾非终结符， 把左侧非终结符FOLLOW加入）。一遍可能算不完，不重不漏，注意推出的情况 3. 如果问是否是LL文法，用两条规则判断（ A | 有FIRST( ) FIRST( ) = ；若 * ，那么FIRST() FOLLOW(A) = ） 4. 如果要画非递归分析表（3个要点，0. 每行对应一个非终结符，每列对应一个终结符；1. 对于A 的FIRST集合，把产生式写在行列
2、(FIRST()交叉处；2. 如果在FIRST()，把A 写在行列(FOLLOW(A)交叉处）SLR文法套路总结 1. 拓广文法 2. 项目集规范族 1. 新加开始记号前加点号（初始状态的核心项目） 2. 算闭包（点号落在非终结符前，抄非终结符产生式，加点号，重复算闭包，直到算不下去为止） 3. 对闭包里每个点号后的符号（终结/非终结符均可）， 尝试点号向右移动一位（可能对应多个项目），得到新的核心项目。 对核心项目们算闭包，得到新状态（判断是否和已有状态重复）。从当前状态出发一条边，边上符号是点号移动跨过的符合，到达时新计算的状态 4. 按层次计算状态，直到算不下去位置（没有新的状态）SLR
3、文法套路总结 画SLR分析表 每个状态一行（上一页），每个终结符对应一列（动作），每个非终结符对应一列（转移） 对每一条边，看边上的符号 如果是终结符，从i状态到j状态，在第i行终结符对应列写sj，移进到状态j 如果是非终结符，从状态i到状态j，在第i行非终结符列，写j，转移 在所有状态中找点号在末尾（形如 A ）的项目，如果有，在状态对应行，FOLLOW(A)对应列写rj，j是A的编号 S S在状态i中，第i行$列写acc 问是不是SLR文法，画分析表，无冲突，则是；有则不是规范LR文法套路总结 1. 拓广文法 2. 项目集规范族 1. 新加开始记号前加点号，后面加入搜索符$（初始状态的核心
4、项目） 2. 算闭包（点号落在非终结符前AB, a ，抄非终结符产生式，加点号，算前向搜索符（FIRST( a )）。重复算闭包，直到算不下去为止）注意：可能出现点号终结符相同而搜索符不同观点项目，是不同的项目 3. 对闭包里每个点号后的符号（终结/非终结符均可），尝试点号向右移动一位（可能对应多个项目），得到新的核心项目。对核心项目们算闭包，得到新状态（判断是否和已有状态重复）。从当前状态出发一条边，边上符号是点号移动跨过的符合，到达时新计算的状态 4. 按层次计算状态，直到算不下去位置（没有新的状态）LR文法套路总结 画LR分析表 每个状态一行（上一页），每个终结符对应一列（动作），每个非
5、终结符对应一列（转移） 对每一条边，看边上的符号 如果是终结符，从i状态到j状态，在第i行终结符对应列写sj，移进到状态j 如果是非终结符，从状态i到状态j，在第i行非终结符列，写j，转移 在所有状态中找点号在末尾（形如 A , a ）的项目，如果有，在状态对应行，a对应列写rj，j是A的编号 S S在状态i中，第i行$列写accLALR文法套路总结 先按LR来做，得到DFA转换关系 忽略搜索符，找到所有项目能一一对应的状态 状态捏成一个（合并），加入搜索符（被合并状态中搜索符的并集） 按LR的方法画分析表S属性、L属性、自上而下、自下而上的关系 综合属性：产生式左部非终结符的属性，依赖右部符
6、号的属性（或左部其他属性） 继承属性：产生式右部非终结符属性，依赖其他符号的属性 S属性就是综合属性 L属性=S属性+依赖左侧记号属性的继承属性综合属性依赖左侧记号属性的继承属性自上而下（LL文法）函数返回值函数参数自下而上（LR文法）归约时执 行语义动 作 （ 栈代码）引入推出空串的标记非终结符，插入在有继 承属性的记号之前，把属性计算放在空串规 约为标记 非终结符的位置（栈代码）右部中左侧符合的属 性或左部的继承属性设计语法制导定义和翻译方案 两者区别：是否要求执行时机 重点：判断要使用继承属性还是综合属性 可以从文法出发，随意做一个/多个推导，得到一个分析树 判断要计算的值是 从下往上传
7、递（综合属性） 从上往下或从左往右传递（继承属性）语法分析1.考虑文法S - (L)|aL - L,S|S(a) 建立句子(a,(a,a)和(a,(a,a),(a,a)的分析树(b) 为(a)的两个句子构造最左推导(c) 为(a)的两个句子构造最右推导(d) 这个文法产生的语言是什么语法分析（a）分析树：(a,(a,a)：(a,(a,a),(a,a) ：语法分析（b）(a,(a,a)和(a,(a,a),(a,a)最左推导语法分析（c）(a,(a,a)和(a,(a,a),(a,a)最右推导语法分析（d）描述的语言：括号匹配的串，串中的各项由”,”隔开，项可以是括号匹配的子串或a语法分析2.考虑文
8、法S - aSbS|bSaS|(a) 为句子abab构造两个不同的最左推导，以说明此文法二义(b) 为abab构造对应的最右推导(c) 为abab构造对应的分析树(d) 这个文法产生的语言是什么语法分析（a）最左推导S=aSbS=abSaSbS=abaSbS=ababS=abab 或 S=aSbS=abS=abaSbS=ababS=abab（b）最右推导S=aSbS=aSb=abSaSb= abSab =abab（c）分析树（d）语言描述的语言是a,b数目相等的串语法分析3.证明下面文法是LL(1)的但不是SLR(1)文法.S A a A b | B b B aA B First(AaAb)=
9、a First(BbBa)=b First(AaAb) First(BbBa) = 文法是LL(1)的.构造SLR(1)项目集: I0: S .SS .AaAbS .BbBaA .B . Follow(A) = Follow(B) = a, b 存在归约-归约冲突, 该文法不是SLR(1)文法.证明如下：语法分析4.试说明没有一个左递归文法可以是LL(1)的。(1) 直接左递归文法中存在产生式:A A1 | A2 |.| Am | 1 | 2 |.| n, 其中 1 2 . n均不以A开头First(Ai) First( j) = First( j) 若 j *, First(A i) Fol
10、low(A) = First( i) , 不是LL(1)文法.(2) 间接左递归文法中存在产生式集合:A B1 1 | 1 | 2 |.| nB1 B2 2.Bm A First(B1 1) = First(A m . 1) First( j) First(B1 1) , j=1,.,nFirst( j) First(B1 1) , j=1,.,n若 j *, First(B1 1) Follow(A) = First( m . 1) , 不是LL(1)文法.语法分析5.证明下面文法是SLR(1)文法, 并构造其SLR分析表.E E + T (1) F F* (5)E T (2) F a (6
11、)T T F (3) F b (7)T F (4)I0: E .E E .E+TE .TT .TFT .FF .F*F .aF .bI1: E E.E E.+TI2: E T.T T.FF .F*F .aF .bI3: T F.F F.*I4: F a.I5: F b.I6: E E+.TT .TFT .FF .F*F .aF .bI7: T TF.F F.*I8: F F*.I9: E E+T.T T.FF .F*F .aF .bFollow(E) = +, $ Follow(T) = +, $, a, b Follow(F) = +, $, *, a, baction goto+ * a
12、b $ E T F 0 s4 s5 1 2 3 1 s6 acc 2 r2 s4 s5 r2 7 3 r4 s8 r4 r4 r4 4 r6 r6 r6 r6 r6 5 r7 r7 r7 r7 r7 6 s4 s5 9 3 7 r3 s8 r3 r3 r3 8 r5 r5 r5 r5 r5 9 r1 s4 s5 r1 7 语法制导的翻译6.对于输入的表达式 5*(4*3+2), 根据语法制导定义建立一棵带注释的分析树.Ln E.val=70 T.val=70F.val=5 * T.val=14 digit.lexval=5 F.val=14 ( E.val=14 )E.val=12 + T.v
13、al=2T.val=12 F.val=2T.val=4 * F.val=3 digit.lexval=2F.val=4 digit.lexval=3digit.lexval=4（lex表示是从词法分析来的）语法制导的翻译7. S L.L | LL L B | BB 0 | 1 (a) 试用各有关综合属性决定S.val.引入L的属性b记录2的L的位数次幂值 S L1.L2 S.val = L1.val +L2.val / L2.b; S L S.val = L.val; L L1 B L.val = L1.val *2 + B.val; L.b = L.b*2; L B L.val = B.val; L.b = 2; B 0 B.val = 0; B 1 B.val = 1;语法制导的翻译语法制导的翻译(b) 试用一个语法制导定义来决定S.val, 在这个定义中B仅有综合属性c,给出由B生成的位对于最后 的数值的分担额.引入B的继承属性i, 综合属性c
