编译原理计科05-南京信息工程大学.doc

1、编译原理期中试卷（计科05）1、 (5)设G=(VT，VN，S，P)是一个上下文无关文法，产生集合P中的任一个产生式应具有什么样的形式？若G是1型文法呢？ 上下文无关文法， 产生式形式为：Pa， PVN， a (VT VN)* 。1型文法：产生式形式为:a b 其中：|a| |b|，仅 Se 例外。2、 (5)何谓二义性文法？试举一例说明。 答：如果一个文法的句子存在两颗分析树，称该句子是二义性的；如果一个文法包含二义性的句子则称该文法是二义性的，否则该文法无二义性。例子：有如下文法：Sif expr then S |other Sif expr then S else S 句子if e1 t

2、hen if e2 then s1 else s2是二义性的。注：原因请参见提纲。3、 (20)给定正则表达式b*(d|ad)（b|ab）+构造DFA(1) 画出NFA:(2) 将NFA确定化为DFAIaIbIdX,4,1 64,12624,164,12273,5,Y73,5,Y3,5,Y85,Y85,Y5,Y85,Y根据上面状态转换举证赋予状态新的符号：IaIbIcSABCACBABCCDEDEEFGFGGFGE,G为终态。画出DFA:(3) DFA最小化:1） 首先分为非终态集S,A,B,C,D,F和终态集E,G2） 对于集合S,A,B,C,D,F，因为S,B,C有a条件输入这个状态转化，

3、而A,D,F没有a条件输入这个状态转化，首先因分为S,B,C和A,D,F两个集合S,Bb=B Cb=E 不属于已划分出的同一个集合的子集，所以S,B,C分为S,B和C ，而S,Bd=C是已划分出的同一个集合的子集，所以不需再分A,D,F中A条件b作为输入，而D,Fb=E,G是同一集合的子集，并且D,F都没有d条件作为输入，所以D,F不需再分。3） 3)对于E,G，E,Ga=F E,Gb=G E和G都无条件d输入，所以E,G不需划分综上所述：所有状态分为S,B C A D,F E,G注：落在统一集合的元素等价，画图时只需选一个为代表，并把与它等价的元素的状态转化加到它身上即可。 4、 (10)按

4、指定的类型给出下列语言的文法(1) L1=anbmc|n=0,m0用正规文法SaS|A AbA|bB Bc(2) L2=a0n1nbdm|n0,m0用二型文法SAB AaT T0T1|01 BbD DdD|d5、(20)判断下面文法是不是LL(1)文法，若是请构造相应的LL(1)分析表，写出aaabd的分析过程。SaH HaMd|d MAb|e AaM|e答： 1）首先将规则分解：SaH HaMd Hd MAb Me AaM Ae 可以判断该文法无左递归；2) 求First和Follow集合非终结符XFirst(X)Follow(X)Sa#Ha,d#Me, a,ed,bAa,eb 求Selec

5、t集合Select(SaH)=First(aH)=a Select(HaMd)=First(aMd)=a Select(Hd)=d Select(MAb)=First(Ab)=a,e Select(Me)=First(e)UFollow(M)= Follow(M)=d,b Select(AaM)=FirstaM=a Select(Ae)=First(e)=eSelect(HaMd) Select(Hd)= Select(MAb) Select(Me)= Select(AaM) Select(Ae)= 该文法是LL(1)文法。3LL(1)分析表如下：令输入符号串已#结尾，即aaabd#adbeS

6、SaHHHaMdHdMMAbMeMeMAbAAaMAe4） aaabd的分析过程如下：步骤符号栈输入串所用产生式0#Saaabd#1#Haaaabd #SaH2#H aabd#3#dMa aabd#HaMd4#dM abd#5#dbA abd#MAb6#dbMa abd#AaM7#dbM bd#8#db bd#Me9#d d#10# #6、(15)写出文法GA: ABa|Cb|c BdA|Ae|f CBg|h消除左递归后的文法。答：(1)经分析发现文法GA并无直接左递归；(2)消除间接左递归：将A,B,C按照B,C,A排序（建议将A放在最后）由于出现CBg形式，将B代入C得：CdAg|Aeg|

7、fg|h又由于A出现ABa ACb将B,C带入A得到：AdAa|Aea|fa|dAgb|Aegb|fgb|hb|c等价于AAea|Aegb |dAa|fa|dAgb |fgb|hb|c将A消除直接左递归（方法请参见书69页倒数10、11行）AdAaA|fa A|dAgb A |fgb A|hb A|c AAea A| egb A|e此时，对于BdA|Ae|f，CdAg|Aeg|fg|h由于未在任何产生式的右部出现，所以是多余的。综上所述:消除递归后的文法为：AdAaA|fa A|dAgb A |fgb A|hb A|c AAea A| egb A|e7、(15)为文法GE:EE+E|E*E|-

8、E|id|(E)构造递归下降识别程序答：（1）消除左递归后有E EE |id E |（E）E E +E E |*E E |e （2）8、(5)简述编译程序的构造过程答1）构造此法分析器：用于输入源程序进行词法分析，输出单词符号； 2）构造语法分析器：对输入的单词符号进行语法分析，识别各类语法单位，判断输入是不是语法上正确的程序3）构造语义分析和中间代码产生器：按照语义规则对已归约出的语法单位进行语义分析并把它们翻译成中间代码。4）构造优化器：对中间代码进行优化。 5) 构造目标代码生成器：把中间的代码翻译成目标程序。6) 构造表格管理程序：登记源程序的各类信息和编译各阶段的进展情况。7)构造错误处理程序：对出错进行处理。9、(5)构造预测分析算法的算法流程图