自上而下的解析器分类

问题描述

我看过Alex Aiken的这门课程并阅读通过许多其他资源.但是我很难找到自上而下的解析器的清晰分类.

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:

回溯

预测性

递归下降VS表驱动

递归下降

表驱动

据我所知，我有四种不同类型的解析器:

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

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

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

如果我是正确的话，有人还能告诉我LL(k)解析器在以下四种类型的解析器中的位置吗?

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

推荐答案

否.你有:

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

因此您可以:

• 递归下降回溯
• 递归下降预测
• 具有回溯功能的表驱动
• 表驱动的预测.

具体来说，具有表/堆栈实现的递归关系"在术语上是矛盾的.

To be specific, 'Recursive descent with table/stack implementation' is a contradiction in terms.

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

All table-driven parser implementations need a stack. This is not a dichotomy.

任何地方.

这篇关于自上而下的解析器分类的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！