两级文法

两级文法是下列两种形式结构之一：

1. 两级形式语言的形式文法，这种语言是按两个级别来指定的形式语言，比如，字和句两个级别。
2. 用来生成其他形式文法的形式文法[1]。定义次级文法的规则的上下文无关文法可以生成导出文法的规则的一个有效的无限集合。可以生成另一个上下文无关文法的两级文法比单一层上下文无关文法更加强力，因为有生成力的两级文法已经实际上被证实是图灵完全的。

例子

众所周知的非上下文无关语言是

$\{a^n b^n a^n | n \ge 1\}.$

这个语言的的两级文法是元文法

N ::= 1 | N1

X ::= a | b

以及文法模式

Start ::= $\langle a^N \rangle\langle b^N \rangle\langle a^N \rangle$

$\langle X^{N1} \rangle$ ::= $\langle X^N \rangle X$

$\langle X^1 \rangle$ ::= X

参见

• Van Wijngaarden文法

外部链接

• Petersson, Kent (1990), "Syntax and Semantics of Programming Languages", Draft Lecture Notes, PDF text。