问题标签 [context-free-grammar]

有没有人有一个很好的工具来绘制由上下文无关语法产生的解析树？有这个问题，但它专门处理有限自动机而不是解析树。我一直在使用graphviz，但是必须单独标记每个节点等有点烦人。

假设我尝试使用 Packrat 解析器解析字符串abc ：

这里我使用了 Packrat 解析器支持的左递归，但我不明白为什么它会失败。根据 Parser 文档 P | 如果 P 成功，Q 等于 P，所以在这种情况下ab应该用“ab”而不是“a”替换，就像我替换ab为：

我正在研究荷兰语语料库，我想知道 NLTK 中是否嵌入了荷兰语语法，以便我可以解析我的句子？一般来说，NLTK 只适用于英语吗？我知道它有 Alpino 荷兰语语料库，但没有迹象表明这些功能（如使用 CFG 解析）也适用于荷兰语。谢谢

我试图通过消除间接递归然后直接递归来消除 CFG 中的左递归，如该算法所示。

我将使用这个语法：

当i = 1和j = 1时，我们正在考虑将所有形式A -> A r的产生式替换为：

A -> δ ₁ γ | δ ₂ γ | .. | δ _k γ

因此，当我查看匹配的A -> A a时，我应该将其替换为

我确定这是错的

当您用产品本身替换产品时，谁能指出我如何替换产品的正确方向？

注意：另外，我只坚持第一条规则，所以为了简单起见省略了其他规则

任何帮助将不胜感激

[更新]尽可能接近原始希腊符号。另外，我可能是在错误的方向上解决这个问题。当i=1和j=1时，A _j -> A a | 美国广播公司 | 卑诗省 | DD，但我应该使用 A _j -> BC | DD 如果是这样，那么我会得到：

因为那将消除该生产中的递归。这是一个更好的方向？

首先，我不知道这是否是我所要求的正确翻译。

在我的一门课程中，我们只是盯着学习正则表达式、形式语言等。

在这种情况下，假设我从 1R 开始，然后我可以继续使用 1R 或 0R。

如果我从 1R 开始，那么只有 1....那么句子（在这种情况下是二进制数）是完整的，对吗？因为我不能在之后“附加”一些东西，所以说 1R 然后我选择 1 然后我再次选择 1R ？

在此先感谢，如果不正确，请重新标记/移动帖子。

添加：

如何生成 1100110？

这不是家庭作业，它是来自 powerpoint 的示例/问题。我不明白这是怎么做到的。

根据我的经验，形式语法通常以类似于以下的形式表示以逗号分隔的列表：

有什么替代方法可以避免提及foo两次？虽然这个人为的例子可能看起来很无辜，但我遇到了非平凡的表达而不是foo. 例如：

我必须确定一种语言（例如 L={a^nb^mc^s | 0<=n<=m<=s}）是否是常规的、上下文无关的、递归的、递归可枚举的，或者它们都不是。

我知道如何确定一种语言是正则的（找到一个有效的 DFA 或正则表达式）还是上下文无关的（找到一个有效的 PDA 或上下文无关的语法）；我知道递归语言有一个总是停止的图灵机，而递归可枚举语言有一个可能不会停止的图灵机。

所以问题是：是否有一个快速的标准来确定语言是递归的还是递归可枚举的，或者两者都不是？例如，我不必构建一个 PDA 来理解一种语言是上下文无关的，我看不到它需要一个堆栈的事实；是否有类似的快速解决问题的方法（希望可以省去构建图灵机的麻烦）？

我正在研究一些测试准备材料并坚持这个问题。

显示 L = {we {a,b}*: w = wR 且每个 a 都紧跟 ab} 的上下文无关文法。

wR 是相反的 w。所以，在英语中，每个“a”后面跟着一个“b”的回文，使用任意数量的a和b。

到目前为止，我得到了这个反向部分，但我不知道如何合并每个 a 后跟 ab 部分，同时确保回文属性仍然有效。

任何帮助是极大的赞赏！

我试图找出是否有可能有一个 CFG 的例子，它不可能给出一个可以接受相同语言的正则表达式。

有谁知道冲突在哪里？

更新

如果我删除exp(res) ::= exp(e1) OP(o) exp(e2).，只会有两个冲突，但我不知道为什么会导致冲突......

更新2

为什么这里可以：