我很难表达Chomsky二型(上下文无关语言)和Chomsky三型(正则语言)之间的区别。
有没有人能用通俗易懂的语言给我解释一下?我很难理解整个语言类型的层次结构。
我很难表达Chomsky二型(上下文无关语言)和Chomsky三型(正则语言)之间的区别。
有没有人能用通俗易懂的语言给我解释一下?我很难理解整个语言类型的层次结构。
类型 II 文法是带有栈的类型 III 文法
基本上,类型 II 文法就是具有嵌套特性的类型 III 文法。
类型 III 文法(正则文法):
使用场景 - CSV(逗号分隔值)
特点:
例如:
this,is,,"an "" example",\r\n
"of, a",type,"III\n",grammar\r\n
<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>
第三类语法由一系列状态组成。它们无法表达嵌套。例如,第三类语法不能要求匹配括号,因为它没有办法显示括号应该“包裹”其内容。这是因为,正如Derek指出的那样,第三类语法不会“记住”通过哪些先前状态来到达当前状态。
第二类语法由一组“产生式”(您可以将它们视为模式)组成,其中可以嵌入其他产生式。因此,它们是递归定义的。一个产生式只能根据它所包含的内容进行定义,并且不能“看到”自身之外的内容;这就是使语法上下文无关的原因。