下载文档原格式
1）不带回溯的自上而下分析算法
a) 消除左递归。
i. 什么是左递归：
ii. 消除直接左递归，消除间接左递归。
b) 消除直接左递归。
c) 消除左递归算法。
注：1）若非终结符排列顺序不同，改写后的文法也不同，但它们是等价的。
d) 消除回溯
i. 产生回溯的原因：进行推导时，若产生式存在多个候选式，选择哪个
候选式进行推导存在不确定性。
ii. 消除回溯的基本原则：对文法的任何非终结符，若能根据当前读头下的符号，准确的选择一个候选式进行推导，那么回溯就可以消除。
注：之所以会产生回溯是因为在推导匹配的过程中存在虚假匹配。
iii. 消除回溯的方法：预测与提左因子
iv. 根据读头下符号选择候选式，使其第一个符号与读头下符号相同，或该候选式可推导出的第一个符号与读头下符号相同。
这相当于向前看了一个符号，所以称为预测。
注：使用了预测之后，选择候选式不再是盲目的了，所以也就无需回溯。
v. 求候选式的终结首符集。
vi. 采用预测方法后PDA 的运行。
vii. 提取公共左因子。
第三章语法分析3.1 完成下列选择题：(1) 文法G：S→xSx|y所识别的语言是。
a. xyxb. (xyx)*c. xnyxn(n≥0)d. x*yx*(2) 如果文法G是无二义的，则它的任何句子α。
a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同(3) 采用自上而下分析，必须。
a. 消除左递 a. 必有ac归b. 消除右递归c. 消除回溯d. 提取公共左因子(4) 设a、b、c是文法的终结符，且满足优先关系ab和bc，则。
b. 必有cac. 必有bad. a～c都不一定成立(5) 在规范归约中，用来刻画可归约串。
a. 直接短语b. 句柄c. 最左素短语d. 素短语(6) 若a为终结符，则A→α·aβ为项目。
a. 归约b. 移进c. 接受d. 待约(7) 若项目集Ik含有A→α· ，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α· ”动作的一定是。
a. LALR文法b. LR(0)文法c. LR(1)文法d. SLR(1)文法(8) 同心集合并有可能产生新的冲突。
a. 归约b. “移进”/“移进”c.“移进”/“归约”d. “归约”/“归约”【解答】(1) c (2) a (3) c (4) d (5) b (6) b (7) d (8) d3.2 令文法G[N]为G[N]: N→D|NDD→0|1|2|3|4|5|6|7|8|9(1) G[N]的语言L(G[N])是什么?(2) 给出句子0127、34和568的最左推导和最右推导。
【解答】(1) G[N]的语言L(G[N])是非负整数。
(2) 最左推导：NNDNDDNDDDDDDD0DDD01DD012D0127NNDDD3D34NNDNDDDDD5DD56D568最右推导：NNDN7ND7N27ND27N127D1270127NNDN4D434NNDN8ND8N68D685683.3 已知文法G[S]为S→aSb|Sb|b，试证明文法G[S]为二义文法。
一、判断题1．SLR(1)分析法是一种规范归约分析法。
（）2．算符优先文法可以是二义性文法。
（）3．每个短语都是某规则的右部。
（）4．语法分析时必须先消除文法中的左递归。
（）5．如果两个正规式是等价的，则它们所表示的正规集相同。
（）（）1.编译程序的输入是高级语言程序，输出是机器语言程序。
（）2.文法G[S]：S→iSeS|iS|i是二义文法。
（）3.若一个语言的句子有无穷多个，则对应的文法必定是递归的。
（）4.上下文无关文法可以产生语言L={a n b n a m b m | n,m≥0}。
（）5.设文法G[N]：N→ND|D，D→0|1|2|3|4|5|6|7，则句子3247的最右推导为：N=>ND=>N4=>ND4=>N74=>ND74=>N274=>D274=>3274。
（）6.每一个NFA都对应有唯一的一个最小化的DFA。
（）7.文法G[S]：S→(S)S|ε不是LL(1)文法。
（）8.若文法任一产生式的右部不含两个相继的非终结符（…QR…），则称该文法为算符文法。
（）9.优先函数是唯一的，有的优先关系矩阵不存在对应的优先函数。
（）10.在LR(1)分析法中，搜索符仅对规约项目才有意义。
1、文法规则的左部就是非终结符号。
2、乔姆斯基定义1型文法对规则的限制比2型文法对规则的限制要多一些。
3、LR（K）分析法能彻底解决冲突。
4、一个程序是正确的是指该程序的语法是完全正确的。
5、每一个编译程序都由完成词法分析、语法分析、语义分析、代码优化和代码生成工作的五部分程序组成。
6、多遍扫描的编译程序优于单遍扫描的编译程序。
7、每个句子都有规范推导；每个句型都有规范推导。
8、存在这样一些语言，它们能被确定有限自动机（DFA）识别，但不能用正规表达式表示。
9、每一个NFA都对应有唯一的一个最小化的DFA。
10、若给定文法G和某个固定的k，则G是否是LR（k）文法是可判定的。
一、单选题（每题2分，共20分）1. 编译器的（）阶段可将源程序的字符流收集到若干记号中。
A. 语法分析B. 语义分析C. 代码生成D. 词法分析2. 文法A aA | b属于正则文法，正则文法在乔姆斯基层次中对应于（）文法。
A. 1型B. 2型C. 3型D. 0型3. 某C语言源代码文件包含#include <stdio.h>，（）将对源代码进行处理，把文件stdio.h 包含进去。
A.编译器B.解释器C.汇编器D.预处理器4. LL(1)文法的充要条件是（）。
A.对于文法中的每条产生式Uα1|α2|…|αn，要求FIRST(αi)∩FIRST(αj)＝Φ（i≠j）B.该文法对应的LL(1)分析表中每个项目最多只有一条产生式。
C.A和BD.都不是5. 以下说法中正确的是（）。
A.任何语言都可以描述为一个正则表达式。
B.对于任何一个NFA M，都存在一个DFA M’，满足L(M)= L(M’)。
C.任何一个DFA只有一个终态。
D.NFA的弧上标记只含输入字母表中的元素。
6.合成属性的计算可以通过对语法树进行（）遍历进行。
A. 前序B.中序C.后序D.任意7.乔姆斯基的2型文法是这样一种语言，其产生式限制为（）。
A. α->βB. P->βC. P->a或P->aβD. αPγ->αβγ8. 正则式的“*”读作（）。
A. 并且B.连接C.正则闭包D.闭包9. 编译程序中的语义分析器接受以（）为单位的输入，并产生信息供以后各阶段使用。
A. 语法树B.子程序C.单词D.语句10.文法A->aAb|ab生成的语言是（）。
A. {ab}B.{aAb}C. {anbn|n≥1}D.{anbn|n≥0}二、判断题（每题2分，共10分，对的打√，错的打×）1. 一个LR(0)文法一定是SLR(1)文法。
（）2. 在类型声明文法中，类型属性type是继承属性。
第一章1、将编译程序分成若干个“遍”是为了。
b．使程序的结构更加清晰2、构造编译程序应掌握。
a．源程序b．目标语言c．编译方法3、变量应当。
c．既持有左值又持有右值4、编译程序绝大多数时间花在上。
d．管理表格5、不可能是目标代码。
d．中间代码6、使用可以定义一个程序的意义。
a．语义规则7、词法分析器的输入是。
b．源程序8、中间代码生成时所遵循的是- 。
c．语义规则9、编译程序是对。
d．高级语言的翻译10、语法分析应遵循。
c．构词规则二、多项选择题1、编译程序各阶段的工作都涉及到。
b．表格管理c．出错处理2、编译程序工作时，通常有阶段。
a．词法分析b．语法分析c．中间代码生成e．目标代码生成三、填空题1、解释程序和编译程序的区别在于是否生成目标程序。
2、编译过程通常可分为5个阶段，分别是词法分析、语法分析中间代码生成、代码优化和目标代码生成。
3、编译程序工作过程中，第一段输入是源程序，最后阶段的输出为标代码生成程序。
4、编译程序是指将源程序程序翻译成目标语言程序的程序。
一、单项选择题1、文法G：S→xSx|y所识别的语言是。
a. xyxb. (xyx)*c. x n yx n(n≥0)d. x*yx*2、文法G描述的语言L(G)是指。
a. L(G)={α|S+⇒α , α∈V T*}b. L(G)={α|S*⇒α, α∈V T*}c. L(G)={α|S*⇒α,α∈(V T∪V N*)}d. L(G)={α|S+⇒α, α∈(V T∪V N*)}3、有限状态自动机能识别。
a. 上下文无关文法b. 上下文有关文法c.正规文法d. 短语文法4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立。
a. 若f(a)>g(b)，则a>bb.若f(a)<g(b)，则a<bc. a~b都不一定成立d. a~b一定成立5、如果文法G是无二义的，则它的任何句子α。
a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同6、由文法的开始符经0步或多步推导产生的文法符号序列是。
一、单项选择题1．如果文法G是无二义的，则它的任何句子α。
Aa. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同2.语法分析时所依据的是。
Aa. 语法规则b. 词法规则c. 语义规则d. 等价变换规则3．文法G：S→xSx|y所识别的语言是。
Ca. xyxb. (xyx)*c. x n yx n (n≥0)d. x*yx*4.由文法的开始符号出发经过若干步（包括0步）推导产生的文法符号序列称为______B________。
A．语言B．句型C．句子D．句柄5．在自上而下的语法分析中，应从 C 开始分析。
A．句型B．句子C．文法开始符号D．句柄6..文法G：S → x xS | y 所识别的语言是（D）。
A．xxy* B．(xxy)* C．xx*yx D．(xx)*y7.文法G：S → xS | y 所识别的语言是（D）。
A．xy* B．(xy)*C．xx*yx D．x*y8.设有文法G[T]:T→T*F|FF→F↑P|PP→(T)|a该文法句型T*P↑(T*F)的句柄是下列符号串（C ）A.（T*F）B. T*FC. PD. P↑(T*F)9.最左简单子树的叶结点，自左至右排列组成句型的________C____________。
A．短语B．句型C．句柄D．间接短语二、填空题语法分析部分：（基本概念、递归下降子程序）1．语法分析的方法通常分为两类：自上而下分析方法和自下而上分析方法。
2．文法中的终结符集和非终结符集的交集是空集。
3．一个句型的最左直接短语称为该句型的___句柄________________。
4．常用的自上而下语法分析方法有递归下降子程序方法和预测分析表方法（LL（1）方法）。
5．关于非终结符A的直接左递归产生式：A→Aα|β，其中α、β是任意的符号串且β不以A开头，则可以将A的产生式改写为右递归的形式为：A→βA’, A’→αA’|ε000000000000000000000000 。
1.设有文法G[S]：S→ABA→bB|AaB→Sb|a试消除该文法的左递归。
解：本题考查消除左递归的方法。
应用消除文法左递归的算法对文法G[S]消除左递归的过程如下：（1）将非终结符排序为：U1=S，U2=A，U3=B（2）进入算法排序：i=1时，对文法无影响i=2，j=1时：A→Aa有直接左递归，消去该直接左递归，得A→bBA’A’→aA’|εi=3，j=1时：改写文法，有B→ABb|aj=2时：改写文法，有B→bBA’Bb|a无左递归。
（3）所以文法G[S]消除左递归后变为：G’[S]：S→ABA→bBA’A’→aA’|εB→bBA’Bb|a2.设有文法G[E]:E→Aa|BbA→cA|eBB→bd试按照递归子程序法为该文法构造语法分析程序。
解：本题考查递归子程序的构造方法。
首先判断文法是否满足递归子程序法对文法的要求，然后再构造递归子程序。
因为：（1）该文法无左递归。
（2）文法的产生式E→Aa|Bb和A→cA|eB的右部有若干选项，判断这两条产生式右部各候选式的终结首符号集合是否两两互不相交。
对产生式E→Aa|Bb，有FIRST(Aa)∩FIRST(Bb)={c，e}∩{b}=ø对产生式A→cA|eB，有FIRST(cA)∩FIRST(eB)={c}∩{e}=ø文法中其他产生式都只有一个非空ε的右部。
综合（1）、（2），该文法可以采用自上而下分析方法进行语法分析而不会出现回朔和无限循环。
下面为该文法的每一个非终结符号构造递归子程序。
假设用READAWORD代表读下一个单词。
用P(E)、P(A)、P(B)分别表示非终结符号E、A、B对应的子程序名。
约定输入符号串以“#”作为输入结束符。
P(E)的递归子程序为：PROCEDURE P(E);BEGINIF WORD IN FIRST(Aa)THENBEGINP(A);READAWORD;IF WORD=’a’THEN READAWORDELSE ERRORENDELSE IF WORD IN FIRST(Bb)THENBEGINP(B);READAWORD;IF WORD=’b’THEN READAWORDELSE ERRORENDELSE ERROREND;P(A)的递归子程序为：PROCEDURE P(A);BEGINIF WORDD=’c’THENBEGINREADAWORD;P(A)ENDELSE IF WORD=’e’THENBEGINREADWORD;P(B)ENDELSE ERROREND;P(B)的递归子程序为：PROCEDURE P(B);BEGINIF WORD=’b’THENBEGINREADAWORD;IF WORD=’d’THEN READAWORDELSE ERRORENDELSE ERROREND;主程序中的主要内容为：READAWORD;P(E);IF WORD=”#”THEN WRITE(“RIGHT!”)ELSE WRITE(“ERROR!”)3.已知文法G[E]：G[E]：E→E+T|TT→T*F|FF→i|(E)请按递归子程序法为其构造语法分析程序。
解：本题考查递归子程序的构造方法。
本题所给文法存在左递归，不满足递归子程序法对文法的要求，必须首先消除文法左递归，然后再构造分析程序。
因为文法只有左递归，采用扩充的BNF范式消除文法左递归得到：G[E]：E→T{+T}T→F{*F}F→i|(E)然后再应用书中介绍的方法即可求解。
假定用“ADV ANCE;”表示对读取下一个单词的过程的调用。
相应的递归子程序为：PROCEDURE P(E);BEGINP(T);WHILE SYM=’+’DOBEGINADV ANCE;P(T)ENDEND;PROCEDURE P(T);BEGINP(F);WHILE SYM=’*’DOBEGINADV ANCE;P(F)ENDEND;PROCEDURE P(F);BEGINIF SYM=’i’THEN ADV ANCEELSE IF SYM=’(’THENBEGINADV ANCE;P(E);IF SYM=’)’THEN ADV ANCEELSE ERRORENDELSE ERROREND;主程序中的主要内容为：ADV ANCE;P(E);IF WORD=”#”THEN WRITE(“RIGHT!”)ELSE WRITE(“ERROR!”)4．文法G[M]是否是LL(1)文法，说明理由。
G[M]：M→TBT→Ba|εB→Db|eT|εD→d|ε解：本题考查LL(1)方法对文法的要求，涉及到FIRST集、FOLLOW集的求法。
首先求出文法的每一个非终结符号的FIRST集、FOLLOW集：FIRST(D)=FIRST(d)∩FIRST(ε)={d, ε}FIRST(B)=FIRST(Db)∩FIRST(eT)∩FIRST(ε)=FIRST(db)∩FIRST(b)∩FIRST(eT)∩FIRST(ε)={d，b，e，ε}FIRST(T)=FIRST(Ba)∩FIRST(ε)={d，b，e，a，ε}FIRST(M)=FIRST(Tb)= {d，b，e，a，ε}FOLLOW(M)={#}FOLLOW(B)=FOLLOW(M)∪FIRST(a)\{ε}={a，#}FOLLOW(T)=FOLLOW(B)\{ε}∪FOLLOW(M) ∪FOLLOW(B)={d，b，e，#，a}FOLLOW(D)=FIRST(b)\{ε}={b}可以看出，对文法G[M]的产生式T→Ba|ε，有FIRST(Ba)∩FOLLOW(T)={d，b，e，a}∩{d，b，e，#，a}={d，b，e，a}≠ø仅此一条就会导致在自上而下的语法分析过程中出现回朔。
所以文法G[M]不是LL(1)文法。
5．构造一个LL(1)文法G，识别语言L：L={ω|ω为{0，1}上不包括两个相邻的1的非空串}并证明你的结论。
解：本题考查文法的构造方法以及LL(1)文法的要求。
首先构造出描述该语言的文法，然后证明该文法是LL(1)文法。
（1）根据题目要求——句子为不包括两个相邻的1的非空串，首先得到一个能够描述所有句子的文法G’[S]：S→0S|1A|0|1A→0S|0再根据LL(1)文法的要求，将文法改写为G[S]：S→0B|1CA→0BB→S|εC→A|ε（2）下面证明文法G[S]是LL(1)文法。
对产生式S→0B|1C，没有空产生式右部(ε)，所以只要考查终结首符号集是否两两互不相交。
有FIRST(0B)∩FIRST(1C)={0}∩{1}=ø对产生式A→0B，只有唯一的不为空ε的右部，不用考查。
对产生式B→S|ε，因为有空产生式右部，所以要考查终结首符号集与后继终结符号集是否相交。
由于FIRST(S)={0，1} FIRST(ε)={ε}FOLLOW(B)= FOLLOW(S) ∪FOLLOW(A)= FOLLOW(S) ∪FOLLOW(C)=FOLLOW(S)={#}∪FOLLOW(B)={#}所以有FIRST(S)∩FIRST(ε)=ø和FIRST(B)∩FOLLOW(B)=ø对产生式C→A|ε，因为有空产生式右部，所以要考查终结首符号集与后继终结符号集是否相交。
由于FIRST(A)={0} FIRST(ε)={ε}FOLLOW(C) =FOLLOW(S) ={#}所以有FIRST(A)∩FIRST(ε)=ø和FIRST(C)∩FOLLOW(C)=ø综上所述，文法G[S]的每一条形如U→X1|X2|…|X n的产生式都满足FIRST(X i)∩FIRST(X j)=ø(i≠j)如果X j*ε时，还满足FIRST(X1)∩FOLLOW(U)=ø所以，文法G[S]是LL(1)文法。
6．有文法G[S]：S→aABbcd|εA→ASd|εB→SAh|eC|εC→Sf|Cg|εD→aBD|ε①求每一个非终结符号的FOLLOW集合。
②对每一个非终结符号的产生式选择，构造FIRST集合。
③该文法是LL(1)文法吗？解：本题考查LL(1)文法的要求，涉及文法符号串FIRST集，文法非终结符号的FOLLOW集的求法。
首先将文法压缩，得到S→aABbcd|εA→ASd|εB→SAh|eC|εC→Sf|Cg|ε①求每一个非终结符号的FOLLOW集合：∵S为开始符号，且有产生式A→ASd B→SAh C→Sf∴FOLLOW(S)={#}∪FIRST(d)∪FIRST(Ah)∪FIRST(f)={#，d，a，h，f}∵S→aABbcd A→ASd B→SAh∴FOLLOW(A)=FIRST(Bbcd)∪FIRST(Sd)∪FIRST(h)={b，a，d，h，e}∵S→aABbcd∴FOLLOW(B)=FIRST(bcd)={b}∵B→eC C→Cg∴FOLLOW(C)=FOLLOW(B)∪FIRST(g)={b，g}②对每一个非终结符号的产生式右部选项，构造FIRST集合对S：FIRST(aABbcd)={a} FIRST(ε)={ε}对A：FIRST(ASd)={a，d} FIRST(ε)={ε}对B：FIRST(SAh)={a，d，h} FIRST(eC)={e}FIRST(ε)={ε}对C：FIRST(Sf)={a，f} FIRST(Cg)={a，f，g}FIRST(ε)={ε}③由于存在产生式C→Sf|Cg|εFIRST(Sf)∩FIRST(Cg)={a，f}∩{a，f，g}≠ø所以该文法不是LL(1)文法。
7．已知文法G[A]：A→aAa|ε（1）该文法是LL(1)文法吗？为什么？（2）若采用LL(1)方法进行语法分析，如何得到该文法的LL(1)分析表？（3）若输入符号串“aaaa”，请给出语法分析过程。
（4）请给出该文法的递归下降分析子程序。
解：（1）因为产生式A→aAa|ε有空产生式右部，而FOLLOW(A)={#}∪FIRST(a)={a，#}造成FIRST(A)∩FOLLOW(A)={a，ε}∩{a，#}≠ø所以该文法不是LL(1)文法。
（2）若采用LL(1)方法进行语法分析，必须修改该文法。
因该文法产生偶数（可以为0）个a，所以得到文法G’[A]：A→aaA|ε此时对产生式A→aaA|ε，有FOLLOW(A)={#}∪FOLLOW(A)={#}，因而FIRST(A)∩FOLLOW(A)={a，ε}∩{#}= ø所以文法G’[A]是LL(1)文法，按LL(1)分析表构造算法构造该文法的LL(1)分析表如表5.1所示。
（3）若采用LL(1)方法进行语法分析，对符号串“aaaa”的分析过程如表5.2所示（4）构造文法G’[A]的递归子程序如下（假定用“ADV ANCE；”表示对读取下一个单词的过程的调用）：PROCEDURE P(A);BEGINIF WOR D=’a’THEN BEGIN ADV ANCE;IF WORD=’a’THEN BEGIN READAWORD;P(A);ENDELSE ERRORENDELSE IF NOT(WORD IN FOLLOW(A))THEN ERROREND;主程序中的主要内容为：ADV ANCE;P(A);IF WORD=”#”THEN WRITE(“RIGHT!”)ELSE WRITE(“ERROR!”)8.设文法G[S]：S→SbA|aAB→SbA→Bc①将该文法改写成LL(1)文法。
