形式文法,计算机科学中的概念,在计算机科学中,形式语言是某个字母表上一些有限长字串的集合,而形式文法是描述这个集合的一种方法。形式文法之所以这样命名,是因为它与人类自然语言中的文法相似的缘故。形式文法描述形式语言的基本想法是,从一个特殊的初始符号出发,不断的应用一些产生式规则,从而生成出一个字串的集合。产生式规则指定了某些符号组合如何被另外一些符号组合替换。
形式文法
正文
数理语言学用于生成语言的文法。形式文法是数目有限的规则的集合,这些规则可生成语言中的合格句子,并排除语言中的不合格句子。形式文法符号为G,文法所生成的语言符号为L(G)。
定义美国语言学家N。乔姆斯基把形式文法G定义为四个项目的组合:
G(VN,VT,S,P)
其中,VN是非终极符号,不能处于生成过程的终点;VT是终极符号,能处于生成过程的终点;VN与VT不相交,没有公共元素;S是VN中的初始符号;P是重写规则,其一般形式为:
嗞
这里,嗞和都是符号串。
如果用符号来表示符号串中的界限,那么,可以从初始符号串S开始,应用重写规则S嗞1,从S构成新的符号串嗞1,再利用重写规则嗞1嗞2,从嗞1构成新的符号串嗞2,一直到得出不能再继续重写的符号串嗞n为止,这样得出的终极符号串嗞n,显然就是语言L(G)中合格的句子。
例如,在英语中,有如下的文法:
G(VN,VT,S,P)
VN{NP,VP,T,N,V}
VT{the,man,boy,ball,saw,hit,took,}
SS
P:SNPVP
NPTN
VPVNP
Tthe
N{man,boy,ball,}
V{saw,hit,took,}
这里,初始符号S表示句子,NP表示名词短语,VP表示动词短语,T表示指示词,N...
(全文)