编译原理学习(二)—文法

编译原理学习(2)—文法

       编译过程的核心就是翻译，加工对象是用某些高级语言编写的程序。编译程序的任务就是将高级语言编写的程序翻译成机器语言程序，在学习和掌握编译程序之前，要对高级程序语言的构词和语法要有初步的了解。程序设计语言就是形式语言，先来介绍形式语言与编译技术密切相关的术语。

        2.1字母表与符号串

            任何一种语言都是由该语言的基本符号所组成的字符串集合的子集。

             1.字母表

            字母表字母表是由若干元素所组成的有限非空集合，其中，每一元素称为符号，故有时又将字母表称为符号集。符号是一个抽象的实体，仅在某些特定的使用场合，才分别赋予它们以具体的含义。因为符号是一个最基本的概念，所以无须再给以形式定义。

           通常，在一个字母表中，可用阿拉伯数字、大写及小写英文字母、各种算术运算符、常用的标点符号以及使用上认为方便的其它符号来表示它的元素。例如，{a,b,c,+,-}就是含有5个元素的一个字母表。

             2.符号串

            符号串是由字母表上一个或多个符号所组成的任何又穷序列。例如，设A={a,b,c}是一个字母表，则a,b,c,aa,ab,ac,ba,bb,bc,ca,cc,cb,aaa等等都是A上的符号串。注意ε也是字母表上的字符串，它由零个符号组成。一个字母表上全部符号串所组成的集合显然为无限集。

             3.符号串及其集合的运算

            符号串长度：我们把符号串中所含符号的个数称为该符号串的长度。例如，符号串abc的长度为3，记为|abc|=3。显然，|ε|=0。

            符号串相等：若x，y是字母表上的两个符号串，那么当且仅当x的各个字符与组成y的各个字符依次相等时，字符串x与字符型y相等，记作想x=y。

            符号串的前缀、后缀:设x是一个符号串，我们把从x的尾部删去若干个(包括0个)符号之后所余下的部分称为x的前缀。仿此，也可定义一个符号串的后缀。例如，若x=abc，则ε,a,ab及abc都是x的前缀；而ε,c,bc及abc都是x的后缀。若x的前缀(后缀)不是x本身，则将其称为x的真前缀 (真后缀)。

             符号串的子串：从一个符号串中删去它的一个前缀和一个后缀之后所余下的部分称为此符号串的子串。例如，若x=abcd，则ε,a,b,c,d,ab,bc,cd,abc,bcd及abcd都是x的子串。可见，x的任何前缀和后缀都是x的子串，但其子串不一定是x的前缀或后缀。特别，ε和x本身既是x的前缀与后缀，也是它的子串。

            符号串的连接和方幂：设x和y是两个符号串，如果我们将符号串y直接拼接在x之后，则称此种操作为符号串x和y的连接，记为xy。例如，若x=NPU，y=1108，则xy=NPU1108。而yx=1108NPU。可见，xy一般不等于yx。显然，空符号串ε与任何符号串x的连接还是x本身，即εx=xε=x，因此，可将ε视为连接操作的单位元素。我们不难将上述定义推广到任意多个符号串相连的情况。一个符号串x与其自身的n-1次连接称为此符号串的n次方幂，记作xn，即x1=x,x2=xx, x3=x2x=xx2=xxx, …xn=xn-1x=xxn-1=xxx…xn个。特别，我们定义x0=ε。

           符号串集合的和与：积设A，B为两个符号串的集合，则将集合A同B的和与积，分别记作A+B(或A∪B)与AB，且定义为：A+B={w|w∈A 或 w∈B}，AB={xy|x∈A 且y∈B}。即集合A+B中含有且仅含有A和B中的所有符号串，集合AB则由形如xy的所有符号串组成，其中x∈A，且y∈B。例如，若A={a,b,c}，B={00,11}，则A+B={a,b,c,00,11}，AB={a00,a11,b00,b11,c00,c11}。

         2.2文法

           在英语中，句子由主语与谓语组成，主语由冠词、形容词及名词组成，这就是说明句子的语法规则。在形式语言里，这种规则可以采用如下的语法规则加以描述：〈句子〉∷=〈主语短语〉〈动词短语〉，每个用一对尖括号“〈”和“〉”括起来的部分，是所要定义语言中的一个语法实体 (或称为语法单位、语法结构、语法范畴、语法成分和语法变量等等)；符号“∷=”为一整体记号，其含义是：“定义为…”。所以，规则①的含义就是：“语法范畴〈句子〉被定义为〈主语短语〉后跟一个〈动词短语〉”。然而，语法范畴〈主语短语〉及〈动词短语〉尚需进一步定义。

                〈句子〉∷=〈主语短语〉〈动词短语〉

                〈主语短语〉∷=the 〈名词〉

        〈动词短语〉∷=〈动词〉〈宾语短语〉

        〈宾语短语〉∷=〈冠词〉〈名词〉

          含有一系列需要定义的语法范畴，通常我们把它们的名字称为非终结符号，由这些非终结符号组成的集合称为非终结符号集，用VN记之。对于上例，我们有VN={〈句子〉，〈主语短语〉，〈动词短语〉，…，〈冠词〉}。

          一个文法：G［S］可表示成形如(VN,VT,P,S)的四元式。其中VN,VT,P均为非空的有限集，分别称为非终结符号集、终结符号集和产生式集，这些集合所含元素的意义如前所述；S∈VN，为文法的开始符号。此外，我们还将出现在各产生式左部和右部的一切符号所组成的集合称为字汇表(或词汇表)，记作V。更确切地说，上面所给出的，实际上是所谓前后文无关文法的定义。之所以如此命名，是因为当用形如U→u的产生式进行推导，以符号串u去替换U时，并不顾及U所处的环境，即与U的前后文无关。以后，除非另作说明，我们所说的文法均指前后文无关文法。

         设G=(VN, VT,P, S)是一文法，α和β是G的字汇表V上的符号串，我们说β是α的直接推导(或α直接产生β)，当且仅当α，β可分别写成α=υUδ及β=υηδ。其中，υ,δ∈V*，且U→η∈P。通常，我们将上述事实记作αGβ，或υUδGυηδ。需要说明的是，在上述定义中，υ和δ之一甚至两者都可以为ε。另外，记号“αGβ”表示在文法G中α直接推导出β，若所涉及的文法G无须特别指明，也可写成αβ。

         当语言为无限集时，是否也能用前面所定义的文法来描述?即无限语言是否有有限表示的问题。若使用所谓递归文法，许多无限的语言仍可用有限个产生式即用有限的文法来描述。E→E+T|T,T→T*F|F,F→(E)|I都是递归的。

             2.3文法的二义性

            如果一个文法所定义的句子中有某个句子或句型，它存在两颗不同的语法树，该文法是二义性文法。

          时间原因关系，内容不是太完全，参考资料《编译原理及实现》，西北工业大学精品课程。

          详情请看：前后文无关文法和语言，文法和语言的定义，文法和语言的形式定义。

          句型分析看：http://jpkc.nwpu.edu.cn/jp2005/20/kcwz/wlkc/wlkc/02/2_3_1.htm

          语法二义性：http://jpkc.nwpu.edu.cn/jp2005/20/kcwz/wlkc/wlkc/02/2_3_2.htm