言。 （西安电子科大2000年研究生试题）
判断题：
3.4.1语法分析之所以采用上下文无关文法是因为它的描述能力最强。 （ ）
3.4.2 欲构造行之有效的自上而下分析器，则必须消除左递归。 （ ） 3.4.3文法( 有图片 )描述的语言是（a|bc）* ( ) 3.4.4 在自下而上的语法分析中，语法树与分析树一定相同。（ ） 3.4.5 二义文法不是上下文无关文法。（陕西省1999年自考题）（ ） 3.4.6 每一个算符优先文法，必定能找到一组优先函数与之对应。（陕西省2000年自考题） （ ）
3.4.7 语法分析时必须先消除文法中的左递归。 （ ） 3.4.8 规范归约和规范推导是互逆的两个过程。 （ ） 3.4.9 一个文法所有句型的集合形成该文法所能接受的语言。 （ ）
3.4.10 LL(1)文法一定不含左递归和二义性。 （ ）
综合题
3.5.1 简答题 1．句柄 2.素短语 3．语法树 4.归约 5.推导
3.5.2给出上下文无关文法的定义。
3.5.3 Chomsky将文法分成四类。指明这四类文法与自动机的对应关系。指出右线性文法、左线性文法、正规文法之间的主要区别。
3.5.4 文法G是LL(1)文法的充分必要条件是什么？
3.5.5 文法G[S］：
S→aSPQ|abQ QP→PQ bP→bb bQ→be cQ→cc
（1)它是Chomsky哪一型文法？ （2）它生成的语言是什么？
3.5.6 指出下述文法的所有类型，并给出所描述的语言。 （1）S→Be （2）A→ε|aB（3）TS→abcA B→eC|Af B→Ab|a S→Aabc A→Ae|e A→ε C→Cf Aa→Sa
D→fDA cA→cS
3.5.7 按指定类型，给出语言的文法。 （1）L=｛aidj>i≥l}的上下文无关文法。
(2)字母表∑={a,b｝上的同时只有奇数个a和奇数个b的所有串的集合的正规文法。 (3）由相同个数a和b组成句子的无二义文法。
3.5.8 下面的二义文法描述命题演算公式，为它写一个等价的非二义文法。 S→SandS|S or S|not S|p|q|(S)
3.5.9 有文法G：S→aAcB|Bd A→AaB|c B→bScA|b
（1)试求句型aAaBcbbdcc和aAcbBdcc的句柄； (2)写出句子acabcbbdcc的最左推导过程。
3.5.10 对文法G：E→E+T|T T→T*P|P P→i
（1)构造该文法的优先关系表（不考虑语句括号＃），并指出此文法是否为算符优先文法；
(2）构造文法G的优先函数
3.5.11 在上一题中，如果将文法改为E→E+E|E*E|i,在不改动文法的情况下是否同样能构造出优先关系表？此外，针对例3.14中的文法与本例中的文法，对算符优先分析快于规范归约进行说明。
3.5.12 对于文法G[S]：
S→(L)|aS|a L→L,S|S （1)画出句型（s，（a））的语法树。
(2)写出上述句型的所有短语、直接短语、句柄和素短语。
3.5.13 构造算符文法G[H]的算符优先关系（含＃）。 G[H]：H→H;M|M M→d|aHb
3.5.14 设有文法G[S]为： S→a|b|(A) A→SdA|S
（1) 完成下列算符优先关系表，见表3.6.并判断G[S]是否为算符优先文法。
(2）给出句型（SdSdS)的短语、简单短语、句柄、素短语和最左素短语。 （3)给出输入串(adb)#的分析过程。
3.5.15 下面映射if语句的文法G[S]是算符优先文法吗？若是，则构造其优先关系矩阵。若不是，请按照多数程序设计语言（如Pascal)的习惯，给出一个相应的算符优先文法。
G[S]：S→iBtS|iBtSeS|a B→b
3.5.16 文法G[
3.5.17 已知文法G[A]为： A→aAB1|a B→Bb|d
（I）试给出与G[A]等价的LL(I）文法G’[A]。 （2)构造G’[A］的预测分析表。 （3）给出输入串aadl#分析过程。
3.5.18 将G[V]改造为LL（1）文法。 G[V]: V→N|N[E] E→V|V+E N→i
3.5.19 有文法G[S]: S-BA A--BS|d B～aA|bS|c
(I）证明文法G是LL(I）文法。 （2）构造LL（1）分析表。
(3）写出句子adccd的分析过程。
3.5.20 考虑文法G[T]：
T→T*F|F F→F↑P|P P→(T)|i
（1)证明T*P↑(T*F)是该文法的一个句型，并指出其直接短语和句柄。 (2)构造文法G的优先关系表（要求写出步骤）。
3.5.21 给出算符优先文法的分析算法。
3.5.22 文法G的产生式集为：S→S+S|S*S|i|（s），对于输入串i+i*i；
（1)给出一个推导； (2）画出一棵语法树；
（3)文法G是否是二义性的，请证明你的结论。
3.5.23 已给文法G[E]：
E→EOE|(E)|i 0→+|*
试将其改造为可进行不带回溯的自顶向下分析的文法，并给出其相应的LL(1)分析表。
3.5.24 考虑文法G(S)：
S→(T)|a+S|a T→T,S|S
消除文法的左递归及提取公共左因子，然后，对每个非终结符，写出不带回溯的递归子程序。
3.5.25 有映射程序设计语言if-the-else语句的文法G[S]: S→iEtSeS|EtS|a
E→b 其中，else遵从最近匹配原则。
（1)试改造文法，并为之构造LL（1）分析表。 (2）利用构造的分析表分析句子ibtibtaea,要求给出分析过程中每一步的分析栈和输入串的变化以及输出信息。
3.5.26 下述文法描述了C语言整数变量的声明语句： D→TL T→int|long|short L→id|L,id
（1)改造上述文法，使其接受相同的输入序列，但文法是右递归的。 (2)分别用上述文法和改造文法，为输入序列int a,b,c构造分析树。
3.5.27 设有文法G[W]：
W→AO
A→AO|W1|0
请改写文法，消除规则左递归和文法左递归。
3.5.28 文法G[P]及相应翻译方案为：
P→bQb {print:”1”｝ Q→cR {print:”2”｝ Q→a {print:”3”｝ R→Qad (print:”4”｝
（1)该文法是不是算符优先文法，请构造算符优先关系表证实之。 (2)输入串为bcccaadadadb时，该翻译方案的输出是什么。
3.5.29 设有文法G[S]： S→SAS|b A→bSb|b
试构造一个与其等价的算符文法。
3.5.30 在算符优先分析法中，为什么要在找到最左素短语的尾时，才返回来确定其对应的头，能否按扫描顺序先找到头后找到对应的尾，为什么？
3.5.31 试证明在算符文法中，任何句型都不包含两个相邻的非终结符。
3.5.32假定文法包含产生式A→α，α∈V*（V是文法的词汇表，由终结符和非终结符组成的集合），证明：如果FIRST（α）∩FOLLOW（A）≠φ，则该文法不是LL（1)文法。
3.5.33 给出文法G1：
S→aSb|P A→bPc|bQc B→Qa|a
（1)它是Chomsky哪一型文法？ （2）它生成的语言是什么？
（3)它是不是算符优先文法？请构造算符优先关系表证实之。
(4)请证实所有①左递归文法②有公共左因子的文法均不是LL（1)文法。 (5)文法G1消除左递归、提取公共左因子后是不是LL (1）文法？请证实。
3.5.34 简答题
（1)什么是文法的二义性？二义性问题的不可判定指的是什么？ (2)在规范句型中，句柄以右的符号有什么特征？为什么？
3.5.35 写正规文法G,它产生的语言是L(G)={ anibncp|m,n,p≥0}
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《编译原理》期中及期末习题(4)在线全文阅读。
相关推荐：