搜索
Part4语法分析授课：胡静语法分析器的作用以语法分析器为核心的编译器模型语法分析器词法分析器中间代码生成器语义分析器一部分中间代码输入字符串程序入口初始化工作语法分析器所处的位置语法分析的例子语法分析的类比针对自然语言的语法分析：识别一个句子是不是符合语法规范&识别每一个成分的功能。语法分析器的作用接收词法分析器提供的记号串检查记号串是否能由源程序语言的文法产生用易于理解的方式提示语法错误信息，并能从常见的错误中恢复过来语法分析器词法分析器符号表前端的其余部分源程序记号取下一个记号语法树中间表示语法分析器工作原理语言的结构是用上下文无关文法描述的，因此，语法分析器的工作本质上就是按照文法的产生式，识别输入符号串是否为一个句子。语法分析器是从左向右的扫描输入字符串，每次读入一个符号，并判断，看是否能从文法的开始符号出发推导出这个输入串。或者，从概念上讲，就是要建立一棵与输入串匹配的语法分析树。语法分析器分类通用的语法分析方法，用来分析任何文法，生成编译器时效率太低编译器使用的语法分析方法—处理文法的一些子类自顶向下（建立分析树）—LL文法，其分析器常用手工实现自底向上（建立分析树）—LR文法，其分析器常利用自动生成工具构造自顶向下分析面临的困难自顶向下分析面临的困难自顶向下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法的开始符号（根结）出发，自顶向下的为输入串建立一棵语法树。这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。自顶向下分析的一般方法是带“回溯”的。自顶向下分析方法的特点自顶向下分析存在的问题左递归文法：有如下文法：令P是文法的任一非终结符，文法中有规则P→P……或者P=+P……，这个文法是左递归的。自顶向下分析的基本缺点是：不能处理具有左递归的文法。？？？？？自顶向下分析存在的问题假定文法G[S]，以及输入串x*y（记为α）。S→xAyA→**|*初始化：第一步扩展Sx*yIPSx*yIPyAx自顶向下分析的困难假定文法G[S]，以及输入串x*y（记为α）。S→xAyA→**|*第二步扩展：回溯x*yIPSx*yIPyAx**SyAx*递归下降分析程序构造前面的巴科斯范式只用到了两个元符号“→”和“|”扩充的巴科斯范式加入几个元语言符号：用花括号{α}表示闭包运算α*。用{α}n0表示α可任意重复0次至n次。{α}00={α}0=ε.用方括号[α]表示{α}10，即表示α的出现可有可无（等价于α|ε）。例如，通常的“实数”可定义为：decimal→[sign]integer.{digit}[exponent]exponent→E[sign]integerinteger→digit[digit]sign→+|-递归下降分析程序的构造当文法满足上述两个文法条件时，我们就可以为它构造一个不带回溯的自顶向下分析程序，这个分析程序是由一组递归过程组成的。每个过程对应文法的一个非终结符。这样的一个分析程序称为递归下降分析器。E→E+T|TT→T*F|FF→(E)|iE→T{+T}T→F{*F}F→(E)|i递归下降分析程序构造TET+FTF*E→T{+T}T→F{*F}F→(E)|iiF()EPROCEDUREE;BEGINT;WHILESYM=‘+’DOBEGINADVANCE;TENDENDPROCEDURET;BEGINF;WHILESYM=‘*’DOBEGINADVANCE;FENDENDLL(1)分析法消除直接左递归——改写成右递归直接左递归的消除P→Pα|βP→βP’P’→αP’|εE→E+T|TT→T*F|FF→(E)|iE→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i消除左递归的一般算法如果一个文法不含回路（形如P=+P的推导），也不含以ε为右部的产生式，那么执行下述算法将保证消除左递归（但改写后的文法可能含有ε为右部的产生式）。消除左递归的算法消除左递归的例子R→Sa|aQ→Rb|bS→Qc|cR→Sa|aQ→Sab|ab|bS→Sabc|abc|bc|cS→abcS’|bcS’|cS’S’→abcS’|εR→Sa|aQ→Sab|ab|bS→abcS’|bcS’|cS’S’→abcS’|εS→Qc|cQ→Rb|bR→bcaR’|caR’|aR’R’→bcaR’|ε回溯问题消除回溯、提取左因子令Ｇ是一个不含左递归的文法，对G的所有非终结符的每个候选α定义它的终结首符集FIRST(α)为：FIRST(α)={a|α=*a…,a∈VT}若α=*ε，则规定ε∈FIRST(α)FIRST(α)是α的所有可能推导的开头终结符或可能的ε如果非终结符Ａ的所有候选首符集两两不相交，即Ａ的任何两个不同候选αi和αｊFIRST(αi)∩FIRST(αj)=Φ那么当要求Ａ匹配输入串时，Ａ就能根据它所面临的第一个输入符号ａ，准确的指派某一个候选前去执行任务。这个候选就是那个终结首符集含ａ的α。消除回溯、提取左因子提取左因子的方法假定Ａ的规则是：Ａ→δβ1|δβ2|…|δβn|γ1|γ2|…|γm（其中，每个γ不以δ开头）那么这些规则可以改写为：A→δA’|γ1|γ2|…|γmA’→β1|β2|…|βn经过反复提取左因子，就能够把每个非终结符（包括新引进者）的所有候选首符集便成为两两不相交。我们为此要付出的代价是大量引进新的非终结符和ε产生式。消除回溯、提取左因子提取左因子的方法假定Ａ的规则是：Ａ→δβ1|δβ2|…|δβn|γ1|γ2|…|γm（其中，每个γ不以δ开头）那么这些规则可以改写为：A→δA’|γ1|γ2|…|γmA’→β1|β2|…|βn经过反复提取左因子，就能够把每个非终结符（包括新引进者）的所有候选首符集便成为两两不相交。我们为此要付出的代价是大量引进新的非终结符和ε产生式。LL(1)分析条件E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i对输入串i+i进行自顶向下分析Ei+iIPTE’i∈FIRST(TE’)Ei+iIPTE’i∈FIRST(FT’)FT’Ei+iIPTE’i∈FIRST(i)FT’iLL(1)分析条件E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i对输入串i+i进行自顶向下分析Ei+iIPTE’+不属于T’的任一候选式的首符集FT’iεETE’FT’iε+TE’εFT’εiLL(1)分析条件如果A的某个候选首符集中包含ε怎么办？假定S是文法G的开始符号，对于G的任何非终结符A，我们定义FOLLOW(A)={a|S=*…Aa…，a∈VT}FOLLOW(A)是所有句型中出现在紧接A之后的终结符或“#”。开始符号的FOLLOW集初始化时加入“#”。当非终结符A面临输入符号a，且a不属于A的任意候选首符集但A的某个候选首符集包含ε时，只有当a∈FOLLOW(A)时，才可能允许A自动匹配。LL(1)分析条件通过上面的讨论，我们可以找出满足构造不带回溯的自顶向下分析的文法条件。文法不含左递归对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A→α1|α2|…|αn，则FIRST(αi)∩FIRST(αj)=Φ(i≠j)对文法中的每个非终结符A，若它存在某个候选首符集包含ε，则，FIRST(A)∩FOLLOW(A)=Φ如果一个文法G满足以上条件，则称该文法G为LL(1)文法。这里LL(1)中的第一个L表示从左到右扫描输入串，第二个L表示最左推导，1表示分析时每一步只需向前查看一个符号。LL(1)分析条件对于一个LL(1)文法，可以对其输入串进行有效的无回溯的自顶向下分析。假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为A→α1|α2|…|αn若a∈FIRST(αi)，则指派αi去执行匹配任务。若a不属于任何一个候选首字符集，则：若ε属于某个FIRST(αi)，且a∈FOLLOW(A)，则让A与ε自动匹配；否则，a的出现是一种语法错误。根据LL(1)文法的条件，每一步这样的工作都是确信无疑的LL(1)分析法预测分析程序工作过程实现LL(1)分析的一种有效方法是使用一张分析表和一个栈进行联合控制。下面要介绍的预测分析程序就是属于这种类型的LL(1)分析器。……a…………#输入串总控程序预测分析表X....#输出预测分析表预测分析表示一个M[A,a]形式的矩阵。其中A为非终结符，a是终结符或‘#’。矩阵元素M[A,a]中存放着一条关于A的产生式，指出当A面临输入符号a时所应采用的候选。M[A,a]中也可能存放一个“出错标志”，指出A根本不该面临输入符号a。i+*()#EE→TE’E→TE’E’E’→+TE’E’→εE’→εTT→FT’T→FT’T’T’→εT’→*FT’T’→εT’→εFF→iF→(E)预测分析过程概述预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a行事的。如下图所示，对于任何(X,a)，总控程序每次都执行下述三种可能的动作之一：若X=a=‘#’，则宣布分析成功，停止分析过程。若X=a≠‘#’，则把X从STACK栈顶弹出，让a指向下一个输入符号。若X是一个非终结符，则查看分析表M。若M[X,a]中存放着关于X的一个产生式，那么，先把X弹出STACK栈顶，然后把产生式的右部符号串按反序一一推进STACK栈（若右部符号为ε，则意味着不推什么东西进栈）。在把产生式的右部符号退进栈的同时应该做这个产生式对应的语义动作（目前暂且不管）。若M[X,a]中存放着“出错标志”，则调用出错诊断程序ERROR。预测分析过程举例i+*()#EE→TE’E→TE’E’E’→+TE’E’→εE’→εTT→FT’T→FT’T’T’→εT’→*FT’T’→εT’→εFF→iF→(E)i1*i2+i3步骤符号栈输入串所用产生式0#Ei*i+i#1#E’Ti*i+i#E→TE’2#E’T’Fi*i+i#T→FT’3#E’T’ii*i+i#F→i4#E’T’*i+i#5#E’T’F**i+i#T’→*FT’6#E’T’Fi+i#7#E’T’ii+i#F→i8#E’T’+i#9#E’+i#T’→ε10#E’T++i#E’→+TE’11#E’Ti#12#E’T’Fi#T→FT’13#E’T’ii#F→i14#E’T’#15#E’#T’→ε16##E’→ε预测分析表的构造FIRST集合和FOLLOW集合的定义FIRST集合的构造算法分析表的构造分析表的构造分析表的构造FIRST集合构造的例子FIRST(E’)={+,ε}FIRST(T’)={*,ε}FIRST(F)={(,i}FIRST(T)={(,i}FIRST(E)={(,i}E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iFOLLOW集合构造的例子FOLLOW(E)={),#}FOLLOW(E’)={),#}FOLLOW(T)={+,),#}FOLLOW(T’)={+,),#}FOLLOW(F)={*,+,),#}E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iFIRST(E’)={+,ε}FIRST(T’)={*,ε}FIRST(F)={(,i}FIRST(T)={(,i}FIRST(E)={(,i}i+*()#EE→TE’E→TE’E’E’→+TE’E’→εE’→εTT→FT’T→FT’T’T’→εT’→*FT’T’→εT’→εFF→iF→(E)LL(1)文法LL(1)分析中的错误处理错误的出现及基本做法栈顶的终结符与当前的输入符号不匹配。非终结符A处于栈顶，面临的输入符号为a，但分析表M中M[A,a]为空。基本的做法就是跳过输入串中的一些符号直至遇到“同步符号”为止。这种做法的效果有赖于同步符号集的选择。同步符号集的选择把FOLLOW(A)中的所有符号放入非终结符A的同步符号集。如果我们跳读一些输入符号直至出现FOLLOW(A)中的同步符号，把A从栈中弹出来，这样就可能使分析继续下去。对于非终结符A来说，只用FOLLOW(A)作为它的同步符号集是不