资源描述:
《语法分析-复习习题.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、上下文无关文法自上而下自下而上LL(1)文法2个函数递归下降预测分析非递归的预测分析最左推导最右推导!LR文法输入LR分析程序输出栈LR分析器的模型actiongotosmXmsm-1Xm-1…s0…a1ai…an$移进-归约分析归约移进-归约冲突规约-归约冲突句柄活前缀右句型的前缀,该前缀不超过最右句柄的右端1。句柄与某个产生式的右部符号串相同2。句柄是句型的一个子串3。把句柄归约成非终结符代表了最右推导逆过程的一步简单的LR方法(SLR)规范的LR方法向前看的LR方法(LALR)温故知新语法分析部分回顾自上而下分析的知识点LL(1)文法的
2、判定FIRST、FOLLOW集的计算(重点)LL(1)文法判定方法LL(1)分析的实现方法递归函数实现非递归的预测分析实现先求FIRST、FOLLOW集画预测分析表2语法分析部分回顾应用LL(1)分析方法的步骤判定文法是否是LL(1)文法如果不是,则改写文法消除左递归提取左因子如果改写后的文法是LL(1)的,那么进行LL(1)分析构造LL(1)分析算法可以采用递归函数实现,也可以采用非递归的栈式分析方法实现3文法G:S->aSb
3、PP->bPc
4、bQcQ->Qa
5、a(1)它是chomsky哪一型文法?(2)它生成的语言是什么?(3)给出提取左
6、因子、消除左递归之后的文法(4)求出每个非终结符的First集和Follow集(5)构建LL(1)预测分析表(6)文法G是否是LL(1)文法(7)利用非递归预测分析程序,验证abacb是否是文法G描述的语言的句子4文法G:S->aSb
7、PP->bPc
8、bQcQ->Qa
9、a(1)它是chomsky哪一型文法?答:它是2型文法,即上下文无关文法。(2)它生成的语言是什么?答:{aibjakcjbi
10、i>=0;j,k>=1}5文法G:S->aSb
11、PP->bPc
12、bQcQ->Qa
13、a(3)给出提取左因子、消除左递归之后的文法答:S->aSb
14、PP-
15、>bP’P’->Pc
16、QcQ->aQ’Q’->aQ’
17、6S->aSb
18、PP->bP’P’->Pc
19、QcQ->aQ’Q’->aQ’
20、First(S)={a,b}First(P)={b}First(P’)={a,b}First(Q)={a}First(Q’)={a,}Follow(S)={$,b}Follow(P)={$,b,c}Follow(P’)={$,b,c}Follow(Q)={c}Follow(Q’)={c}(4)求出每个非终结符的First集和Follow集7(5)构建LL(1)预测分析表输入符号非终结符abc$SS->aSbS
21、->PPP->bP’P’P’->QcP’->PcQQ->aQ’Q’Q’->aQ’Q’->8(6)文法G是否是LL(1)文法答:构建出的LL(1)分析表不含有多重定义的条目,因此文法G是LL(1)文法。9(7)利用非递归预测分析程序,验证abacb是否是文法G描述的语言的句子栈输入输出$Sabacb$$bSaabacb$S->aSb$bSbacb$$bPbacb$S->P$bP’bbacb$P->bP’$bP’acb$10栈输入输出$bcQacb$P’->Qc$bcQ’aacb$Q->aQ’$bcQ’cb$$bccb$Q’->$bb$$$接
22、上表11语法分析部分回顾例2文法G[E]:E->[TT->TE
23、F]F->a
24、aF(1)判断这个文法是不是LL(1)的?(2)消除左递归、提取左因子之后的文法G’是否是LL(1)的?12例1解答:提取左因子,消除左递归后文法变为G’[E]:E->[TT->F]T’T’->ET’
25、F->aF’F’->F
26、G[S]:E->[TT->TE
27、F]F->a
28、aF语法分析部分回顾13FIRST(E)={[}FIRST(T)={a}FIRST(T’)={[,}FIRST(F)={a}FIRST(F’)={a,}FOLLOW(E)={[,$}FOLL
29、OW(T)={[,$}FOLLOW(T’)={[,$}FOLLOW(F)={]}FOLLOW(F’)={]}G’[E]:E->[TT->F]T’T’->ET’
30、F->aF’F’->F
31、不是LL(1)文法!通过提取左因子和消除左递归的方法,并不一定能够把文法改写为一个LL(1)文法语法分析部分回顾14左递归的消除G[S]:S->Qc
32、cQ->Sa
33、a这是一类间接左递归S->Sac
34、ac
35、cQ->Sa
36、a语法分析部分回顾15左递归的消除G[S]:S->Qc
37、cQ->Sa
38、a这是一类间接左递归S->acS’
39、cS’S’->acS’
40、Q->Sa
41、
42、a语法分析部分回顾S->Sac
43、ac
44、cQ->Sa
45、a16语法分析部分回顾LR分析部分的知识点活前缀识别活前缀的DFA分析表分析算法17语法分析内容总结自下而上分