LL(1)文法分析

自顶向下

自顶向下是一种从开始符号推导出输入符号所对应的语法的过程,举个例子:

上面便是个从开始符号S出发,推导出aabb语法情况的过程,可以通过这个信息产生语法树。

那么如何推导呢?下面是通过一个栈来做的穷举推导过程,这种推导是需要回溯的:

上面的例子里面,出栈一个非终结符的时候,便从这个终结符的几个产生式里找一个做尝试,如果此路不通,就回退到尝试的路口,然后换一个产生式继续努力,直到找到一条看起来可以走下去的路继续重复以上的步骤(如果所有产生式都不能走通,就判断为语法有问题)。

可以想象,如果从A开始就选错了产生式,然后B尝试了所有产生式都没走通,那么回溯的层次就不仅仅是B自己一层了。这就好像一条路有X个岔路,然后每个岔路又有各自Y个岔路,而每个子岔路下面仍然有可能有Z个岔路,而目的地是X5Y2Z8,这种做法好像赌博碰运气一样,看天吃饭。有没有其他好的方法呢?

继续阅读