[第五章自顶向下语法分析.ppt

2.左递归问题 【例】文法G[E]： E→E+T|T T→T*F|F F→(E)|i 给出i*i+i自顶向下的分析过程。 要实行自顶向下分析，必须要消除文法的左递归 从左向右扫描源程序，同时实施最左推导 E E + T E + T E + T … 失败：由于使用最左推导，对左递归文法进行自顶向下分析时，会导致死循环。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 将左递归规则改为右递归规则 A→A?|? 【例】文法G[E]： E→E+T| T T→T*F| F F→(E)|i E→TE E→+TE|? T→FT T→*FT|? F→(E)|i 消除左递归 A→?A A→?A|? （1）消除直接左递归 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 消除直接左递归——课内练习 文法G : P ? PaPb|BaP 转化为： P ?BaPP` P` ?aPbP`| ? 注：只有最左边的P参加变换。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. (2)消除间接左递归（了解自学） 先通过产生式进行非终结符置换 将间接左递归变为直接左递归 消除直接左递归 把置换的产生式加入 详例见书文法G6，P89 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 5.3 某些非LL(1)文法到LL(1)文法的等价转换 消除左递归和提取公共左因子 【例】 G[S]: S→aSb|A A→bAc|bBc B→Ba|a S→aSb|A A→bAc|bBc B→aB B→aB|? 消除左递归 提取公因子 S→aSb|A A→bA A→Ac|Bc B→aB B→aB|? LL(1)文法的判别条件 LL(1)文法 【例】 G[S]: S→aSb|A A→bAc|bBc B→Ba|a Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 不确定的自顶向下分析思想 当文法不满足LL(1)时，不能用确定的自顶向下分析，但可用不确定的自顶向下分析，也就是带回溯的自顶向下分析法（试探）。 由于相同左部的产生式的右部First集交集不为空引起 由于相同左部非终结符的右部存在能推导出?的产生式，且该非终结符的Follow集中含有其他产生式右部First集的元素 文法含左递归 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 确定的自顶向下分析方法 递归子程序法 对文法中的每个非终结符（语法成分）编写一个子程序，而子程序的代码结构由相应非终结符的产生式右部所决定： 产生式右部的终结符与输入符号相匹配 非终结符与相应的子程序调用对应 构造方法非常简单 程序结构清晰 递归调用较多，占用内存多、速度慢 如果所采用的高级语言不允许递归，则不能使用此方法 特 点 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 自左向右扫描分析输入符号串 从识别符号开始生成句子的最左推导 LL(1):向前看一个输入符号，便能唯一确定产生式 LL(k):向前看k个输入符号，才能唯一确定产生式 基本思想： LL(1)分析法 使用下推自动机的方式实现。 使用一个二维分析表和栈联合进行控制来实现分析。 确定的自顶向下分析方法 预测分析法 Evaluation only. Cre