2008～2009学年度第二学期《编译原理》考试试卷答案-A

六、已知文法G[S]：S→＊A，A→＊|0A1 ：（8分）

1.计算非终结符的FIRSTVT集和LASTVT集.并找出终结符之间的所有优先关系（包括句子左右的语句括号＃）。

FIRSTVT LASTVT S {*} {*,1} A {*.0} {*,1}

0=1,#=#,左边＃右边#

2．根据1，构造G的算符优先关系矩阵。此文法是算法符优先文法吗？ 0 1 * # 0 < ＝ < 1 > > * < > < > # < =

七、设有文法G[S]：S→(S)|b （共6分）

1．构造能识别文法G[S]的规范句型活前缀的DFA；（3分）

Sˊ→·S S →· (S) S S→·b ( Sˊ→S· S→(·S) b (S) S S → (S · ) ) S→(S)· S →·S→·b S→b· (

2．构造它的LR(0)分析表。（3分）

5

ACTION GOTO ( ) b # S

0 S1 S3 1 1 acc 2 S3 4 3 r2 r2 r2 4 5 r1 S5 r1 r1

6