生成文法

生成文法
术语名称	生成文法
英语名称	generative grammar

生成文法(generative grammar)是描述形式语言中语法规则的一种方式，对应形式语言中进行“规则描述”的表示方式。

可以认为生成文法本身是一种用于描述形式语言的形式元语言。

描述方式

生成文法对语言进行如下建模。

生成文法包括以下四个部分：

• 终结符(terminal)集合 [math]\displaystyle{ V_T }[/math] 。其中“终结”一词指不可细分，生成过程中都是终结符时生成过程终结。
• 非终结符(nonterminal)集合 [math]\displaystyle{ V_N }[/math] 。
• 生成式/产生式(generative form)集合 [math]\displaystyle{ P }[/math] ：一些形如 [math]\displaystyle{ \alpha\rightarrow \beta }[/math] 的表达式，其中 [math]\displaystyle{ \alpha,\beta }[/math] 是一系列的终结符或非终结符，表示左侧的结构可以被重写为右侧的结构。
• 开始符号(start symbol) [math]\displaystyle{ S }[/math] ：一个必须是 [math]\displaystyle{ P }[/math] 中第一个生成式左侧的符号，且可以出现在多个产生式的左侧。指定生成的起点。