本文学习文法的定义,什么是文法?


我们先从一个自然语言的例子讲起,这是一个简化版本的用来描述英语句子构成规则的文法。

<句子> -> <名词短语><动词短语>
<名词短语> -> <形容词><名词短语>
<名词短语> -> <名词>
<动词短语> -> <动词><名词短语>
<形容词> -> little
<名词> -> boy
<名词> -> apple
<动词> -> eat

从这个文法中,我们可以看出一个句子是由一个名词短语加上一个动词短语构成的。一个名词短语可以由一个形容词加一个名词短语构成,还可以由一个名词构成。一个动词短语是由一个动词加上一个名词短语构成。 形容词可以是little,名词可以是boy或者apple,动词可以是eat。

从这个例子中,我们可以提取出一些文法的组成要素。在这个文法中出现的符号可以分为两类。

  • 用尖括号括起来的部分称为是语法成分。

  • 未用尖括号括起来的部分表示语言的基本符号。

因为这个文法是用来描述句子的构成规则的,那么句子的基本符号就是单词。如果一个文法是用来描述单词的构成规则的话,那么这个文法的基本符号就是字母。

文法的形式化定义

根据上述例子,我们可以给出文法的形式化定义。文法用大写字母G来表示,我们把一个文法G定义成了一个四元组。

G = (VT , VN , P , S )

VT:终结符集合

V表示向量vector,T表示终结符terminal symbol。什么是终结符呢?终结符就是文法所定义的语言的基本符号。例如在刚才的这个例子中,这个文法是用来描述句子的组成规则的,那么句子的基本符号是单词,因此这些单词构成了这个文法的终结符集,终结符有时候也称为token。

VT = { apple, boy, eat, little }

VN:非终结符集合

非终结符是用来表示语法成分的符号。例如上述文法中,用尖括号括起来的符号。

VN = { <句子>, <名词短语>, <动词短语>, <名词>, … }

由于可以从他们进一步推导出其他的语法成分,因此他们称为是非终结符。非终结符,有时也称为是语法变量。

需要注意的是终结符集合和非终结符集合是不相交的。

VT ∩VN = Φ

终结符和非终结符统称为文法符号,因此VT并上VN表示的是文法符号集。

VT∪VN: 文法符号集

P:产生式集合

产生式描述了将终结符和非终结符组合成串的方法。简而言之,产生式就是用来产生串的式子。产生式的一般形式是α加一个箭头加上一个β,读作α定义为β。

α->β

从下面两个式子我们可以看出α和β表示的是文法符号串。

α∈(VT∪VN)+,且α中至少包含VN中的一个元素
β∈(VT∪VN)*

因为这个VT是终结符集合,它是一个字母表,VN是非终结符集合,他也是一个字母表,所以这两个字母表的并集还是一个字母表。

我们前面讲过字母表闭包的表示的是这个字母表上的符号串构成的集合,因此α和β都是文法符号串。

α中要求至少要包含一个非终结符,α也称为产生式的头或者左部,β称为产生式的体或者右部。

例如在刚才的这个文法中的每一条规则都是一个产生式。

S:文法的开始符号

S是一个特殊的非终结符,它表示的是该文法中最大的语法成分。

S∈ VN

例如在上述的例子中,这个文法是用来描述句子的构成规则,所以句子就是这个文化中最大的语法成分,因此句子就是这个文化的开始符号。

S=<句子>

下面来看一个文法的例子,这是一个简化版本的用来表示算术表达式的文法。

G =( { id, +, , (, ) }, {E}, P, E )
P ={ E → E + E , E → E
E , E → ( E ) , E → id }

在这个文法中,终结符集合中,包括了以下几个终结符:分别id,也就是标识符,+,*,(),这些都是最终出现在句子中的单词。

因此他们构成了这个文法的终结符集合,这个文法的非终结符集合中只有一个非终结符,就是E。

E表示的是表达式Expression,我们来看一下这个文法它的产生式集合,有四个产生式,分别是E定义为E + E,E定义为E * E,E定义为(E),E定义为id。

由于这是一个用来描述表达式的文法,因此表达式是这个文法最大的语法成分,E就是这个文法的开始符号,而且这个文法中也没有其他的非终结符。

我们这里约定在不引起歧义的前提下,可以只写文法的产生式

例如上述文法我们可以简写为下面这种形式,就是只把他的产生式列出来就可以表示这个文法。

G : E → E + E
E → E * E
E → ( E )
E → id

产生式的简写

下面来看一下产生式的简写。对一组有相同左部的α产生式α定义为β1,α定义为β2,一直到α定义为βn,

α→β1 , α→β2 , … , α→βn

可以简记为一下形式:

α→β1 | β2 | … | βn

其中|读作或者,β1到βn称为是α的候选式。

例如对于下面E产生式,

E → E + E
E → E E
E → ( E )
E → id

就可以把它简写下面的形式

E → E + E | E E | ( E ) | id

符号约定

为了避免总是声明哪些符号是终结符,哪些符号是非终结符,对符号的使用做一些约定。

约定下述符号是终结符:

字母表中排在前面的小写字母,比如说a、b、c表示的是终结符
运算符,如+*
标点符号,如括号、逗号等
数字0、1、. . . 、9
粗体的字符串,如id,if

约定下述符号是非终结符:

字母表中排在前面的大写字母,如A、B、 C。
字母S。通常用来表示文法的开始符号。
小写斜体的名字,如expr用来表示表达式expression、stmt用来表示句子statement等。
代表程序构造的大写字母。如E(表达式,expression)、T(项,term) 和F(因子,factor)

约定字母表中排在后面的大写字母,比如说大写的X、Y、Z表示的是文法符号,也就是说,它既可以表示终结符,也可以表示非终结符。

字母表中排在后面的小写字母主要是u、v、w、x、y、z表示的是终结符号串,既然是串就有可能是空串,因此这里包括空串。

小写的希腊字母,比如说α, β, γ等等表示的是文法符号串。既然是文法符号串,那么也包括空串。 除非特别说明第一个产生式的左部就是文法的开始符号。

总结:

字母表中排在前面的小写字母用来表示终结符
字母表中排在前面的大写字母用来表示非终结符
字母表中排在后面的大写字母用来表示文法符号,文法符号可以是终结符,也可以是非终结符。
字母表中排在后面的小写字母,用来表示终结符号串
小写的希腊字母用来表示文法符号串

原文链接:

最后修改日期:2020年5月14日

留言

撰写回覆或留言