CFG生产规则在代码中的外观如何？

那里有这么多的信息，但这不是真的有助于像我这样的noob。我阅读了许多关于上下文无关语言和下推自动化的文章。现在我试图了解代码中可能会看到某些东西。CFG生产规则在代码中的外观如何？

让我们假设我们定义的语言，如：

L = {am bn | m >= n}

给我们以下的生产规则：

S -> B |^
B -> aBb | A 
A -> aA | a

正是这将如何看起来像伪代码？我假定所有的生产规则都是1状态定义为S1或者都是单独的状态？无论哪种方式，我不知道，如果有人能帮助我理解这是如何工作的，这将是非常好的。

我知道我们分析了一个输入的字符，并且取决于输入的是什么输入，其中一个规则适用于将一个符号推入我们的PDA堆栈。

来源

2017-03-22 Asperger

什么，具体来说，你想要你的代码吗？请明确点。 CFG描述语言。你想让你的代码输出分析树吗？你想让你的代码识别语言中的字符串吗？或者生成它们？如果生成它们，哪些？你没有时间全部生成它们。 – Patrick87

您的生产规则仅生成m> n的字符串，这种平等是不可能的。正如帕特里克所说，如果你想要一个算法，你应该明确指出哪个问题。 –

@PeterLeupold好的我今天会更新我的问题。你是对的，很多信息都不见了，我会编辑我的例子。 – Asperger

有多种方法可以将CFG转换为实际解析的代码片段，每种方法都有其优点和缺点。一些算法，如CYK算法，Unger算法和（我个人最喜欢的）Earley算法可以将任意CFG和一个字符串作为输入，然后使用动态编程为该字符串确定一个分析树（如果存在的话）。这些算法的操作与典型的下推自动机不相似，因为它们一次处理一个字符时填写值表。

一些解析算法，特别是LR（1）和LR解析器的一般系列，更直接地维护解析堆栈并使用有限状态控制来驱动解析器。尽管LR（1）解析器不能处理所有可能的CFG，但它们只能处理确定性的CFG - 但像GLR解析器这样的变体可以通过并行地运行多个堆栈来处理所有语法。编译器生成工具bison和yacc在这个系列中生成解析器，如果你看看它们的输入文件是如何工作的，你就会了解CFG是如何在软件中编码的。（1）解析器和简单的回溯解析器自顶而下工作，通常使用堆栈（通常是运行时调用堆栈）解析输入字符串。尽管如此，他们无法处理所有语法。 ANTLR解析器生成器在该系列中生成解析器。

Packrat解析器通过使用修改的CFG来编码，该编码使用什么样的顺序来编码优先级。使用这些解析器的代码倾向于密切地反映语法的形状。解析器组合器是另一种现代技术，解析逻辑看起来很像CFG。

如果您有兴趣了解更多信息，我会建议您参加一个编译器课程或者获取Grune和Jacobs的“解析技巧：实用指南”的副本。

来源

2017-08-29 15:49:33 templatetypedef

CFG生产规则在代码中的外观如何？

回答

相关问题