问题标签 [formal-languages]

我正在阅读解析器和解析器生成器，并在维基百科的 LR parsing -page 中找到了这个语句：

可以使用 LR 解析器的某些变体来解析许多编程语言。一个值得注意的例外是 C++。

为什么会这样？C++ 的哪些特殊属性导致无法使用 LR 解析器进行解析？

使用google，我只发现可以用LR（1）完美解析C，但C ++需要LR（∞）。

我知道 Perl 正则表达式引擎的某些功能不是正则的。但是，它是什么类？它可能与上下文无关，但 CS 理论从来都不是我最擅长的学科。

递归集和递归函数有什么区别？

我们可以计算正则表达式之间的某种距离吗？

这个想法是要测量两个正则表达式在哪方面是相似的。

请帮我找到语法或自动机来决定以下语言：

a ⁿ b ⁿ c ⁿ其中 n≥1

如果您查看程序的调用堆栈并将每个返回指针视为令牌，那么需要什么样的自动机来为程序的有效状态构建识别器？

作为推论，需要什么样的自动机来为特定的错误状态构建识别器？

（注意：我只查看可以从此函数获得的信息。）

我的想法是，如果这些形成常规语言，那么可以围绕它构建一些有趣的工具。例如，给定一组崩溃/故障转储，自动将它们分组并生成识别器以识别已知错误的新实例。

注意：我并不是建议将其作为诊断工具，而是将其作为数据管理工具，用于将一堆崩溃报告变成更有用的东西。

• “这 54 次崩溃似乎是相关的，这 42 次也是如此。”
• “这些新的崩溃似乎与日期 X 之前的任何事情都无关。”
• 等等

似乎我并不清楚我想要完成什么，所以这里有一个例子：

假设您有一个包含三个错误的程序。

• 导致无效参数被传递给单个函数的两个错误导致相同的健全性检查。
• 一个函数，如果给定一个（有效的）极端情况，就会进入无限递归。

同样，当程序崩溃（断言失败、未捕获的异常、seg-V、堆栈溢出等）时，它会抓取堆栈跟踪，提取其上的调用站点并将它们发送到 QA 报告服务器。（我假设只提取该信息，因为 1，每个项目成本一次很容易获得，2，它具有简单、明确的含义，可以在没有任何关于程序的特殊知识的情况下使用）

我提议的是一个工具，它会尝试将传入的报告分类为与已知错误之一（或作为新错误）相关联。

最简单的事情是假设一个故障站点是一个错误，但在第一个示例中，在同一个位置检测到两个错误。下一个最简单的方法是要求整个堆栈匹配，但同样，这在第二个示例这样的情况下不起作用，其中您有多个（有效）有效代码可以触发相同的错误。

我正在尝试了解 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？

编程语言是正式的编程语言是什么意思？哪些语言是正式的编程语言？哪些是非正式的编程语言？

我还没有找到好的解释。

我正在尝试学习与编程语言相关的 Chomsky Hierarchy 的某些方面，但我仍然需要阅读 Dragon Book。

我读过大多数编程语言都可以解析为上下文无关语法（CFG）。就计算能力而言，它等于下推非确定自动机之一。我对吗？

如果是真的，那么一个 CFG 怎么可能持有图灵完备的无限制语法（UG）？我之所以问是因为，即使 CFG 描述了编程语言，它们实际上也用于描述图灵机，因此通过 UG。

我认为这是因为至少有两个不同级别的计算，第一个是 CFG 的解析，侧重于与语言的结构（表示？）相关的语法，而另一个侧重于语义（意义，解释数据本身？）与图灵完备的编程语言的能力有关。同样，这些假设是否正确？

在乔姆斯基的层次结构中，没有定义递归语言集。我知道递归语言是递归可枚举语言的子集，并且所有递归语言都是可判定的。

我很好奇的是递归语言与上下文相关语言的比较。我可以假设上下文相关语言是递归语言的严格子集，因此所有上下文相关语言都是可判定的吗？