我很难表达Chomsky二型（上下文无关语言）和Chomsky三型（正则语言）之间的区别。
有没有人能用通俗易懂的语言给我解释一下？我很难理解整个语言类型的层次结构。
3个回答
26
类型 II 文法是带有栈的类型 III 文法
基本上，类型 II 文法就是具有嵌套特性的类型 III 文法。
类型 III 文法（正则文法）：
使用场景 - CSV（逗号分隔值）
特点：
- 可以使用有限状态机进行读取
- 不需要中间存储
- 可以使用正则表达式进行读取
- 通常使用一维或二维数据结构表示
- 是平面的，即没有嵌套或递归属性
例如：
this,is,,"an "" example",\r\n
"of, a",type,"III\n",grammar\r\n
只要你能理解以上文本的所有规则和边缘情况，你就能解析CSV。 类型II语法（上下文无关）： 用例 - HTML（超文本标记语言）或一般的SGML
特点：
- 可以使用DPDA（确定性下推自动机）读取
- 需要栈进行中间存储
- 可以表示为AST（抽象语法树）
- 可能包含嵌套和/或递归属性
<h1>Useless Example</h1>
<p>Some stuff written here</p>
<p>Isn't this fun</p>
但是尝试使用有限状态机解析它:
<body>
<div id=titlebar>
<h1>XHTML 1.0</h1>
<h2>W3C's failed attempt to enforce HTML as a context-free language</h2>
</div>
<p>Back when the web was still pretty boring, the W3C attempted to standardize away the quirkiness of HTML by introducing a strict specification</p
<p>Unfortunately, everybody ignored it.</p>
</body>
看到区别了吗？想象一下，如果你在编写解析器，可以在开放标签上开始并在关闭标签处完成，但是当遇到第二个开放标签时，会发生什么情况？
很简单，您将第一个开放标签推入堆栈并开始解析第二个标签。对于存在的许多嵌套级别，请重复此过程，并且如果语法良好，则可以逐层取消堆栈，反向地取消堆栈
由于“纯”无上下文语言的严格性质，它们相对罕见，除非它们由程序生成。 JSON是一个典型例子。
无上下文语言的优点是虽然非常富有表现力，但仍然相对简单易于解析。
但等等，我刚刚说HTML是无上下文的。是的，如果它格式良好（即XHTML）。
虽然XHTML可能被认为是无上下文的，但定义不太严格的HTML实际上被视为类型I（即上下文敏感）。原因是当解析器到达结构不良的代码时，它实际上会根据周围的上下文来决定如何解释代码。例如，如果元素缺少其结束标记，则需要确定该元素在层次结构中的位置，然后才能决定应将关闭标记放在何处。
可以使无上下文语言具有上下文敏感性的其他功能包括模板，导入，预处理器，宏等。
简而言之，上下文敏感语言看起来非常像无上下文语言，但是上下文敏感语言的元素可能根据程序状态以不同的方式进行解释。
免责声明：我没有接受过正式的CompSci培训，因此此答案可能包含错误或假设。如果您问我终端和非终端之间的区别，您将得到一个茫然的眼神。我通过实际构建Type III（Regular）解析器并广泛阅读其他内容来学习这些东西。
- Evan Plaice
3
另一个包含算术表达式的例子。解析包含相同优先级操作的表达式，例如（1 + 1 + 2 - 4），是“正则”的，即第3型。解析包含不同优先级级别操作的表达式，例如（1 + 2 *（4-1）），是第2型。 - KRoy
还可以参考回文不能用正则语法表达的问题：https://dev59.com/R3RB5IYBdhLWcg3wpotm - KRoy
你的回答很好地介绍了类型。谢谢。 - Octane
5
第三类语法由一系列状态组成。它们无法表达嵌套。例如，第三类语法不能要求匹配括号，因为它没有办法显示括号应该“包裹”其内容。这是因为，正如Derek指出的那样，第三类语法不会“记住”通过哪些先前状态来到达当前状态。
第二类语法由一组“产生式”（您可以将它们视为模式）组成，其中可以嵌入其他产生式。因此，它们是递归定义的。一个产生式只能根据它所包含的内容进行定义，并且不能“看到”自身之外的内容；这就是使语法上下文无关的原因。
- Nate C-K
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接