use*_*621 46 html sgml grammar language-theory
我不是在谈论类似XHTML的代码.我正在谈论像这个疯狂的标记,这是完全有效的HTML(!)
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
<html<head>
<title//
<p ltr<span id=p></span</p>
</>
因此,鉴于SGML注入的巨大复杂性,HTML是一种无上下文的语言吗？这是一种正式的语言吗？用语法？
HTML5怎么样？
我是正式语言概念的新手,所以请耐心等待.是的,我已阅读维基百科的文章;)
Apa*_*ala 55
Context Free是语言理论中的一个概念,它在解析器实现中具有重要意义.甲上下文无关语言可以由描述上下文无关文法,它是一个在其中所有的规则具有在箭头的左侧的单个非结束符:
X??
这个简单的限制允许X由左边出现的规则的右侧替代,而不考虑之前或之后的内容.例如,如果在派生或解析一个到达时:
?X?
一个是肯定的
???
也有效.非上下文规则的示例如下:
XY??
Xa??
aX??
那些将需要知道什么可以得出arround X来确定规则是否适用,并且导致非确定性(周围的东西X也想知道它导出的是什么),这在解析中是禁止的,并且在任何情况下我们希望语言定义明确.
证明语言无上下文的唯一方法是证明它有一个无上下文的语法,这不是一件容易的事.CFG已经描述了大多数编程语言,因此完成了工作.但是还有其他语言,包括使用逻辑或简单英语描述的编程语言,因此需要工作来查找它们是否是无上下文的.
对于HTML,关于其上下文自由的答案是肯定的.SGML是一个定义良好的上下文无关语言,在其上定义的HTML也是一个CFL.Web上有两种语言的解析器和语法.无论如何,这存在LL(k)的语法进行有效的 HTML足以证明,语言是上下文无关,因为LL是CF的一个子集,证明
但HTML在Web生活中的演变方式迫使浏览器将其视为未定义的.现代Web浏览器将竭尽全力尝试从他们发现的几乎任何东西中渲染出合理的东西.他们使用的语法不是CFG,解析器远比SGML/HTML所需的语法复杂.
HTML在几个级别定义.
<tags>定义分层文档结构的开始和结束组成.您可以出于任何目的使用XML或类似XML的东西,就像Apache Ant构建脚本一样.语法部分定义得足够好,可以验证.语义部分比语法部分大得多,并且根据关于HTTP的浏览器动作和文档对象模型(DOM)以及如何将模型呈现到屏幕来定义.
到底:
hsi*_*nen 13
有效的HTML不是无上下文的语言.
首先,作为SGML应用程序的HTML对于所有实际用途都是虚构的,因此分析SGML来回答这个问题是没有用的.(但是,SGML小说可能也不是没有上下文的.)
查看实际定义的HTML解析算法更有用.它适用于两个级别:标记化和树构建.在讨论解析器时,HTML调用标记化是比通常称为标记化的更高级别的操作.对于HTML,标记化将字符流拆分为单元,如开始标记,结束标记,注释和文本.标记化器扩展了字符引用.通常,在谈论解析器时,您可能会将诸如小于号之类的东西视为"令牌",并将字符引用视为由令牌组成,而不是由令牌化程序解析.
如果考虑将输入流拆分为标记的过程,则HTML语言的该级别是常规的(树构建器的反馈除外).
但是,有三个复杂情况:第一个是将输入流拆分为令牌只是第一个,然后是树构建器的一方实际上关心令牌中的标识符.第二个是树构建器反馈到tokenizer,以便tokenizer进行的某些状态转换取决于树构建器的状态!第三个是语言中的有效文档由适用于树构建器阶段输出的规则定义,并且这些规则足够复杂,无法使用树自动机完全定义(由RELAX NG表示不具有表现力)足以描述所有有效性约束).
这不是一个实际的证据,但你可以通过从并发症#2和#3开展真正的证明.
请注意,无效文档的情况并不是特别有趣,因为这个语言是否是无上下文的问题,因为存在无上下文语法,该语法生成所有可能的字符串而不考虑具有某些可理解解释的解析树就HTML解析器生成的树而言.HTML解析器将成功使用所有可能的字符串,因此从这个意义上说,所有可能的字符串都是"无效的HTML"语言.
编辑:有趣的问题留给读者练习:
HTML是否没有解析错误但是忽略了无上下文语言的有效性？
HTML是否没有解析错误并忽略了一般有效性,但只有有效的元素名称才允许使用无上下文的语言？
(并发症#2适用于两种情况.)
Bra*_*don 10
请参阅下方编辑
这取决于.
如果你在谈论仅由理论HTML组成的子集,那么是的.
如果你还包括现实生活,工作HTML,每天数百万人在互联网上的许多顶级网站上成功访问和使用,那么NO.
这就是HTML的灵活性.解析引擎添加标签,关闭标签,并处理理论CFG无法做到的事情.如果您使用自动机,您可能还记得正式语法中的生产规则在lhs(左侧)上不能为空(也就是epsilon/lambda).由于解析引擎基本上使用的是正式语法和自动机不能拥有的知识,因此不受此限制,并且"语法"将epsilon/lambda -> result根据语法中不可用的信息选择特定的epsilon/lambda规则. .
由于我认为任何正式语法都不允许空lhs,因此HTML不能通过正式语法定义,也不是正式语言.
当然,HTML5可能会试图转向 "更正式"的语言描述,但它在现实中成为无上下文语言的可能性(即与语法不匹配的字符串被拒绝)是关于XHTML 2.0风靡世界的可能性.完全取代HTML(XHTML是他们使HTML成为正式语言的尝试......由于其脆弱性而被大量拒绝).
值得注意的是,HTML 5是在实施之前要定义的第一个HTML标准!这是正确的,HTML 1-4包含一个人在浏览器中实现的随机想法,并且基于哪些功能被普遍使用和广泛实现,被收集到标准中.然后他们尝试了XHTML,完全没有被采用.甚至网络上的"xhtml"也会在几乎所有情况下自动解析为HTML,以防止错误的语法错误.现在你可以看到我们如何到达这里以及为什么它不可能很快被正式化.
课程:"从理论上讲,理论与实践之间没有区别.在实践中,有." - Yogi Berra
编辑:
实际上,在阅读完文档之后,即使根据HTML 4.01规范,HTML也实际上并不符合SGML.要查看自己,请在http://www.w3.org/TR/html4/strict.dtd上查看HTML 4.01严格文档类型定义(doctype),并注意以下几行:
HTML 4.01规范包含无法在DTD中表达的其他语法约束.
所以我会说,由于这些功能,它可能不是CFL(虽然从技术上讲它并不反驳有一些可能的PDA接受HTML 4.01的假设,但它确实阻止了SGML是CFL的论点,因此HTML是一个CFL).
HTML5触发器,放弃了对SGML的任何隐含的一致性,但可能是由CFG描述的.然而,它仍将提供不基于cfg的尽力解析,因此IMO当前的情况(即正式定义语言规范,无效字符串仍然被接受,解析并以尽力而为的方式呈现)在这方面不太可能长时间,长时间地彻底改变.
HTML5 与以前的 HTML 版本不同，它严格定义了不完全正确的代码的解析行为。HTML5 之前的解析器各不相同，每个解析器都尽力“猜测”代码作者的意图。
| 归档时间： |
|
| 查看次数： |
13642 次 |
| 最近记录： |