上下文无关语法和其他语法有什么区别？

Question

哪些语法不是上下文无关的？请给我一些非上下文无关的例子。

Is this grammar context free?

A->aSb|aaS|aaaS|B
S->aSb|Bb|lambda
B->Bb|lambda

Answer 1

The grammar is context-free, because there's no context around the left-hand side. See below.

Assuming:

• The Greek letters like ?, ?, and ? are arbitrary productions
• Uppercase letters like X and Y are nonterminal symbols
• Lowercase letters like z are terminal symbols
• ? is the special empty production

We have the following definitions:

1. Regular grammars are those whose rules can be written in the forms:

   X: z Y
   X: z
   X: ?
   

   For example:

   Digits: '0' Digits
   Digits: '1' Digits
   Digits: '2' Digits
   ...
   Digits: '9' Digits
   Digits: ?
   

2. Context-free grammars are those whose rules can be written in the form:

   X: ?
   

   In other words, only single nonterminals can be transformed at a time, independently of what might surround them.

   For example:

   Expression: AdditiveExpression
   AdditiveExpression: AdditiveExpression '+' MultiplicativeExpression
   AdditiveExpression: AdditiveExpression '-' MultiplicativeExpression
   AdditiveExpression: MultiplicativeExpression
   MultiplicativeExpression: MultiplicativeExpression '*' PrimaryExpression
   MultiplicativeExpression: MultiplicativeExpression '/' PrimaryExpression
   MultiplicativeExpression: PrimaryExpression
   PrimaryExpression: Number
   PrimaryExpression: '(' Expression ')'
   

3. Context-sensitive grammars are those whose rules can be written in the form:

   ?X?: ???
   

   In other words, the context around X can help you decide that X should be transformed into ?, but the context itself does not become transformed.

   For example:

   Expression: 'x' Foo 'y'
   'x' Foo 'y': 'x' Bar 'y'
   Bar: 'z'
   

   A more realistic example that shows why this is useful can be found on Math.StackExchange.

4. Unrestricted grammars are those whose rules can be written in the form:

   ?X?: ?
   

   换句话说，任何包含非终结符的符号序列都可以被处理成任何其他符号序列。基本上，这代表了对内存的任意操作，或图灵完备性。

   例如：

   Expression: 'x' Foo 'y'
   'x' Foo 'y': 'z'
   

   你永远不会在实践中看到这些。