编译原理word版.

1、第三章复习：程序语言的语法描述 几个概念:考虑一个有穷 字母表 字符集其中每一个元素称为一个字符上的字(也叫字符串) 是指由中的字符所构成的一个有穷序列不包含任何字符的序列称为空字，记为用*表示上的所有字的全体,包含空字复习：程序语言的语法描述 *的子集U和V的连接（积）定义为UV ab | aÎU & bÎV V自身的 n次积记为Vn=VVV规定V0=e，令 V*=V0V1V2V3 称V*是V的闭包;记 VVV* ，称V+是V的正规闭包。复习：程序语言的语法描述 上下文无关文法的定义： 一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中VT：终结符

2、集合(非空)VN：非终结符集合(非空)，且VT Ç VN=ÆS：文法的开始符号，SÎVNP：产生式集合(有限)，每个产生式形式为P®a， PÎVN， a Î (VT È VN)*开始符S至少必须在某个产生式的左部出现一次。复习：程序语言的语法描述 定义：称aAb直接推出agb，即aAbÞagb 仅当A ® g是一个产生式， 且a， bÎ (VT È VN)* 。如果a1 Þ a2 Þ ¼ Þan，则我们称这个序列是从a1到an的一个推导。若存在一

3、个从a1到an的推导，则称a1可以推导出an 。复习：程序语言的语法描述 最左推导：任何一步a Þ b都是对a中的最左非终结符进行替换。 最右推导：任何一步a Þ b都是对a中的最右非终结符进行替换。复习：程序语言的语法描述 用一张图表示一个句型的推导,称为语法树。复习：程序语言的语法描述 定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。复习：程序语言的语法描述 形式语言鸟瞰¨ 0型(短语文法，图灵机)： 产生式形如： a ® b 其中：aÎ (VT &#

4、200; VN)*且至少含有一个非终结符；bÎ (VT È VN)*¨ 1型(上下文有关文法，线性界限自动机)： 产生式形如： a ® b 其中：|a| £ |b|，仅 S®e 例外。复习：程序语言的语法描述 形式语言鸟瞰¨ 2型(上下文无关文法，非确定下推自动机)： 产生式形如： A ® b 其中：AÎ VN；bÎ (VT È VN)*。¨ 3型(正规文法，有限自动机)： 产生式形如： A ® aB 或 A ® a 其中： aÎ VT*；A，B

5、ÎVN 产生式形如： A ® Ba 或 A ® a 其中： aÎ VT*；A，BÎVN第三章 词法分析词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。词法分析器(Lexical Analyzer) 又称扫描器(Scanner)：执行词法分析的程序3.1 对于词法分析器的要求一、词法分析器的功能和输出形式功能:输入源程序、输出单词符号单词符号的种类：基本字：如 begin，repeat，¼标识符表示各种名字：如变量名、数组名和过程名常数：各种类型的常数运算符：+，-，*，/，¼界符：逗号、分号、括号和空

6、白输出的单词符号的表示形式:(单词种别，单词自身的值)单词种别通常用整数编码表示。若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定基本字、运算符和界符都是一符一种。若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值。标识符单列一种；常数按类型分种(整、实、布尔等）。例 C程序 while (i>=j) i-;输出单词符号：< while, - >< (, - >< id, 指向i的符号表项的指针 >< >=, - >< id, 指向j的符号表项的指针 >< ), - >< i

7、d, 指向i的符号表项的指针 >< -, - >< ;, - >二、词法分析器作为一个独立子程序词法分析是作为一个独立的阶段，是否应当将其处理为一遍呢？作为独立阶段的优点：结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝节问题。不作为一遍：将其处理为一个子程序。词法分析器的结构输入串放在输入缓冲区中。预处理子程序：剔除无用的空白、跳格、回车和换行等编辑性字符;区分标号区、捻接续行和给出句末符等扫描缓冲区二、单词符号的识别:超前搜索1 基本字识别:例如:DO99K=1，10 DO 99 K = 1，10 IF(5.EQ.M)GOTO55 IF (5.EQ.M)

8、GOTO 55DO99K=1.10IF(5)=55需要超前搜索才能确定哪些是基本字2 标识符识别:字母开头的字母数字串，后跟界符或算符3 常数识别:识别出算术常数并将其转变为二进制内码表示。有些也要超前搜索。 5.EQ.M 5.E084 算符和界符的识别把多个字符符合而成的算符和界符拼合成一个单一单词符号。:=， *， .EQ. ， +，-，>=三、状态转换图1 概念状态转换图是一张有限方向图。一个状态转换图可用于识别(或接受)一定的字符串。6)IsLetter和 IsDisgital 布尔函数，判断ch中字符是否为字母和数字7) Reserve 整型函数，对于 strToken 中的字

9、符串查找保留字表，若它实保留字则给出它的编码，否则回送08) Retract 子程序，把搜索指针回调一个字符位置9)InsertId 整型函数，将strToken中的标识符插入符号表，返回符号表指针10)InsertConst 整型函数过程，将strToken中的常数插入常数表，返回常数表指针。 int code, value;strToken := “ ”;/*置strToken为空串*/GetChar(); GetBC();if (IsLetter()beginwhile (IsLetter() or IsDigit()beginConcat(); GetChar(); endRetrac

10、t();code := Reserve();if (code = 0)beginvalue := InsertId(strToken);return ($ID, value);endelsereturn (code, -);endelse if (IsDigit()beginwhile (IsDigit()beginConcat( ); GetChar( );endRetract();value := InsertConst(strToken);return($INT, value);endelse if (ch =) return ($ASSIGN, -);else if (ch =+) r

11、eturn ($PLUS, -);else if (ch =*)beginGetChar();if (ch =*) return ($POWER, -);Retract(); return ($STAR, -);endelse if (ch =;) return ($SEMICOLON, -);else if (ch =() return ($LPAR, -);else if (ch =) return ($RPAR, -);else ProcError( );/* 错误处理*/3.3 正规表达式与有限自动机几个概念:考虑一个有穷 字母表 字符集其中每一个元素称为一个字符上的字(也叫字符串)

12、是指由中的字符所构成的一个有穷序列不包含任何字符的序列称为空字，记为用*表示上的所有字的全体,包含空字例如: 设 =a， b，则 *=,a,b,aa,ab,ba,bb,aaa,.*的子集U和V的连接（积）定义为UV ab | aÎU & bÎV V自身的 n次积记为Vn=VVV规定V0=e，令 V*=V0V1V2V3 称V*是V的闭包;记 VVV* ，称V+是V的正规闭包。3.3.1 正规式和正规集正规集可以用正规表达式（简称正规式）表示。正规表达式是表示正规集一种方法。一个字集合是正规集当且仅当它能用正规式表示。正规式和正规集的递归定义：对给定的字母表S1)e 和

13、Æ都是S上的正规式，它们所表示的正规集为e和Æ2) 任何aÎS ，a是S上的正规式，它所表示的正规集为a ;3) 假定e1和e2都是S上的正规式，它们所表示的正规集为L(e1)和L(e2)，则i) (e1|e2)为正规式，它所表示的正规集为L(e1)ÈL(e2)，ii) (e1.e2)为正规式，它所表示的正规集为L(e1)L(e2)，iii) (e1)*为正规式，它所表示的正规集为(L(e1)*，仅由有限次使用上述三步骤而定义的表达式才是S上的正规式，仅由这些正规式表示的字集才是S上的正规集。所有词法结构一般都可以用正规式描述。若两个正规式所表示的正规集

14、相同，则称这两个正规式等价。如b(ab)*=(ba)*b(a*b*)*=(a|b)* 对正规式，下列等价成立：e1|e2 = e2|e1 交换律e1 |(e2|e3) = (e1|e2)|e3 结合律e1(e2e3) = (e1e2)e3 结合律e1(e2|e3) = e1e2|e1e3 分配律(e2|e3)e1 = e2e1|e3 e1分配律ee = e e = e e1e2 <> e2 e1 3.3.2 确定有限自动机(DFA)对状态图进行形式化，则可以下定义：自动机M是一个五元式M=(S, S, f, S0, F),其中：1. S: 有穷状态集，2. S：输入字母表(有穷)，

15、3. f: 状态转换函数，为S´S®S的单值部分映射，f(s，a)=s表示：当现行状态为s，输入字符为a时，将状态转换到下一状态s。我们把s称为s的一个后继状态。4. S0ÎS是唯一的一个初态； 5 FÍS ：终态集(可空)。例如：DFA M=(0，1，2，3，a，b，f，0，3)， 其中：f定义如下：f(0，a)=1f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1f(2，b)=3f(3，a)=3 f(3，b)=3DFA可以表示为状态转换图。假定DFA M含有m个状态和n个输入字符，那么，这个图含有m个状态结点，每个结点顶多含有n条箭弧

16、射出，且每条箭弧用上的不同的输入字符来作标记。对于S*中的任何字a，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于a，则称a为DFA M所识别(接收)DFA M所识别的字的全体记为L(M)。可以证明：S上的字集VÍS*是正规集，当且仅当存在上的DFA M，使得VL(M)。3.3.3 非确定有限自动机(NFA) 定义：一个非确定有限自动机(NFA) M是一个五元式M=(S, S, f, S0, F)，其中：1 S: 有穷状态集；2 S ：输入字母表(有穷)；3 f: 状态转换函数，为S´S*®2S的部分映射(非单值)；4 S0Í

17、S是非空的初态集；5 F ÍS ：终态集(可空)。从状态图中看NFA 和DFA的区别： 1 弧上的标记可以是S*中的一个字，而不一定是单个字符； 2 同一个字可能出现在同状态射出的多条弧上。DFA是NFA的特例。定义：对于任何两个有限自动机M和M，如果L(M)=L(M)，则称M与M等价。自动机理论中一个重要的结论：判定两个自动机等价性的算法是存在的。对于每个NFA M存在一个DFA M，使得 L(M)=L(M)。亦即DFA与NFA描述能力相同。1. 假定NFA M=<S, S, d, S0, F>，我们对M的状态转换图进行以下改造： 1) 引进新的初态结点X和终态结点Y，

18、X,YÏS， 从X到S0中任意状态结点连一条e箭弧， 从F中任意状态结点连一条e箭弧到Y。 2) 对M的状态转换图进一步施行替换，其中k是新引入的状态。逐步把这个图转变为每条弧只标记为S上的一个字符或e，最后得到一个NFA M，显然L(M)=L(M)识别所有含相继两个a或相继两个b的字2. 把上述NFA确定化采用子集法.设a是S中的一个字符，定义Ia= e-closure(J) 其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。e-closure(1)=1，2=I J=5，4，3 Ia= e-closure(J)= e-closure(5，4，3) =5，4，3，6，2，7，

19、8把确定化的过程: 不失一般性，设字母表只包含两个a和b，我们构造一张表:现在把这张表看成一个状态转换矩阵，把其中的每个子集看成一个状态。这张表唯一刻划了一个确定的有限自动机M，它的初态是e-closure(X) ，它的终态是含有原终态Y的子集。不难看出，这个DFA M与M等价。3.3.4 正规文法与有限自动机的等价性对于正规文法G和有限自动机M，如果L(G)L(M)，则称G和M是等价的。关于正规文法和有限自动机的等价性，有以下结论：3.3.4 正规文法与有限自动机的等价性定理： 1.对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机(FA) M，使得L(M)L(G)。 2.对每

20、一个FA M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)L(GR)L(GL)。证明： 1. 对每一个右线性正规文法G或左线性正规文法G，都构造一个有限自动机（FA） M，使得L(M)L(G)。(1) 设右线性正规文法G=<VT, VN, S, P >。将VN中的每一非终结符号视为状态符号，并增加一个新的终结状态符号f，fÏVN。 令M=<VNf, VT, d, S, f>，其中状态转换函数d由以下规则定义：(a) 若对某个AÎVN及aÎVTe，P中有产生式Aa，则令d(A,a)=f(b) 对任意的AÎVN及a&

21、#206;VTe，设P中左端为A，右端第一符号为a的所有产生式为：AaA1|aAk （不包括Aa）， 则令d(A,a)=A1,Ak。 显然，上述M是一个NFA。对于右线性正规文法G，在S w的最左推导过程中:· 利用A®aB一次就相当于在M中从状态A经过标记为a的箭弧到达状态B（包括a=e的情形）;· 在推导的最后，利用A®a一次则相当于在M中从状态A经过标记为a的箭弧到达终结状态f（包括a=e的情形）。综上，在正规文法G中，S w的充要条件是：在M中，从状态S到状态f有一条通路，其上所有箭弧的标记符号依次连接起来恰好等于w，这就是说，wÎL(

22、G)当且仅当wÎL(M)，故L(G)L(M)。(2) 设左线性正规文法G=<VT, VN, S, P>。将VN中的每一符号视为状态符号，并增加一个初始状态符号q0，q0ÏVN。 令M=<VNq0, VT, d, q0, S>，其中状态转换函数d由以下规则定义：(a) 若对某个AÎVN及aÎVTe，若P中有产生式A®a，则令d(q0,a)=A(b) 对任意的AÎVN及aÎVTe，若P中所有右端第一符号为A，第二个符号为a的产生式为：A1Aa, , AkAa， 则令d(A,a)=A1,Ak。与(1)类似，

23、可以证明L(G)L(M)。例:GR(A) ：A0 | 0B | 1DB0D | 1CC0 | 0B | 1DD0D | 1D从GR出发构造NFA M = <A, B, C, D, f, 0, 1, d¢, A, f>，M的状态转换图如右图所示。显然 L(M) = L(GR)。3.3.4 正规文法与有限自动机的等价性定理： 1.对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机(FA) M，使得L(M)L(G)。 2.对每一个FA M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)L(GR)L(GL)。证明2：对每一个DFA M，都存在一个右线

24、性正规文法GR和左线性正规文法GL，使得L(M)L(GR)L(GL)。 设DFA M=<S, S, d, s0, F> (1) 若s0ÏF，我们令GR=<S, S, s0, P>，其中P是由以下规则定义的产生式集合：对任何aÎS及A,BÎS，若有d(A,a)=B，则： (a) 当BÏF时，令AaB， (b) 当BÎF时，令Aa|aB。对任何wÎS*，不妨设w=a1ak，其中aiÎS (i=1,k)。若s0 w，则存在一个最左推导： s0Þa1A1Þa1a2A2ÞÞ

25、;a1aiAiÞa1ai+1Ai+1ÞÞa1ak因而，在M中有一条从s0出发依次经过A1，Ak-1到达终态的通路，该通路上所有箭弧的标记依次为a1,ak。反之亦然。所以，wÎL(GR)当且仅当wÎL(M)。q 现在考虑s0ÎF的情形： 因为d(s0, e)=s0，所以eÎL(M)。但e不属于上面构造的GR所产生的语言L(GR)。不难发现，L(GR)=L(M)-e。 所以，我们在上述GR中添加新的非终结符号s0¢，(s0¢ÏS)和产生式s0¢®s0|e，并用s0¢代替

26、s0作开始符号。这样修正GR后得到的文法GR¢仍是右线性正规文法，并且L(GR¢)=L(M)。 (2) 类似于(1)，从DFA M出发可构造左线性正规文法GL，使得L(GL)=L(M)。 最后，由DFA和NFA之间的等价性，结论2得证。例3.4 设DFA M = <A, B, C, D, 0, 1, d, A, B>。M的状态转换图如下图所示。L(M) = 0(10)*GR = <0, 1, A, B, C, D, A, P>，其中P由下列产生式组成：A0 | 0B | 1DB0D | 1CC0 | 0B | 1DD0D | 1DL(GR) = L(

27、M) = 0(10)*例3.4 设DFA M = <A, B, C, D, 0, 1, d, A, B>。M的状态转换图如图3.9(a)所示。从NFA M出发构造左线性正规文法GL = <0, 1, B, C, D, f, f, P¢>，其中P¢由下列产生式组成：f0 | C0CB1B0 | C0D1 | C1 | D0 | D1 | B0易证 L(GL) = L(M)。3.3.5 正规式与有限自动机的等价性定理： 1. 对任何FA M，都存在一个正规式r，使得L(r)=L(M)。 2. 对任何正规式r，都存在一个FA M，使得L(M)=L(r)。2

28、 对转换图概念拓广，令每条弧可用一个正规式作标记。(对一类输入符号)证明： 1 对S上任一NFA M，构造一个S上的正规式r，使得L(r)=L(M)。首先，在M的转换图上加进两个状态X和Y，从X用e弧连接到M的所有初态结点，从M的所有终态结点用e弧连接到Y，从而形成一个新的NFA，记为M，它只有一个初态X和一个终态Y，显然L(M)=L(M)。然后，反复使用下面的一条规则，逐步消去的所有结点，直到只剩下X和Y为止；证明2: 对于S上的正规式r，构造一个NFA M，使L(M)=L(r)，并且M只有一个终态，而且没有从该终态出发的箭弧。 下面使用关于r中运算符数目的归纳法证明上述结论。(1) 若r具

29、有零个运算符，则r=e或r=f或r=a，其中aÎS。此时下图所示的三个有限自动机显然符合上述要求。(2) 假设结论对于少于k(k³1)个运算符的正规式成立。 当r中含有k个运算符时，r有三种情形：l 情形1：r=r1|r2，r1,r2中运算符个数少于k。从而，由归纳假设，对ri存在Mi=<Si, Si, di, qi, fi>，使得L(Mi)=L(ri)，并且Mi没有从终态出发的箭弧（i=1,2）。不妨设S1S2=f，在S1 S2中加入两个新状态q0，f0。 令M=<S1S2q0,f0, S1S2, d, q0, f0>，其中d定义如下：(a) d(

30、q0, e)=q1,q2(b) d(q,a)= d1(q,a), 当qÎS1-f1, aÎS1e(c) d(q,a)= d2(q,a), 当qÎS2-f2, aÎS2e(d) d(f1,e)=d(f2,e)=f0。 M的状态转换如右图所示。 L(M)=L(M1)L(M2) =L(r1)L(r2)=L(r)l 情形2：r=r1r2, 设Mi同情形1(i=1,2)。 令M=<S1S2, S1S2, d, q1, f2>，其中d定义如下：(a) d(q,a)= d1(q,a), 当qÎS1-f1, aÎS1e(b) d(q,a)

31、= d2(q,a), 当qÎS2, aÎS2e(c) d(f1,e)=q2 M的状态转换如右图所示。 L(M)=L(M1)L(M2) =L(r1)L(r2)=L(r)。l 情形3：r=r1*。设M1同情形1。令M=<S1q0, f0, S1, d, q0, f0>，其中q0, f0ÏS1，d定义如下：(a) d(q0,e)=d(f1,e)=q1, f0(b) d(q,a)= d1(q, a), 当qÎS1-f1, aÎS1e。M的状态转换如右图所示。L(M) = L(M1)* = L(r1)* = L(r)至此，结论2获证。1) 构

32、造S上的NFA M 使得 L(V)=L(M)首先，把V表示成逐步把这个图转变为每条弧只标记为S上的一个字符或e，最后得到一个NFA M，显然L(M)=L(V)(a|b)*(aa|bb)(a|b)*3.3.6 确定有限自动机的化简对DFA M的化简:寻找一个状态数比M少的DFA M，使得L(M)=L(M)假设s和t为M的两个状态，称s和t等价:如果从状态s出发能读出某个字a而停止于终态，那么同样，从t出发也能读出a而停止于终态；反之亦然。两个状态不等价，则称它们是可区别的。对一个DFA M最少化的基本思想: 把M的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集的任

33、何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状态。具体做法: 对M的状态集进行划分首先，把S划分为终态和非终态两个子集，形成基本划分P。 假定到某个时候，P已含m个子集，记为P=I(1)，I(2)，¼，I(m)，检查P中的每个子集看是否能进一步划分:对某个I(i)，令I(i)=s1,s2, ¼,sk，若存在一个输入字符a使得Ia(i) 不会包含在现行P的某个子集I(j)中，则至少应把I(i)分为两个部分。例如，假定状态s1和s2经a弧分别到达t1和t2，而t1和t2属于现行P中的两个不同子集，说明有一个字a， t1读出a后到达终态，而t2读出a后不能到达终

34、态，或者反之，那么对于字aa ， s1读出aa后到达终态，而s2读出aa不能到达终态，或者反之，所以s1和s2不等价。则将I(i)分成两半，使得一半含有s1 : I(i1)=s|sÎI(i)且s经a弧到达t, 且t与t1属于现行P中的同一子集 另一半含有s2 : I(i2)=I(i)-I(i1)一般地，对某个a和I(i)，若Ia(i) 落入现行P中 N个不同子集，则应把I(i)划分成N个不相交的组，使得每个组J的Ja都落入的P同一子集。这样构成新的划分。重复上述过程，直到P所含子集数不再增长。对于上述最后划分P中的每个子集，我们选取每个子集I中的一个状态代表其他状态，则可得到化简后的

35、DFA M。若I含有原来的初态，则其代表为新的初态，若I含有原来的终态，则其代表为新的终态。3.4 词法分析器的自动产生-LEXAUXILIARY DEFINITIONletter®A|B|.|Zdigit ®0|1|.|9RECOGNITION RULES1DIM RETURN (1,-) 2IF RETURN (2,-) 3DO RETURN (3,-) 4STOP RETURN (4,-) 5END RETURN (5,-) 6letter(letter|digit) * RETURN (6, TOKEN) 7digit(digit)* RETURN (7, DTB)

36、 8= RETURN (8, -) 9+ RETURN (9,-) 10* RETURN (10,-) 11* RETURN (11,-) 12, RETURN (12,-) 13( RETURN (13,-) 14) RETURN (14,-) LEX的工作过程：首先，对每条识别规则Pi构造一个相应的非确定有限自动机Mi；然后，引进一个新初态X，通过e弧，将这些自动机连接成一个新的NFA；最后，把M确定化、最小化，生成该DFA的状态转换表和控制执行程序作业P64-7，8，12，14 例: 对下图NFA M构造其DFA.编译原理第四章 语法分析自上而下分析第四章 语法分析自上而下分析本章主要介

37、绍语法分析的处理要进行语法分析，必须对语言的语法结构进行描述。采用正规式和有限自动机可以描述和识别语言的单词符号；用上下文无关文法来描述语法规则。上下文无关文法的定义： 一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合(非空)，且VT Ç VN=ÆS：文法的开始符号，SÎVNP：产生式集合(有限)，每个产生式形式为P®a， PÎVN， a Î (VT È VN)*开始符S至少必须在某个产生式的左部出现一次。例，定义只含+，*的算术表达式的文法 G=<i，+，*

38、，(，)，E，E， P>， 其中，P由下列产生式组成：E ® iE ® E+EE ® E*EE ® (E)定义：称aAb直接推出agb，即aAbÞagb 仅当A ® g是一个产生式， 且a， bÎ (VT È VN)* 。如果a1 Þ a2 Þ ¼ Þan，则我们称这个序列是从a1到an的一个推导。若存在一个从a1到an的推导，则称a1可以推导出an 。例：对文法(1)E Þ (E) Þ (E+E)Þ (i+E)Þ (i+i)4.

39、1 语法分析器的功能语法分析的任务是分析一个文法的句子结构。语法分析器的功能：按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子(合式程序)。语法分析的方法：自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。n 算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。n LR分析法：规范归约G(E)： E ® i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i

40、 E+E En 语法分析的方法：¨ 自下而上分析法(Bottom-up)¨ 自上而下分析法(Top-down)n 基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找"匹配"的推导。n 递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。n 预测分析程序F 优点：直观、简单和宜于手工实现。n 4.2 自上而下分析面临的问题n 自上而下就是从文法的开始符号出发，向下推导，推出句子。¨ 带“回溯”的¨ 不带回溯的递归子程序(递归下降)分析方

41、法。n 自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。n 例3.4.1 假定有文法G(S): (1) SxAy (2) A*|* 分析输入串x*y(记为a)。n 当某个非终结符有多个产生式候选时，可能带来如下问题:1. 分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。2. 文法左递归问题。一个文法是含有左递归的，如果存在非终结符Pn 4.3 LL(1)分析法n 构造不带回溯的自上而下分析算法¨ 要消除文法的左递归性¨ 克

42、服回溯n 4.3.1 左递归的消除n 直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为PPa | b 其中b不以P开头。 我们可以把P的规则等价地改写为如下的非直接左递归形式：PbP¢P¢aP¢|en 一般而言，假定P关于的全部产生式是PPa1 | Pa2 | | Pam | b1 | b2|bn其中，每个a都不等于e，每个b都不以P开头 那么，消除P的直接左递归性就是把这些规则改写成： Pb1P¢ | b2P¢ | | bnP¢P¢a1P¢ | a2P¢ | | amP¢ | en

43、例 文法G(E):EET | TTT*F | FF(E) | i经消去直接左递归后变成： ETE¢ E¢+TE¢ | e TFT¢ T¢*FT¢ | e F(E) | in 例如文法G(S):SQc|cQRb|bRSa|a (4.3)虽没有直接左递归，但S、Q、R都是左递归的SÞQcÞRbcÞSabcn 消除左递归的算法:1. 把文法G的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序执行；2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPjg的

44、规则改写成 Pid1g|d2g|dkg ; (其中Pjd1|d2|dk是关于Pj的所有规则) 消除关于Pi规则的直接左递归性 END3. 化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。n 例 考虑文法G(S)SQc|cQRb|bRSa|an 令它的非终结符的排序为R、Q、S。n 对于R，不存在直接左递归。n 把R代入到Q的有关候选后，把Q的规则变为 QSab | ab | bn 例 考虑文法G(S)SQc|cQRb|bRSa|an 令它的非终结符的排序为R、Q、S。n Q的规则变为 QSab | ab | bn 现在的Q不含直接左递归，把它代入到S的有关候选后，S

45、变成SSabc | abc | bc | cn 例 考虑文法G(S)SQc|cQRb|bRSa|an S变成SSabc | abc | bc | cn 消除S的直接左递归后：SabcS¢ | bcS¢ | cS¢S¢abcS¢ | eQSab |ab | bRSa|an 例 考虑文法G(S)SQc|cQRb|bRSa|an 消除S的直接左递归后：SabcS¢ | bcS¢ | cS¢S¢abcS¢ | eQSab |ab | bRSa|an 关于Q和R的规则已是多余的，化简为：SabcS

46、2; | bcS¢ | cS¢S¢abcS¢ | e (4.4)n 注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。n 例如，若对文法(4.3)的非终结符排序选为S、Q、R，那么，最后所得的无左递归文法是：SQc | cQRb | bRbcaR¢ | caR¢ |a R¢ (4.5)R¢ bca R¢ | en 文法(4.4)和(4.5)的等价性是显然的。n 4.3.2 消除回溯、提左因子n 为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，

47、能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。n Aa 1 | a 2 | | a nn 令G是一个不含左递归的文法，对G的所有非终结符的每个候选a定义它的终结首符集FIRST(a)为：n 提取公共左因子: 假定关于A的规则是 Adb 1 | db 2 | | db n | g 1 | g 2 | | gm (其中，每个g 不以d开头) 那么，可以把这些规则改写成AdA¢ | g 1 | g 2 | | g mA¢b 1 | b 2 | | b nn 经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变

48、成为两两不相交。n 4.3.3 LL(1)分析条件n ETE¢ E¢+TE¢ | e TFT¢ T¢*FT¢ | e F(E) | in i + in 4.3.3 LL(1)分析条件n 假定S是文法G的开始符号，对于G的任何非终结符A，我们定义n 对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为Aa 1 | a 2 | | a n1. 若aÎFIRST(a i)，则指派a i执行匹配任务；2. 若a不属于任何一个候选首符集，则： (1)

49、 若e属于某个FIRST(ai )且 aÎFOLLOW(A)， 则让A与e自动匹配。 (2) 否则，a的出现是一种语法错误。n 回顾：LL(1)分析法n 构造不带回溯的自上而下分析算法¨ 要消除文法的左递归性¨ 克服回溯n 一般而言，假定P关于的全部产生式是PPa1 | Pa2 | | Pam | b1 | b2|bn其中，每个a都不等于e，每个b都不以P开头 那么，消除P的直接左递归性就是把这些规则改写成： Pb1P¢ | b2P¢ | | bnP¢P¢a1P¢ | a2P¢ | | amP¢

50、 | en 消除左递归的算法:1. 把文法G的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序执行；2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPjg的规则改写成 Pid1g|d2g|dkg ; (其中Pjd1|d2|dk是关于Pj的所有规则) 消除关于Pi规则的直接左递归性 END3. 化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。n 回顾：LL(1)分析法n 构造不带回溯的自上而下分析算法¨ 要消除文法的左递归性¨ 克服回溯n 4.3.2 消除回溯、提左因子n 为了消除回溯就必

51、须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。n Aa 1 | a 2 | | a nn 令G是一个不含左递归的文法，对G的所有非终结符的每个候选a定义它的终结首符集FIRST(a)为：n 提取公共左因子: 假定关于A的规则是 Adb 1 | db 2 | | db n | g 1 | g 2 | | gm (其中，每个g 不以d开头) 那么，可以把这些规则改写成AdA¢ | g 1 | g 2 | | g mA¢b 1 | b 2 | | b nn 经过反复提取左因子，就

52、能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。n FOLLOW定义n 假定S是文法G的开始符号，对于G的任何非终结符A，我们定义n 对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为Aa 1 | a 2 | | a n1. 若aÎFIRST(a i)，则指派a i执行匹配任务；2. 若a不属于任何一个候选首符集，则： (1) 若e属于某个FIRST(ai )且 aÎFOLLOW(A)， 则让A与e自动匹配。 (2) 否则，a的出现是一种语法错误。构造FIRST(a)

53、n 对每一文法符号XÎVTVN构造FIRST(X) 连续使用下面的规则，直至每个集合FIRST不再增大为止：1. 若XÎVT，则FIRST(X)X。2. 若XÎVN，且有产生式Xa，则把a加入到FIRST(X)中；若Xe也是一条产生式，则把e也加到FIRST(X)中。3. l 若XY是一个产生式且YÎVN，则把FIRST(Y)中的所有非e-元素都加到FIRST(X)中；l 若XY1Y2Yk是一个产生式，Y1，Yi-1都是非终结符，而且，对于任何j，1£j£i-1，FIRST(Yj)都含有e(即Y1Yi-1e)， 则把FIRST(Yi)

54、中的所有非e-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有e，j1，2，k，则把e加到FIRST(X)中。n 对文法G的任何符号串a=X1X2Xn构造集合FIRST(a)。1. 置FIRST(a)FIRST(X1)e；2. 若对任何1£j£i-1，eÎFIRST(Xj)，则把FIRST(Xi)e加至FIRST(a)中；特别是，若所有的FIRST(Xj)均含有e，1£j£n，则把e也加至FIRST(a)中。显然，若ae则FIRST(a)e。构造FOLLOW(A)n 对于文法G的每个非终结符A构造FOLLOW(A)的办法是，连续使用下面的规则，直至每个FOLLOW不再增大为止：1. 对于文法的开始符号S，置于FOLLOW(S)中；2. 若AaBb是一个产生式，则把FIRST(b)e加至FOLLOW(B)中；n 例4.6 对于文法G(E)ETE¢E¢+TE¢ | eTFT¢ T¢*FT¢ | eF(E) | i构造每个非终结符的FIRST和FOLLOW集合：n 4.4 递归下降分析程序构造n 构造不带回溯的自上而下分析程序¨ 要消除文法的左递归性¨ 克服回溯n 构造不带回溯的自上而下分析器n