自由语法与上下文的关系
有人可以向我解释为什么这种类型的语法[上下文无关语法和上下文敏感语法]接受字符串？
我知道的是
上下文无关文法是一种形式语法，其中每个生产（重写）规则是V→w的形式，其中V是单个非终结符号，w是终端和/或非终端的串。 w可以是空的
语境敏感语法是一种形式语法，其中任何生产（重写）规则的左侧和右侧可以被终端和非终端符号的上下文包围。
但我怎么能解释为什么这些语法接受一个字符串？
这里的一个重要细节是，语法不接受字符串; 他们生成字符串。 文法是语言的描述，提供了生成语言中包含的所有可能字符串的方法。 为了判断一个特定的字符串是否包含在这个语言中，你可以使用一个识别器，某种自动机来处理给定的字符串，并说“是”或“否”。
上下文无关语法（CFG）是一种语法，其中（如您所记下的）每个产品具有形式A→w，其中A是非终结符，w是终端和非终结符的字符串。 非正式地说，CFG是一种语法，任何非终结者都可以在任何时候扩展到任何一个作品。 语法的语言是可以从开始符号导出的一组终端字符串。
上下文敏感语法（CSG）是一种语法，其中每个产品的形式为wAx→wyx，其中w和x是终端和非终端的字符串，y也是终端的字符串。 换句话说，制作给出的规则是“如果你在给定的上下文中看到A，你可以用字符串y代替A.” 不幸的是，这些语法被称为“上下文敏感语法”，因为它意味着“上下文无关”和“上下文敏感”不是相反的，并且这意味着有某些语法类可以采用很多上下文信息，但没有正式被认为是上下文敏感的。
要确定字符串是包含在CFG还是CSG中，有许多方法。 首先，你可以为给定的语法构建一个识别器。 对于CFG，下推自动机（PDA）是一种自动机，它可以精确地接受上下文无关的语言，并且可以将任何CFG转换为PDA。 对于上下文相关的语法，您要使用的自动机称为线性有界自动机（LBA）。
然而，如果对这些方法进行天真的处理，这些方法效率不高。 为了确定字符串是否包含在CFG的语言中，有更高效的算法。 例如，许多语法可以为它们构建LL（k）或LR（k）语法分析器，这允许您（以线性时间）决定语法中是否包含字符串。 所有语法都可以使用Earley分析器进行分析，Earley分析器可以在O（n3）中确定语法中是否包含长度为n的字符串（有趣的是，它可以解析O（n2）中任何明确的CFG，并且可以使用lookahead解析任何在O（n）时间LR（k）语法！）。 如果你完全对“语法G所产生的语言中包含的字符串x”这个问题感兴趣，那么其中一种方法就非常出色。 如果您想知道如何生成字符串x（通过查找分析树），您可以调整这些方法以提供此信息。 然而，一般来说，解析CSGs是PSPACE完整的，所以没有已知的解析算法在最坏情况下运行多项式时间。 但是，有些算法在实践中倾向于快速运行。 “分析技术：实用指南”（见下文）的作者汇集了一个精彩的页面，其中包含各种解析算法，其中包括解析上下文相关语言的解析算法。
如果您有兴趣了解更多关于解析的内容，请考虑查看Grune和Jacobs撰写的优秀着作“解析技巧：实用指南，第二版”，该书讨论了用于确定字符串是否包含在语法中的各种解析算法如果是的话，它是如何由解析算法生成的。
希望这可以帮助！
如前所述，语法不接受字符串，但它只是生成您所分析语言的特定单词的一种方式。 事实上，作为形式语言理论中的生成规则的语法，而不是有限状态自动机做你正在说的，特定字符串的识别。 特别是，您需要递归枚举自动机来识别类型1语言（Chomsky层次结构中的上下文相关语言）。 只有特定语言的语法才会授予您指定收集到CS语言字符串集合的所有字符串的属性。 我希望我的解释清楚。
显示语法接受字符串的一种简单方法是显示该字符串的生产规则。
链接地址: http://www.djcxy.com/p/74863.html