Chomsky 3型和Chomsky 2型语法之间的区别 [英] The difference between Chomsky type 3 and Chomsky type 2 grammar
问题描述
我很难说出Chomsky类型2(无上下文语言)和Chomsky类型3(常规语言)之间的区别.
I'm having trouble articulating the difference between Chomsky type 2 (context free languages) and Chomsky type 3 (Regular languages).
外面有人可以用简单的英语给我答案吗?我无法理解整个层次结构.
Can someone out there give me an answer in plain English? I'm having trouble understanding the whole hierarchy thing.
推荐答案
II型语法是带有堆栈的III型语法
II型语法基本上是带有嵌套的III型语法.
A Type II grammar is basically a Type III grammar with nesting.
III型语法(常规):
用例-CSV(逗号分隔值)
Use Case - CSV (Comma Separated Values)
特征:
- 可以使用FSM(有限状态机)通过读取
- 不需要中间存储空间
- 可以用正则表达式读取
- 通常使用1D或2D数据结构表示
- 是平坦的，表示没有嵌套或递归属性
例如:
this,is,,"an "" example",\r\n
"of, a",type,"III\n",grammar\r\n
只要您能弄清楚上述文本的所有规则和小写字母，就可以解析CSV.
As long as you can figure out all of the rules and edge cases for the above text you can parse CSV.
II型语法(上下文无关):
用例-一般是HTML(超文本标记语言)或SGML
Use Case - HTML (Hyper Text Markup Language) or SGML in general
特征:
- 可以使用DPDA(确定性下推自动机)读取
- 将需要一个堆栈用于中间存储
- 可以表示为AST(抽象语法树)
- 可能包含嵌套和/或递归属性
HTML可以表示为常规语法:
HTML could be expressed as a regular grammar:
<h1>Useless Example</h1>
<p>Some stuff written here</p>
<p>Isn't this fun</p>
但是它尝试使用FSM对此进行解析:
But it's try parsing this using a FSM:
<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>
看到区别了吗?假设您正在编写一个解析器，可以从一个打开标签开始，然后在一个结束标签上完成，但是当您在到达结束标签之前遇到第二个开始标签时会发生什么呢?
See the difference? Imagine you were writing a parser, you could start on an open tag and finish on a closing tag but what happens when you encounter a second opening tag before reaching the closing tag?
很简单，您将第一个开始标签推到堆栈上，然后开始解析第二个标签.对存在的尽可能多的嵌套级别重复此过程，如果语法结构良好，则可以在与构建堆栈相反的级别上一次将堆栈展开一层
It's simple, you push the first opening tag onto a stack and start parsing the second tag. Repeat this process for as many levels of nesting that exist and if the syntax is well-structured, the stack can be un-rolled one layer at a time in the opposite level that it was built
由于纯"上下文无关语言的严格性质，除非它们是由程序生成的，否则它们相对很少见. JSON是一个很好的例子.
Due to the strict nature of 'pure' context-free languages, they're relatively rare unless they're generated by a program. JSON, is a prime example.
无上下文语言的好处是，尽管非常有表现力，但它们解析起来仍然相对简单.
The benefit of context-free languages is that, while very expressive, they're still relatively simple to parse.
但是，等等，我不只是说HTML是上下文无关的.是的，如果格式正确(例如XHTML).
But wait, didn't I just say HTML is context-free. Yep, if it is well-formed (ie XHTML).
尽管XHTML可能被认为是上下文无关的，但松散定义的HTML实际上将被视为类型I(即上下文敏感).原因是，当解析器到达结构不良的代码时，它实际上会根据周围的上下文来决定如何解释代码.例如，如果某个元素缺少其结束标记，则在确定结束标记的放置位置之前，需要确定该元素在层次结构中的位置.
While XHTML may be considered context-free, the looser-defined HTML would actually considered Type I (Ie Context Sensitive). The reason being, when the parser reaches poorly structured code it actually makes decisions about how to interpret the code based on the surrounding context. For example if an element is missing its closing tags, it would need to determine where that element exists in the hierarchy before it can decide where the closing tag should be placed.
可能使无上下文语言对上下文敏感的其他功能包括模板，导入，预处理器，宏等.
Other features that could make a context-free language context-sensitive include, templates, imports, preprocessors, macros, etc.
简而言之，上下文相关的语言看起来很像上下文无关的语言，但是上下文敏感的语言的元素可能会根据程序状态以不同的方式进行解释.
In short, context-sensitive languages look a lot like context-free languages but the elements of a context-sensitive languages may be interpreted in different ways depending on the program state.
免责声明:我没有接受CompSci的正式培训，因此此答案可能包含错误或假设.如果您问我终端机和非终端机之间的区别，您将无所适从.通过实际构建Type III(常规)解析器并广泛阅读其余内容，我学到了很多.
这篇关于Chomsky 3型和Chomsky 2型语法之间的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
