问题标签 [context-free-grammar]

我正在寻找一种没有多余括号的算术表达式的明确语法。例如，括号在 中是多余的id+(id*id)，但在 中不是(id+id)*id。

我查看了 Bison 帮助并写了这个，但我不确定它是否完全正确。我还需要一个yylex()处理词法分析器（它应该是Flex工具）。我知道一些关于上下文无关语法的基本知识。但我不知道如何正确实施它们！:(

我想要一个用于 HTML 的简单 Bison 语法。问题是：以下语法应该改变什么？

这是 Bison 的输出：

它不会是一个完整的 HTML 解析器。我只想验证没有任何CSS样式的非常简单的 HTML 文档JavaScripts或...我也看到了这个。注意：解决方案必须是 Bison 语法！

我应该手动应用生产规则来找出这个语法生成的语言吗？这很乏味，有什么技巧/提示可以加快速度吗？

编辑：我发现 Matajon 的回答很好，那就是考虑由非终端符号生成的每种语言，然后将它们组合起来。

但是当我必须解决一些像这样的复杂示例时，我仍然陷入困境：

疯了，不是吗？取自过去的考试（编程语言课程）。

真正的现代正则表达式实际上可以识别哪一类语言？

每当存在带有反向引用（例如(.*)_\1）的无限长度捕获组时，正则表达式现在正在匹配非常规语言。但这本身并不足以匹配诸如S ::= '(' S ')' | ε匹配括号对的上下文无关语言之类的东西。

递归正则表达式（对我来说是新的，但我确信存在于 Perl 和 PCRE 中）似乎至少可以识别大多数 CFL。

有没有人做过或读过这方面的研究？这些“现代”正则表达式的局限性是什么？他们对 LL 或 LR 语法的识别比 CFG 严格多还是严格少？或者是否存在两种语言都可以被正则表达式识别但不能被 CFG 识别，反之亦然？

相关论文的链接将不胜感激。

自从我与 CFG 合作以来已经有一段时间了。无论如何，我有一个特定的语法可以正确地完成所有操作，但最后（我排除了其他标准数学操作）。

S ::= S+T | 意法半导体 | 吨

T ::= 非终结符 | 身份证 | -S | (S)

根据我所拥有的一切.. 我知道 -S 应该是 -T。但另外......这对优先级有什么影响。是模棱两可的吗？从数学上讲，我可以它显然是不正确的..但这不应该对歧义问题产生影响。

如果是 -T，它的优先级是否与 (S) 相同？

真的试图理解这是如何发生的，它循环回到开始状态。

是否有任何工具可以将 ANTLR 语法语法与其他 BNF 语法转换？有几种带有规范的 Backus-Naur 形式（BNF、EBNF、ABNF、W3C-BNF、XBNF...），例如，请参阅此列表。ANTLR 语法似乎只通过示例来描述。我知道 ANTLR 语法文件包含的不仅仅是上下文无关语法的规范，但您至少应该能够转换公共子集 - 有人自动完成了吗？

铁路图是一种可视化上下文无关语法的流行方法，您可以将 Backus-Naur Form 映射到这些图表。但是BNF 的一些变体，例如W3C-BNF允许异常（因为上下文无关语言不会在差异下关闭，这些异常必须是常规的）。我想在铁路图中可视化带有异常的语法。我应该发明自己的图形符号扩展还是有人已经对此进行了实验？

这是一个例外规则的例子（是的，你也可以毫无例外地表达这个特定的语法，但这不是重点）：

异常可以是任何常规语法。我考虑过通过某种特殊类型的箭头或线条（这里用感叹号表示）添加与非终端符号连接的异常：

PS：语法错了，应该是

也许否定的非直觉使用是它在正式语法中很少使用的原因之一？

前任。

S-> S + T | 吨

T-> U - T | ü

U -> ID | ñ

显然没有保留关联性。但无论如何我都看不出它是模棱两可的。那么这是一个非模棱两可的cfg吗？

B是无用的生产。现在移除后

它是否正确 ？

你好，

我有以下形式的产品：

任何人都可以通过删除左递归来帮助我将其转换为 LL(1) 形式吗？？我已经对此表示反对，但我仍然无法理解:(。以下是我的尝试。

上述转换是否正确？？我从这里做什么？

我使用了在wikipedia中找到的以下一般规则。

转换时：