1.文法G(Z):Z->aZb|ab定义的是什么样的语言?
因Z->aZb->aaZbb->aaaZbbb或Z->ab
所以文法定义的语言是:L(G(Z)) = { anbn | n≥1 }
2.写出教材22页例2.2中标识符的文法四元组形式。
文体 G = (VN,VT,P,S)
其中 VN = {W(标识符),Q(字母),K(数字)},VT = {a,b,c,···,x,y,z,0,1,···,9}
P = { <W> -> <Q>
<W> -> <W> <Q>
<W> -> <W> <K>
<Q> -> a
<Q> -> b
•••
<Q> -> z
<K> -> 0
<K> -> 1
•••
<K> -> 9 }
S = <W>
3.写出下列表达式的最左推导、最右推导和语法树。
G(E):
E=> E + T | T
T=>T * F | F
F=>(E)| i
- i*i+i
- i+i*i
- i+(i+i)
注意观察最左和最右推导过程的不同,以及语法树的异同。
(1)最左推导:E => E+T => T+T => T*F+T => F*F+T => i*F+T => i*i+T => i*i+F => i*i+i
最右推导:E => E+T => E+F => E+i => T+i => T*F+i => T*i+i => F*i+i => i*i+i
语法树:
(2)最左推导:E => E+T => T+T => F+T => i+T => i+T*F => i+F*F => i+i*F => i+i*i
最右推导:E => E+T => E+T*F => E+T*i => E+F*i => E+i*i => T+i*i => F+i*i => i+i*i
语法树:
(3)最左推导:E => E+T => T+T => F+T => i+T => i+F => i+(E) => i+(E+T) => i+(T+T) => i+(F+T) => i+(i+T) => i+(i+F) => i+(i+i)
最右推导:E => E+T => E+F => E+(E) => E+(E+T) => E+(E+F) => E+(E+i) => E+(T+i) => E+(F+i) => E+(i+i) => T+(i+i) => F+(i+i) => i+(i+i)
语法树: