编译原理(陈火旺第三版)练习答案

人、狼、羊、白菜：

{{M、W、G、C}，{}}表示在左岸，{{}，{M、W、G、C}}在右岸，将可能存在的状态中去掉不安全状态，剩下：

{{M、W、G、C}，{}}，{{}，{M、W、G、C}}，{{M、W、G}，{C}}，{{M、W、C}，{G}}， {{M、G、C}，{W}} ，{{C}，{M、W、G}} ，{{G}，{M、W、C}}，{{W}，{M、G、C}}， {{M、G}，{W、C}} ，{{W，C}，{M、G}}

箭弧上的标记符：<M>：表示人单独过河、<MG>：表示人和羊过河、<MW>：表示人和狼过河、<MC>：表示人和白菜过河

编译原理(陈火旺第三版)练习答案

第四章

P81-1

（1） 按照T，S的顺序消除左递归 G'（S）：S→a| |（T） T→ST'

T'→，ST'|ε

递归下降子程序： procedure S: begin

if sym = ‘a’or sym= ‘ ’

then advance else if sym=‘（’ then begin advance；T；

if sym = ‘)’ then advance; else error; end

else error end

procedure T; begin S;T' End

Procedure T'; Begin

If sym = ‘,’ Then begin Advance; S;T'

End End

其中：sysm为输入串指针所指的符号；advance是把输入指针调至下一输入符号。 （2） 求First和Follow集合： First（S）={a 、 、（} First（T）={a 、 、（} First（T'）={， 、ε} Follow（S）={ , 、) 、 #} Follow(T) = { ) } Follow(T'）={ ) } a ( ) , # S S→a S→ S→(T) T T→ST' T→ST' T→ST'

T'

T'→ε

T'→，ST'