6.3 广度优先自顶向下解析

用于自顶向下解析问题的广度优先方法是去维护一个所有预测的列表。然后每一个预测都像上面6.2节说的那样处理，也就是说，如果栈顶是一个非终结符，这个预测栈就被一些新的预测栈替换，新的预测栈数量跟它所对应的选择数相同。在这每一个新栈里，栈顶的非终结符被对应的选择替换。这个预测步骤对所有预测栈施用（包括新生成的），直到所有预测栈栈顶都是终结符。

这时对所有预测栈，我们将最前面的终结符与当前输入符号进行匹配，将不匹配的预测栈删去。如果没有预测栈剩下来，那么这个句子不属于该语言。所以，我们的自动机现在维护一个（stack,analysis stack）预测元组的列表而不是单一一个预测元组，其中每一个对应一个可能选择，如图Fig6.7所示。

这个方法对在线解析（on-line parsing）同样适用，因为它按从左到右的顺序处理输入串。任何从左到右处理输入并且得到最左推导（leftmost derivation）的解析方法被称为LL解析方法。第一个L代表从左到右，第二个L代表最左推导。

依此我们基本知道了该怎么写出这样一个解析器，但现在我们还有一个小问题没有解决：终止。当最终我们得到了一个空的预测栈时，输入句子就属于该语法描述的语言吗？不，仅当输入被读完的情况下才是！为了避免这个额外的检查，并且避免出现已经达到句尾但解析没有停止的情况，我们引入一个特殊的终止记号（end marker） #.这个终止记号同时附加在句子和预测的末尾，所以当符号成功匹配时我们就能知道这个预测匹配了输入句子，解析成功。