形式文法
维基百科,自由的 encyclopedia
在形式语言理论中,文法(为了避免歧义,常称作“形式文法”)是形式语言中字符串的一套产生式规则(英语:Production (computer science))。这些规则描述了如何用语言的字母表生成符合语法(英语:syntax (programming languages))的有效的字符串。文法不描述字符串的含义,也不描述在任何上下文中可以用它们做什么——只描述它们的形式。
形式语言理论是应用数学的一个分支,是研究形式文法和语言的学科。它在理论电脑科学、理论语言学、形式语义学、数理逻辑等领域有着广泛的应用。
形式文法是从一个“开始符号”出发的一套重写字符串的规则。因此,文法通常被认为是语言生成器。然而,它有时也可以用作“识别器”(电脑学中的一种函数,用于确定给定字符串是否属于该语言,是否为语法错误)的基础。形式语言理论使用另一个理论来描述识别器,也就是自动机理论。自动机理论有一个有趣的结果,某些形式语言是无法设计出识别器的。[1] 语法分析是通过将一段话语(自然语言中的一个字符串)分解成一组符号,并根据语言的语法分析每一个符号的过程。大多数语言的话语含义都是根据其句法结构来确定的——这种做法被称为组合语义学。因此,在语言中描述话语含义的第一步就是把它分解成若干部分,然后观察它经过分析后的形式(在电脑科学中被称为分析树,在生成文法中被称为深层结构)。