编译原理4自顶向下的语法分析

1、Part4Part4语法分析语法分析 授课：胡静授课：胡静 语法分析器的作用语法分析器的作用 以语法分析器为核心的编译器模型以语法分析器为核心的编译器模型 语法分语法分 析器析器 词法分词法分 析器析器 中间代码中间代码 生成器生成器 语义分析器语义分析器 一部分中一部分中 间代码间代码 输入字输入字 符串符串 程序入口程序入口 初始化工作初始化工作 语法分析器所处的位置语法分析器所处的位置 语法分析的例子语法分析的例子 语法分析的类比语法分析的类比 针对自然语言的语法分析：针对自然语言的语法分析： 识别一个句子是不是符合语法规范识别一个句子是不是符合语法规范 BEGIN T; WHILE S

2、YM = + DO BEGIN ADVANCE; T END END PROCEDURE T; BEGIN F; WHILE SYM = * DO BEGIN ADVANCE; F END END LL(1)LL(1)分析法分析法 消除直接左递归消除直接左递归改写成右递归改写成右递归 直接左递归的消除直接左递归的消除 PP | PP PP | EE+T | T TT*F | F F(E) | i ETE E+TE | TFT T*FT | F(E) | i 消除左递归的一般算法消除左递归的一般算法 如果一个文法不含回路（形如如果一个文法不含回路（形如P=+P的推导），也的推导），也 不含以不含

3、以为右部的产生式，那么执行下述算法将保证为右部的产生式，那么执行下述算法将保证 消除左递归（但改写后的文法可能含有消除左递归（但改写后的文法可能含有为右部的产为右部的产 生式）。生式）。 消除左递归的算法消除左递归的算法 消除左递归的例子消除左递归的例子 RSa | a QRb | b SQc |c RSa |a QSab | ab | b SSabc | abc | bc | c SabcS | bcS | cS SabcS | RSa |a QSab | ab | b SabcS | bcS | cS SabcS | SQc | c QRb | b RbcaR |caR | aR Rbca

4、R | 回溯问题回溯问题 消除回溯、提取左因子消除回溯、提取左因子 令是一个不含左递归的文法，对令是一个不含左递归的文法，对G的所有非终结符的每个候的所有非终结符的每个候 选选定义它的终结首符集定义它的终结首符集FIRST()为：为： FIRST()=a | =*a, aVT 若若=*，则规定，则规定FIRST() FIRST()是是的所有可能推导的开头终结符或可能的的所有可能推导的开头终结符或可能的 如果非终结符的所有候选首符集两两不相交，即的任何如果非终结符的所有候选首符集两两不相交，即的任何 两个不同候选两个不同候选i和和 FIRST(i) FIRST(j)= 那么当要求匹配输入串时，就

5、能根据它所面临的第一个那么当要求匹配输入串时，就能根据它所面临的第一个 输入符号，准确的指派某一个候选前去执行任务。这个候输入符号，准确的指派某一个候选前去执行任务。这个候 选就是那个终结首符集含的选就是那个终结首符集含的。 消除回溯、提取左因子消除回溯、提取左因子 提取左因子的方法提取左因子的方法 假定的规则是：假定的规则是： 1 |2 | |n |1 |2 | |m （其中，每个（其中，每个不以不以开头）开头） 那么这些规则可以改写为：那么这些规则可以改写为： AA |1 |2 | |m A1 |2 | |n 经过反复提取左因子，就能够把每个非终结符（包括新引进经过反复提取左因子，就能够把

6、每个非终结符（包括新引进 者）的所有候选首符集便成为两两不相交。我们为此要付出者）的所有候选首符集便成为两两不相交。我们为此要付出 的代价是大量引进新的非终结符和的代价是大量引进新的非终结符和产生式。产生式。 消除回溯、提取左因子消除回溯、提取左因子 提取左因子的方法提取左因子的方法 假定的规则是：假定的规则是： 1 |2 | |n |1 |2 | |m （其中，每个（其中，每个不以不以开头）开头） 那么这些规则可以改写为：那么这些规则可以改写为： AA |1 |2 | |m A1 |2 | |n 经过反复提取左因子，就能够把每个非终结符（包括新引进经过反复提取左因子，就能够把每个非终结符（包

7、括新引进 者）的所有候选首符集便成为两两不相交。我们为此要付出者）的所有候选首符集便成为两两不相交。我们为此要付出 的代价是大量引进新的非终结符和的代价是大量引进新的非终结符和产生式。产生式。 LL(1)LL(1)分析条件分析条件 ETE E+TE | TFT T*FT | F(E) | i 对输入串对输入串i+i进行自顶向下分析进行自顶向下分析 E i + i IP T E iFIRST(TE) E i + i IP TE iFIRST(FT) F T E i + i IP TE iFIRST(i) F T i LL(1)LL(1)分析条件分析条件 ETE E+TE | TFT T*FT |

8、 F(E) | i 对输入串对输入串i+i进行自顶向下分析进行自顶向下分析 E i + i IP TE +不属于不属于T的任一候选式的首符集的任一候选式的首符集 F T i E T E FT i +T E FT i LL(1)LL(1)分析条件分析条件 如果如果A的某个候选首符集中包含的某个候选首符集中包含怎么办？怎么办？ 假定假定S是文法是文法G的开始符号，对于的开始符号，对于G的任何非终结符的任何非终结符A， 我们定义我们定义 FOLLOW(A)=a | S=*Aa，aVT FOLLOW(A)是所有句型中出现在紧接是所有句型中出现在紧接A之后的终结之后的终结 符或符或“#”。 开始符号的开

9、始符号的FOLLOW集初始化时加入集初始化时加入“#”。 当非终结符当非终结符A面临输入符号面临输入符号a，且，且a不属于不属于A的任意候的任意候 选首符集但选首符集但A的某个候选首符集包含的某个候选首符集包含时，只有当时，只有当a FOLLOW(A)时，才可能允许时，才可能允许A自动匹配。自动匹配。 LL(1)LL(1)分析条件分析条件 通过上面的讨论，我们可以找出满足构造不带回溯的自顶向通过上面的讨论，我们可以找出满足构造不带回溯的自顶向 下分析的文法条件。下分析的文法条件。 文法不含左递归文法不含左递归 对于文法中每一个非终结符对于文法中每一个非终结符A的各个产生式的候选首符集两两的各个

10、产生式的候选首符集两两 不相交。即，若不相交。即，若A1 |2 | |n，则，则FIRST(i)FIRST(j)= (ij) 对文法中的每个非终结符对文法中的每个非终结符A，若它存在某个候选首符集包含，若它存在某个候选首符集包含， 则，则，FIRST(A)FOLLOW(A)= 如果一个文法如果一个文法G满足以上条件，则称该文法满足以上条件，则称该文法G为为LL(1)文法。文法。 这里这里LL(1)中的第一个中的第一个L表示从左到右扫描输入串，第二个表示从左到右扫描输入串，第二个L 表示最左推导，表示最左推导，1表示分析时每一步只需向前查看一个符号。表示分析时每一步只需向前查看一个符号。 LL(

11、1)LL(1)分析条件分析条件 对于一个对于一个LL(1)文法，可以对其输入串进行有效的无文法，可以对其输入串进行有效的无 回溯的自顶向下分析。回溯的自顶向下分析。 假设要用非终结符假设要用非终结符A进行匹配，面临的输入符号为进行匹配，面临的输入符号为a， A的所有产生式为的所有产生式为A1 |2 | |n 若若aFIRST(i)，则指派，则指派i去执行匹配任务。去执行匹配任务。 若若a不属于任何一个候选首字符集，则：不属于任何一个候选首字符集，则： 若若属于某个属于某个FIRST(i)，且，且aFOLLOW(A)，则让，则让A 与与自动匹配；自动匹配； 否则，否则，a的出现是一种语法错误。的

12、出现是一种语法错误。 根据根据LL(1)文法的条件，每一步这样的工作都是确信文法的条件，每一步这样的工作都是确信 无疑的无疑的 LL(1)LL(1)分析法分析法 预测分析程序工作过程预测分析程序工作过程 实现实现LL(1)分析的一种有效方法是使用一张分析表和一个栈进分析的一种有效方法是使用一张分析表和一个栈进 行联合控制。下面要介绍的预测分析程序就是属于这种类型行联合控制。下面要介绍的预测分析程序就是属于这种类型 的的LL(1)分析器。分析器。 预测分析表预测分析表 预测分析表示一个预测分析表示一个MA,a形式的矩阵。其中形式的矩阵。其中A为非终结符，为非终结符，a是是 终结符或终结符或# 。

13、 矩阵元素矩阵元素MA,a中存放着一条关于中存放着一条关于A的产生式，指出当的产生式，指出当A面临输面临输 入符号入符号a时所应采用的候选。时所应采用的候选。 MA,a中也可能存放一个中也可能存放一个“出错标志出错标志”，指出，指出A根本不该面临根本不该面临 输入符号输入符号a。 i+*()# EETEETE EE+TEEE TTFTTFT TTT*FTTT FFiF(E) 预测分析过程概述预测分析过程概述 预测分析程序的总控程序在任何时候都是按预测分析程序的总控程序在任何时候都是按STACK栈顶符号栈顶符号 X和当前的输入符号和当前的输入符号a行事的。如下图所示，对于任何行事的。如下图所示，

14、对于任何(X,a)， 总控程序每次都执行下述三种可能的动作之一：总控程序每次都执行下述三种可能的动作之一： 若若X = a = #，则宣布分析成功，停止分析过程。，则宣布分析成功，停止分析过程。 若若X = a #，则把，则把X从从STACK栈顶弹出，让栈顶弹出，让a指向下一个输入符指向下一个输入符 号。号。 若若X是一个非终结符，则查看分析表是一个非终结符，则查看分析表M。 若若MX,a中存放着关于中存放着关于X的一个产生式，那么，先把的一个产生式，那么，先把X弹出弹出STACK 栈顶，然后把产生式的右部符号串按反序一一推进栈顶，然后把产生式的右部符号串按反序一一推进STACK栈（若栈（若

15、右部符号为右部符号为，则意味着不推什么东西进栈）。，则意味着不推什么东西进栈）。 在把产生式的右部符号退进栈的同时应该做这个产生式对应的语义在把产生式的右部符号退进栈的同时应该做这个产生式对应的语义 动作（目前暂且不管）。动作（目前暂且不管）。 若若MX,a中存放着中存放着“出错标志出错标志”，则调用出错诊断程序，则调用出错诊断程序ERROR。 预测分析预测分析 过程举例过程举例 i+*()# EETEETE EE+TEEE TTFTTFT TTT*FTTT FFiF(E) i1*i2+i3 步骤步骤符号栈符号栈输入串输入串所用产生式所用产生式 0#Ei*i+i# 1#ETi*i+i#ETE

16、2#ETFi*i+i#TFTTFT 3#ETii*i+i#Fi 4#ET *i+i# 5#ETF* *i+i#T*FT 6#ETF i+i# 7#ETi i+i#Fi 8#ET +i# 9#E +i#T 10#ET+ +i#E+TE 11#ET i# 12#ETF i#TFT 13#ETi i#Fi 14#ET # 15#E #T 16# #E 预测分析表的构造预测分析表的构造 FIRSTFIRST集合和集合和FOLLOWFOLLOW集合的定义集合的定义 FIRSTFIRST集合的构造算法集合的构造算法 分析表的构造分析表的构造 分析表的构造分析表的构造 分析表的构造分析表的构造 FIRSTF

17、IRST集合构造的例子集合构造的例子 FIRST(E)=+, FIRST(T)=*, FIRST(F)=( , i FIRST(T)=( , i FIRST(E)=( , i ETE E+TE | TFT T*FT | F(E) | i FOLLOWFOLLOW集合构造的例子集合构造的例子 FOLLOW(E)=),# FOLLOW(E)=),# FOLLOW(T)=+,),# FOLLOW(T)=+,),# FOLLOW(F)=*,+,),# ETE E+TE | TFT T*FT | F(E) | i FIRST(E)=+, FIRST(T)=*, FIRST(F)=( , i FIRST(

18、T)=( , i FIRST(E)=( , i i+*()# EETEETE EE+TEEE TTFTTFT TTT*FTTT FFiF(E) LL(1)LL(1)文法文法 LL(1)LL(1)分析中的错误处理分析中的错误处理 错误的出现及基本做法错误的出现及基本做法 栈顶的终结符与当前的输入符号不匹配。栈顶的终结符与当前的输入符号不匹配。 非终结符非终结符A处于栈顶，面临的输入符号为处于栈顶，面临的输入符号为a，但分析，但分析 表表M中中MA,a为空。为空。 基本的做法就是跳过输入串中的一些符号直至遇到基本的做法就是跳过输入串中的一些符号直至遇到 “同步符号同步符号”为止。这种做法的效果有赖

19、于同步符为止。这种做法的效果有赖于同步符 号集的选择。号集的选择。 同步符号集的选择同步符号集的选择 把把FOLLOW(A)中的所有符号放入非终结符中的所有符号放入非终结符A的同步符号集。的同步符号集。 如果我们跳读一些输入符号直至出现如果我们跳读一些输入符号直至出现FOLLOW(A)中的同步中的同步 符号，把符号，把A从栈中弹出来，这样就可能使分析继续下去。从栈中弹出来，这样就可能使分析继续下去。 对于非终结符对于非终结符A来说，只用来说，只用FOLLOW(A)作为它的同步符号作为它的同步符号 集是不够的。例如，如果分号作为语句的终结符，那么作为集是不够的。例如，如果分号作为语句的终结符，那

20、么作为 语句开头的关键字就可能不在产生表达式的非终结符的语句开头的关键字就可能不在产生表达式的非终结符的FOL LOW集合中。这样，在一个赋值语句后少一个分号就可能集合中。这样，在一个赋值语句后少一个分号就可能 导致作为下一个语句开头的关键字被跳过导致作为下一个语句开头的关键字被跳过 如果把如果把FIRST(A)中的符号加入非终结符中的符号加入非终结符A的同步符号集，那的同步符号集，那 么当么当FIRST(A)中的一个符号在输入中出现时，可以根据中的一个符号在输入中出现时，可以根据A恢恢 复语法分析复语法分析 同步符号集的选择同步符号集的选择 如果一个非终结符产生空串，那么推导如果一个非终结符产生空串，那么推导的产生式可以作为的产生式可以作为 缺省的情况，这样做可以推迟某些错误检查，但不能导致放缺省的情况，这样做可以推迟某些错误检查，但不能导致放 弃一个错误。这种方法减少在错误恢复期间必须考虑的非终弃一个错误。这种方法减少在错误恢复期间必须考虑的非终 结符数。结符数。 如果不能匹配栈顶的终结符号，一种简单的想法是弹出栈顶如果不能匹配栈顶的终结符号，一种简单的想法是弹出栈顶 的这个终结符号，并发出一条信息，说明已经插入这个终结的这个终结符号，并发出一条信息，说明已