(完整版)编译原理(清华大学第2版)课后习题答案
- 格式:docx
- 大小:512.50 KB
- 文档页数:37
第三章
N=>D=> {0,1,234,5,6,7,8,9}
N=>ND=>NDD
L={a |a(0|1|3..|9) n且n>=1} (0|1|3..|9) n且n>=1
{ab,}
a b n>=1
第6题.
(1) < 表达式> => < 项> => < 因子> => i
⑵ < 表达式> => < 项> => < 因子> => (< 表达式>)=> (< 项>)
=> (< 因子>)=>(i)
⑶ < 表达式> => < 项> => < 项>*<因子> => < 因子>*<因子> =i*i
(4) < 表达式> => < 表达式> + < 项> => < 项>+<项> => < 项>*<因子>+<项>
=> < 因子>*<因子>+<项> => < 因子>*<因子>+<因子> =i*i+i (5) < 表达式> => < 表达式>+<项>=><项>+<项> => < 因子>+<项>=i+<项>
=> i+< 因子> => i+(< 表达式>)=> i+(< 表达式>+<项>)
=> i+(< 因子>+<因子>)
=> i+(i+i)
(6) < 表达式> => < 表达式>+<项> => < 项>+<项> => < 因子>+<项> => i+< 项>
=> i+< 项>*< 因子> => i+< 因子>*< 因子> =i+i*i
第7题
语法树
a
推导:S=>SS*=>SS+S*=>aa+a* 11. 推导:E=>E+T=>E+T*F
语法树:
短语:T*F E+T*F
直接短语:T*F
句柄:T*F
12
.
短语:
直接短语:
句柄:
13.(1)最左推导:S => ABS => aBS =>aSBBS => aBBS
=> abBS => abbS => abbAa => abbaa
最右推导:S => ABS => ABAa => ABaa => ASBBaa
=> ASBbaa => ASbbaa => Abbaa => a1b1b2a2a3
(2)
文法:S ABS
S Aa S £ A a B b
(3)
短语:al , bl , b2, a2 , , bb , aa , abbaa, 直接短语: al , bl , b2, a2 ,, 句柄:al
14 (1)
S AB A aAb | B aBb |
(2)
S 1S0 S
A A
0A1 | £
第四章
1. 1.构造下列正规式相应的 DFA
(1)
1(0|1)*101 NFA
(2) 1(1010*|1(010)*1)*0 NFA
0,1
(3) NFA
1 {X}0 {Z} {X} *
{Z }
{X,Z} {Y} {X,Z} * {X,Z}
{X,Y}
{Y}
{X,Y}
b
a,b
(4)NFA
用0, 1, 2, 3, 4, 5 分别代替{X} {Z} {X,Z} {Y} {X,Y} {X,Y,Z} 得DFA状态图为:
3.解:构造DFA矩阵表示
构造DFA的矩阵表示
其中0表示初态,*表示终态
4.(1 )解
构造状态转换矩阵:
a b {0}0* {0,1} {1} n {0,1} * {0,1} {1} {1} {0}
a b
* 0 1 2
* 1 1 2
2 0
{2 , 3}a={0,3}
{2},{3},{0,1}
{0,1}a={1,1} {0,1}b={2,2}
(2)解:首先把M的状态分为两组:终态组{0},和非终态组{1 , 2, 3,4,5} 此时G=( {0},{1,2,3,4,5} ) {1,2,3,4,5} a={1,3,0,5}
{1,2,3,4,5} b={4,3,2,5}
由于{4} a={0} {1,2,3,5} a={1,3,5} 因此应将{1,2,3,4,5} 划分为{4},{1,2,3,5} G=({0}{4}{1,2,3,5})
{1,2,3,5} a={1,3,5}
{1,2,3,5} b={4,3,2}
因为{1,5} b={4} {23} b={2,3}
所以应将{1,2,3,5}戈U分为{1,5}{2,3}
G=({0}{1,5}{2,3}{4})
{2,3} a={1,3} {2,3} b={3,2}
因为{2} a={1} {3} a={3} 所以{2,3}应划分为{2}{3}
所以化简后为G=( {0},{2},{3},{4},{1,5} )
7.去除多余产生式后,构造NFA如下
{1,5} a={1,5} {1,5} b={4} 所以{1,5} 不用再划分
G={(0,1,3,4,6),(2,5)}
{0,1,3,4,6}a={1,3}
{0,1,3,4,6}b={2,3,4,5,6}
所以将{0,1,3,4,6}戈U分为{0,4,6}{1,3}
G={(0,4,6),(1,3),(2,5)}
{0,4,6}b={3,6,4} 所以划分为{0},{4,6}
G={(0),(4,6),(1,3),(2,5)}
不能再划分,分别用0, 4, 1 , 2代表各状态,构造DFA状态转换图如下;
&代入得
S = 0(1S|1)| 1(0S|0)
=01(S| £ ) | 10(S| £ )
=(01|10)(S| £ )
=(01|10)S | (01|10)