问题标签 [chomsky-hierarchy]

我想解析一种编程语言。我阅读了很多关于形式语言、乔姆斯基层次结构和 ANTLR 的内容。但是我找不到有关如何将 ANTLR v3 语言作为 LL(*) 递归下降解析器接受到 chomsky 层次结构的信息。

Chomsky 类型如何与 LL(*) 混合？非常感谢任何信息（在线、书籍、论文）。

编辑：ANTLR 的句法/语义谓词和回溯如何映射到这个？

我目前正在学习离散数学测试，我们正在学习乔姆斯基的层次结构和识别层次结构每个级别的自动机类型。我被告知大多数计算机语言都属于层次结构的“第 2 级和第 1 级”，但不准确。

我的问题是：

1. 每个级别都有哪些功能？

2. 这仅仅是理论基础吗？我想知道像 Dennis Ritchie 和 James Gosling 这样的语言设计师在设计 C 和 Java 时是否必须考虑到这一点。他们有吗？有人会如何应用这个？

3. 我们被告知图灵机可以识别层次结构的第 0 级。如果有，是否有属于 0 级的语言特征？我猜这可能是自然语言处理，是吗？

标准是否指定了官方的 C++ 语法？

我搜索了，但没有在任何地方找到它。

另外，我希望详细了解 C++ 语法，例如它属于哪种语法类别等。任何指向正确方向的链接都会有所帮助。

按类别，我的意思是

取自这里。

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

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

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

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

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

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

阅读Chomsky 层次结构……我知道 regexp 无法解析 type-2 语法（无上下文语法），也无法解析 type-1 和 type-0。正则表达式可以解析/捕获所有类型 3 语法（正则语法）吗？

我必须编写一个函数来检查输入字符串对于给定的语言规范是否有效。我认为这将是一个标准的 CFG -> Chomsky Normal Form，然后是 CYK 解析，但是语言中的一条规则是防止这种情况发生。

有些规则很简单，如果我们定义了 terminal {a,b,c,d,e,f,P,Q,R,S}，那么有效的字符串就是

1) 任何孤立的小写终端
2) 如果 'x' 是一个有效的字符串，那么 Sx 也是

但是第三条规则是

3) 如果 X 和 Y 是有效的输入字符串，那么 PXY、QXY、RXY 也是

其中{P,Q,R}是剩余的大写终结符，X 和 Y 是非终结符。

这个的生产规则是什么样的？我以为会是这样的

但这有两个问题。首先，这不是 CFG 规则——这是否意味着该语言定义了 CSG？

第二个是这行不通，因为

XY -> PXY -> PPXY

在所有情况下都不是有效的消息。

我试图理解四种不同的乔姆斯基语言类型，但我发现的定义对我来说没有任何意义。我知道类型 0 是自由语法，类型 1 是上下文相关的，类型 2 是上下文无关的，而类型 3 是常规的。所以，有人可以解释一下，并把它放在上下文中，谢谢。

我很难阐明 Chomsky 类型 2（上下文无关语言）和 Chomsky 类型 3（常规语言）之间的区别。

有人可以用简单的英语给我答案吗？我无法理解整个层次结构。

在形式语言的乔姆斯基分类中，我需要一些Non-Linear, Unambiguous and also Non-Deterministic上下文无关语言（N-CFL）的例子吗？

1. 线性语言：线性语法是可能的（⊆ CFG），例如
   L ₁ = {a ⁿ b ⁿ | n≥0}

2. 确定性上下文无关语言（D-CFG）：确定性下推自动机（D-PDA）是可能的，例如
   L ₂ = {a ⁿ b ⁿ c ^m | n ≥ 0, m ≥ 0 }
   L ₂是明确的。

非线性的 CF 文法是非线性的。
L _nl = {w: n _a (w) = n _b (w)} 也是非线性 CFG。

-- 3. Non-Deterministic Context Free Language(N-CFG) :only Non-Deterministic Push-Down-Automata(N-PDA)可能的例如
L ₃ = {ww ^R | w ∈ {a, b} ^* }
L ₃也是线性CFG。

--4。模棱两可的 CFL : only ambiguous CFG is possible
L ₄ = {a ⁿ b ⁿ c ^m |的 CFL n ≥ 0, m ≥ 0 } U {a ⁿ b ^m c ^m | n ≥ 0, m ≥ 0 }
L ₄既是非线性又是模糊 CFG 和每个模糊 CFL \subseteq N-CFL。

我的问题是：
是否所有非线性、非确定性 CFL 都是模棱两可的？如果不是，那么我需要一个非线性、非确定性 CFL 且明确的示例？

给定下面的维恩图：

也在这里问