无上下文语法与上下文有关语法的区别？

Question

无上下文语法与上下文有关语法的区别？

algorithmparsinggrammarcontext-free-grammarcontext-sensitive-grammar

49

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

我所知道的是： 上下文无关文法是一种形式文法，在该文法中，每个产生式（重写）规则都是V→w的形式，其中V是单个非终结符号，w是终结符和/或非终结符的字符串。 w可以为空。 上下文相关文法是一种形式文法，在该文法中，任何产生式（重写）规则的左部和右部都可以被终端和非终端符号的上下文包围。

但是我该如何解释为什么这些语法可以接受一个字符串呢？

- user1004413

3个回答

1

正如之前所说，语法不接受字符串，而只是一种生成分析语言特定单词的方式。实际上，在形式语言理论中，语法作为生成规则，而有限状态自动机则执行你所说的特定字符串的识别。特别地，你需要递归可枚举自动机来识别类型1语言（乔姆斯基层次结构中的上下文有关语言）。对于特定语言的语法仅允许你指定所有字符串属性，这些字符串集合到CS语言的字符串集合中。希望我的解释清楚明白。

- Alessandro S

0

一种简单的方法展示一个文法接受一个字符串是通过展示该字符串的产生规则。

- Rob Neuhaus

在维基语法的例子中，那个例子是我应该写的来展示语法接受一个字符串吗？但我想知道如何将其与无上下文和有上下文相关联。 - user1004413

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

一个重要的细节是，语法不“接受”字符串；它们生成字符串。语法是语言的描述，提供一种生成语言中包含的所有可能字符串的方法。为了确定特定字符串是否包含在语言中，您将使用识别器，一种处理给定字符串并回答“是”或“否”的自动机。上下文无关文法（CFG）是一种语法，其中（如您所指出的）每个产生式的形式为A→w，其中A是非终端符号，w是终端符号和非终端符号的字符串。非正式地说，CFG是一种语法，其中任何非终端符号都可以在任何时候扩展到其任何产生式之一。语法的语言是可以从起始符号派生的终端符号字符串集合。上下文敏感文法（CSG）是一种语法，其中每个产生式的形式为wAx→wyx，其中w和x是终端符号和非终端符号的字符串，y也是终端符号的字符串。换句话说，这些产生式提供了规则，即“如果您在给定上下文中看到A，则可以将A替换为字符串y。”不幸的是，这些语法被称为“上下文敏感语法”，因为它意味着“上下文无关”和“上下文敏感”不是相反的，这意味着有某些类别的语法，它们可能考虑了大量的上下文信息，但在形式上并不被认为是上下文敏感的。

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

然而，如果天真地处理这些方法，它们并不是非常有效。为了确定一个字符串是否包含在CFG的语言中，有更有效的算法。例如，许多语法可以为它们构建LL(k)或LR(k)解析器，这使您能够（在线性时间内）决定一个字符串是否包含在语法中。所有语法都可以使用Earley解析器进行解析，该解析器可以在O（n³）中确定长度为n的字符串是否包含在语法中（有趣的是，它可以在O（n²）中解析任何不含歧义的CFG，并且具有前瞻性，可以在O（n）时间内解析任何LR（k）语法！）。如果您只对问题“字符串x是否包含在由语法G生成的语言中”感兴趣，则其中一种方法将非常出色。如果您想知道如何生成字符串x（通过查找解析树），则可以将这些方法调整为提供此信息。然而，解析CSG通常是PSPACE完全的，因此没有已知的解析算法可以在最坏情况下多项式时间内运行。虽然有一些实际上往往运行得很快的算法。《解析技术：实用指南》（见下文）的作者已经组织了一个包含各种解析算法的奇妙页面，其中包括解析上下文敏感语言的算法。

如果你对解析有兴趣，可以考虑阅读 Grune 和 Jacobs 的优秀书籍 "Parsing Techniques: A Practical Guide, Second Edition"。该书讨论了各种解析算法，用于确定字符串是否包含在语法中，并确定它是如何由解析算法生成的。