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

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

2、析器的作用接收词法分析器提供的记号串接收词法分析器提供的记号串检查记号串是否能由源程序语言的文法产生检查记号串是否能由源程序语言的文法产生用易于理解的方式提示语法错误信息，并能从常见的用易于理解的方式提示语法错误信息，并能从常见的错误中恢复过来错误中恢复过来语法分语法分析器析器词法词法分析器分析器符号表符号表前端的其前端的其余部分余部分源程序源程序记号记号取下一取下一个记号个记号语法树语法树中间表示中间表示语法分析器工作原理语法分析器工作原理语言的结构是用上下文无关文法描述的，因此，语法分析器语言的结构是用上下文无关文法描述的，因此，语法分析器的工作本质上就是按照文法的产生式，识别输入符号串是

3、否的工作本质上就是按照文法的产生式，识别输入符号串是否为一个句子。为一个句子。语法分析器是从左向右的扫描输入字符串，每次读入一个符语法分析器是从左向右的扫描输入字符串，每次读入一个符号，并判断，看是否能从文法的开始符号出发推导出这个输号，并判断，看是否能从文法的开始符号出发推导出这个输入串。或者，从概念上讲，就是要建立一棵与输入串匹配的入串。或者，从概念上讲，就是要建立一棵与输入串匹配的语法分析树。语法分析树。语法分析器分类语法分析器分类 通用的语法分析方法，用来分析任何文法，生成编译器时效率太通用的语法分析方法，用来分析任何文法，生成编译器时效率太低低编译器使用的语法分析方法编译器使用的语法

4、分析方法处理文法的一些子类处理文法的一些子类自顶向下（建立分析树）自顶向下（建立分析树）LL文法，其分析器常用手工实现文法，其分析器常用手工实现自底向上（建立分析树）自底向上（建立分析树）LR文法，其分析器常利用自动生成工文法，其分析器常利用自动生成工具构造具构造自顶向下分析面临的困难自顶向下分析面临的困难自顶向下分析面临的困难自顶向下分析面临的困难 自顶向下分析的主旨是，对任何输入串，试图用一切自顶向下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法的开始符号（根结）出发，自顶可能的办法，从文法的开始符号（根结）出发，自顶向下的为输入串建立一棵语法树。向下的为输入串建立一棵语法树。这

5、种分析过程本质上是一种试探过程，是反复使用不这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。同产生式谋求匹配输入串的过程。 自顶向下分析的一般方法是带自顶向下分析的一般方法是带“回溯回溯”的。的。自顶向下分析方法的特点自顶向下分析方法的特点自顶向下分析存在的问题自顶向下分析存在的问题左递归文法：左递归文法：有如下文法：有如下文法：令令P是文法的任一非终结符，文法中有规则是文法的任一非终结符，文法中有规则PP或或者者P=+P，这个文法是左递归的。，这个文法是左递归的。自顶向下分析的基本缺点是：不能处理具有左递归的自顶向下分析的基本缺点是：不能处理具有左递归的文法。文法

6、。？自顶向下分析存在的问题自顶向下分析存在的问题假定文法假定文法GS，以及输入串，以及输入串x*y（记为（记为）。）。SxAyA*|*初始化：初始化：第一步扩展第一步扩展Sx*yIPSx*yIPyAx自顶向下分析的困难自顶向下分析的困难假定文法假定文法GS，以及输入串，以及输入串x*y（记为（记为）。）。SxAyA*|*第二步扩展：第二步扩展：回溯回溯x*yIPSx*yIPyAx*SyAx*递归下降分析程序构造递归下降分析程序构造前面的巴科斯范式只用到了两个元符号前面的巴科斯范式只用到了两个元符号“”和和“|” 扩充的巴科斯范式加入几个元语言符号：扩充的巴科斯范式加入几个元语言符号：用花括号用

7、花括号表示闭包运算表示闭包运算*。用用n0表示表示可任意重复可任意重复0次至次至n次。次。00=0=.用方括号用方括号表示表示10，即表示，即表示的出现可有可无（等价于的出现可有可无（等价于 |）。）。 例如，通常的例如，通常的“实数实数”可定义为：可定义为：decimalsigninteger.digitexponentexponentEsignintegerintegerdigitdigitsign+ | -递归下降分析程序的构造递归下降分析程序的构造当文法满足上述两个文法条件时，我们就可以为它构当文法满足上述两个文法条件时，我们就可以为它构造一个不带回溯的自顶向下分析程序，这个分析程序造

8、一个不带回溯的自顶向下分析程序，这个分析程序是由一组递归过程组成的。每个过程对应文法的一个是由一组递归过程组成的。每个过程对应文法的一个非终结符。这样的一个分析程序称为递归下降分析器。非终结符。这样的一个分析程序称为递归下降分析器。 EE+T | TTT*F | FF(E) | iET+TTF*FF(E) | i递归下降分析程序构造递归下降分析程序构造ET+TTF*FF(E) | iPROCEDURE E;BEGINT;WHILE SYM = + DOBEGIN ADVANCE; T ENDENDPROCEDURE T;BEGINF;WHILE SYM = * DOBEGIN ADVANCE;

9、 F ENDENDLL(1)LL(1)分析法分析法消除直接左递归消除直接左递归改写成右递归改写成右递归直接左递归的消除直接左递归的消除PP | PPPP | EE+T | TTT*F | FF(E) | iETEE+TE | TFTT*FT | F(E) | i消除左递归的一般算法消除左递归的一般算法如果一个文法不含回路（形如如果一个文法不含回路（形如P=+P的推导），也的推导），也不含以不含以为右部的产生式，那么执行下述算法将保证为右部的产生式，那么执行下述算法将保证消除左递归（但改写后的文法可能含有消除左递归（但改写后的文法可能含有为右部的产为右部的产生式）。生式）。 消除左递归的算法消除

10、左递归的算法消除左递归的例子消除左递归的例子RSa | aQRb | bSQc |cRSa |aQSab | ab | bSSabc | abc | bc | cSabcS | bcS | cSSabcS | RSa |aQSab | ab | bSabcS | bcS | cSSabcS | SQc | cQRb | bRbcaR |caR | aRRbcaR | 回溯问题回溯问题消除回溯、提取左因子消除回溯、提取左因子令是一个不含左递归的文法，对令是一个不含左递归的文法，对G的所有非终结符的每个候的所有非终结符的每个候选选定义它的终结首符集定义它的终结首符集FIRST()为：为：FIRST

11、()=a | =*a, aVT 若若=*，则规定，则规定FIRST()FIRST()是是的所有可能推导的开头终结符或可能的的所有可能推导的开头终结符或可能的 如果非终结符的所有候选首符集两两不相交，即的任何如果非终结符的所有候选首符集两两不相交，即的任何两个不同候选两个不同候选i和和FIRST(i) FIRST(j)=那么当要求匹配输入串时，就能根据它所面临的第一个那么当要求匹配输入串时，就能根据它所面临的第一个输入符号，准确的指派某一个候选前去执行任务。这个候输入符号，准确的指派某一个候选前去执行任务。这个候选就是那个终结首符集含的选就是那个终结首符集含的。 消除回溯、提取左因子消除回溯、提

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

13、方法假定的规则是：假定的规则是：1 |2 | |n |1 |2 | |m（其中，每个（其中，每个不以不以开头）开头）那么这些规则可以改写为：那么这些规则可以改写为：AA |1 |2 | |mA1 |2 | |n经过反复提取左因子，就能够把每个非终结符（包括新引进经过反复提取左因子，就能够把每个非终结符（包括新引进者）的所有候选首符集便成为两两不相交。我们为此要付出者）的所有候选首符集便成为两两不相交。我们为此要付出的代价是大量引进新的非终结符和的代价是大量引进新的非终结符和产生式。产生式。 LL(1)LL(1)分析条件分析条件ETEE+TE | TFTT*FT | F(E) | i对输入串对输

14、入串i+i进行自顶向下分析进行自顶向下分析Ei + iIPTEiFIRST(TE)Ei + iIPTEiFIRST(FT)FTEi + iIPTEiFIRST(i)FTiLL(1)LL(1)分析条件分析条件ETEE+TE | TFTT*FT | F(E) | i对输入串对输入串i+i进行自顶向下分析进行自顶向下分析Ei + iIPTE+不属于不属于T的任一候选式的首符集的任一候选式的首符集FTiETEFTi+TEFTiLL(1)LL(1)分析条件分析条件如果如果A的某个候选首符集中包含的某个候选首符集中包含怎么办？怎么办？假定假定S是文法是文法G的开始符号，对于的开始符号，对于G的任何非终结符

15、的任何非终结符A，我们定义我们定义FOLLOW(A)=a | S=*Aa，aVTFOLLOW(A)是所有句型中出现在紧接是所有句型中出现在紧接A之后的终结之后的终结符或符或“#”。 开始符号的开始符号的FOLLOW集初始化时加入集初始化时加入“#”。当非终结符当非终结符A面临输入符号面临输入符号a，且，且a不属于不属于A的任意候的任意候选首符集但选首符集但A的某个候选首符集包含的某个候选首符集包含时，只有当时，只有当aFOLLOW(A)时，才可能允许时，才可能允许A自动匹配。自动匹配。 LL(1)LL(1)分析条件分析条件通过上面的讨论，我们可以找出满足构造不带回溯的自顶向通过上面的讨论，我们

16、可以找出满足构造不带回溯的自顶向下分析的文法条件。下分析的文法条件。 文法不含左递归文法不含左递归对于文法中每一个非终结符对于文法中每一个非终结符A的各个产生式的候选首符集两两的各个产生式的候选首符集两两不相交。即，若不相交。即，若A1 |2 | |n，则，则FIRST(i)FIRST(j)=(ij)对文法中的每个非终结符对文法中的每个非终结符A，若它存在某个候选首符集包含，若它存在某个候选首符集包含，则，则，FIRST(A)FOLLOW(A)=如果一个文法如果一个文法G满足以上条件，则称该文法满足以上条件，则称该文法G为为LL(1)文法。文法。这里这里LL(1)中的第一个中的第一个L表示从左

17、到右扫描输入串，第二个表示从左到右扫描输入串，第二个L表示最左推导，表示最左推导，1表示分析时每一步只需向前查看一个符号。表示分析时每一步只需向前查看一个符号。 LL(1)LL(1)分析条件分析条件对于一个对于一个LL(1)文法，可以对其输入串进行有效的无文法，可以对其输入串进行有效的无回溯的自顶向下分析。回溯的自顶向下分析。假设要用非终结符假设要用非终结符A进行匹配，面临的输入符号为进行匹配，面临的输入符号为a，A的所有产生式为的所有产生式为A1 |2 | |n若若aFIRST(i)，则指派，则指派i去执行匹配任务。去执行匹配任务。若若a不属于任何一个候选首字符集，则：不属于任何一个候选首字

18、符集，则：若若属于某个属于某个FIRST(i)，且，且aFOLLOW(A)，则让，则让A与与自动匹配；自动匹配；否则，否则，a的出现是一种语法错误。的出现是一种语法错误。根据根据LL(1)文法的条件，每一步这样的工作都是确信文法的条件，每一步这样的工作都是确信无疑的无疑的 LL(1)LL(1)分析法分析法预测分析程序工作过程预测分析程序工作过程实现实现LL(1)分析的一种有效方法是使用一张分析表和一个栈进分析的一种有效方法是使用一张分析表和一个栈进行联合控制。下面要介绍的预测分析程序就是属于这种类型行联合控制。下面要介绍的预测分析程序就是属于这种类型的的LL(1)分析器。分析器。 预测分析表预

19、测分析表预测分析表示一个预测分析表示一个MA,a形式的矩阵。其中形式的矩阵。其中A为非终结符，为非终结符，a是是终结符或终结符或# 。矩阵元素矩阵元素MA,a中存放着一条关于中存放着一条关于A的产生式，指出当的产生式，指出当A面临输面临输入符号入符号a时所应采用的候选。时所应采用的候选。MA,a中也可能存放一个中也可能存放一个“出错标志出错标志”，指出，指出A根本不该面临根本不该面临输入符号输入符号a。 i+*()#EETEETEEE+TEEETTFTTFTTTT*FTTTFFiF(E)预测分析过程概述预测分析过程概述预测分析程序的总控程序在任何时候都是按预测分析程序的总控程序在任何时候都是按

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

21、式的右部符号串按反序一一推进栈顶，然后把产生式的右部符号串按反序一一推进STACK栈（若栈（若右部符号为右部符号为，则意味着不推什么东西进栈）。，则意味着不推什么东西进栈）。在把产生式的右部符号退进栈的同时应该做这个产生式对应的语义在把产生式的右部符号退进栈的同时应该做这个产生式对应的语义动作（目前暂且不管）。动作（目前暂且不管）。若若MX,a中存放着中存放着“出错标志出错标志”，则调用出错诊断程序，则调用出错诊断程序ERROR。 预测分析预测分析过程举例过程举例i+*()#EETEETEEE+TEEETTFTTFTTTT*FTTTFFiF(E)i1*i2+i3步骤步骤符号栈符号栈输入串输入串

22、所用产生式所用产生式0#Ei*i+i#1#ETi*i+i#ETE2#ETFi*i+i#TFTTFT3#ETii*i+i#Fi4#ET *i+i#5#ETF* *i+i#T*FT6#ETF i+i#7#ETi i+i#Fi8#ET +i#9#E +i#T10#ET+ +i#E+TE11#ET i#12#ETF i#TFT13#ETi i#Fi14#ET #15#E #T16# #E预测分析表的构造预测分析表的构造FIRSTFIRST集合和集合和FOLLOWFOLLOW集合的定义集合的定义FIRSTFIRST集合的构造算法集合的构造算法分析表的构造分析表的构造分析表的构造分析表的构造分析表的构造分

23、析表的构造FIRSTFIRST集合构造的例子集合构造的例子FIRST(E)=+,FIRST(T)=*,FIRST(F)=( , iFIRST(T)=( , iFIRST(E)=( , iETEE+TE | TFTT*FT | F(E) | iFOLLOWFOLLOW集合构造的例子集合构造的例子FOLLOW(E)=),#FOLLOW(E)=),#FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=*,+,),#ETEE+TE | TFTT*FT | F(E) | iFIRST(E)=+,FIRST(T)=*,FIRST(F)=( , iFIRST(T)=( , iFI

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

25、选择。号集的选择。 同步符号集的选择同步符号集的选择 把把FOLLOW(A)中的所有符号放入非终结符中的所有符号放入非终结符A的同步符号集。的同步符号集。如果我们跳读一些输入符号直至出现如果我们跳读一些输入符号直至出现FOLLOW(A)中的同步中的同步符号，把符号，把A从栈中弹出来，这样就可能使分析继续下去。从栈中弹出来，这样就可能使分析继续下去。对于非终结符对于非终结符A来说，只用来说，只用FOLLOW(A)作为它的同步符号作为它的同步符号集是不够的。例如，如果分号作为语句的终结符，那么作为集是不够的。例如，如果分号作为语句的终结符，那么作为语句开头的关键字就可能不在产生表达式的非终结符的语句开头的关键字就可能不在产生表达式的非终结符的FOLLOW集合中。这样，在一个赋值语句后少一个分号就集合中。这样，在一个赋值语句后少一个分号就可能导致作为下一个语句开头的关键字被跳过可能导致作为下一个语句开头的关键字被跳过如果把如果把FIRST(A)中的符号加入非终结符中的符号加入非终结符A的同步符号集，那的同步符号集，那么当么当FIRST(A)中的一个符号在输入中出现时，可以根据中的一个符号在输入中出现时，可以根据A恢恢复语法分析复语法分析同步符号集的选择同步符号集的选择 如果一个非终结符产生空串，那么推导如果一个非终结符产生空串，那么推导的产生式可以作为的产生式可以作