最新编译原理期末试题及答案南京廖华答案网

最新编译原理期末试题及答案下载本文

文章发布时间 : 2024/9/27 5:57:59星期五

精品文档

2 - 0 ε a 1 a b ε + 3

（2）将（1）所得的非确定有限自动机确定化

ε a b -0 1 2 +3 1 1 3 12 2 +

-+ a 0 b a 1 + a

（3）对（2）得到的DFA化简，合并状态0和2 为状态2：

2 -+ b a 1 + a

（4）令状态1和2分别对应非终结符B和A

G: A→aB|a|ε； B→aB|bA|a|b|ε；可化简为：G: A→aB|ε；B→aB|bA|ε

四、

设将文法G改写成等价的LL(1)文法，并构造预测分析表。

G：S→S*aT|aT|*aT； T→+aT|+a

解：消除左递归后的文法G’: S→aTS’|*aTS’

S’→*aTS’|ε

T→+aT|+a

提取左公因子得文法G’’: S→aTS’|*aTS’ S’→*aTS’|ε T→+aT’

T’→T|ε Select(S→aTS’)={a} Select(S→*aTS’)={*}

Select(S→aTS’)∩Select(S→*aTS’)=Ф Select(S’→*aTS’)={*}

Select(S’→ε)=Follow(s’)={#} 精品文档

精品文档

Select(S’→*aTS’)∩Select(S’→ε)= Ф Select(T→+aT’)={+}

Select(T’→T)=First(T) ={+}

Select(T’→ ε)=Follow(T’)={*,#}

Select(T’→T)∩Select(T’→ε)= Ф 所以该文法是LL(1)文法。预测分析表： * + a # S →*aTS’ →aTS’ S’ →*aTS’ →ε T →+aT’ T’ → ε →T → ε

6设文法G 为：

S→A；A→BA|ε；B→aB|b 解：（1）拓广文法G’：(0) S’→S (1) S→A (2) A→BA(3) A→ε(4) B→aB (5) B→b ；a, b}；FIRST(B) = {a, b} 构造的DFA 如下:

项目集规范族看出，不存在冲突动作。∴该文法是LR(1)文法。（2） LR(1)分析表如下：

(3)输入串abab 的分析过程为：

精品文档

FIRST(A) = {ε,

精品文档

五、对文法G(S)：S → a | ^ | (T)；T → T，S | S

FIRSTVT(S)?{a,^,(} 答：(1) FIRSTVT(T)?{,,a,^,(}

LASTVT(S)?{a,^,)}LASTVT(T)?{,,a,^,)}

(2) 是算符优先文法，因为任何两个终结符之间至多只有一种优先关系。（2

分）

(3) 给出输入串(a,a)#的算符优先分析过程。步骤 1 2 3 4 5 6 7 8 9 10 栈当前输入字符剩余输入串动作 # #( #(a #(N #(N, #(N,a #(N,N #(N #(N) #N ( a , , a ) ） ) # # a,a# ,a)# a)# a)# )# # # # #<( 移进 (, 归约 (<, 移进 ,) 归约 ,>) 归约 (=) 移进 )># 归约接受 a ^ ) a ^ ( ) , # > > > > > > = > > > < ( < < < = < , < < < > > # < <

五、设有文法G[A]：

(1) 计算该文法的每一个非终结符的FIRST集和FOLLOW集； (2) 试判断该文法是否为LL（1）文法。（15） A B 精品文档

FIRST A,b,c,d,g b FOLLOW A,c,d 精品文档 C D E A,c,d D C,g C,d,g A,b,c,g 是LL（1）文法。

2．对于文法G[S]：S?AB，A?Aa|bB，B?a|Sb求句型baSb的全部短语、直接短语和句柄？

句型baSb的语法树如图五(2)所示。

A B

b b B S

解：baSb为句型baSb的相对于S的短语，ba为句型baSb的相对于A的短语，Sb为句型baSb的相对于B的短语，且为直接短语，a为句型baSb的相对于B的短语，且为直接短语和句柄。

3．设有非确定的有自限动机NFA M=({A，B，C}，{0，1}，?，{A}，{C})，其中：

? (A，0)={C} ? (A，1)={A，B} ? (B，1)={C} ? (C，1)={C}。请画出状态转换距阵和状态转换图。解：状态转换距阵为：

? A B C 0 C ? ? 1 A，B C C

状态转换图为 1 1