编译原理之自顶向下分析(daywolf原创) 自顶向下分析算法通过最左推导中描叙出各个步骤来分析记号串输入，一般用递归下降分析和LL(1)分析。其中LL(1)分析表示从左向右地处理输入，它为输入串描述一个最左推导，只用一个符号来预测分析的方向。现在在一般的程序里都是使用LL(1)分析方法，我们在这里就只介绍LL(1)。
LL(1)由于并没有使用递归的方法，所以必须使用分析栈。这里有一个问题不知道大家有没有注意?栈究竟用几个才是适合呢?如果是LL(1)的话就应该使用一个，如果是LL(2)的话就应该使用两个，如此类推。我们先介绍自顶向下方法中的两个动作，第一个是生成，英文是generate，第二个是匹配。我们这里不作任何的解释，实际行动最重要，哈哈。好，请看下面的例子。
有一个简单的文法：S->aS|b,其中e标识为空
分析栈 输入 动作
1 $ ab$ 生成S->aS
2 $Sa ab$ 匹配
3 $S b$ 生成S->b
4 $b b$ 匹配
5 $ $ 接收 看到了没有，是不是很简单呢？解释一下，分析栈要先放进一个$符号标识结束，生成了之后要把内容以相反的方向压进栈。
由于左递归是很难做出算法的，下面我们来看看用LL(1)是怎样消除左递归的。什么？不知道左递归是什么。好吧，让我告诉你，例如有这样的文法A->Aa|b,你看一下会生成什么b,ba,baa,baaa....当然还有更复杂的，不用急下面会慢慢介绍。这个简单的左递归可以转化为右递归
A -> BA'
A'-> aA'|e
上面的是简单的直接左递归，当然还有普遍的直接左递归，文法为A->Aa1|Aa2|...|b1|b2
转化为
A -> B1A'|B2A'|...BmA'
A'-> a1A'|a2A'|...|e
还有一般的左递归，是指不带e产生式且不带有循环的文法，由于一般程序设计中不会出现在这里就不作介绍了。如果想再学习可以参Principles and Practice一书。
你有没有发现我们只说了左递归的情况，那右递归又有没有什么消除方法呢？答案是有的。例如下面的一个例子是如下：A->ab|ar
很明显，LL(1)分析方法不能区分这种情况中的产生式选择。这种简单揭发式将左边的a分解出来，我们称为提取左因子，结果如下。
A ->aA'
A'->b|r 哇，我介绍了很多啦，有没有什么奖励啦？哈哈。其他就要自己动手咯。
|
本类阅读TOP10