context-sensitive grammar（CSG）是一种语法，其中每个产品的形式为wAx→wyx，其中w和x是终端和非终端的字符串，y也是一串终端 . 换句话说，制作给出的规则是“如果你在给定的上下文中看到A，你可以用字符串y替换A..440964_ context-sensitive grammars " because it means that " context-free " and " context-sensitive”不是对立的，它意味着某些类别的语法可以考虑大量的上下文信息，但没有被正式认为是上下文敏感的 .
3 回答
这里一个重要的细节是语法不接受字符串;他们生成字符串 . 语法是对语言的描述，它提供了生成语言中包含的所有可能字符串的方法 . 为了判断语言中是否包含特定字符串，您将使用识别器，某种处理给定字符串的自动机，并说"yes"或"no."
context-free grammar（CFG）是一种语法，其中（如您所述）每个产品的形式为A→W，其中A是非终结符，w是一串终端和非终结符 . 非正式地说，CFG是一种语法，任何非终结者都可以在任何时候扩展到任何一个作品 . 语法的语言是可以从起始符号导出的终端串的集合 .
context-sensitive grammar（CSG）是一种语法，其中每个产品的形式为wAx→wyx，其中w和x是终端和非终端的字符串，y也是一串终端 . 换句话说，制作给出的规则是“如果你在给定的上下文中看到A，你可以用字符串y替换A..440964_ context-sensitive grammars " because it means that " context-free " and " context-sensitive”不是对立的，它意味着某些类别的语法可以考虑大量的上下文信息，但没有被正式认为是上下文敏感的 .
要确定字符串是否包含在CFG或CSG中，有许多方法 . 首先，您可以为给定的语法构建识别器 . 对于CFG，pushdown automaton（PDA）是一种自动机，可以精确接受无上下文语言，并且有一种简单的结构可以将任何CFG转换为PDA . 对于上下文相关语法，您将使用的自动机称为linear bounded automaton（LBA） .
然而，如果天真地对待这些上述方法，则效率不高 . 要确定字符串是否包含在CFG的语言中，有更高效的算法 . 例如，许多语法可以为它们构建LL(k)或LR(k)解析器，这允许您（在线性时间内）判断语法中是否包含字符串 . 所有语法都可以使用Earley parser进行解析，在O（n3）中可以确定语法中是否包含长度为n的字符串（有趣的是，它可以解析O（n2）中任何明确的CFG，并且前瞻可以解析任何LR （k）O（n）时间内的语法！） . 如果你纯粹对"is string x contained in the language generated by grammar G?"这个问题感兴趣，那么其中一种方法就会非常出色 . 如果您想知道如何生成字符串x（通过查找parse tree），您可以调整这些方法以提供此信息 . 但是，解析CSG通常是PSPACE-complete，因此没有已知的解析算法可以在最坏情况下的多项式时间运行 . 但是，有些算法在实践中往往会快速运行 . 解析技术：实用指南（见下文）的作者将a fantastic page containing all sorts of parsing algorithms放在一起，包括解析上下文敏感语言的作者 .
如果您有兴趣了解有关解析的更多信息，请考虑查看Grune和Jacobs的优秀书籍“Parsing Techniques: A Practical Guide, Second Edition”，该书讨论了用于确定字符串是否包含在语法中的各种解析算法，如果是，它是如何包含的由解析算法生成 .
希望这可以帮助！
显示语法接受字符串的一种简单方法是显示该字符串的生成规则 .
如前所述，语法不接受字符串，但它只是一种方式，以生成您分析的语言的特定单词 . 实际上，语法作为形式语言理论中的生成规则，而不是有限状态自动机，你所说的就是对特定字符串的识别 . 特别是，您需要递归可枚举自动机才能识别Type 1 Languages（Chomsky层次结构中的上下文敏感语言） . 特定语言的语法仅授予您指定收集到CS语言字符串集的所有字符串的属性 . 我希望我的解释清楚 .