问题标签 [context-free-grammar]

如何为您要从头开始设计的新编程语言（命令式编程语言）定义语法（无上下文）。

换句话说：当您想从头开始创建一种新的编程语言时，您将如何进行。

我正在做一个项目，我必须在其中读取语法文件（将其分解为我的数据结构），目标是能够生成随机的“DearJohnLetter”。

我的问题是，在读取 .txt 文件时，我不知道如何确定该文件是否应该是一个完全空白的行，这对程序是不利的。

这是文件的一部分的示例，我如何判断下一行是否应该是空行？（顺便说一句，我只是使用缓冲阅读器）谢谢！

我对 ANTLR 很陌生，所以这可能是一个简单的问题。
我已经定义了一个简单的语法，它应该包括带有数字和标识符的算术表达式（以字母开头并以一个或多个字母或数字继续的字符串。）

语法如下所示：

我正在使用 ANTLR v3 和 ANTLR IDE Eclipse 插件。当我使用解释器解析表达式时(8 + a45)，只生成部分解析树：

为什么第二项 (a45) 没有被解析？如果两个术语都是数字，也会发生同样的情况。

有没有办法为 ANTLRv3 生成的 Parser 和 Lexer 类指定自定义类名（意味着独立于语法名）？

所以在这种情况下

它会自动创建 MDDParser 和 MDDLexer，但我希望将它们作为 MDDBaseParser 和 MDDLexer。

我正在复习我的计算理论课程笔记，但我无法理解如何完成某个证明。这是问题：

很明显，必须使用抽水引理。所以，我们有

1. |维| >= 1
2. |vxy| <= p (p 是泵送长度，>= 1)
3. uv^ixy^iz 对于所有 i >= 0 都存在于 A 中

尝试考虑选择正确的字符串似乎有点不确定。我在想0^p 1^q 0^p，但我不知道我是否可以模糊地制作aq，而且由于你没有约束，这可能会让事情变得不守规矩..

那么，怎么办呢？

我只是对不同的语言进行了一些思考（因为我正在为即将到来的期末考试复习），我想不出一个有效的下推自动机来处理语言 A = {0^n 1^n 0^n | n >= 0}。这不是上下文无关的语言，对吗？

我正在尝试了解 shift-reduce 解析。假设我们有以下语法，使用强制操作顺序的递归规则，受ANSI C Yacc 语法的启发：

我们想使用 shift-reduce 解析来解析 1+2。首先，将 1 作为数字移动。我的问题是，它是否会被简化为 P，然后是 M，然后是 A，最后是 S？它怎么知道在哪里停下来？

假设它确实一直减少到 S，然后移动“+”。我们现在有一个堆栈，其中包含：

如果我们移动'2'，减少可能是：

现在，在最后一行的任一侧，S 可以是 P、M、A 或 NUMBER，并且它仍然有效，因为任何组合都是文本的正确表示。解析器如何“知道”它

这样它就可以将整个表达式简化为A，然后S？换句话说，它如何知道在移动下一个令牌之前停止减少？这是 LR 解析器生成的关键难点吗？

编辑：对问题的补充如下。

现在假设我们解析1+2*3. 一些移位/减少操作如下：

这是正确的（当然，它还没有完全解析）？此外，1 符号前瞻是否也告诉我们不要减少A+M到A，因为这样做会导致读取后不可避免的语法错误*3？

我有这个问题，我需要在 CNF 中将以下 CFG 转换为 CFG。

我知道步骤如下。

1. 删除 epsilon 转换 - 完成
2. 删除单元制作
3. 通过以下方式转换为 CNF：
   1. 为每个术语引入一个新的非终结符
   2. 用新的非终结符替换产生式规则中的终结符
   3. 引入新的非终结符以减少每个产生式右侧的长度

我对如何解决上述问题感到有些困惑。大多数情况下，我对第 2 步和单元制作感到困惑。

我有以下问题：

语言 L1 = {a^n * b^n : n>=0} 和 L2 = {b^n * a^n : n>=0} 是上下文无关语言，因此它们在 L1L2 下是封闭的，因此 L={a ^n * b^2n A^n : n>=0} 也必须是上下文无关的，因为它是由闭包属性生成的。

我必须证明这是否属实。所以我检查了 L 语言，我认为它不是上下文无关的，然后我还看到 L2 只是 L1 反转。

我是否必须检查 L1、L2 是否是确定性的？

如果给你一种语言，你如何判断它是正规的、CF 但不是正规的，还是短语结构而不是 CF？有没有解决这个问题的好方法？我可以随意尝试制作 FA 或 PDA，但我觉得有更好的方法来做。

经典例子：

L = { a^nb^nc^n | n >= 0 }

从哪里开始？谢谢。