编译原理重点题型简答综合选择填空

? 构造下面文法的LL(1)分析表 S→aBc|bAB A→aAb|b B→b|ε

构造其LL(1)分析表，并分析符号串baabbb是否是该文法的句子 答：FIRST(S)={a,b} FIRST(A)={a,b} FIRST(B)={b,ε} FOLLOW(S)={#} FOLLOW(A)={b,#} FOLLOW(B)={c,#} LL(1)分析表：

分析符号串baabbb的过程：

? 设有文法G[S]：S→CC (1) C→cC (2) C→d (3) 求：1）拓广文法

2）文法的LR(1)项目集规范族（识别活前缀的DFA） 3）构造规范LR分析表

4）给出句子cdd的LR(1)分析过程 1）拓广文法

S’→S(0) S→CC(1) C→cC(2) C→d(3)

2）LR(1)项目集规范族

I0={[S’→?S,#]，[S→?CC,#]，[C→?cC,c/d]，[C→?d,c/d]} I1=GO(I0,S)={[S’→S?,#]}

I2=GO(I0,C)={[S→C?C,#]，[C→?cC,#]，[C→?d,#]}

I3=GO(I0,c)=GO(I3,c)={[C→c?C,c/d]，[C→?cC,c/d]，[C→?d,c/d]} I4=GO(I0,d)=GO(I3,d)={[C→d?,c/d]} I5=GO(I2,C)={[S→CC?,#]}

I6=GO(I2,c)=GO(I6,c)={[C→c?C,#]，[C→?cC,#]，[C→?d,#]} I7=GO(I2,d)=GO(I6,d)={[C→d?,#]} I8=GO(I3,C)={[C→cC?,c/d]} I9=GO(I6,C)={[C→cC?,#]}

14、给出下述文法对应的正规式： S→0A|1B A→1S|1 B→0S|0

分析与解析：将A，B产生式的右部代入S中 01S|01|10S|10=(01|10)S|(01|10) 所以，(01|10)*(01|10)

15、已知文法G[A]：A→B|AaB|AbB B→C|BcC|BdC C→fAg|e

给出符号串eceae的最右推导、语法树

16、设有文法G[S]=({S,A,B},{a,b},P,S)，其中P为： S→AB A→Aa|bB B→a|Sb

求句型baSb的全部短语、直接(简单)短语和句柄。

短语有：ba,Sb,a,baSb直接短语：a,Sb句柄：a

17、设有文法G[E]：E→EE+

E→EE*

E→a (1) 构造该文法的LR(0)项目集规范族

(2) 该文法的LR(1)文法吗，请说明理由？若是请构造它的LR(1)分析表 解答：首先拓广文法如下： S→E E→EE+

E→EE* E→a

(1)构造该文法的LR(0)项目集规范族：

I0=CLOSOURE({S→·E})={ S→·E，E→·EE+，

E→·EE*，E→·a } I1=GO(I0,E)= { S→E·，E→E·E+，E→E·E*，E→·EE+， E→·EE*，E→·a } I2=GO(I0,a)=GO(I1,a)= { E→a· }

I3=GO(I1,E)=GO(I3,E)= { E→EE·+，E→EE·*，E→E·E+，E→E·E*，E→·EE+，E→·EE*，E→·a }

I4=GO(I3,+)= { E→EE+·} I5=GO(I3,*)= { E→EE*· } (2)该文法是LR(1)文法，因为：

在LR(0)项目集规范族的每个项目子集中，都不存在移进－归约冲突和归约－归约冲突，所以该文法是LR(0)文法，自然也是SLR(1)文法和LR(1)文法，现构造LR(1)项目集族如下： I0=CLOSURE({[S→·E,#]})={ [S→·E,#]，[E→·EE+,#/a]，

[E→·EE*,#/a]，[E→·a,#/a] } I1=GO(I0,E)= { [S→E·,#]，[E→E·E+,#/a]，[E→E·E*,#/a]，

[E→·EE+,+/*/a]，[E→·EE*,+/*/a]，[E→·a,+/*/a] } I2=GO(I0,a)= { [E→a·,#/a] }

I3=GO(I1,E)= { [E→EE·+,#/a]，[E→EE·*,#/a]，

[E→E·E+,+/*/a]， [E→E·E*,+/*/a]，E→·EE+,+/*/a]， [E→·EE*,+/*/a]， [E→·a ,+/*/a] } I4=GO(I1,a)=GO(I3,a)=GO(I7,a)={ [E→a·,+/*/a]} I5=GO(I3,+)= { [E→EE+·,#/a] } I6=GO(I3,*)= { [E→EE*·,#/a] }

I7=GO(I3,E)=GO(I7,E)={ [E→EE·+,+/*/a]，[E→EE·*,+/*/a]，

[E→E·E+,+/*/a]， [E→E·E*,+/*/a]， [E→·EE+,+/*/a]， [E→·EE*,+/*/a]， [E→·a ,+/*/a] } I8=GO(I7,+)= { [E→EE+·,+/*/a] } I9=GO(I7,*)= { [E→EE*·,+/*/a] }

18、假设有以下算符优先文法：G[A]: A→A;D|D D→D(E)|F F→a|(A) E→E+A|A

(1)给出该文法的算符优先关系表。(2)写出句子(a+a)的算符优先分析过程。