自上而下的解析器分类
Top-down parser classification
我看过 Alex Aiken 的 this course 并通读了许多其他资源。但我正在努力寻找自上而下解析器的清晰分类。
This document 也没有提供明确的分类，但至少给出了一些我将在 post 中使用的定义。所以这是我到目前为止的分类：
回溯 VS 预测
回溯
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.
预测
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.
递归下降 VS table-驱动
递归下降
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驱动
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
据我所知，我现在有四种不同类型的解析器：
- 递归下降+回溯
- 递归下降+预测
- Table-驱动 + 回溯
- Table-驱动+预测
如果我是对的，有人能告诉我 LL(k) 解析器在以下 4 种类型的解析器中的位置吗？
没有。你有：
- 回溯与预测
- 递归下降 vs table 驱动
所以你可以拥有：
- 递归下降回溯
- 递归下降预测
- table-回溯驱动
- table-驱动预测。
具体来说，'Recursive descent with table/stack implementation'是自相矛盾
所有 table 驱动的解析器实现都需要一个堆栈。这不是二分法。
where in the following 4 types of parsers the LL(k) parser falls?
任何地方。
我看过 Alex Aiken 的 this course 并通读了许多其他资源。但我正在努力寻找自上而下解析器的清晰分类。
This document 也没有提供明确的分类，但至少给出了一些我将在 post 中使用的定义。所以这是我到目前为止的分类：
回溯 VS 预测
回溯
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.
预测
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.
递归下降 VS table-驱动
递归下降
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驱动
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
据我所知，我现在有四种不同类型的解析器：
- 递归下降+回溯
- 递归下降+预测
- Table-驱动 + 回溯
- Table-驱动+预测
如果我是对的，有人能告诉我 LL(k) 解析器在以下 4 种类型的解析器中的位置吗？
没有。你有：
- 回溯与预测
- 递归下降 vs table 驱动
所以你可以拥有：
- 递归下降回溯
- 递归下降预测
- table-回溯驱动
- table-驱动预测。
具体来说，'Recursive descent with table/stack implementation'是自相矛盾
所有 table 驱动的解析器实现都需要一个堆栈。这不是二分法。
where in the following 4 types of parsers the LL(k) parser falls?
任何地方。