高级语言及其语法描述

1、高级语言及其语法描述高级语言及其语法描述引论引论词法分析词法分析语法分析语法分析语法分析语法分析自下而上自下而上属性文法和语法制导翻译属性文法和语法制导翻译1 12 23 34 45 56 6语义分析与中间代码产生语义分析与中间代码产生符号表符号表运行时存储空间组织运行时存储空间组织优化优化目标代码生成目标代码生成7 78 89 910101111词法分析的任务：词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。因此，词法分析是编译的基础。执行词法分析的程序称词法分析器词法分析器，简称扫描器扫描器。3.1 对词法分析器的

2、要求对词法分析器的要求1. 词法分析器的功能和输出形式词法分析器的功能和输出形式功能：功能：输入源程序，输出单词符号。单词符号是一个程序语言的基本语法符号。程序语言的单词符号一般可分为下列五种：程序语言的单词符号一般可分为下列五种： 关键字：关键字：具有固定意义的标识符，称为保留字或基本字。如begin, end, if ，通常不用作一般标识符。 标识符：标识符：表示各种名字，如变量名、数组名、过程名 常数：常数：其类型一般有整型、实型、布尔、文字等。如100、3.14159、TRUE、sample 运算符：运算符：+, , , / 等。 界符：界符：逗号，分号，括号，/, / 等。一个程序语

3、言的关键字、运算符和界符都是确定的，一般只有几十个或上百个，标识符和常数则不受限制。常采用二元式来表示识别出的单词符号：(单词种别，单词符号的属性值) 单词种别通常用整数编码，如何分种，怎样编码，取决于处理的方便性。标识符一般统归一种常数按类关键字：全体为一种或一字一种运算符：一符一种，或具有共性的为一种界符：一符一种 对一符一种，可不需属性，但多符一种时必须要有属性信息，属性反映单词符号的特性或特征，而属性值反映特性或特征的值。例如：对标识符，其属性值可为存放它的有关信息的符号表项的指针。若假定关键字、运算符、界符都是一符一种，标识符单列一种，常数按类，则代码段：while (i = j)

4、i ; 可转换为如下序列： =， 2. 词法分析器作为一个独立子程序词法分析器作为一个独立子程序可使整个编译程序的结构更简洁、清晰和条理化。但并不意味词法分析必须安排成独立的一遍，语法分析时每当需要一个单词符号时就调用这个子程序(后文假定如此)。1. 输入、预处理输入、预处理第一步工作，输入源程序文本，放在输入缓冲区中。词法分析的工作可直接在这个缓冲区中进行，但在许多情况下，把输入串预处理一下，对单词符号的识别工作将是比较方便的。3.2 词法分析器的设计词法分析器的设计预处理预处理： 剔除空白符、跳格符、回车、换行符等编辑性文字及注释文字。它们不是程序的必要组成部分，存在的意义仅仅是为了改善程

5、序的易读性和易理解性。 空白符作为界符时，把若干个空白符结合成一个。我们可以设想构造一个预处理子程序，它能够完成上述的预处理任务。每当词法分析器调用它时，它就处理出一串确定长度(如120个字符)的输入字符，并将其装进词法分析器指定的缓冲区中(扫描缓冲区)，这样词法分析器就可在此缓冲区中直接进行单词符号的识别，而不必照管其它繁琐事务。一般采用两个指示器，一个指向当前正在识别的单词的开始位置，另一个用于搜索，为保证单词符号不会被缓冲区边界所打断，扫描缓冲区使用一个一分为二的区域。起点指示器搜索指示器假定每半区可容120字符，互补使用，若搜索到边界仍没结果，则调用预处理程序，令其装入后续120个输入

6、字符到另半区。所以对单词符号的长度必须限制，如：不得多于120字符，以确保在搜索指示器对另半区进行扫描的期间，现行单词的终点必定能够到达。必须超前扫描许多个字符，直到能肯定词性为止。2. 单词符号的识别：超前搜索单词符号的识别：超前搜索词法分析器的工作过程：词法分析器的工作过程：调用预处理子程序处理完一串输入字符放入扫描缓冲区后，分析器就从此缓冲区中逐一识别单词符号，缓冲区被处理完后，又调用预处理子程序装入新串。 关键字的识别关键字的识别如FORTRAN，关键字不加特殊保护，如程序段：1 DO99K=1，102 IF(5.EQ.M)I=103 DO99K=1.104 IF(5)=551, 3区

7、别：等号后第一个界符1逗点3句末符2, 4区别：右括号后第一个字符2字母4等号为了识别DO和IF，必须区分1, 3和2, 4，所以必须超前搜索多个字符，才能完成当前单词符号的识别。 标识符标识符字母开头的“字母/数字”串。由于后跟算符或界符，所以容易识别。 常数常数如FORTRAN的5.E08与5.EQ.M也必须超前搜索。 算符和界符算符和界符多字符复合而成的算符与界符(如+， ，=等)拼合成一个单词符号。是不可分的整体，同样需要超前搜索。3. 状态转换图状态转换图设计词法分析器的一个好工具设计词法分析器的一个好工具状态转换图是一张有限方向图有限方向图。在图中，结点代表状态状态，用圆圈表示，状

8、态之间用箭弧连结。箭弧上的标记(字符)代表在射出结点状态下可能出现的输入字符或字符类。如下图所示。21X3Y一张状态转换图只包含有限个状态，具有一个初态及至少一个终态。状态转换图可用于识别状态转换图可用于识别/接受一定的字符串：接受一定的字符串：210字母字母或数字其它*(a)标识符的识别标识符的识别210数字 数字其它*(b)整数的识别整数的识别1072345数字数字数字.E或D+或 -数字数字其它*6.数字E或D数字其它(c)Fortran实常数的识别实常数的识别3.3 正规表达式与有限自动机正规表达式与有限自动机1. 正规式与正规集正规式与正规集对字母表，我们感兴趣的是它的一些特殊字集，

9、即正规集。递归定义：递归定义： 和都是上的正规式，其表示的正规集分别为 和； 任何a，a是上的一个正规式，其正规集为a； 假定U和V都是上的正规式，其正规集分别为L(U)和L(V)，则(U|V), (UV)和(U)*也都是正规式，其正规集分别为 L(U)L(V), L(U)L(V)(连接积)和(L(U)*(闭包)。仅由有限次使用上述三步骤得到的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集，不致混淆时，括号可省，算符优先： |, 号可省。例1：令=a, b，则正规式正规集ba* 上所有b开头后跟任意多个a的字a(a|b)*以a为首的字(a|b)* (aa|bb) (a|b)*含

10、有相继两个a或b的字例2：令=A, B, 0, 1，则正规式正规集(A|B) (A|B|0|1)*标识符全体(0|1) (0|1)*数的全体等价：若两个正规式所表示的正规集相同，则二者等价，U=V。例如：b(ab)*=(ba)*b, (a|b)*=(a*b*)* 令U、V、W均为正规式，则有： U|V=V|U，(交换律) U|(V|W)=(U|V)W, U(VW)=(UV)W, (结合律) U(V|W)=UV|UW, (V|W)U=VU|WU (分配律) U=U =U2. 确定有限自动机确定有限自动机 (DFA)一个确定有限自动机(DFA)M是一个五元式M=(S, , , s0, F) S是一

11、个有限集，每个元素为一个状态 是有穷字母表，每个元素为一个输入字符 是一个从S至S的单值部分单值部分映射，(s, a) =s意为：当现行状态为s，输入字符a时，将转换到下一状态s (后继状态) s0 S 唯一的初态 FS 终态集(可空)显然，一个DFA可用一个矩阵来表示，行为状态，列为输入字符，元素为(s, a)的值，称为状态转换矩阵。例：若DFA M=(0, 1, 2, 3, a, b, , 0, 3)，其中(0, a)=1, (0, b)=2,(1, a)=3, (1, b)=2,(2, a)=1, (2, b)=3,(3, a)=3, (3, b)=3,也可表示成一张(确定的)状态转换图

12、。状态状态ab012313132233对*中的任何字，若存在一条从初态到某一终态的通路，且通路上所有标记符连接而成的字等于，则称可为DFA M所识别识别 (读出读出或接受接受)，若M的初态结点又是终态结点，则空字可为M所识别，识别的全体记为L(M)。1230aaaabbb3如果一个DFA M的输入字母表为，也称M是上的一个DFA，上的一个字集V*是正规的，当且仅当上存在DFA M，使V=L(M)。：SS为单值函数若改为多值函数则成为非确定有限自动机NFA。3. 非确定有限自动机非确定有限自动机 (NFA)一个非确定有限自动机(NFA)M是一个五元式M=(S, , , S0, F) S是一个有限

13、集，每个元素为一个状态 有穷字母表，每个元素为一个输入字符 是一个从S*至S的子集的映照，即：S* 2S显然，一个含有m个状态和n个输入字符的NFA可表示成如下的状态转换图：该图含有m个状态结点，每个结点可射出若干条箭弧与别的结点相连接，每条弧用*中的一个字(不一定要不同的字而且可以是空字)做标记(称为输入字)，整张图至少含有一个初态结点以及若干个(可以是0个)终态结点。某些结点既可是初态结点也可是终态结点。 S0 S，是一个非空初态集 FS ，是一个终态集(可空)对*中的任何字，若存在一条从某一初态结点到某一终态结点的通路，且通路上所有标记符依序连接而成的字(忽略那些标记为的字)等于，则称可

14、为NFA M所识别识别 (读出读出或接受接受)，若M的某些结点既是初态结点又是终态结点，或存在一条从某初态结点到终态结点的通路，则空字可为M所识别，识别的全体记为L(M)。显然，DFA是NFA的特例，但对每个NFA M存在一个DFA M ，使L(M)=L(M)NFA的确定化的确定化子集法子集法(1) 假定假定NFA M=，对，对M的状态的状态图进行如下改造：图进行如下改造： 引进新的初态结点X和终态结点Y，X,Y S从X到S0中任意状态结点连一条箭弧，从F中任意状态结点连一条箭弧到Y 对M的状态转换图进一步施行下图替换，重复这种分裂直至每条箭弧上的标记或为，或为中的单个字母。最终得到的NFA记

15、为M ，显然L(M )=L(M)。jiABkiAjBjiA/BiAjBjiA*kijA(2) M 进一步变换为进一步变换为DFA： 假定I是M 的状态集的子集，定义I的闭包-CLOSURE(I)为：(a) 若q I，则q -CLOSURE(I)；(b) 若q I，则从q出发经任意条弧而能到达的任何状态q 都属于-CLOSURE(I)； 假定I是M 的状态集的子集，a ，定义：Ia=-CLOSURE(J)，其中，J是那些可从I中的某一状态结点出发经过一条a弧而到达的状态结点的全体。 假定=a1,ak。构造一张表，每行含k+1列。置该表的首行首列为-CLOSURE(X) 。一般而言，如果某一行的第

16、一列的状态子集已经确定，例如记为I，那么，置该行的i+1列为Iai(i=1,k)。然后，检查该行上的所有状态子集，看是否已在表的第一列中出现，将未曾出现者填入到后面空行的第一列。重复上述过程，直至出现在第i+1列(i=1,k)上的所有状态子集均已在第一列上出现。因为M 的状态子集的个数是有限的，所以上述过程必定在有限步内终止。例：正规式(a|b)*(aa|bb)(a|b)*的NFA及构造出的状态转换矩阵如下：b5X62Yb1ba34aabaIIaIbX,5,15,3,15,4,15,3,15,3,1,2,6,Y5,4,15,4,15,3,15,4,1,2,6,Y5,3,1,2,6,Y5,3,1

17、,2,6,Y5,4,1,6,Y5,4,1,6,Y5,3,1,6,Y5,4,1,2,6,Y5,4,1,2,6,Y5,3,1,6,Y5,4,1,2,6,Y5,3,1,6,Y5,3,1,2,6,Y5,4,1,6,Y对前表中的所有状态子集重新命名，得到对前表中的所有状态子集重新命名，得到：sab012132215334465565634025b1baba436aababbaab未化简的DFA4. 正规文法与有限自动机的等价性正规文法与有限自动机的等价性对正规文法G与有限自动机M，如果L(G)=L(M)，则称G和M是等价的：(1) 对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机M，使得

18、L(G)=L(M)(2) 对每一个有限自动机M，都存在一个右线性正规文法GR或左线性正规文法GL，使得L(M) = L(GR) = L(GL) 5. 正规式与有限自动机的等价性正规式与有限自动机的等价性(1) 对任何有限自动机FA M，都存在一个正规式r，使得L(r)=L(M)；(2) 对任何正规式r，都存在一个有限自动机FA M，使得L(M) = L(r)。6. DFA的化简的化简一个DFA M的化简是指：寻找一个状态数比M少的DFA M，使得L(M) =L(M )。假定s和t是M的两个不同状态，称s和t是等价的等价的：如果从状态s出发能读出某个字w而停于终态，那么同样从t出发也能读出同样的字w而停于终态；反之，若从t出发能读出某个字w而停于终态，则从s出发也能读出同样的字w而停于终态。如果DFA M的两个状态s和t不等价，则称这两个状态是可区别的可区别的。例如，终态和非终态是可区别的，因为终态能读出空字，非终态则不能读出空字。