内容发布更新时间 : 2025/1/7 13:08:30星期一 下面是文章的全部内容请认真阅读。

A→[B，B→X]{A}，X→(a|b){a|b}即 A→[B B→X]{A} X→(a|b){a|b}

可以先变换：B→X]{ [B } A()

{ if ( sym==’[‘ ){ scaner(); B(); } else error(); } B() { X();

if(sym==’ ] ‘){ scaner(); while(sym==’[‘) { scaner();B(); } }else error(); } X()

{if(sym==’a‘) {scanner();}

else if(sym==’b‘) {scanner();} else error(); while(sym==’a‘ or sym==’b‘) { scanner();} }

得 分 五、综合题(本大题共2小题，每小题7分，共14分)

1．将下列NFA确定化，并画出最小化的DFA。

输入a 输入b ｛0｝ ｛0，1｝ ｛1｝ ｛1｝ {0,1} {1} ｛0，1｝ {0,1} {1}

{0} {1,2} f(1,a)=2 f(2,a)=2 f(1,b)=1 f(2,b)=1 {1,2}等价

得 分 2. 给定文法G[S]:S→AS|b，A→SA|a， 1）构造它的LR(0)项目集规范簇；

2）构造识别该文法所有活前缀的DFA。

项目集规范族： I0：S’→ .S

S→.AS S→.b A→.SA A→.a I1: S’→ S. A→S.A A→.SA A→.a S→.AS S→.b 等

DFA即我们经常画出的图（I0、I1等之间有弧和弧上标记的符号） 参看习题4.8