编译习题课

1．构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正规式。 2．已知文法G[S]： S→MH|a H→LSo|ε K→dML|ε L→eHf M→K|bLM 判断G是否是LL(1)文法，如果是，构造LL(1)分析表。 3．设文法G(S)： 构造各非终结符的FIRSTVT和LASTVT集合及算符优先分析表； 4．若有定义二进制数的文法如下： S→L.L|L L→LB|B B→0|1 (1) 试为该文法构造LR分析表，并说明属哪类LR分析表。 (2) 给出输入串101.110的分析过程。 5．请将表达式-(a+b)*(c+d)-(a+b)分别表示成三元式、间接三元式和四元式序列。 6．采用语法制导翻译思想，表达式E的"值"的描述如下： 产生式       语义动作 (0) S′→E    {print E.VAL} (1) E→E1+E2   　{E.VAL∶=E1.VAL+E2.VAL} (2) E→E1*E2　   {E.VAL∶=E1.VAL*E2.VAL} (3) E→(E1)   　{E.VAL∶=E1.VAL} (4) E→n     　{E.VAL∶=n.LEXVAL} 假如终结符n可以是整数或实数，算符+和*的运算对象类型一致，语义处理增加"类型匹配检查"，请给出相应的语义描述。 7．请将下列语句: while (AD) then { X:=Y+Z； Y=Z+2; Z=Z+1; } 翻译成四元式. 解答： 4． 6． (0) S′→E { if error≠1 then print E.VAL} (1) E→E1+E2 { if E1.TYPE=int AND E2.TYPE=int then begin E.VAL:=E1.VAL + E2.VAL; E.YTPE:=int; end else if E1.TYPE=real AND E2.TYPE=real then begin E.VAL:=E1.VAL + E2.VAL; E.YTPE:=real; end else error=1 } (2) E→E1*E2 { if E1.TYPE=int AND E2.TYPE=int then begin E.VAL:=E1.VAL * E2.VAL;; E.YTPE:=int; end else if E1.TYPE=real AND E2.TYPE=real then begin E.VAL:=E1.VAL * E2.VAL;; E.YTPE:=real; end else error=1 } (3) E→(E1) { E.VAL:=E1.VAL; 　E.TYPE:=E1.TYPE } (4) E→n { E.VAL:=n.LEXVAL;　E.TYPE:=n.LEXTYPE }