什么是文法?我们从一个自然语言的例子讲起:
这是一个简化版本的英文文法。比如一个句子是由名词短语和动词短语构成的。名词短语由形容词和名词短语构成。从这个例子中我们能够看出语法的基本构成。用尖括号括起来的部分是语法成分,而没有被尖括号括起来的部分是语言的基本符号。英文的基本符号就是单词了。
那么编译语言的文法形式化定义是什么呢?
文法G = (Vt, Vn, P, S)是由四元组Vt,Vn,P,S所构成的。
其中:
Vt是终结符集合,是文法定义语言的基本符号,就像是英文中的单词一样。
Vn是非终结符。用来表示语法成分的符号,类似上面的<名词短语>,也就是语法变量。
P是产生式。描述了终结符和非终结符组合成串的方法。表示形式是:α -> β, α至少要包含一个非终结符。
S是开始符号。是一个非终结符,是一个文法的最大的语法成分。就如同上面的<句子>
例如:
上面这张图中描述的是加法乘法表达式的文法。其中我们能够看出,终结符Vt = {id, + * (,)}这些都是最终的一个一个语法不能被替换的元素;非终结符是E,他表示表达式,它可以被替换成各种数字等等。产生式P包含四种,可以被替换成加法,乘法,括号以及单独的数字。S开始符号是E,因为只有这一个非终结符,自然就是最大的了。
一般来说,第一个产生式的左部那个非终结符就是开始符号。
Wzing04211 发布了111 篇原创文章 · 获赞 138 · 访问量 18万+ 私信 关注