编译原理 文法

什么是文法?我们从一个自然语言的例子讲起:

                                    编译原理 文法

这是一个简化版本的英文文法。比如一个句子是由名词短语和动词短语构成的。名词短语由形容词和名词短语构成。从这个例子中我们能够看出语法的基本构成。用尖括号括起来的部分是语法成分,而没有被尖括号括起来的部分是语言的基本符号。英文的基本符号就是单词了。

那么编译语言的文法形式化定义是什么呢?

                                                                 编译原理 文法

文法G = (Vt, Vn, P, S)是由四元组Vt,Vn,P,S所构成的。

其中:

Vt是终结符集合,是文法定义语言的基本符号,就像是英文中的单词一样。

Vn是非终结符。用来表示语法成分的符号,类似上面的<名词短语>,也就是语法变量。

P是产生式。描述了终结符和非终结符组合成串的方法。表示形式是:α -> β, α至少要包含一个非终结符。

S是开始符号。是一个非终结符,是一个文法的最大的语法成分。就如同上面的<句子>

例如:

                                                                 编译原理 文法

上面这张图中描述的是加法乘法表达式的文法。其中我们能够看出,终结符Vt = {id, + * (,)}这些都是最终的一个一个语法不能被替换的元素;非终结符是E,他表示表达式,它可以被替换成各种数字等等。产生式P包含四种,可以被替换成加法,乘法,括号以及单独的数字。S开始符号是E,因为只有这一个非终结符,自然就是最大的了。

一般来说,第一个产生式的左部那个非终结符就是开始符号。

编译原理 文法编译原理 文法 Wzing04211 发布了111 篇原创文章 · 获赞 138 · 访问量 18万+ 私信 关注
上一篇:[剑指-Offer] 32 I. II.III从上到下打印二叉树(层序遍历、栈、常规解法)


下一篇:KVM(Keyboard、Video、Mouse)和KVM(Kernel-based Virtual Machine)的理解