华南师范大学-编译原理期末复习整理-pdf例题.doc

正则表达式：例2.1 在仅由字母表中的3个字符组成的简单字母表=a, b, c中，考虑在这个字母表上的仅包括一个b的所有串的集合。( a | c )* b ( a | c )*例2.2 在与上面相同的字母表中，如果集合是包括了最多一个b的所有串。( a | c )* b? ( a | c )*DFA：例2.6 串中仅有一个b的集合的正则表达式对应的DFA为？例2.8 科学表示法的数字常量的正则表达式为：nat = 0-9+signedNat = (+|-)? natnumber = signedNat(“.” nat)? (E signedNat)?如何画对应的DFA？解：先设digit = 0-9，sig = (+|-)，得：例2.9 非嵌套注释的DFA描述。Pascal注释 ( )* 对应的DFA为：C注释 /* .( */不同时出现 ). */ 的DFA为：NFA：例2.12 根据Thompson方法将正则表达式 ab|a转换为NFA。例2.13 利用Thompson方法画出正则表达式letter(letter| digit)*对应的NFA。例2.14 与正则表达式a*相对应的NFA为：NFA转DFA：例2.15 将下面的NFA转换为DFA：解：例2.16 将下面的NFA转换为DFA：解：例2.17 正则表达式letter(letter| digit)*对应的NFA转换成DFA：解：DFA最小化：例2.18 将与正则表达式letter(letter| digit)*相对应的DFA最小化：（08级的大三第二学期考这道）解：状态转换表为letterdigit12,3,4,5,7,102,3,4,5,7,104,5,6,7,9,104,5,7,8,9,104,5,6,7,9,104,5,6,7,9,104,5,7,8,9,104,5,7,8,9,104,5,6,7,9,104,5,7,8,9,10最小化DFA为：例2.19 将下面与正则表达式(a| ) b*对应的DFA进行最小化。解：状态转换表为ab1232333最小化DFA为：词法分析代码：state := 1; startwhile state = 1 or 2 docase state of1: case input character ofletter:advance the input;state := 2;else state := . error or other;end case;2: case input character ofletter, digit:advance the input;state := 2; actually unnecessaryelse state := 3;end case;end case;end while;if state = 3 then accept else error;state := 1; startwhile state = 1, 2, 3 or 4 docase state of1:case input character of“/”:advance the input;state := 2;else state := . ; error or otherend case;2:case input character of“*”:advance the input;state := 3;else state := . ; error or otherend case;3: case input character of“*”:advance the input;state := 4;else advance the input; and stay in state 3end case;4:case input character of“/”:advance the input;state := 5;“*”:advance the input; and stay in state 4elseadvance the input;state := 3;end case;end case;end while;if state = 5 then accept else error;递归子程序分析法问题1：GS = S aA | bBA cdA | dB efB | f试编写一个能分析该文法所对应任何串（如串acdd）的程序。void match( expectedToken )if( token = expectedToken )getToken();elseError();void S()if( token = a )match(a);A();else if( token = b )match(b);B();else Error();/Svoid A()if( token = c )match(c);match(d);A();else if( token = d )match(d);else Error();/Avoid B()if( token = e )match(e);match(f);B();else if( token = f )match(f);else Error();/Bint main()getToken();S();return 0;/main问题2：exp exp addop term | termaddop + | -term term mulop factor | factormulop * | /factor ( exp ) | number请写出递归子程序分析算法。解：先消除左递归，得到exp term addop term addop + | -term factor mulop factor mulop * | /factor ( exp ) | number程序如下：void match( expectedToken )if( token = expectedToken )getToken();elseError();void exp()term();while( token = + | token = - )match(token);term();void term()factor();while( token = * | token = / )match(token);factor();void factor()if( token = ( )match();exp();match();else if( token = number )match(number);else Error();int main()getToken();exp();return 0;写出递归构建语法树的程序：void match( expectedToken )if( token = expectedToken )getToken();elseError();BtreeNode * exp()BtreeNode * Node, * tempNode;Node = term();while( token = + | token = - )tempNode = new BtreeNode;tempNode-data = token;match(token); tempNode-lchild = Node;tempNode-rchild = term();Node = tempNode;return Node;BtreeNode * term()BtreeNode * Node, * tempNode;Node = factor();while( token = * | token = / )tempNode = new BtreeNode;tempNode-data = token;match(token); tempNode-lchild = Node;tempNode-rchild = factor();Node = tempNode;return Node;BtreeNode * factor()BtreeNode * Node;if( token = ( )match();Node = exp();match();else if( token = number )Node = new BtreeNode;Node-data = token;match(number);Node-lchild = Node-rchild = NULL;else Error();return Node;int main()BtreeNode *root;getToken();root = exp();return 0;例4.3 消除下面文法的左递归A Ba | Aa | cB Bb | Ab | d解：先消除A的直接左递归：A Baa | ca再将其代入到B的文法表达式中：B Bb | Baab | cab | d再消除B的直接左递归：B (d|cab)(b|aab)例4.9 考虑简单整型算术表达式的文法：exp exp addop term | termaddop + | -term term mulop factor | factormulop * | /factor ( exp ) | number试求：First(exp) = ?First(term) = ?First(factor) = ?解：先消除左递归：exp term addop term addop + | -term factor mulop factor mulop * | /factor ( exp ) | number由此得First(exp) = (, number First(term) = (, number First(factor) = (, number 例4.10 考虑if语句的文法：statement if-stmt | otherif-stmt if (exp) statement else-partelse-part else statement | exp 0 | 1试求：Follow(statement) = ?Follow(if-stmt) = ?Follow(else-part) = ?Follow(exp) = ?解：Follow(statement) = else, $ Follow(if-stmt) = else, $ Follow(else-part) = else, $ Follow(exp) = ) LL(1)分析法：问题1:GS = S Ab | BcA aA | dBB c | e画出LL(1)分析表和当匹配串adcb时的分析栈。解：分析表为abcdeSS AbS BcS AbS BcAA aAA dBBB cB e分析栈为：步骤符号栈输入串动作1SadcbS Ab2bAadcbA aA3bAaadcb匹配4bAdcbA dB5bBddcb匹配6bBcbB c7bccb匹配8bb匹配9成功问题2:GS = S AbB | BcA aA | B d | e画出LL(1)分析表和当匹配串abd时的分析栈。解：分析表为：abcdeSS AbBS AbBS BcS BcAA aAA BB dB e分析栈为：步骤符号栈输入串动作1SabdS AbB2BbAabdA aA3BbAaabd匹配4BbAbdA 5Bbbd匹配6BdB d7dd匹配8成功LR(0)分析法：问题1：GA：A (A) | a画出DFA，并写出串(a)的分析过程。解：先扩充文法，得到：A .AA .(A)A .aDFA为：分析表为：状态动作规则输入Goto(a)A0移进3211规约A A2规约A a3移进3244移进55规约A (A)分析串(a)时的分析栈为：步骤分析栈输入动作1$0(a)$移进2$0(3(a)$移进3$0(3(3a)$移进4$0(3(3a2)$用A a规约5$0(3(3A4)$移进6$0(3(3A4)5)$用A (A) 规约7$0(3A4)$移8$0(3A4)5$用A (A) 规约9$0A1$接受SLR(1)分析：问题1：文法： E E + n | n画出该文法的SLR(1)的DFA图、分析表和分析串n+n+n时的分析栈。解：先扩充文法，得到E EE E + nE n画出其DFA为：其分析表如下：状态输入Goton+$E0s211s3接受2r(E n)r(E n)3s44r(E E + n)r(E E + n)分析串n+n+n时的分析栈为：步骤分析栈输入动作1$0n+n+n$移进22$0n2+n+n$用E n规约3$0E1+n+n$移进34$0E1+3n+n$移进45$0E1+3n$+n$用E E + n规约6$0E1+n$移进37$0E1+3n$移进48$0E1+3n4$用E E + n规约9$0E1$接受LR(1)分析：问题1：文法： A (A) | a画出该文法的LR(1)的DFA图和分析表。解：先扩充文法，得到：A AA (A)A a其DFA为：分析表为：状态输入Goto(a)$A0s2s311接受2s5s643r(A a)4s75s5s686r(A a)7r(A (A)8s99r(A (a)问题2：文法：S id | V := EV idE V | n画出该文法的LR(1)的DFA图和分析表。解：首先将文法扩展，得到：S SS idS V := EV idE VE nDFA图如下：分析表如下：状态输入Gotoid:=n$VES0s2311接受2r(V id)r(S id)3s44s8s7655r(SV:=E)6r(E V)7r(E n)8r(V id)将上题的DFA图改写成符合LALR(1)的DFA：后缀表示：写出if( mn ) k=1; else m=0; 的后缀表示。解：m n 10