algorithm - 上下文无关语法与上下文相关语法？

Question

有人可以向我解释为什么这种语法[上下文无关语法和上下文相关语法]接受字符串吗？

我所知道的是

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

上下文相关文法是一种形式文法，其中任何产生（重写）规则的左侧和右侧都可能被终结符号和非终结符号的上下文包围。

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

Answer 1

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

上下文无关文法(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 解析器来解析，它在 O(n ³ ) 中可以确定一个长度为 n 的字符串是否包含在文法中（有趣的是，它可以在 O(n ²)，并且通过前瞻可以在 O(n) 时间内解析任何 LR(k) 语法！）。如果您纯粹对“语法 G 生成的语言中包含字符串 x 吗？”这个问题感兴趣，那么其中一种方法会非常好。如果您想知道字符串 x 是如何生成的（通过查找解析树），您可以调整这些方法来提供此信息。然而，解析 CSG 通常是 PSPACE 完备的，因此没有已知的在最坏情况多项式时间内运行的解析算法。不过，有些算法在实践中往往运行得很快。Parsing Techniques: A Practical Guide （见下文）的作者整理了一个很棒的页面，其中包含各种解析算法，包括一种解析上下文相关语言的语言。

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

Answer 2

如前所述，语法不接受字符串，但它只是生成您分析的语言的特定单词的一种方式。事实上，语法作为形式语言理论中的生成规则，而不是有限状态自动机做你所说的，特定字符串的识别。特别是，您需要递归可枚举自动机来识别类型 1 语言（乔姆斯基层次结构中的上下文敏感语言）。特定语言的语法只允许您指定聚集到 CS 语言字符串集的所有字符串的属性。我希望我的解释很清楚。

Answer 3

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