语法分析-复习习题

语法分析-复习习题

ID:39707027

大小:352.50 KB

页数:29页

时间:2019-07-09

语法分析-复习习题_第1页
语法分析-复习习题_第2页
语法分析-复习习题_第3页
语法分析-复习习题_第4页
语法分析-复习习题_第5页
资源描述:

《语法分析-复习习题》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、上下文无关文法自上而下自下而上LL(1)文法2个函数递归下降预测分析非递归的预测分析最左推导最右推导!LR文法输入LR分析程序输出栈LR分析器的模型actiongotosmXmsm-1Xm-1…s0…a1ai…an$移进-归约分析归约移进-归约冲突规约-归约冲突句柄活前缀右句型的前缀,该前缀不超过最右句柄的右端1。句柄与某个产生式的右部符号串相同2。句柄是句型的一个子串3。把句柄归约成非终结符代表了最右推导逆过程的一步简单的LR方法(SLR)规范的LR方法向前看的LR方法(LALR)温故知新语法分析部分回顾自上而下

2、分析的知识点LL(1)文法的判定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)它是chomsk

6、y哪一型文法?(2)它生成的语言是什么?(3)给出提取左因子、消除左递归之后的文法(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、b

13、QcQ->Qa

14、a(3)给出提取左因子、消除左递归之后的文法答:S->aSb

15、PP->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)求出每

21、个非终结符的First集和Follow集7(5)构建LL(1)预测分析表输入符号非终结符abc$SS->aSbS->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’$

22、bP’acb$10栈输入输出$bcQacb$P’->Qc$bcQ’aacb$Q->aQ’$bcQ’cb$$bccb$Q’->$bb$$$接上表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语法分析部分回顾13F

29、IRST(E)={[}FIRST(T)={a}FIRST(T’)={[,}FIRST(F)={a}FIRST(F’)={a,}FOLLOW(E)={[,$}FOLLOW(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、

34、a这是一类间接左递归S->Sac

35、ac

36、cQ->Sa

37、a语法分析部分回顾15左递归的消除G[S]:S->Qc

38、cQ->Sa

39、a这是一类间接左递归S->acS’

40、cS’S’->acS’

41、Q->Sa

42、a语法分析部分回顾S->Sac

43、ac

44、cQ->Sa

45、a16语法分析部分回顾LR分析部分的知识点活前缀识别活前缀的DFA分析表分析算法17语法分析内容总结自下而上分

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。