编译原理课程总复习.ppt-淘文阁

资源描述

《编译原理课程总复习.ppt》由会员分享，可在线阅读，更多相关《编译原理课程总复习.ppt（135页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、编译原理课程总复习贾棋前端：依赖于源语前端：依赖于源语前端：依赖于源语前端：依赖于源语言，独立于目标机言，独立于目标机言，独立于目标机言，独立于目标机器。器。器。器。词法分析器词法分析器词法分析器词法分析器语法分析器语法分析器语法分析器语法分析器语义分析器语义分析器语义分析器语义分析器源程序源程序源程序源程序中间代码生成器中间代码生成器中间代码生成器中间代码生成器代码优化器代码优化器代码优化器代码优化器代码生成器代码生成器代码生成器代码生成器目标程序目标程序目标程序目标程序出错管理器出错管理器出错管理器出错管理器符号表管理器符号表管理器符号表管理器符号表管理器前端前端后端后端后端：依赖于后端

2、：依赖于后端：依赖于后端：依赖于目标机器，独目标机器，独目标机器，独目标机器，独立于源语言。立于源语言。立于源语言。立于源语言。第二章词法分析器词法分析器词法分析器记号（记号（token）流）流源代码源代码词法分析器工作原理词法分析器工作原理词法分析器工作原理词法分析器工作原理：源程序源程序字符流字符流顺序顺序顺序顺序组合组合组合组合词法词法单元单元词法词法记号记号模式模式模式模式非形式非形式化描述化描述形式化形式化描述描述正规式正规式字母字母组合组合组合组合串串语言语言集合集合集合集合集合集合集合集合字母表字母表名名字字词法记号的描述与识别 n n正规式的例子正规式的例子 =a a,b b

4、l语言的标识符集合语言的标识符集合letter A|B|Z|a|b|zdigit 0|1|9id letter(letter|digit)*n n正规定义的例子正规定义的例子PascalPascal无符号数集合，例无符号数集合，例无符号数集合，例无符号数集合，例19461946,11.2811.28,63.6E863.6E8,1.99E1.99E 6 6 digitdigit 0 0|1|9|1|9digitsdigits digitdigit digitdigit*optional_fractionoptional_fraction .digitsdigits|optional_expone

5、ntoptional_exponent (E(+|(E(+|)digits)|)digits)|numnumdigitsdigits optional_fractionoptional_fraction optional_exponentoptional_exponent简化表示简化表示简化表示简化表示numnum digitdigit+(.digitdigit+)?(E(+|)?(E(+|)?digit)?digit+)?)?简化规则：简化规则：简化规则：简化规则：(1)r+=rr*(2)r?=r|(3)a-z=a|b|c|z(4)abc=a|b|c源程序源程序字符流字符流顺序顺序顺序顺序组

6、合组合组合组合词法词法单元单元词法词法记号记号模式模式模式模式非形式非形式化描述化描述形式化形式化描述描述正规式正规式字母字母组合组合组合组合串串语言语言集合集合集合集合集合集合集合集合字母表字母表名名字字连接连接连接连接指数指数指数指数和和和和 L LU UMM连接连接连接连接 LMLM闭包闭包闭包闭包 L L*正闭包正闭包正闭包正闭包 L L+?计算机计算机计算机计算机实现实现实现实现状态状态状态状态转换转换转换转换图图图图状态转换图转换图转换图关系算符的转换图关系算符的转换图关系算符的转换图关系算符的转换图051624837return(relop,LE)return(relop,

7、NE)return(relop,LT)return(relop,GE)return(relop,GT)return(relop,EQ)开始开始=*otherotherreloprelop|=|=|=有限自动机正规式正规式计算机计算机计算机计算机实现实现实现实现状态转换图状态转换图？有限自动机有限自动机有限自动机有限自动机不确定有不确定有不确定有不确定有限自动机限自动机限自动机限自动机确定有限确定有限确定有限确定有限自动机自动机自动机自动机等价等价等价等价有限自动机不确定的有限自动机（简称不确定的有限自动机（简称NFA）一个数学模型，它包括一个数学模型，它包括一个数学模型，它

8、包括一个数学模型，它包括:n n 状态集合状态集合状态集合状态集合S S；n n 输入符号集合输入符号集合输入符号集合输入符号集合；n n 转换函数转换函数转换函数转换函数movemove:S S ()P P(S S)；n n 状态状态状态状态s s0 0是开始状态；是开始状态；是开始状态；是开始状态；n n F F S S是接受状态集合是接受状态集合是接受状态集合是接受状态集合。12开始开始a0abb识别语言识别语言识别语言识别语言(a a|b b)*abab 的的的的NFANFA缺点：缺点：缺点：缺点：1 1、输入字、输入字、输入字、输入字符包括符包括符包括符包括 2 2、一个状态对于、

9、一个状态对于、一个状态对于、一个状态对于某个字符，可能有某个字符，可能有某个字符，可能有某个字符，可能有多条输出边多条输出边多条输出边多条输出边有限自动机确定的有限自动机（简称确定的有限自动机（简称DFA)一个数学模型，包括：一个数学模型，包括：状态集合状态集合状态集合状态集合S S；输入字母表输入字母表输入字母表输入字母表；转换函数转换函数转换函数转换函数move move:S S S S；唯一的初态唯一的初态唯一的初态唯一的初态 s s S S；终态集合终态集合终态集合终态集合F F S S；12开始开始a0abbab识别语言识别语言识别语言识别语言(a a|b b)*abab

10、的的的的DFADFA优点：优点：优点：优点：1 1、输入字、输入字、输入字、输入字符不包括符不包括符不包括符不包括 2 2、一个状态对于、一个状态对于、一个状态对于、一个状态对于某个字符，只可能某个字符，只可能某个字符，只可能某个字符，只可能存在唯一条输出边存在唯一条输出边存在唯一条输出边存在唯一条输出边NFA到DFA的转换子集构造法子集构造法19开始开始 0ab ab6782345 输入符号输入符号输入符号输入符号a ab b状态状态状态状态 NFA到DFA的转换子集构造法子集构造法19开始开始 0ab ab6782345 输入符号输入符号输入符号输入符号a ab bA A状态状态状态状态

11、A A=0,1,2,4,7=0,1,2,4,7DFADFA中第一个状态由中第一个状态由中第一个状态由中第一个状态由NFANFA中的开始状态求中的开始状态求中的开始状态求中的开始状态求闭包得到闭包得到闭包得到闭包得到NFA到DFA的转换子集构造法子集构造法19开始开始 0ab ab6782345 输入符号输入符号输入符号输入符号a ab bA AB B状态状态状态状态 A A=0,1,2,4,7 =0,1,2,4,7 B B=1,2,3,4,6,7,8 =1,2,3,4,6,7,8 NFA到DFA的转换子集构造法子集构造法19开始开始 0ab ab6782345 输入符号输入符号输入符号输入符

12、号a ab bA AB BB B状态状态状态状态 A A=0,1,2,4,7 =0,1,2,4,7 B B=1,2,3,4,6,7,8 =1,2,3,4,6,7,8 NFA到DFA的转换子集构造法子集构造法19开始开始 0ab ab6782345 输入符号输入符号输入符号输入符号a ab bA AB BC CB B状态状态状态状态 A A=0,1,2,4,7 =0,1,2,4,7 B B=1,2,3,4,6,7,8 =1,2,3,4,6,7,8 C C=1,2,4,5,6,7 =1,2,4,5,6,7 NFA到DFA的转换子集构造法子集构造法19开始开始 0ab ab6782345 输入符号输

13、入符号输入符号输入符号a ab bA AB BC CB BC C状态状态状态状态 A A=0,1,2,4,7 =0,1,2,4,7 B B=1,2,3,4,6,7,8 =1,2,3,4,6,7,8 C C=1,2,4,5,6,7 =1,2,4,5,6,7 NFA到DFA的转换子集构造法子集构造法19开始开始 0ab ab6782345 输入符号输入符号输入符号输入符号a ab bA AB BC CB BB BC C状态状态状态状态 A A=0,1,2,4,7 =0,1,2,4,7 B B=1,2,3,4,6,7,8 =1,2,3,4,6,7,8 C C=1,2,4,5,6,7 =1,2,4,5

14、,6,7 NFA到DFA的转换子集构造法子集构造法19开始开始 0ab ab6782345 输入符号输入符号输入符号输入符号a ab bA AB BC CB BB BD DC C状态状态状态状态 A A=0,1,2,4,7 =0,1,2,4,7 B B=1,2,3,4,6,7,8 =1,2,3,4,6,7,8 C C=1,2,4,5,6,7 =1,2,4,5,6,7 D D=1,2,4,5,6,7,9 =1,2,4,5,6,7,9 NFA到DFA的转换子集构造法子集构造法19开始开始 0ab ab6782345 输入符号输入符号输入符号输入符号a ab bA AB BC CB BB BD DC

15、 CD D状态状态状态状态 A A=0,1,2,4,7 =0,1,2,4,7 B B=1,2,3,4,6,7,8 =1,2,3,4,6,7,8 C C=1,2,4,5,6,7 =1,2,4,5,6,7 D D=1,2,4,5,6,7,9 =1,2,4,5,6,7,9 NFA到DFA的转换子集构造法子集构造法19开始开始 0ab ab6782345 输入符号输入符号输入符号输入符号a ab bA AB BC CB BB BD DC CB BC CD D状态状态状态状态 A A=0,1,2,4,7 =0,1,2,4,7 B B=1,2,3,4,6,7,8 =1,2,3,4,6,7,8 C C=1,

16、2,4,5,6,7 =1,2,4,5,6,7 D D=1,2,4,5,6,7,9 =1,2,4,5,6,7,9 NFA到DFA的转换子集构造法子集构造法19开始开始 0ab ab6782345 输入符号输入符号输入符号输入符号a ab bA AB BC CB BB BD DC CB BC CD DB BC C状态状态状态状态 A A=0,1,2,4,7 =0,1,2,4,7 B B=1,2,3,4,6,7,8 =1,2,3,4,6,7,8 C C=1,2,4,5,6,7 =1,2,4,5,6,7 D D=1,2,4,5,6,7,9 =1,2,4,5,6,7,9 只要含有只要含有只要含有只要含有

17、NFANFA中终结中终结中终结中终结状态就标志为状态就标志为状态就标志为状态就标志为DFADFA的终结的终结的终结的终结状态状态状态状态NFA到DFA的转换BD开始开始aAabbabCba19开始开始 0ab ab6782345 输入符号输入符号输入符号输入符号a ab bA AB BC CB BB BD DC CB BC CD DB BC C状态状态状态状态 12开始开始a0abbabDFA的化简的化简BD开始开始aAabbaa,bCbaEbqq死状态死状态死状态死状态左图无须加死状态，右图加入死状态左图无须加死状态，右图加入死状态左图无须加死状态，右图加入死状态左图无须加死状态，右图加入死

18、状态E E。BD开始开始aAabbabCbaDFA的化简的化简可区别的状态可区别的状态A A和和和和B B是可区别的状态是可区别的状态是可区别的状态是可区别的状态A A和和和和C C是不可区别的状态是不可区别的状态是不可区别的状态是不可区别的状态BD开始开始aAabbabCbaDFA的化简的化简方法方法1.A,B,C,D1.A,B,C,Dmovemove(A(A,B,C,B,C,a a=B=Bmovemove(A(A,B,C,B,C,b b=C,D=C,D2.A,C,B,D2.A,C,B,Dmovemove(A(A,C,C,a a=B=Bmovemove(A(A,C,C,b b=C=CBD开始

19、开始aAabbabCba初始划分为接受初始划分为接受初始划分为接受初始划分为接受状态子集和非接状态子集和非接状态子集和非接状态子集和非接收状态子集收状态子集收状态子集收状态子集划分完毕之后如果有死状态，将划分完毕之后如果有死状态，将划分完毕之后如果有死状态，将划分完毕之后如果有死状态，将其删掉，从开始状态不可及的状其删掉，从开始状态不可及的状其删掉，从开始状态不可及的状其删掉，从开始状态不可及的状态也删除态也删除态也删除态也删除DFA的化简的化简方法方法1.A,B,C,D1.A,B,C,Dmovemove(A(A,B,C,B,C,a a=B=Bmovemove(A(A,B,C,B,C,b b=

20、C,D=C,D2.A,C,B,D2.A,C,B,Dmovemove(A(A,C,C,a a=B=Bmovemove(A(A,C,C,b b=C=CBD开始开始aAabbabCba12开始开始a0abbabn n将下图的将下图的将下图的将下图的DFADFA极小化。极小化。极小化。极小化。a aa astartstart0 01 12 23 3a ab bb bb bb bb b4 4DFADFA0123aabbabbbstart45aaa,b加入死状态后的加入死状态后的加入死状态后的加入死状态后的DFADFA1 1、加入死状态、加入死状态、加入死状态、加入死状态2 2、合并不可区分状态、合并不可

21、区分状态、合并不可区分状态、合并不可区分状态先把状态集分成非接受状态集先把状态集分成非接受状态集先把状态集分成非接受状态集先把状态集分成非接受状态集0,1,2,3,50,1,2,3,5和接受状态集和接受状态集和接受状态集和接受状态集44这两个子集。这两个子集。这两个子集。这两个子集。1 1集合集合集合集合44不能再分解，我们看集合不能再分解，我们看集合不能再分解，我们看集合不能再分解，我们看集合0,1,2,3,50,1,2,3,5。move move(0,1,2,3,5,a)=1,2,5(0,1,2,3,5,a)=1,2,5 move move(0,1,2,3,5,b)=3,4,5(0,1,2

22、,3,5,b)=3,4,5由于由于由于由于b b 转换的结果转换的结果转换的结果转换的结果3,4,53,4,5不是最初划分的某个集合的子集，因此不是最初划分的某个集合的子集，因此不是最初划分的某个集合的子集，因此不是最初划分的某个集合的子集，因此0,1,2,3,50,1,2,3,5需要需要需要需要再分，由于状态再分，由于状态再分，由于状态再分，由于状态1 1和状态和状态和状态和状态2 2的的的的b b转换都到状态转换都到状态转换都到状态转换都到状态4 4。因此状态集合的进一步划分是：。因此状态集合的进一步划分是：。因此状态集合的进一步划分是：。因此状态集合的进一步划分是：1,21,2，0,3,

23、50,3,5和和和和442 2由于由于由于由于move move(1,2,a)=2,5(1,2,a)=2,5 move move(1,2,b)=4(1,2,b)=4move move(0,3,5,a)=1,5 (0,3,5,a)=1,5 move move(0,3,5,b)=3,5(0,3,5,b)=3,5显然显然显然显然1,21,2和和和和0,3,50,3,5需要再分，分别分成：需要再分，分别分成：需要再分，分别分成：需要再分，分别分成：11和和和和22以及以及以及以及0,30,3和和和和553 3由于由于由于由于move move(0,3,a)=1(0,3,a)=1 move move(0

24、,3,b)=3(0,3,b)=3因此不需要再分。这样状态因此不需要再分。这样状态因此不需要再分。这样状态因此不需要再分。这样状态0 0和状态和状态和状态和状态3 3合并成一个状态，我们取合并成一个状态，我们取合并成一个状态，我们取合并成一个状态，我们取0 0为代表，再删去死状态为代表，再删去死状态为代表，再删去死状态为代表，再删去死状态5 5，就得到该题的结果。，就得到该题的结果。，就得到该题的结果。，就得到该题的结果。正确做法！正确做法！正确做法！正确做法！012bbbb4aastart最简最简DFAn n最初的划分是最初的划分是最初的划分是最初的划分是0,1,2,30,1,2,3和和和和4

25、4。n n1 1状态集合的进一步划分是：状态集合的进一步划分是：状态集合的进一步划分是：状态集合的进一步划分是：n n1,21,2，0,30,3和和和和44 n n2 2忽略了死状态的影响，会认为它们都不需要再分忽略了死状态的影响，会认为它们都不需要再分忽略了死状态的影响，会认为它们都不需要再分忽略了死状态的影响，会认为它们都不需要再分错误做法！错误做法！错误做法！错误做法！1 1、直接合并不可区分状态、直接合并不可区分状态、直接合并不可区分状态、直接合并不可区分状态0 01 1b bb ba aa astartstarta a4 4一个不正确的结果一个不正确的结果一个不正确的结果一个不正确

26、的结果a aa astartstart0 01 12 23 3a ab bb bb bb bb b4 4DFADFA从正规式到有限自动机正规式正规式计算机计算机计算机计算机实现实现实现实现状态转换图状态转换图有限自动机有限自动机有限自动机有限自动机不确定有不确定有不确定有不确定有限自动机限自动机限自动机限自动机确定有限确定有限确定有限确定有限自动机自动机自动机自动机等价等价等价等价？从正规式到有限自动机 19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a a|b b)*abab的分解的分解的分解的分解从正规式到有限自动机 19开始开始 0ab

28、bab的分解的分解的分解的分解从正规式到有限自动机19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a a|b b)*abab的分解的分解的分解的分解从正规式到有限自动机 19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a a|b b)*abab的分解的分解的分解的分解从正规式到有限自动机 (a|b)*ab的两个的两个NFA的比较的比较12开始开始a0abb19开始开始 0ab ab6782345 从语言到确定的有限自动机n n例：识别例：识别 =0,1上能被上能被5整除的二进制数整除的二进制数012

29、3开始开始4方法：方法：方法：方法：1 1、列出全部可能的状态、列出全部可能的状态、列出全部可能的状态、列出全部可能的状态2 2、从各个状态出发，构造边及输入字符记号、从各个状态出发，构造边及输入字符记号、从各个状态出发，构造边及输入字符记号、从各个状态出发，构造边及输入字符记号n n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始40从语言到确定的有限自动机n n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始410从语言到确定的有限自动机n n例：识别例：识别 =0,1上能被能上能被能5整除的二

30、进制数整除的二进制数0123开始开始4100从语言到确定的有限自动机n n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始41001从语言到确定的有限自动机n n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始410010从语言到确定的有限自动机n n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始4100101从语言到确定的有限自动机n n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始41001010

31、从语言到确定的有限自动机n n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始410010101从语言到确定的有限自动机n n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始4100101010从语言到确定的有限自动机n n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始41001010101从语言到确定的有限自动机n n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始41001010101从语言到确定的

32、有限自动机构造构造DFA,接受接受 0和和1的个数都是偶数的字符串的个数都是偶数的字符串312011110000开始开始偶偶0偶偶1奇奇0奇奇1奇奇0偶偶1偶偶0奇奇1从语言到确定的有限自动机小结正规式正规式计算机计算机计算机计算机实现实现实现实现状态转换图状态转换图不确定有不确定有不确定有不确定有限自动机限自动机限自动机限自动机确定有限确定有限确定有限确定有限自动机自动机自动机自动机等价等价等价等价用正规式语法结构来指导构造过程用正规式语法结构来指导构造过程用正规式语法结构来指导构造过程用正规式语法结构来指导构造过程子集构造法子集构造法子集构造法子集构造法合并不可区别状态合并

33、不可区别状态合并不可区别状态合并不可区别状态最简确定最简确定最简确定最简确定有限自动有限自动有限自动有限自动机机机机等价等价等价等价语言语言语言语言确定有限确定有限确定有限确定有限自动机自动机自动机自动机状态列举法状态列举法状态列举法状态列举法第三章语法分析器n n主要内容主要内容qq上下文无关文法上下文无关文法上下文无关文法上下文无关文法qq自上而下分析和自下而上分析自上而下分析和自下而上分析自上而下分析和自下而上分析自上而下分析和自下而上分析上下文无关文法与正规式比较上下文无关文法与正规式比较上下文无关文法上下文无关文法上下文无关文法上下文无关文法qE E A E|(E)|E|idqA

34、+|*正规式定义正规式定义正规式定义正规式定义qletter A-Za-zqdigit 0-9qid letter(letter|digit)*p上下文无关文法是一个四元组上下文无关文法是一个四元组上下文无关文法是一个四元组上下文无关文法是一个四元组p最左推到、最右推导最左推到、最右推导最左推到、最右推导最左推到、最右推导p二义性二义性二义性二义性语言和文法消除左递归消除左递归n n文法文法左递归左递归A+A n n直接左递归直接左递归AA|q串的特点串的特点 .n n消除直接左递归消除直接左递归A A A A|语言和文法 n n非直接左递归非直接左递归S Aa|b A Sd|n n先变换成

36、义性左递归左递归左递归左递归消除左递归消除左递归消除左递归消除左递归左因子左因子左因子左因子消除左因子消除左因子消除左因子消除左因子A 1|2A+Aa 0 0型文法型文法型文法型文法1 1型文法型文法型文法型文法2 2型文法型文法型文法型文法3 3型文法型文法型文法型文法FIRST集、FOLLOW集qqFIRST(FIRST()=)=a a|*a a,a a V VT T 特别是，特别是，特别是，特别是，*时，规定时，规定时，规定时，规定 FIRST(FIRST()qqFOLLOW(FOLLOW(A A)=)=a a|S S *AaAa，a a V VT T 如如如如果果果果 A A是是是是

37、某某某某个个个个句句句句型型型型的的的的最最最最右右右右符符符符号号号号，那那那那么么么么$属属属属于于于于FOLLOW(FOLLOW(A A)n nFIRSTFIRST集合计算方法集合计算方法集合计算方法集合计算方法qq若若若若X Xa a.，则将终结符加入则将终结符加入则将终结符加入则将终结符加入FIRST(X)FIRST(X)中中中中qq若若若若X X ，则将，则将，则将，则将加入加入加入加入FIRST(X)FIRST(X)中中中中qq若若若若X XYY，且，且，且，且Y Y属于非终结符，则将属于非终结符，则将属于非终结符，则将属于非终结符，则将FIRST(Y)F

38、IRST(Y)加加加加入到入到入到入到FIRST(X)FIRST(X)中中中中qq若若若若X XY1Y2.YK,Y1Y2.YK,且且且且Y1,Y2,.Yi-1Y1,Y2,.Yi-1都是非终结符，且都是非终结符，且都是非终结符，且都是非终结符，且Y1,Y2,.Yi-1Y1,Y2,.Yi-1的的的的FIRSTFIRST集合中均包含集合中均包含集合中均包含集合中均包含，则将，则将，则将，则将FIRST(YFIRST(Yj j)的的的的所有非所有非所有非所有非元素加入到元素加入到元素加入到元素加入到FIRST(X)FIRST(X)中，（中，（中，（中，（j j=1,2,.i=1,2,.i）.特别地

39、，特别地，特别地，特别地，若若若若Y1YKY1YK均有均有均有均有产生式，则将产生式，则将产生式，则将产生式，则将加到加到加到加到FIRST(X)FIRST(X)中。中。中。中。FIRST集合及集合及FOLLOW集合的计算方法集合的计算方法n nFOLLOWFOLLOW集合计算方法集合计算方法集合计算方法集合计算方法qq对文法开始符号对文法开始符号对文法开始符号对文法开始符号S,S,置置置置$于于于于FOLLOW(S)FOLLOW(S)中。中。中。中。qq若有若有若有若有A A B B ，则将，则将，则将，则将FIRST(FIRST()加入加入加入加入FOLLOW(B)FOLLOW(B)中

40、。中。中。中。（此处（此处（此处（此处可以为空可以为空可以为空可以为空）qq若若若若A A B B 或或或或A A B B ,且且且且 *（即（即（即（即属于属于属于属于FIRST(FIRST()）,则将则将则将则将 FOLLOW(A)FOLLOW(A)加入加入加入加入FOLLOW(B)FOLLOW(B)中中中中（此处（此处（此处（此处可以为空可以为空可以为空可以为空）。FIRST集合及集合及FOLLOW集合的计算方法集合的计算方法FIRST集合及集合及FOLLOW集合的计算方法集合的计算方法例例例例 E E TE TE E E +TE TE|T T FT FT T T *FT FT|F

42、T T)=FIRST()=FIRST(F F)=(,id)=(,id FIRST(FIRST(E E )=+,)=+,FIRST集合及集合及FOLLOW集合的计算方法集合的计算方法例例例例 E E TE TE E E +TE TE|T T FT FT T T *FT FT|F F (E E)|id)|idFIRST(FIRST(E E)=FIRST()=FIRST(T T)=FIRST()=FIRST(F F)=(,id)=(,id FIRST(FIRST(E E )=+,)=+,FRIST(FRIST(T T )=)=*,FIRST集合及集合及FOLLOW集合的计算方法集合的计算方法例例例例

43、 E E TE TE E E +TE TE|T T FT FT T T *FT FT|F F (E E)|id)|idFIRST(FIRST(E E)=FIRST()=FIRST(T T)=FIRST()=FIRST(F F)=(,id)=(,id FIRST(FIRST(E E )=+,)=+,FRIST(FRIST(T T )=)=*,FOLLOW(FOLLOW(E E)=FOLLOW()=FOLLOW(E E )=),$)=),$FIRST集合及集合及FOLLOW集合的计算方法集合的计算方法例例例例 E E TE TE E E +TE TE|T T FT FT T T *FT FT|F

44、F (E E)|id)|idFIRST(FIRST(E E)=FIRST()=FIRST(T T)=FIRST()=FIRST(F F)=(,id)=(,id FIRST(FIRST(E E )=+,)=+,FRIST(FRIST(T T )=)=*,FOLLOW(FOLLOW(E E)=FOLLOW()=FOLLOW(E E )=),$)=),$FOLLOW(FOLLOW(T T)=FOLLOW()=FOLLOW(T T )=+,),$)=+,),$FIRST集合及集合及FOLLOW集合的计算方法集合的计算方法例例例例 E E TE TE E E +TE TE|T T FT FT T T *

45、FT FT|F F (E E)|id)|idFIRST(FIRST(E E)=FIRST()=FIRST(T T)=FIRST()=FIRST(F F)=(,id)=(,id FIRST(FIRST(E E )=+,)=+,FRIST(FRIST(T T )=)=*,FOLLOW(FOLLOW(E E)=FOLLOW()=FOLLOW(E E )=),$)=),$FOLLOW(FOLLOW(T T)=FOLLOW()=FOLLOW(T T )=+,),$)=+,),$FOLLOW(FOLLOW(F F)=+,)=+,*,),$,),$自上而下分析 n nLL(1)文法文法任何两个产生式任何两个

46、产生式A|都满足下列条件：都满足下列条件：qq FIRST(FIRST()FIRST(FIRST()=)=qq若若若若 *，那么，那么，那么，那么FIRST(FIRST()FOLLOW(FOLLOW(A A)=)=LL(1)LL(1)文法有一些明显的性质文法有一些明显的性质文法有一些明显的性质文法有一些明显的性质没有公共左因子没有公共左因子没有公共左因子没有公共左因子不是二义的不是二义的不是二义的不是二义的不含左递归不含左递归不含左递归不含左递归自上而下分析非递归的预测分析非递归的预测分析a a+b b$输入输入预测分析程序预测分析程序分析表分析表M输出输出 X XY YZ Z$栈栈自上而下分

47、析非终非终非终非终结符结符结符结符输输输输入入入入符符符符号号号号 id id+*.E E E E TE TE E E E E +TE TE T T T T FT FT T T T T T T *FT FT F F F F id id 自上而下分析栈栈栈栈输输输输入入入入输输输输出出出出$E E id id*id+id$id+id$预测预测预测预测分析器接受输入分析器接受输入分析器接受输入分析器接受输入id id*id+id id+id的动作的动作的动作的动作自上而下分析栈栈栈栈输输输输入入入入输输输输出出出出$E E id id*id+id$id+id$E E T T

48、 id id*id+id$id+id$E E TE TE 预测预测预测预测分析器接受输入分析器接受输入分析器接受输入分析器接受输入id id*id+id id+id的动作的动作的动作的动作自上而下分析栈栈栈栈输输输输入入入入输输输输出出出出$E E id id*id+id$id+id$E E T T id id*id+id$id+id$E E TE TE$E E T T F F id id*id+id$id+id$T T FT FT 预测预测预测预测分析器接受输入分析器接受输入分析器接受输入分析器接受输入id id*id+id id+id的动作的动作的动作的动作自上而下分析栈栈栈栈

49、输输输输入入入入输输输输出出出出$E E id id*id+id$id+id$E E T T id id*id+id$id+id$E E TE TE$E E T T F F id id*id+id$id+id$T T FT FT$E E T T id id id id*id+id$id+id$F F id id 预测预测预测预测分析器接受输入分析器接受输入分析器接受输入分析器接受输入id id*id+id id+id的动作的动作的动作的动作自上而下分析构造预测分析表构造预测分析表（1 1）对文法的每个产生式对文法的每个产生式对文法的每个产生式对文法的每个产生式A A ，执行执行执行执

50、行(2)(2)和和和和(3)(3)。（2 2）对对对对FIRST(FIRST()的的的的每每每每个个个个终终终终结结结结符符符符a a，把把把把A A 加加加加入入入入MM A A,a a。（3 3）如如如如果果果果在在在在FIRST(FIRST()中中中中，对对对对FOLLOW(FOLLOW(A A)的的的的每每每每个个个个终终终终结结结结符符符符b b（包括包括包括包括$）,把把把把A A 加入加入加入加入MM A A,b b。（4 4）MM的其它没有定义的条目都是的其它没有定义的条目都是的其它没有定义的条目都是的其它没有定义的条目都是errorerror。自上而下分析非终非终非终非终结

展开阅读全文