文库摘要：

写一文法，使其语言是偶正整数的集合
要求：
(1) 允许0打头
(2) 不允许0打头
解：
(1) G[S]=({S,P,D,N},{0,1,2,…,9},P,S)
P:
SPD|D
P->NP|N
D0|2|4|6|8
N->0|1|2|3|4|5|6|7|8|9
(2) G[S]=({S,P,R,D,N,Q },{0,1,2,…,9},P,S)
P:
SPD|P0|D
P->NR|N
R->QR|Q
D2|4|6|8
N->1|2|3|4|5|6|7|8|9
Q->0|1|2|3|4|5|6|7|8|9
6. 已知文法G：
<表达式>::=<项>|<表达式>+<项>|<表达式>-<项>
<项>::=<因子>|<项>*<因子>|<项>/<因子>
<因子>::=(<表达式>)|i。
试给出下述表达式的推导及语法树。
(1)i;   (2)(i)   (3)i*i;
(4)i*i+i;   (5)i+(i+i);  (6)i+i*i。
解： 本文来自文库分享网www.wkfxw.com
(1) v=<表达式>=><项>=><因子>=>i=w
(2) v=<表达式>=><项>=><因子>=>(<表达式>)=>(<项>)=>(<因子>)=>(i)=w
(3) v=<表达式>=><项>=><项>*<因子>=><因子>*<因子>=>i*i=w
(4) v=<表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项>
=><因子>*<因子>+<因子>=>i*i+i=w
(5) v=<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<因子>=>i+(<表达式>)
=> i+(<表达式>+<项>)=>i+(<项>+<项>)=> i+(<因子>+<因子>)=>i+(i+i)=w
(6) v=<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项>
=>i+<项>*<因子>=> i+<因子>*<因子>=> i+i*i=w

语法树见下图: