2022年编译原理期末复习题 .pdf

《2022年编译原理期末复习题 .pdf》由会员分享，可在线阅读，更多相关《2022年编译原理期末复习题 .pdf（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八节习题一、单项选择题1、将编译程序分成若干个“遍”是为了。a提高程序的执行效率b使程序的结构更加清晰c利用有限的机器内存并提高机器的执行效率d利用有限的机器内存但降低了机器的执行效率2、构造编译程序应掌握。a源程序b目标语言c编译方法d以上三项都是3、变量应当。a持有左值b持有右值c既持有左值又持有右值d既不持有左值也不持有右值4、编译程序绝大多数时间花在上。a出错处理b词法分析c目标代码生成d管理表格5、不可能是目标代码。a汇编指令代码b可重定位指令代码c绝对指令代码d中间代码6、使用可以定义一个程序的意义。a语义规则b词法规则c产生规则d词法规则7、词法分析器的输入是。a单词符号串b源

2、程序c语法单位d目标程序8、中间代码生成时所遵循的是-。a语法规则b词法规则c语义规则d等价变换规则9、编译程序是对。a汇编程序的翻译b高级语言程序的解释执行c机器语言的执行d高级语言的翻译10、语法分析应遵循。a语义规则b语法规则c构词规则d等价变换规则解答1、将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选b。2、构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选d。3、对编译而言，变量既持有左值又持有右值，故选c。4、编译程序打交道最多的就是各种表格，因此选d。5、目标代码包括汇编指令代码、可重定位指令代码和绝对指令代码3 种，因此不是目标代码的只能选d。6、

3、词法分析遵循的是构词规则，语法分析遵循的是语法规则，中间代码生成遵循的是语义规则，并且语义规则可以定义一个程序的意义。因此选a。7、b 8、c 9、d 10、c 二、多项选择题名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 20 页 -1、编译程序各阶段的工作都涉及到。a语法分析b表格管理c出错处理d语义分析e词法分析2、编译程序工作时，通常有阶段。a词法分析b语法分析c中间代码生成d语义检查e目标代码生成解答1b、c 2.a、b、c、e 三、填空题1、解释程序和编译程序的区别在于。2、编译过程通常可分为5 个阶段，分别是、语法分析、代码优化和目标代码生成。3、编译程序工作过程中

4、，第一段输入是，最后阶段的输出为程序。4、编译程序是指将程序翻译成程序的程序。解答是否生成目标程序2、词法分析中间代码生成3、源程序目标代码生成4、源程序目标语言一、单项选择题1、文法 G：SxSx|y所识别的语言是。a.xyx b.(xyx)*c.xnyxn(n0)d.x*yx*2、文法 G 描述的语言L(G)是指。a.L(G)=|S+?,VT*b.L(G)=|S*?,VT*c.L(G)=|S*?,(VTVN*)d.L(G)=|S+?,(VTVN*)3、有限状态自动机能识别。a.上下文无关文法b.上下文有关文法c.正规文法d.短语文法4、设 G 为算符优先文法，G 的任意终结符对a、b 有以

5、下关系成立。a.若 f(a)g(b)，则 ab b.若 f(a)g(b)，则 ag)(b)或 f(a)g(b)并不能判定原来的a 与 b 之间是否存在优先关系：故选c。5、如果文法G 无二义性，则最左推导是先生长右边的枝叶：对于d，如果有两个不同的是了左推导，则必然有二义性。故选a。6、选 c。7、由图 2-8-1 的语法树和优先关系可以看出应选b。8、规范推导是最左推导，故选d。9、由 T T,和 T(得 FIRSTVT(T)=(,，)；由 T S 得 FIRSTVT(S)?FIRSTVT(T)，而 FIRSTVT(S)=b,(；即FIRSTVT(T)=b,(,，；因此选 c。10、d 11

6、、c 12、b 13、b 14、b 二、多项选择题1、下面哪些说法是错误的。a.有向图是一个状态转换图b.状态转换图是一个有向图c.有向图是一个DFA d.DFA 可以用状态转换图表示2、对无二义性文法来说，一棵语法树往往代表了。a.多种推导过程b.多种最左推导过程c.一种最左推导过程d.仅一种推导过程e.一种最左推导过程3、如果文法G 存在一个句子，满足下列条件之一时，则称该文法是二义文法。a.该句子的最左推导与最右推导相同b.该句子有两个不同的最左推导c.该句子有两棵不同的最右推导d.该句子有两棵不同的语法树E E+F E+T P T i P#+#图 2-8-1 句型 P+T+I 的语法及

7、优先关系名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 20 页 -e.该句子的语法树只有一个4、有一文法G：SAB AaAb|BcBd|它不产生下面集合。a.anbmcndm|n,m0 b.anbncmdm|n,m0 c.anbmcmdn|n,m0 d.anbncmdm|n,m0 e.anbncndn|n0 5、自下而上的语法分析中，应从开始分析。a.句型b.句子c.以单词为单位的程序d.文法的开始符e.句柄6、对正规文法描述的语言，以下有能力描述它。a.0 型文法b.1 型文法c.上下文无关文法d.右线性文法e.左线性文法解答1、e、a、c 2、a、c、e 3、b、c、d 4

8、、a、c 5、b、c 6、a、b、c、d、e 三、填空题1、文法中的终结符和非终结符的交集是。词法分析器交给语法分析器的文法符号一定是，它一定只出现在产生式的部。2、最左推导是指每次都对句型中的非终结符进行扩展。3、在语法分析中，最常见的两种方法一定是分析法，另一是分析法。4、采用语法分析时，必须消除文法的左递归。5、树代表推导过程，树代表归约过程。6、自下而上分析法采用、归约、错误处理、等四种操作。7、Chomsky 把文法分为种类型，编译器构造中采用和文法，它们分别产生和语言，并分别用和自动机识别所产生的语言。解答1、空集终结符右2、最左3、自上而上自下而上4、自上而上5、语法分析6、移进

9、接受7、4 2 型3 型上下文无关语言正规语言下推自动机有限四、判断题1、文法SaS|bR|描述的语言是(a|bc)*()RcS 2、在自下而上的语法分析中，语法树与分析树一定相同。（）3、二义文法不是上下文无关文法。（）4、语法分析时必须先消除文法中的左递归。（）5、规范归约和规范推导是互逆的两个过程。（）6、一个文法所有句型的集合形成该文法所能接受的语言。（）解答1、对2、错3、错4、错5、错6、错五、简答题1、句柄2、素短语3、语法树4、归约5、推导解答 1、句柄：一个句型的最左直接短语称为该句型的句柄。2、素短语：至少含有一个终结符的素短语，并且除它自身之外不再含任何更小的素短语。3、

10、语法树：满足下面4 个条件的树称之为文法GS的一棵语法树。每一终结均有一标记，此标记为VNVT中的一个符号；树的根结点以文法GS 的开始符 S 标记；若一结点至少有一个直接后继，则此结点上的标记为VN中的一个符号；若一个以A 为标记的结点有K 个直接后继，且按从左至右的顺序，这些结点的标记分别为 X1,X2,XK，则 AX1,X2,XK，必然是G 的一个产生式。4、归约：我们称 直接归约出 A，仅当 A是一个产生式，且、(VNVT)*。归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。5、推导：我们称A直接推出，即 A，仅当A 是一个产生式，且、(VNVT)

11、*。如果12n，则我们称这个序列是从1至2的一个推导。若存在一个从 1n的推导，则称 1可推导出 n。推导是归约的逆过程。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 20 页 -六、问答题1、给出上下文无关文法的定义。解答 一个上下文无关文法G 是一个四元式（VT,VN,S,P），其中：VT是一个非空有限集，它的每个元素称为终结符号；VN是一个非空有限集，它的每个元素称为非终结符号，VTVN=；S是一个非终结符号，称为开始符号；P 是一个产生式集合（有限），每个产生式的形式是P，其中，PVN，(VTVN)*。开始符号S至少必须在某个产生式的左部出现一次。2、文法 GS：SaS

12、PQ|abQQP PQbPbbbQbccQcc（1）它是 Chomsky 哪一型文法？（2）它生成的语言是什么？解答 （1）由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部的符号长度，所以文法GS是 Chomsky1 型文法，即上下文有关文法。（2）按产生式出现的顺序规定优先级由高到低（否则无法推出句子），我们可以得到：SabQabc SaSPQaabQPQaabPQQaabbQQaabbcQaabbcc SaSPQaaSPQPQaaabQPQPQaaabPQQPQaaabPQPQQaaaPPQQQaaabbPqqqaaabbQQQaaabbbcQQaaabbbccQ

13、aaabbbccc 于是得到文法GS生成的语言L=anbncn|n1 3、按指定类型，给出语言的文法。L=aibj|ji1的上下文无关文法。【解答】（1）由 L=aibj|ji1知，所求该语言对应的上下文无关文法首先应有SaSb 型产生式，以保证 b 的个数不少于a 的个数；其次，还需有 SSb 或 SbS 型的产生式，用以保证b 的个数多于a 的个数；也即所求上下文无关文法GS为：GS：SaSb|Sb|b 4、有文法G：SaAcB|Bd A AaB|c B bScA|b（1）试求句型aAaBcbbdcc 和 aAcbBdcc 的句柄；（2）写出句子acabcbbdcc的最左推导过程。【解答】

14、（1）分别画出对应两句型的语法树，如图2-8-2 所示句柄:AaB Bd S a A c B A a B b S c A B d c b(a)S a A c B B S c A B d c(b)名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 20 页 -S（L）L，S S (L)S a 图 2-8-3 句型（S,（a）的语法树 T T*F F P P（T）T*F 图 2-8-4 句型 T*P（T*F）的语法树图 2-8-2 语法树（2）句子 acabcbbdcc的最左推导如下：SaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcA acabcbbdc

15、Aacabcbbdcc 5、对于文法GS：S（L）|aS|a LL,S|S（1）画出句型（S,（a）的语法树。（2）写出上述句型的所有短语、直接短语、句柄和素短语。【解答】（1）句型（S,（a）的语法树如图2-8-3 所示（2）由图 2-8-3 可知：短语：S、a、(a)、S,(a)、(S,(a)；直接短语：a、S；句柄：S；素短语：素短语可由图2-8-3 中相邻终结符之间的优先关系求得，即；因此素短语为a。6、考虑文法GT：TT*F|F FFP|P P（T）|i 证明 T*P（T*F）是该文法的一个句型，并指出直接短语和句柄。【解答】首先构造T*P（T*F）的语法树如图2-8-4 所示。由图

16、 2-8-4 可知，T*P（T*F）是文法GT 的一个句型。直接短语有两个，即P 和 T*F；句柄为P。一、单项选择题1、词法分析所依据的是。a.语义规则b.构词规则c.语法规则d.等价变换规则2、词法分析器的输出结果是。a.单词的种别编码b.单词在符号表中的位置c.单词的种别编码和自身值d.单词自身值3、正规式M1和 M2等价是指。a.M1和 M2的状态数相等b.M1和 M2的有向弧条数相等#（，（a）#名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 20 页 -c.M1和 M2所识别的语言集相等d.M1和 M2状态数和有向弧条数相等4、状态转换图（见图3-6-1）接受的字集为

17、。a.以 0 开头的二进制数组成的集合b.以 0 结尾的二进制数组成的集合c.含奇数个0 的二进制数组成的集合d.含偶数个0 的二进制数组成的集合5、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，。a.词法分析器应作为独立的一遍b.词法分析器作为子程序较好c.词法分析器分解为多个过程，由语法分析器选择使用d.词法分析器并不作为一个独立的阶段解答1、b 2、c 3、c 4、d 5、b 二、多项选择题1、在词法分析中，能识别出。a.基本字b.四元式c.运算符d.逆波兰式e.常数2、令=a,b，则上所有以b 开头，后跟若干个ab 的字的全体对应的正规式为。a.b(ab)*b.b(a

18、b)+c.(ba)*b d.(ba)+b e.b(a|b)解答1、a、c、e 2、a、b、d 三、填空题1、确定有限自动机DFA 是的一个特例。2、若二个正规式所表示的相同，则认为二者是等价的。3、一个字集是正规的，当且仅当它可由所。解答1、NFA 2、正规集3、DFA（NFA）所识别四、判断题1、一个有限状态自动机中，有且仅有一个唯一终态。（）2、设 r 和 s分别是正规式，则有L（r|s）=L(r)|L(s)。（）3、自动机M 和 M 的状态数不同，则二者必不等价。（）4、确定的自动机以及不确定的自动机都能正确地识别正规集。（）5、对任意一个右线性文法G，都存在一个NFA M，满足 L(G

19、)=L(M)。（）6、对任意一个右线性文法G，都存在一个DFA M，满足 L(G)=L(M)。（）7、对任何正规表达式e，都存在一个NFA M，满足 L(G)=L(e)。（）8、对任何正规表达式e，都存在一个DFA M，满足 L(G)=L(e)。（）解答1、2、3、错4、5、6、7、8、正确五、基本题1、设 M（x,y,a,b,f,x,y）为一非确定的有限自动机，其中f 定义如下：f（x,a）x,y f（x,b）y f（y,a）f（y,b）x,y 试构造相应的确定有限自动机M。解答：对照自动机的定义M=(S,f,S0,Z)，由 f 的定义可知f(x,a)、f(y,b)均为多值函数，所以是一非确

20、定有限自动机，先画出NFA M 相应的状态图，如图3-6-2 所示。用子集法构造状态转换矩阵表3-6-3 所示。I IaIbx x,y y y x,y a a b b b 图 3-6-2 NFA M X Y 0 1 0 图 3-6-1 Y X 名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 20 页 -a a,b b b 图 3-6-5 DFA M 0 2 1 aadb*b*(d|ad)(b|ab)(b|ab)*X Y X 1 2 3 Y X 4 1 3 5 Y 6 7 8(d|ad)(b|ab)(b|ab)*2 dbadabb|ab bX 4 1 3 5 Y 2 bdbbabb

21、图 3-6-7 的 NFA M x,y x,y x,y 将转换矩阵中的所有子集重新命名而形成表3-6-4 所示的状态转换矩阵。表 3-6-4 状态转换矩阵a b 0 2 1 1 2 2 2 2 即得到 M =（0,1,2,a,b,f,0,1,2），其状态转换图如图3-6-5 所示。将图 3-6-5 的 DFA M 最小化。首先，将M 的状态分成终态组1，2与非终态组 0；其次，考察1,2。由于 1,2a=1,2b=2?1,2，所以不再将其划分了，也即整个划分只有两组0，1,2：令状态 1 代表 1,2，即把原来到达2 的弧都导向1，并删除状态2。最后，得到如图3-6-6 所示化简DFA M 。

22、2、对给定正规式b*（d|ad）（b|ab）+，构造其 NFA M；解答：首先用A+=AA*改造正规式得：b*(d|ad)(b|ab)(b|ab)*；其次，构造该正规式的NFA M，如图3-6-7 所示。a a,b b 图 3-6-6 化简后的 DFA M 0 1 名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 20 页 -1、构造下面文法的LL（1）分析表。D TL T int|realL id RR,id R|解答：LL（1）分析表见表4-3-1 分析虽然这个文法很简单，我们还是从求开始符号集合和后继符号集合开始。FIRST（D）=FIRST（T）=int,real FOLL

23、OW（D）=FOLLOW（L）=#FIRST（L）=id FOLLOW（T）=id FIRST（R）=，,FOLLOW（R）=#有了上面每个非终结符的FIRST 集合，填分析表时要计算一个产生式右部的 FIRST（）就不是件难事了。填表时唯一要小心的时，是产生式R 右部的一个开始符号，而#在 FOLLOW（R）中，所以 R 填在输入符号#的栏目中。表 4-3-1 LL（1）分析表非终结符输入符号int real id，#D DTLDTLT TintTrealL Lid RR R,id RR 2、下面文法GS是否为 LL（1）文法？说明理由。S A B|P Q x A x y B b c P d

24、 P|Q a Q|解答：该文法不是LL（1）文法，见下面分析中的说明。分析只有三个非终结符有两个选择。1、P 的两个右部d P 和 的开始符号肯定不相交。2、Q 的两个右部a Q 和 的开始符号肯定不相交。3、对 S来说，由于 x FIRST(A B)，同时也有 x FIRST(P Q x)（因为 P 和 Q 都可能为空）。所以该文法不是LL（1）文法。3、设有以下文法：GS：SaAbDe|d ABSD|e BSAc|cD|DSe|（1）求出该文法的每一个非终结符U 的 FOLLOW集。（2）该文法是LL（1）文法吗？（3）构造 CS的 LL（1）分析表。解答：（1）求文法的每一个非终结符U

25、的 FOLLOW集的过程如下：因为：S是识别符号，且有ABSD、BSAc、DSe，所以 FOLLOW（S）应包含名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 20 页 -FIRST(D)FIRST(Ac)FIRST(e)#=a,da,d,c,ee#=a,c,d,e#又因为 ABSD 和 D，所以 FOLLOW中还包含FOLLOW(A)。因为 SaAbDe 和 BSAc,所以FOLLOW（A）=FIRST（bDe）FIRST（c）=b,c 综合、得FOLLOW（S）=a,d,c,e,#a,b,c,d,e,#因为 ABSD，所以FOLLOW（B）=FIRST（SD）=a,d 因为

26、SaAbDe|d、ABSD|e 和 BSAc|cD，所以FOLLOW（D）=FIRST（e）FOLLOW（A）FOLLOW（B）=eb,ca,d=a,b,c,d,e（2）GS 不是 LL（1）文法。因为产生式BSAc|cD|中FIRST（SAc）FOLLOW（B）=a,d?（3）构造 GS的 LL（1）分析表。按照 LL（1）分析表的构造算法构造方法GS的 LL（1）分析表如表4-3-2 所示。表 4-3-2 GS的 LL（1）分析表a b c d e#S aAbDe d A BSD BSD BSD e B Sac/cD Sac/D Se/Se/4、将文法 GV 改造成为 LL(1)的。GV：

27、VN|NE EV|V+E Ni 解答：对文法 GV 提取公共左因子后得到文法：GV：VNA A|E E VB B|+ENi 求出文法G V 中每一个非终结符号的FIRST 集：FIRST(V)=i FIRST(A)=,FIRST(E)=i FIRST(B)=+,FIRST(N)=i 求出文法G V 中每一个非终结符号的FOLLOW集：FOLLOW(V)=#FIRST(B)FOLLOW(E)=#,+,FOLLOW(A)=FOLLOW(V)=+,#FOLLOW(E)=FIRST()FOLLOW(B)=FIRST()FOLLOW(E)=FOLLOW(B)=FOLLOW(E)=FOLLOW(N)=FI

28、RST(A)FOLLOW(V)=,+,#可以看到，对文法G V 的产生式A|E，有FIRST(E)FOLLOW(A)=+,#=?对产生式B|+E，有名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 20 页 -FIRST(+E)FOLLOW(B)=+=?而文法的其他产生式都只有一个不为 的右部，所以文法GV 是 LL(1)文法。5、已知文法：GA：AaAa|（1）该文法是LL（1）文法吗？为什么？（2）若采用LL（1）方法进行语法分析，如何得到该文法的LL（1）分析表？（3）若输入符号串“aaaa”，请给出语法分析过程。解答：（1）因为产生式AaAa|有空产生式右部，而FOLLO

29、W(A)=#FIRST(a)=a,#造成FIRST(A)FOLLOW(A)=A,a,#?所以该文法不是LL（1）文法。（2）若采用LL（1）方法进行语法分析，必须修改该文法。因该文法产生偶数（可以为0）个 a，所以得到文法G A：AaaA|此时对产生式AaaA|，有FOLLOW(A)=#FOLLOW(A)=#，因而FIRST(A)FOLLOW(A)=a,#=?所以文法G A是 LL（1）文法，按 LL（1）分析表构造算法构造该文法的LL（1）分析表如表4-3-3所示。表 4-3-3 文法 G A 的 LL(1)分析表A#A AaaA A（3）若采用LL(1)方法进行语法分析，对符号串“aaaa

30、”的分析过程如表4-3-4 所示。表 4-3-4 对符号串“aaaa”的分析过程步骤分析栈输入串产生式/动作1#A a a a a#AaaA 2#A a a a a a a#匹配3#A a a a a#匹配4#A a a#AaaA 5#A a a a a#匹配6#A a a#匹配7#A#A8#接受第七节习题设有文法GS为：Sa|b|(A)ASdA|S（1）完成下列算符优先关系表，见表5-7-1，并判断GS 是否为算符优先文法。表 5-7-1 算符优先关系表名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 20 页 -a b()d#a?b?(?)?d#?（2）给出句型（SdSdS）

31、的短语、简单短语、句柄、素短语和最左素短语。（3）给出输入串（adb）#的分析过程。解答：（1）先求文法GS的 FIRSTVT集和 LASTVT集：由 Sa|b|(A)得：FIRSTVT(S)=a,b,();由A Sd 得：FIRSTVT(A)=d;又 由A S得：FIRSTVT(S)?FIRSTVT(A)，即FIRSTVT(A)=d,a,b,(;由 Sa|b|(A)得；LASTVT(S)=a,b,;由A dA得：LASTVT(A)=d,又 由A S 得：LASTVT(S)?LASTVT(A)，即LASTVT(A)=d,a,b,)。构造优先关系表方法如下：对 P ab，或 P aQb，有 a?

32、b;对 P aR，而 bFIRSTVT(R)，有 a?b;对 P Rb，而 aFIRSTVT(R)，有 a?b。由此得到：由 S(A)得：(?);由 S(A得：(?FIRSTVT(A)，即：(?d,(?a,(?b,(?(;由 A dA 得：d?FIRSTVT(A)，即：d?d,d?a,d?b,d?(;由 SA)得，LASTVT(A)?)，即：d?),a?),b?),)?);由 ASd得：LASTVT(S)?d，即：a?d,b?d,)?d;此外，由#S#得：#?#；由#?FIRSTVT(S)得：#?a,#?b,#?(；脂由 LASTVT(S)?#得：d?#,a?#,b?#,)?#。最后得到算符优

33、先关系表，见表5-7-2。表 5-7-2 算符优先关系表a b()d#a?b?(?)?d?#?由表 5-7-2 可以看出，任何两个终结符之间至少只满足?、?、?三种优先关系之一，故GS 为算符优先文法。（2）为求出句型（SdSdS）的短语、简单短语、句柄，我们先画出该句型对应的语法树，如图5-7-3 所示。由图5-7-3 得到：短语：S，SdS，SdSdS，（SdSdS）简单短语（即直接短语）：S 句柄（即最左直接短语）：S 素短语：SdS，它同时也是该句型的最左素短语。S A S A S d（）A S d 名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 20 页 -（3）输入

34、串（adb）#的分析过程见表5-7-4 表 5-7-4 输入串（adb）#的分析过程符号栈输入串说明#(adb)#移进#（adb)#移进#（a db)#用 Sa 归约#（S db)#移进#（Sd b)#移进#（Sdb)#用 Sb 归约#（SdS)#用 AS归约#（SdA)#用 ASdA 归约#（A)#移进#（A）#用 S（A）归约#S#分析成功第四节习题一、单项选择题1、若 a 为终结符，则A a为项目a.归约b.移进c.接受d.待约2、若项目集Ik含有 A ，则在状态k 时，仅当面临的输入符号a FOLLOW(A)时，才采取“A ”动作的一定是。a.LALR文法b.LR（0）文法c.LR（1

35、）文法d.SLR（1）文法3、就文法的描述能力来说，有。a.SLR（1）?LR（0）b.LR（1）?LR（0）c.SLR（1）?LR（1）d.无二义文法?LR（1）4、在 LR（0）的 ACTION子表中，如果某一行中存在标记“rj”的栏，则。a.该行必定填满rjb.该行未填满rjc.其他行也有rjd.goto子表中也有rj5、一个指明了在分析过程中的某时刻所能看到产生式多大一部分。a.活前缀b.前缀c.项目d.项目集解答：1、A 称为归约项目，对文法开始符S 的归约项目，如S 称为接受项目，A a（a 为终结符）称为移进项目。在此选b.2、当用产生式A归约时，LR（0）无论面临什么输入符号都

36、进行归约；SLR（1）则仅当面临的输入符号a FOLLOW(A)时进行归约；LR（1）则当在把归约为 A 的规范句型的前缀 Aa前提下，当后跟终结符a 时，才进行归约；因此选d。3、由于 LR（0）?SLR（1）?LR（1）?无二义文法，故选c。4、选 a。5、选 c。二、多项选择题1、一个 LR 分析器包括。a.一个总控程序b.一个项目集c.一个活前缀d.一张分析表e.一个分析栈2、LR 分析器核心部分是一张分析表，该表包括等子表。a.LL(1)分析b.优先关系c.GOTO d.LR e.ACTION 名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 20 页 -3、每一项AC

37、TIONS，a所规定的动作包括。a.移进b.比较c.接受d.归约e.报错4、对 LR 分析表的构造，有可能存在动作冲突。a.移进b.归约c.移进/归约d.移进/移进e.归约/归约5、就文法的描述能力来说，有。a.SLR（1）?LR（1）b.LR（1）?SLR（1）c.LR（0）?LR（1）d.LR（1）?无二义文法e.SLR（1）?无二义文法6、对 LR 分析器来说，存在等分析表的构造方法。a.LALR b.LR（0）c.SLR（1）d.SLR（0）e.LR（1）7、自上而下的语法分析方法有。a.算符优先分析法b.LL（1）分析法c.SLR（1）分析法d.LR（0）分析法e.LALR（1）分析

38、法解答：1、一个 LR 分析器包括一个总控程序和一张分析表，选a、d。2、选 c、e。3、选 a、c、d、e。4、在 LR 分析表的构造中有可能存在“移进”/“归约”和“归约”/“归约”冲突；故选c、e。5、选 a、b、c、d、e。6、选 a、b、c、e。7、选 a、c、d、e。三、填空题1、对于一个文法，如果能够构造。使得它的均是唯一确定的，则称该文法为LR 文法。2、字的前缀是指该字的。3、活前缀是指的一个前缀，这种前缀不含之后的任何符号。4、在 LR 分析过程中，只要的已扫描部分保持可归约成一个，则扫描过的部分正确。5、将识别的 NFA 确定化，使其成为以为状态的DFA，这个DFA 就是

39、建立的基础。6、A 称为项目；对文法开始符S 为项目；若a 为终结符，则称A a为项目；若B 为非终结符，则称A a为项目。7、LR（0）分析法的名字中“L”表示，“R”表示，“0”表示。解答：1、一张分析表每个入口2、任意首部3、规范句型句柄4、输入串活前缀5、活前缀项目集合LR 分析算法6、归约接受移进待约7、自左至右分析采用最右推导的逆过程即最左归约向右查看 0 个字符四、综合题1、对于文法GS：SAS|b ASA|a（1）列出所有LR（0）项目（2）列出构成文法LR（0）项目集规范族。解答：首先将文法G拓广为 GS ：S SSAS|b ASA|a（1）文法 GS 的 LR（0）项目是：

40、1、S S 5、SAS9、ASA 2、S S6、S b 10、ASA3、S AS 7、Sb11、A a 4、SAS 8、ASA 12、Aa2、列出构成文法LR（0）项目集规范族。用-CLOSURE（闭包）办法构造文法G 的 LR（0）项目集规范族如下：I0：1、S S I3：9、ASA I6：12、Aa3、S AS 8、A SA I7：7、Sb8、A SA 3、S AS 名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 20 页 -11、A a 6、S b 6、S b 11、A a I1：2、S SI4：10、ASA9、ASA 4、SAS 8、A SA 3、S AS 11、A a

41、 6、S b 3、S AS 8、A SA 6、S b 11、A a I2：4、SAS I5：5、SAS3、S AS 9、ASA 6、S b 8、A SA 8、A SA 11、A a 11、A a 3、S AS 6、S b 注意：I1中的 S S和 ASA 是由状态I0中的 1 和 3 读入一个S 字符后得到的下一个项目；，而 I4中的 ASA 和 AAS则是由 I3中的 9 和 3 读入一个A 字符后得到的下一个项目；I5中的 SAS和 ASA 则是由 I4中的 4 和 8 读入一个 S 字符后得到的下一个项目。状态全体构成了文法G 的 LR（0）规范族。第八节习题一、单项选择题1、中间代码生

42、成所依据的是。a.语法规则b.词法规则c.语义规则d.等价变换规则2、四元式之间的联系是通过实现的。a.指示器b.临时变量c.符号表d.程序变量3、后缀式ab+cd+/可用表达式来表示。a.a+b/c+d b.(a+b)/(c+d)c.a+b/(c+d)d.a+b+c/d 4、表达式（AB）（CD）的逆波兰表示为。a.ABCDb.ABCD c.AB CD d.AB CD 5、中间代码的树型表示所对应的表达式为。a.A+B+C+D b.A+(B+C)+D c.(A+B)+C+D d.(A+B)+(C+D)6、四元式表示法的优点为。a.不便于优化处理，但便于表的更动b.不便于优化处理，但节省存储空

43、间c.便于优化处理，也便于表的更动d.便于表的更动，也节省存储空间7、终结符具有属性。a.传递b.继承c.抽象d.综合解答1、选 c。2、四元式之间的联系是通过临时变量实现的，故选b。3、选 b。4、选 b。5、选 d。6、四元式表示法的优点与间接三元式相同，故选c。7、选 d。二、多顶选择题1、中间代码主要有。a四元式b二元式c三元式d后缀式e间接三元式2、下面中间代码形式中，能正确表示算术表达式a+b+c 的有。+A B C D+名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 20 页 -+c a b+a+b c*+c+a*aab+c+babc+cdea+b+c 3、在下面

44、的语法制导翻译中，采用拉链-回填技术。a赋值语句bgoto语句c条件语句d循环语句4、下列中间代码形式有益于优化处理。a三元式b四元式c间接三元式d逆波兰表示法e树形表示法5、在编译程序中安排中间代码生成的目的是。a便于进行存储空间的组织b利于目标代码的优化c利于编译程序的移植d利于目标代码的移植e利于提高目标代码的质量6、下面的中间代码形式中，能正确表示算术表达式a+b*c。题）aab+c*babc*+ca+b*c de7、三地址代码语句具体实现通常有表示方法。a逆波兰表示b三元式c间接三元式d树形表示e四元式解答1、选 a、c、d、e。2、b、d 的中间代码不能正确表示a+b+c，而 e

45、不是中间代码：故选a、c。3、凡涉及到跳转的语句都需要采用拉链回填技术，故选b、c、d。4、选 b、c。5、选 b、d。6、选 b、e。7、选 b、c、e。三、填空题1、中间代码有等形式，生成中间代码主要是为了使。2、语法制导翻译既可以用来产生代码，也可以用来产生指令，甚至可用来对输入串进行。3、当源程序中的标号出现“先引用后定义”时，中间代码的转移地址须持时才能确定，因而要进行。4、文法符号的属性有两种，一种称为，另一种称为。5、后缀式abc-/所代表的表达式是，表达式(a-b)*c 可用后缀式表示。6、用一张辅以的办法来表示中间代码，这种表示法称为间接三元式。解答1、逆波兰记号、树形表示、

46、三元式、四元式目标代码的优化容易实现2、中间目标解释执行3、标号定义回填4、继承属性综合属性5、a/(b-c)ab-c*6、间接码表三元式表四、综合题1、给出下列表达式的逆波兰表示（后缀式）：a*(-b+c)(A B)(C DE)2、写出算术表达式：A+B*(C-D)+E/(C-D)N 的四元式序列；三元式序列；间接三元式序列解答 1、abc+*;名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 20 页 -ABCD E第三节习题一、单项选择题1、编译程序使用区别标识符的作用域。a.说明标识符的过程或函数名b.说明标识符的过程或函数的静态层次c.说明标识符的过程或函数的动态层次d

47、.标识符的行号2、在目标代码生成阶段，符号表用于。a.目标代码生成b.语义检查c.语法检查d.地址分配3、过程信息表不包含。a.过程入口地址b.过程的静态层次c.过程名d.过程参数信息4、下列关于标识符和名字叙述中，正确的是。a.标识符有一定的含义b.名字是一个没有意义的字符序列c.名字有确切的属性d.ac 都不正确解答：1、b 2、d 3、b 4、c 二、多项选择题1、符号表的每一项均包含。a.名字栏b.类型栏c.信息栏d.值栏e.ad 均包含2、对编译程序所用到的符号表，涉及的操作有。a.填写或更新信息栏内容b.填入新名c.给定名字，访问它的有关信息d.杂凑技术e.线性表和排序二叉树3、源

48、程序中的错误一般有。a.词法错误b.语法错误c.语义错误d.编译错误e.违反环境限制的错误解答：1、a、c 2、a、b、c 3、a、b、c、e 三、填空题1、符号表中名字栏内容有两种填写方式，它们是填写和填写。2、词法分析阶段的错误主要是，可通过的办法纠正错误。3、符号表中名字的有关信息在和过程中陆续填入。4、在目标代码生成阶段，符号表是的依据。解答：1、标识符标识符地址及长度2、拼写错误最小距离匹配3、词法分析语法语义分析4、地址分配四、问答题：1、在编译过程中为什么要建立符号表？解答：2、表达式的四元式序列：表达式的三元式序列间接三元式序列（1）(-,C,D,T1)（1）(-,C,D)（1

49、）(-,C,D)（2）(*,B,T1,T2)（2）(*,B,(1)（2）(*,B,(1)（3）(+,A,T2,T3)（3）(+,A,(2)（3）(+,A,(2)（4）(-,C,D,T4)（4）(-,C,D)(,(1),N)（5）(,T4,N,T5)（5）(,(4),N)(/,E,(4)(/,E,T5,T6)(/,E,(5)(+,(3),(5)(+,T3,T6,T7)(+,(3),(6)名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 20 页 -在编译过程中始终要涉及到对一些语法符号的处理，这就需要用到语法符号的相关属性。为了在需要时能找到这些语法成分及其相关属性，就必须使用一些

50、表格来保存这些语法成分及其属性，这些表格就是符号表。第四节习题一、单项选择题1、程序所需的数据空间在程序运行前可确定，称为管理技术。a.动态存储b.栈式存储c.静态存储d.堆式存储2、堆式动态分配申请和释放存储空间遵守原则。a.先请先放b.先请后放c.后请先放d.任意3、静态分配允许程序出现。a.递归过程b.可变体积的数据项目c.静态变量d.待定性质的名字4、在编译方法中，动态存储分配的含义是。a.在运行阶段对源程序中的数组、变量、参数等进行分配b.在编译阶段对源程序中的数组、变量、参数进行分配c.在编译阶段对源程序中的数组、变量、参数等进行分配，在运行时这些数组、变量、参数的地址可根据需要改