兩級文法

兩級文法是下列兩種形式結構之一：

1. 兩級形式語言的形式文法，這種語言是按兩個級別來指定的形式語言，比如，字和句兩個級別。
2. 用來生成其他形式文法的形式文法[1]（頁面存檔備份，存於網際網路檔案館）。定義次級文法的規則的上下文無關文法可以生成導出文法的規則的一個有效的無限集合。可以生成另一個上下文無關文法的兩級文法比單一層上下文無關文法更加強力，因為有生成力的兩級文法已經實際上被證實是圖靈完全的。

例子

眾所周知的非上下文無關語言是

$\{a^{n}b^{n}a^{n}|n\geq 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（頁面存檔備份，存於網際網路檔案館）。