问题标签 [context-free-grammar]

作为序言，我对这类东西的了解是微不足道的。

无论如何，我一直在开发一种上下文无关的语法来描述代数表达式的结构，这样我就可以自学 CYK 解析算法是如何工作的。我了解这种结构如何仅与中缀代数表达式一起使用，但我无法理解如何开发一种可以同时处理“-”运算符的一元和二元定义的语法。

作为参考，这是我在 CNF 中编写的语法（其中 S 是开始符号）：

S -> x
A -> OS
S -> LB
B -> SR
S -> KS
O -> +
O -> -
O -> *
O -> /
O -> ^
K -> -
L -> (
R - > )

问题是 CYK 解析算法在遇到“-”运算符时，如何提前知道是否在 S -> KS 和 A -> OS 之间做出决定？这样的语法不再是上下文无关的了吗？最重要的是，由于编程语言可以处理带有二进制和一元减号的语言，我应该如何合理地解析这个？

我一直在使用以下数据结构来表示 Haskell 中的命题逻辑：

欢迎对此结构提出任何意见。

但是，现在我想扩展我的算法来处理 FOL - 谓词逻辑。在 Haskell 中表示 FOL 的好方法是什么？

我见过的版本 - 几乎 - 上面的扩展，以及基于更经典的上下文无关语法的版本。有没有这方面的文献，可以推荐？

我正在使用 ANTRL，这是我的一些语法，它给我带来了错误。

这是错误“Decision can match input such as "ELSE" using multiple alternatives ”。

我该如何解决？

问题指出：

给出一个生成语言 A = {a^ib^jc^k | 的上下文无关文法 i=j 或 j=k 其中 i,j,k >= 0} 语法是否有歧义？为什么或者为什么不？ [介绍。到 TOC Sipser 2.10]

这本书没有太多关于如何仅从语言描述生成上下文无关语法的好例子。

我应该尝试创建一个下推自动机然后尝试从那里转换吗？或者这件事有一些一般指导方针吗？

我目前正在尝试实现一个 LALR 解析器生成器，如“编译器原理技术和工具”（也称为“龙书”）中所述。

很多已经奏效了。解析器生成器当前能够生成完整的 goto-graph。

转到图：

我在实现生成动作表的算法时遇到了麻烦！我的算法计算以下输出：

sx... 转移到状态 x
rx... 减少到状态 x

r? 意味着我不知道如何获取解析器应该减少的状态（？）。有谁知道一个算法得到？使用上面的goto-graph？

如果有什么描述不够清楚，请询问，我会尽力解释得更好！谢谢你的帮助！

好吧，我试图理解跟随集，我想我明白了，除了一件事：

按照本页的规则，FOLLOW(X) 应包含 $，即文件结尾字符（规则 1）。然后，按照规则 3，FOLLOW(X) 包含 FOLLOW(X) 的所有内容，这让我的大脑融化了。

对我来说，直觉上，FOLLOW(X) 应该是 {a,b,$}，但是在kfg Edit中尝试这个例子只给了我 {$}。为什么？

我怎么知道这些语言是否是上下文无关的？

试图弄清楚在上下文无关语法中删除左递归。我习惯了某些形式，但这个让我有点困惑。

我还必须设计一个像样的解析器，我可以做到。然而，弄清楚这个左递归（尤其是第一个递归）让我感到困惑。

在哪里可以找到 PL/SQL 编程语言的官方语法？我看到Antlr 项目有一个用户贡献的语法，但我希望找到一个更权威的来源。

根据定义，语法包含产生式，非常简单的语法示例：

我想在 c# 中实现语法类，但我不确定如何存储产品，例如如何区分终端和非终端符号。我在想：

左边永远是非终结符号（它是关于上下文无关语法）但生产的右边可以包含终结符号和非终结符号

所以现在我在考虑两种实现方式：

1. 非终结符号将使用括号写入，例如：

   E+E 将被表示为字符串“[E]+[E]”

2. 创建额外的数据结构 NonTerminal

   struct NonTerminal { 字符串符号；}

E+E 将表示为数组/列表：

但认为有更好的想法，听到一些回应会很有帮助