《《编译原理习题课》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《编译原理习题课》PPT课件.ppt（29页珍藏版）》请在金锄头文库上搜索。
1、习题课 令文法G E 为 E T E T E TT F T F T FF E i证明E T F是它的句型 指出这个句型的所有短语 直接短语和句柄 E E T E T F短语 E T F和T F直接短语 T F句柄 T F E E T T F 一个上下文无关文法生成的句子abbaa的推导树如图 1 给出该句子的相应的最左推导和最右推导 2 该文法的产生式集合P可能有哪些元素 3 找出该句子的所有的短语 简单短语 句柄 S ABS aBS aSBBS a BBS a bBS a bbS a bbAa a bbaa最左推导最右推导略产生式集合 S ABSB SBBS AaS B bA a短语 句柄
2、S A B S a S B B A a b b a 习题解答 7 给文法G S S aA bQA aA bB bB bD aQQ aQ bD bD bB aAE aB bFF bD aE b构造相应的最小的DFA 由于从S出发任何输入串都不能到达状态E和F 所以 状态E F为多余的状态 不予考虑 简化产生式后生成的NFA 因为4 5状态包含Z 所以都是终态 1 2 3 6 7都是非终态 1态输入b后为3 是非终态 2和3输入b后为4和5是终态 所以1和2 3是不同的状态 2和3是相同等价状态 4和5是等价状态 6何是等价状态 所以 最后剩下 1 2 4 6四个状态 最小化的DFA 1 2 4
3、3 7 6 a b b a a 5 b a b a b a b b a 8 给出下述文法所对应的正规式 S 0A 1BA 1S 1B 0S 0将A 1S 1和B 0S 0分别代入S 0A 1B得 S 01S 01S 10S 10得产生式 S 01S 10S 01 10化简得 S 01 10 S 01 10 S 01 10 01 10 得正规式 01 10 01 10 将图4 18的DFA最小化 并用正规式描述它所识别的语言 因为6 7是DFA的终态 其他是非终态 可将状态集分成两个子集 P1 1 2 3 4 5 P2 6 7 由于F 6 b F 7 b 6 而6 7又没有其他输入 所以6 7等
4、价 由于F 3 c F 4 c 3 F 3 d F 4 d 5 F 3 b 6 F 4 b 7 而6 7等价 所以3 4等价 由于F 1 b F 2 b 2 F 1 a 3 F 2 a 4 而3 4等价 所以1 2等价 由于状态5没有输入字符b 所以与1 2 3 4都不等价 综上所述 上图DFA的状态可最细分解为 P 1 2 3 4 5 6 7 最小化后的DFA 该DFA用正规式表示为 b a c da bb 习题解答 2 对下面的文法G E TE E E T FT T T F PF F F P E a b 计算这个文法的每个非终结符的FIRST集和FOLLOW集 证明这个方法是LL 1 的
5、构造它的预测分析表 S为文法开始符号 一定是FOLLOW S 元素设A B 是一个产生式 则First 的非空元素属于FOLLOW B 如果 则FOLLOW A 的元素就要加入到FOLLOW B 中 因为 D 1A 1A B 两个产生式 在推导过程中 可能会出现这样的句型S 1A 1 1 B 1 1 B 1 计算每个非终结符的FIRST和FOLLOW集合 计算每个非终结符的FIRST集合 FIRST E FIRST T FIRST F FIRST P a b FIRST E FIRST T FIRST F FIRST P a b FIRST T FIRST T a b FIRST F FIRS
6、T P a b FIRST F FIRST P FIRST P a b 计算每个非终结符的FOLLOW集合 FOLLOW E FOLLOW E FOLLOW E FOLLOW T FIRST E FOLLOW E 不包含 FOLLOW T FOLLOW T FIRST E FOLLOW E FOLLOW F FIRST T FOLLOW T a b 不包含 FOLLOW F FOLLOW F FIRST T FOLLOW T a b FOLLOW P FIRST F FOLLOW F a b 不包含 在求FOLLOW集合时 要特别注意P76页的定义 A B FOLLOW B 包含 的FIRST
7、元素 如果 则FOLLOW A 的元素就要加入到FOLLOW B 中 证明这个方法是LL 1 的 SELECT E TE FIRST T a b SELECT E E SELECT E FOLLOW E SELECT T FT FIRST F a b SELECT T T FIRST T a b SELECT T FOLLOW T SELECT F PF FIRST P a b SELECT F F SELECT F FOLLOW F a b SELECT P E SELECT P a a SELECT P b b SELECT P 预测分析表 习题 第3题 有文法G S S S S VV T
8、 ViTT F T FF V 给出 i 的规范推导 指出句型F Fi 的短语 句柄 素短语 G S 是否为OPG 若是 给出 1 中句子的分析过程 给每个产生式加标号 S V V T V ViT T F T T F F V F 给出 i 的规范推导 最右推导 S V ViT ViF Vi T i T F i T i F i i 指出句型F Fi 的短语 句柄 素短语 短语 F Fi F F F 直接短语 最左的直接短语为句柄 普通 素短语 F F算符优先意义的句柄 G S 是否为OPG 求所有非终结符的FIRSTVT求所有非终结符的LASTVT根据产生式求出所有优先关系 相等关系小于关系 终结
9、符在前 非终结符在后 利用非终结符的FIRSTVT 大于关系 非终结符在前 终结符在后 利用非终结符的LASTVT FIRSTVT和LASTVT 算符优先关系 是算符优先文法 i 的分析过程 证明下列文法不是LR 0 但是SLR 0 S AA Ab bBaB aAc a aAb 习题第7题 1 首先拓展文法 S AA AbA bBaB aAcB aB aAb 2 分解LR 0 项目 S A S A A Ab A A b A Ab A bBa A b Ba A bB a A bBa B aAc B a Ac B aA c B aAc B a B a B aAb B a Ab B aA b B a
10、Ab 3 构建NFA S A S A B aAc B a Ac B aA c B aAc A Ab A A b A Ab B a B a A bBa A b Ba A bB a A bBa B aAb B a Ab B aA b B aAb 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 a A b a a A c A A b b B a 19 有穷自动机的确定化 用LR 0 项目代替DFA状态图 1 S AA AbA bBa 6 A Ab 7 A b Ba 2 A b BaB aAcB aB aAb 10 A Ab B aAb 4 B a AcB a B a AbA AbA bBa 9 A bBa 11 B aAc 5 A bB a 3 S A A A b 8 A A bB aA cB aA b b A a B b b A a B b c ACTION元素有冲突 所以不是LR 0 文法 并且FOLLOW A 与FOLLOW B 无交集 并且 它们的后跟字符集中分别包含a b c 所以可以确定10号状态的操作 FOLLOW S 与 b 也无交集 并且3和4项目集合中移进项目的符号是b 所以可以确定移进 是SLR 1 文法 S AA AbA bBaB aAcB aB aAb FOLLOW A b c FOLLOW B a FOLLOW S
