use*_*413 39 algorithm grammar parsing context-free-grammar context-sensitive-grammar
有人可以向我解释为什么这种语法[无上下文语法和上下文敏感语法]接受一个字符串？
我所知道的是
无上下文语法是一种形式语法,其中每个生成(重写)规则是V→w的形式,其中V是单个非终结符号,w是一串终端和/或非终端.w可以是空的
上下文敏感语法是一种形式语法,其中任何生成(重写)规则的左侧和右侧可以被终端和非终结符号的上下文包围.
但是,我怎么能解释为什么这些语法接受一个字符串？
tem*_*def 111
这里一个重要的细节是语法不接受字符串; 他们生成字符串.语法是对语言的描述,它提供了生成语言中包含的所有可能字符串的方法.为了判断语言中是否包含特定字符串,您将使用识别器,某种自动机处理给定字符串并说"是"或"否".
无上下文语法(CFG)是一种语法,其中(如您所述)每个产品的形式为A→w,其中A是非终结符,w是一串终端和非终结符.非正式地说,CFG是一种语法,任何非终结者都可以在任何时候扩展到任何一个作品.语法的语言是可以从起始符号导出的终端串的集合.
甲上下文敏感语法(CSG)是一种语法,其中每个生产具有形式蜡→WYX,其中w和x是终端和非终结符和y的字符串也端子的字符串.换句话说,制作规则说"如果你在给定的上下文中看到A ,你可以用字符串y替换A." 令人遗憾的是,这些语法被称为"上下文敏感的语法",因为它意味着"无上下文"和"上下文敏感"并不是对立的,这意味着某些类别的语法可以说需要大量的语境考虑到信息但未正式认为是上下文敏感的.
要确定字符串是否包含在CFG或CSG中,有许多方法.首先,您可以为给定的语法构建识别器.对于CFG,下推式自动机(PDA)是一种自动机,可以精确接受无上下文语言,并且有一种简单的结构可以将任何CFG转换为PDA.对于上下文相关语法,您将使用的自动机称为线性有界自动机(LBA).
然而,如果天真地对待这些上述方法,则效率不高.要确定字符串是否包含在CFG的语言中,有更高效的算法.例如,许多语法可以为它们构建LL(k)或LR(k)解析器,这允许您(在线性时间内)判断语法中是否包含字符串.可以使用Earley解析器解析所有语法,在O(n 3)中可以确定语法中是否包含长度为n的字符串(有趣的是,它可以解析O(n 2)中任何明确的CFG ,并且具有前瞻性可以在O(n)时间内解析任何LR(k)语法!).如果你纯粹对"语法G生成的语言中是否包含字符串x？"这一问题感兴趣,那么其中一种方法就会非常出色.如果您想知道如何生成字符串x(通过查找解析树),您可以调整这些方法以提供此信息.但是,解析CSG通常是PSPACE-complete,因此在最坏情况下的多项式时间内没有已知的解析算法.但是,有些算法在实践中往往会快速运行." 解析技术:实用指南"(见下文)的作者汇总了一个包含各种解析算法的精彩页面,其中包括解析上下文相关语言的算法.
如果您有兴趣了解有关解析的更多信息,请考虑查看Grune和Jacobs 的优秀书籍" Parsing Techniques:A Practical Guide,Second Edition ",该书讨论了用于确定字符串是否包含在语法中的各种解析算法如果是这样,解析算法如何生成它.
希望这可以帮助!