上下文无关语法与上下文敏感语法？

Question

有人可以向我解释为什么这种类型的语法[context-free grammar和context-sensitive grammar]接受一个String？

我知道什么是

上下文无关文法是一个正式的语法在每一个生产（重写）规则为V→W^ 的形式，其中V是一个非终结符和w是一个字符串终端和/或非终端。 W可以是空

上下文敏感的语法是正规的语法，其中左手侧和任何生产（重写）规则可以由终端和终结符的背景下所包围的右手侧。

但我怎么能解释为什么这些语法接受一个字符串？

Answer 1

显示语法接受字符串的一种简单方法是显示该字符串的生产规则。

Answer 2

这里的一个重要细节是，语法不要接受字符串;他们生成字符串。文法是语言的描述，提供了生成语言中包含的所有可能字符串的方法。为了判断语言中是否包含特定的字符串，可以使用识别器，某种自动机处理给定的字符串，并说“是”或“否”。

A context-free grammar（CFG）是一种语法，其中（如您所述）每个产品的格式为A → w，其中A是非终结符，w是终端和非终结符的字符串。非正式地说，CFG是一种语法，任何非终结者都可以在任何时候扩展到任何生产。语法的语言是可以从开始符号导出的一组终端字符串。

A context-sensitive grammar（CSG）是一种语法，其中每个产品的形式为wAx → wyx，其中w和x是终端和非终端的字符串，y也是终端的字符串。换句话说，这些作品给出的规则是“如果你在给定的上下文看到A ，你可以用字符串y代替A.”不幸的是，这些语法被称为“上下文敏感语法”，因为它意味着“上下文无关”和“上下文敏感”不是相反的，并且这意味着有某些类型的语法可以采用很多上下文信息，但没有正式被认为是上下文敏感的。

要确定字符串是否包含在CFG或CSG中，有许多方法。首先，你可以为给定的语法构建一个识别器。对于CFG，pushdown automaton（PDA）是一种精确接受上下文无关语言的自动机类型，并且将任何CFG转换为PDA都有一个简单的构造。对于上下文敏感的语法，您要使用的自动机被称为（LBA）。

但是，如果天真地对待这些方法，这些方法效率不高。为了确定字符串是否包含在CFG的语言中，有更高效的算法。例如，许多语法可以为它们构建LL(k)或LR(k)解析器，这允许您（线性时间）决定语法中是否包含字符串。所有语法都可以使用Earley parser进行分析，在O中可以确定语法中是否包含长度为n的字符串（有趣的是，它可以解析O中任何明确的CFG，并且使用lookaheads可以解析O（n）时间内的任何LR（k）语法！）。如果你完全对“语法G所产生的语言中包含的字符串x”这个问题感兴趣，那么其中一种方法就非常出色。如果您想知道字符串x是如何生成的（通过查找），您可以调整这些方法以提供此信息。然而，一般来说，解析CSGs是PSPACE完整的，所以没有已知的解析算法在最坏情况下运行多项式时间。但是，有些算法在实践中倾向于快速运行。作者解析技巧：实用指南（见下文）已放在一起a fantastic page containing all sorts of parsing algorithms，其中包括解析上下文敏感语言。

如果您有兴趣了解更多关于解析的知识，可以考虑查看Grune和Jacobs撰写的优秀书籍“Parsing Techniques: A Practical Guide, Second Edition”，其中讨论了用于确定字符串是否包含在语法中的各种解析算法，如果是这样，它是如何由解析算法生成的。

希望这会有所帮助！

Answer 3

如前所述，语法不接受字符串，但它只是一种方法，用于生成您分析的语言的特定单词。事实上，作为形式语言理论中的生成规则的语法，而不是有限状态自动机做你正在说的，特定字符串的识别。 特别是，您需要递归枚举自动机来识别类型1语言（Chomsky层次中的上下文相关语言）。 只有特定语言的语法才会授予您指定收集到CS语言字符串集合的所有字符串的属性。 我希望我的解释清楚。