例如有文法下.doc

《例如有文法下.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、例如：有文法如下：(1)S->aAcBe(2)A->b(3)A->Ab(4)B->d问语句abbcde是不是该文法的合法语句?例如：表达式文法：EE+E

2、E-E

3、E*E

4、E/E

5、(E)

6、i如：i+i-i*(i+i)归约过程如下：1）i+i-i*(i+i)设算数级别最高，最先归约2）E+i-i*(i+i)3）E+E-i*(i+i)+,-同级，先归约左边“+”4）E-i*(i+i)5）E-E*(i+i)-,×不同级，先归约右边“×”6）E-E*(E+i)7）E-E*(E+E)先算括号内，再算括号外8）E-E*(E)9）E-E*E先归

7、约“×”，再归约“+”10）E-E11）E例：设文法G的产生式为：S->aAcBeA->Ab

8、bB->d计算每个非终结符的FIRSTVT与LASTVT及所有终结符之间的关系解：FIRSTVT(S)={a}LASTVT(S)={e}FIRSTVT(A)={b}LASTVT(A)={b}FIRSTVT(B)={d}LASTVT(B)={d}例：构造下面文法的算符优先表S->ifEbthenEelseEE->E+T

9、TT->T*F

10、FF->iEb->b解：1）求各非终结符的首终结符和尾终结符集，为了考率语句的开始和结束符号“#”,对文

11、法拓广,加一个产生式S’#S#FIRSTVT(S)={if}LASTVT(S)={else,+,*,i}FIRSTVT(E)={+,*,i}LASTVT(E)={+,*,i}FIRSTVT(T)={*,i}LASTVT(T)={*,i}FIRSTVT(F)={i}LASTVT(F)={i}FIRSTVT(Eb)={b}LASTVT(Eb)={b}2)填写算符优先表例如：考虑非二义的表达式文法G(E):—E->E+T

12、TT->T*F

13、FF->(E)

14、i—识别句子i+i*i的过程（1）规范归约—i+i*i#1.F+i*i#2.T+i

15、*i#3.E+i*i#4.E+F*i#5.E+T*i#2.非规范分析(2).算符优先分析在算符优先分析，仅研究终结符之间的优先关系，而不考虑非终结符之间的优先关系；但句柄是由终结符和非终结符一起构成的，所以算符优先分析相对来说是非规范的分析。对上题的分析过程：—i+i*i#—1.E+i*i#—2.E+T*i#—3.E+T*F#两种分析的语法树对比：例如：考虑非二义的表达式文法G(E):—E->E+T

16、TT->T*F

17、FF->(E)

18、i—句型#T+T*F+i#的素短语，为什么？由定义可知，素短语：T*F,I最左素短语：T*F例如：

19、根据下面文法及其算符优先表，按通用通用算符优先分析的算法分析语句ifbthenielsei#S->ifEbthenEelseEE->E+T

20、TT->T*F

21、FF->iEb->b