《编译原理》期中及期末习题(6)

合性，终结符“；”满足左结合性，且“，”的优先级高于“；”的优先级。 文法G[T]：T→TAT|bTe｝a A→，|；

4.5.8 二义文法G[S],符的优先性和结合性说明如下： （a）else与最近的if结合 (b）“；”优先性大于if (c）“；”优先性大于else (d)“；”服从左结合

请使用LR分析法的基本思想，凭借上述条件，为G[S]构造LR分析表，要求写出详细 的构造过程。

G[S]:S→if S else S S→if S S→S;S S→a

4.5.9 已知文法G[S]为 S→aAd|;Bd|aB↑|;A↑

A→a

B→a

（1)试判断G[S]是否为LALR(1)文法。

(2)当一个文法是LR(1)而不是LALR(1)时，那么LR(1)项目集的同心集合并后会出现哪几种冲突，请说明理由。

4.5.10 文法G[T]及其LR分析表（见表4.9)如下，给出串bibi的分析过程。 （1）T→EbH （2）E→d （3）E→ε （4）H→i （5）H→Hbi （6）H→ε

4.5.11 给出文法G[S]及图4.9所示的LR(1)项目集规范族中的0、1, 2, 3, 4. G[S]: S→S;B|B B→BaA|A A→b(S)

4.5.12 证明AdBd是文法G[S]的活前缀，说明活前缀在LR分析中的作用。给出串dbdb#的LR

分析过程。

G[S］： （1）S→AdB (4) B→b （2）A→a （5）B--Bdb （3）A→ε （6）B→ε

4.5.13 一个非LR（1）的文法如下：

L→MLb|a M→ε

请给出所有有移进一归约冲突的LR(1)项目集，以说明该文法确实不是LR(1)的。

4.5.14 文法G(S)的产生式集为：

S→(EtSeS)|(EtS)|i =E E→+EF|F F→*Fi|i

构造文法G的SLR(1)分析表。要求先画出相应的DFA。

4.5.15 下述文法是哪类LR文法？并构造相应分析表。

4.5.16 给定文法G［A]：A→(A)|a

（1)证明：LR(1)项目[A→(A·），］］对活前缀“((a”是有效的；

(2)画出LR(1)项目识别所有活前缀的DFA; （3）构造LR(1）分析表；

(4)合并同心集，构造LALR(1)分析表。

4.5.17 已知布尔表达式的方法G[B]如下：

度为G[B]构造LR分析表。

4.5.18 8086/8088汇编语言对操作数域的检查可以用LR分析表实现。设m代表存储器，r代表寄存器，i代表立即数；并且为了简单起见，省去了关于m,r,和i的产生式，暂且认为m、r、i为终结符，则操作数域P的文法G如：试构造能够正确识别操作数域的LR分析表。

4.5.19 为语言｛amb0|n>m≥0｝写3个文法，它们分别是二义文法、LR(1）文法以及非LR（1)且非二义的文法。不必证明所写文法的正确性，但每个文法的产生式不能超过4个。

4.5.20 由文法二义引起的LR(1)分析动作冲突，可以依据消除二义的规则而得到LR(1)分析表，根据此表可以正确识别输入串是否为相应语言的句子。对于非二义非LR(1)文法引起的LR(1)分析动作的冲突，是否也可以依据什么规则来消除LR(1)分析动作的冲突而得到LR(1)分析表，并且根据此表识别相应语言的句子？若可以，是否可以给出这样的规则？

4.5.21 有文法G＝（｛S｝，｛a｝，｛S→SaS,S→ε，S），该文法是_____。 A. LL(l)文法。 B.二义性文法 C.算符优先文法 D. SLR(1)文法

4.5.22 试证明任何一个SLR(1）文法一定是一个LALR(1)文法。

4.5.23 文法G[P]：P→aPb|Q Q→bQc|bSc S→Sa|a

（1)请构造它的SLR分析表，以说明它是不是SLR文法。 (2)在消除左递归、提取公共因子后可得等价文法G[P’］，它是不是LL(1)文法。

4.5.24 给出文法G2: S→SaS|SbS|cSd|eS|f （1)请证实这是一个二义文法；

（2)给出什么样的约束条件，可构造无冲突的LR分析表？请证实你的论点。

4.5.25 有简单语言的文法G(VT,VN,P,δ，其中，VT＝｛黑体小写字母串，标点符号，赋值号，运算符｝

VN＝{P,D,L,S,E,T,B｝ δ: P→begin D;S end D→id:L

L→integer|boolean S→id:=Elif B then S E→E+TIT T→id B→id|true|false

（1)试写出该文法的一个句子；

(2)该文法属于以下哪几种文法，不属于哪几种文法，请说明理由。 a)上下文无关文法 b) LL(1)文法 c) SLR(1)文法

4.5.26 试分析LR(0)、SLR(1), LR(1)和LALR(1)分析表的优缺点。

4.5.27 比较LL(K)和LR(K)的异同点。

4.5.28 文法G[A］的LR分析表，见表4.21，请给出串ab的分析过程。G[A］的拓广文法为G[A`］。

4.5.29 文法G[S]及其LR分析表（见表4.22）如下，请给出对串baba#的分析过程。

4.5.30 为下面的二义文法G构造一个LR分析表（详细说明构造方法），其中“*”的优先级高于“＋”，且，\、“＋”都服从左结合。 文法G：E→E+E|E*E|a

4.5.31根据程序设计语言的一般要求，为定义条件语句的二义文法G[S]构造SLR(1)分析表，要求写出步骤和必要说明。

G[S］：S→iSeS|iS|a

4.5.32 对下列文法：

1）S'→S 2）S→bRST 3）S→bR 4）R→dSa 5）R→e 6）T→fRa 7）T→f

（1）求各非终结符的FIRST和FOLLOW集合。 （2）构造该文法的SLR(1)分析表。（请将终结符和非终结符以abdef#SRT顺序构造分 析表）

4.5.33 下述文法是SLR文法吗？若是，给出分析表；否则，说明理由。 （1）S→bASB|bA （2）A→dSa|e （3）B→cAa|c

4.5.34 己知某语言L={ambn|n>m≥0}。试写出产生该语言的两种文法G1和G2,其中G1是 LR(1)文法，G2是非LR(1)和非二义性文法。

4.5.35 构造一个LR(1）文法G,它产生语言L（G）={w}w|(a|b)*，w中a和b的个数相等｝。

4.5. 36 试证明任何的SLR(l)文法都是LR(1)文法。

4.5.37 给定拓广文法G (S为G的开始符号），G的产生式（附带编号）如下： 0）S→E 1）E→E+T 2）E→T 3）T→i 4）T→(E)

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《编译原理》期中及期末习题(6)在线全文阅读。