查看“︁两级文法”︁的源代码

{{Unreferenced|time=2023-06-20T15:50:10+00:00}}
'''两级文法'''是下列两种形式结构之一：
# 两级[[形式语言]]的[[形式文法]]，这种语言是按两个级别来指定的形式语言，比如，字和句两个级别。
# 用来生成其他形式文法的形式文法[http://web.cs.wpi.edu/~jshutt/adapt/2level.html]{{Wayback|url=http://web.cs.wpi.edu/~jshutt/adapt/2level.html |date=20170126084126 }}。定义次级文法的规则的[[上下文无关文法]]可以生成导出文法的规则的一个有效的无限集合。可以生成另一个上下文无关文法的两级文法比单一层上下文无关文法更加强力，因为有生成力的两级文法已经实际上被证实是[[图灵完全]]的。

==例子==
众所周知的非上下文无关语言是
:<math>\{a^n b^n a^n | n \ge 1\}.</math>
这个语言的的两级文法是元文法
:N ::= 1 | N1
:X ::= a | b
以及文法模式
:Start ::= <math> \langle a^N \rangle\langle b^N \rangle\langle a^N \rangle </math>
:<math> \langle X^{N1} \rangle</math> ::= <math>\langle X^N \rangle X </math>
:<math> \langle X^1 \rangle</math> ::= X

==参见==
*[[Van Wijngaarden文法]]

==外部链接==
* Petersson, Kent (1990), "Syntax and Semantics of Programming Languages", Draft Lecture Notes, [http://www.cs.chalmers.se/~kentp/proglang.pdf PDF text]{{Wayback|url=http://www.cs.chalmers.se/~kentp/proglang.pdf |date=20070207111006 }}。

[[Category:形式语言|L]]


{{compu-lang-stub}}