自上而下的解析器分类(Top-down parser classification)

2019-09-25 16:30发布

I've watched this course by Alex Aiken and read through many other resources. But I'm struggling to find clear classification of top-down parsers.

This document doesn't provide a clear classification either but at least gives some definitions I'll use in the post. So here is the classification I've come up so far:

Backtracking VS Predictive

Backtracking

One solution to parsing would be to implement backtracking.  Based on the information  the parser currently has about the input, a decision is made to go with one particular  production.  If this choice leads to a dead end, the parser would have to backtrack to that decision point, moving backwards through the input, and start again making a different  choice and so on until it either found the production that was the appropriate one or ran  out of choices.

Predictive

A predictive  parser is characterized by its ability to choose the production to apply solely on the basis  of the next input symbol and the current nonterminal being processed.

Recursive descent VS table-driven

Recursive descent

A  recursive-descent parser consists of several small functions, one for each nonterminal in  the grammar.  As we parse a sentence, we call the functions that correspond to the left  side nonterminal of the productions we are applying.  If these productions are recursive,  we end up calling the functions recursively.

Table driven

There is another method for implementing a predictive parser that uses a table to store that production along with an explicit stack to keep track of where we are in the parse

As I understand now I have four different types of parsers:

  • Recursive descent + backtracking
  • Recursive descent + prediction
  • Table-driven + backtracking
  • Table-driven + prediction

If I'm correct, can some also tell me where in the following 4 types of parsers the LL(k) parser falls?

Answer 1:

不,你必须:

  • 回溯VS预测
  • 递归下降VS表驱动

所以,你可以有:

  • 递归下降回溯
  • 递归下降预测
  • 表驱动与回溯
  • 表驱动的预测。

具体而言,“以表/堆栈实现递归下降”是一种自相矛盾的说法。

所有表驱动的解析器实现需要一个堆栈。 这不是一个二分法。

其中以下4种类型的解析器LL(k)的解析器落入?

无处不在。



文章来源: Top-down parser classification