上下文无关文法与上下文相关的语法？ [英] Context-free grammars versus context-sensitive grammars?

问题描述

有人能向我解释为什么语法这种[上下文无关文法和上下文敏感的语法]接受一个字符串？

Can someone explain to me why grammars [context-free grammar and context-sensitive grammar] of this kind accepts a String?

我所知道的是

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

Context-free grammar is a formal grammar in which every production(rewrite) rule is a form of V→w Where V is a single nonterminal symbol and w is a string of terminals and/or non-terminals. w can be empty

上下文相关的语法是一个正式的语法在两侧面和任何生产的右手边（重写）规则可以由终端和非终结符的情况下所包围。

Context-sensitive grammar is a formal grammar in which left-hand sides and right hand sides of any production (rewrite) rules may be surrounded by a context of terminal and nonterminal symbols.

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

But how can i explain why these grammar accepts a String?

推荐答案

在这里，一个重要的细节是语法不的接受的字符串;他们的生成的字符串。语法是语言提供用于生成包含在语言的所有可能的字符串的方法描述。为了告诉我们，如果一个特定的字符串包含在语言中，您将使用的识别的，自动机的某种用于处理特定字符串，并说是或否。

An important detail here is that grammars do not accept strings; they generate strings. Grammars are descriptions of languages that provide a means for generating all possible strings contained in the language. In order to tell if a particular string is contained in the language, you would use a recognizer, some sort of automaton that processes a given string and says "yes" or "no."

一个上下文无关文法（CFG）是一个语法的地方（如你所述）每个生产具有形成A＆RARR; w，其中A是一个非终结w是终端和非终结符的字符串。通俗地说，一个CFG是一个语法，其中非终端可以扩展出其任何作品在任何点。一个语法的语言是终端集可以从开始符号来导出串

A context-free grammar (CFG) is a grammar where (as you noted) each production has the form A → w, where A is a nonterminal and w is a string of terminals and nonterminals. Informally, a CFG is a grammar where any nonterminal can be expanded out to any of its productions at any point. The language of a grammar is the set of strings of terminals that can be derived from the start symbol.

一个上下文的相关的语法（CSG）是一个语法，每个生产有形式的蜡和RARR; WYX，其中w和x是终端和终结符号和y弦也是端子的字符串。换句话说，该作品给规则说：如果你看到一个的在特定情况下的，可以更换有由字符串年。

A context-sensitive grammar (CSG) is a grammar where each production has the form wAx → wyx, where w and x are strings of terminals and nonterminals and y is also a string of terminals. In other words, the productions give rules saying "if you see A in a given context, you may replace A by the string y."

要确定一个字符串是否包含在CFG或CSG，有许多方法。首先，你可以建立一个识别器对于给定的语法。为CFGS，所述的 下推自动的的（PDA）是一种类型的自动机接受precisely上下文无关语言，并有一个简单的结构用于使任何CFG成的PDA。对于上下文相关的语法，你可以使用自动机被称为的 线性有界自动机 的（ LBA）。

To determine whether a string is contained in a CFG or a CSG, there are many approaches. First, you could build a recognizer for the given grammar. For CFGs, the pushdown automaton (PDA) is a type of automaton that accepts precisely the context-free languages, and there is a simple construction for turning any CFG into a PDA. For the context-sensitive grammars, the automaton you would use is called a linear bounded automaton (LBA).

然而，这些上述方法中，如果处理过的天真地，不是很有效。要确定的字符串是否被包含在CFG的语言，有更高效的算法。例如，许多语法可以具有 LL（k）的或 LR（K）专为他们分析器，它允许你（线性时间）决定一个字符串是否包含在语法。所有语法可以使用​​欧莱分析器，这为O（n ³ ）可以确定解析长度为n的字符串是否包含在语法（有趣​​的是，它可以分析任何明确的CFG在为O（n ² ），并用向前看符号可以解析任何LR（k）文法的O（N）时间！）。如果你在这个问题纯属兴趣是字符串x包含在文法G产生的语言？，那么这些方法之一将是极好的。如果你想知道的字符串x是如何产生的（通过发现的 解析树 的），可以适应这些方法也提供这些信息。同样，对于航母打击大队，有一些（合理的）效率分析算法在那里，但我不熟悉任何人提供太多细节。但是，的解析技术作者：实用指南的（见下文），已经把含有一个梦幻般的页面各种分析算法中，其中包括一个分析上下文敏感的语言。

However, these above approaches, if treated naively, are not very efficient. To determine whether a string is contained in the language of a CFG, there are far more efficient algorithms. For example, many grammars can have LL(k) or LR(k) parsers built for them, which allows you to (in linear time) decide whether a string is contained in the grammar. All grammars can be parsed using the Earley parser, which in O(n³) can determine whether a string of length n is contained in the grammar (interestingly, it can parse any unambiguous CFG in O(n²), and with lookaheads can parse any LR(k) grammar in O(n) time!). If you were purely interested in the question "is string x contained in the language generated by grammar G?", then one of these approaches would be excellent. If you wanted to know how the string x was generated (by finding a parse tree), you can adapt these approaches to also provide this information. Similarly, for CSGs, there are some (reasonably) efficient parsing algorithms out there, but I'm not familiar with any of them to provide much detail. However, the authors of Parsing Techniques: A Practical Guide (see below) have put together a fantastic page containing all sorts of parsing algorithms, including one that parses context-sensitive languages.

如果您有兴趣了解更多关于解析，可以考虑一下优秀图书解析技术：实用指南，第二版的由Grune和雅各布，其中讨论了各种分析算法，用于确定一个字符串是否包含在语法和，如果是的话，它是如何通过解析算法生成​​

If you're interested in learning more about parsing, consider checking out the excellent book "Parsing Techniques: A Practical Guide, Second Edition" by Grune and Jacobs, which discusses all sorts of parsing algorithms for determining whether a string is contained in a grammar and, if so, how it is generated by the parsing algorithm.

希望这有助于！

这篇关于上下文无关文法与上下文相关的语法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！