编译原理-语法分析

1.语法分析概述

  1.1 定义

          语法分析就是根据高级语言的语法规则对程序的语法结构进行分析。如下图所示：

1.2 任务

           语法分析的任务就是在词法分析识别出正确的单词符号串是否符合语言的语法规则，分析并识别各种语法成分，同时进行语法检查和错误处理，为语义分析和代码生成做准备。

1.3 地位

           语法分析在编译过程中处于核心地位。

1.4 语法分析程序

           执行语法分析的程序称为语法分析程序，也称为语法分析器。

1.5 文法

           通过对高级语言的语法规则进行形式化的描述，从而能够更加精确的描述高级语言程序的语法结构，这种描述称为文法。适合描述高级语言语法规则的文法是上下文无关法。

1.6 判断依据

         对给定的输入符号串能否根据文法的规则建立起一颗语法树。

2.上下文无关文法

2.1 原理

          上下文无关法用递归的方式来描述语法规则。语法分析的过程就是按照文法规则对读入的token串进行分析的过程。token串中的每个单词符合对应与文法的一个符号。

2.2 文法的定义

2.2.1 概念

        文法是描述语言的语法结构的形式规则（即语法规则），这些规则必须准确且可理解。

1.非终结符	代表一个语法范畴，表示一类具有某种性质的语法单位。在程序设计语言中，非终结符有算术表达式， 赋值语句等。用Vn表示非终结符的集合。
2.终结符	出现在最终的句子中的符号称为终结符，在程序设计语言的语法规则中终结符就是单词 符号，比如关键字、标识符、界符等等。用Vt表示终结符的集合。
3.产生式	按照一定格式书写的，用于定义语法范畴的规则。说明了终结符和非终结符组合成字符串的方式， 用P表示产生式的集合。
4.开始符号	是一个特殊的非终结符，至少在一个产生式的左部出现，用S表示，代表该文法定义的语言最终要 得到的语法范畴在程序设计语言中，开始符号就是<程序>。

2.2.2 形式化定义

       文法的形式化定义为：文法G是一个四元组，G=（Vn，Vt，P，S），其中Vn是非终结符集，Vt是终结符集，S是开始符号，P是产生式集合。

2.2.3 定义

       一般的在书写产生式有下列约定：

1.第一条产生式的左部是开始符号

2.在产生式中，用大写字母表示非终结符；小写字母表示终结符；小写希腊字母（如α、β）代表任意的文法字符串。

3.如果S是文法G的开始符号，也可以将文法G写成G[S]

4.有时为了书写简洁，常把相同左部的多个产生式用|进行缩写。如A->a1|a2|a3|a4|a5|....

2.3 推导

      从文法的开始符号出发，反复连续使用所有可能的产生式，将一个符号串中的非终结符用某个产生式右部进行替换和展开，直到全部为终结符为止，这个过程就称为推导。

2.3.1 最左推导

        如果在推导过程中，每一步都是替换符号串中最左边的非终结符，这样的推导称为最左推导。

2.3.2 最右推导

        如果在推导过程中，每一步都是替换符号串中最右边的非终结符，这样的推导称为最右推导。

2.4 文法产生的语言

2.4.1 定义

S（句型）	由开始符号出发推导出的符号串，包含非终结符和终结符。
X（句子）	仅含终结符的句型
L(G)（语言）	文法G产生的所有的句子的集合

2.4.2 等价

      如果文法G1与文法G2产生的语言相同，即L(G1) = L(G2)，则称文法G1与文法G2是等价的。

2.5 语法树

2.5.1 定义

          根据文法可以手工或自动生成一个有效的语法分析程序，用来判断输入的符号串在语法上是否正确。判断的一句就是对给定的输入符号串能否根据文法规则建立起一颗语法树。

          上述用推导的方式来考察文法定义语言的过程，但是推导不能表示句子的各个组成部分间的结构关系。语法树能够表示句子的构成和层次关系。

         语法树就是用一棵树来表示一个句型的推导过程，有时也称为语法分析树。语法树是一棵倒立的树，根在上，枝叶在下。根节点由开始符号标记。随着推导的展开，当某个非终结符被它的候选式所替换时，这个非终结符就产生下一代新结点。

         语法树的叶子结点由非终结符、终结符和c 标记。

2.5.2 分类

       由于对一个句子或者一个句型的推导过程不止一种，因此语法树也表示了一个句型的不同的推导过程，包括：最左推导和最右推导。

2.5.3 二义文法

         如果一个文法存在某个句型对应两棵或两棵以上不同的语法树，则称为这个文法为二义文法。也就是说，二义文法是存在某个句型也不只有一个最左（最右）推导的文法。对二义文法中某些句子的分析过程中不是唯一的，也就不能确定某个句子应该选择那棵语法树进行分析。所以要使用一些附加的规则来消除二义性。

      文法的二义性不能代表语言一定是二义的，只有当产生的一个语言的所有的文法都是二义的，这个语言才是二义的。因为可以用无二义的文法代替二义的文法。

2.5.4 消除二义性

      利用运算符之间的优先级和结合性来消除算术表达式文法的二义性。在通常的算术运算中，*和/比+和-的优先级高，都遵循左结合的原则，如下所示：

优先级	结合性	运算符
1	左结合	+，-
2	左结合	*，/

        其中左结合性的含义是：当出现相同优先级的运算符时，从左到右进行运算。优先级越高，越优先运算。

2.5.5 语法分析方法

        按照语法树的建立方法，可以粗略的把语法分析分为两类：自上而下语法分析法与自下而上语法分析法。

3.3 自上而下的语法分析

3.3.1 定义

       自上而下的语法分析方法就是对任何输入串（由token串构成的源程序），试图用一切可能的办法，从文法开始符号（根结点）出发，自上而下的为输入串建立一棵语法树，或者说，为输入串寻找一个最左推导。

3.3.2 问题引入

       在替换一个非终结符时，如果一个非终结符有多个候选式，选择哪个候选式是一个问题。自上而下分析的过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。确定的自上而下的分析就是每一次的候选式都是确定的，然而在试探过程中可能会出现以下问题：

     1）试探与回溯

       试探与回溯是一种穷尽一切可能的办法，效率低，代价高，导致分析器不稳定。使用自上而下分析时，要设法消除回溯。

       即当文法中存在形如A->αβ1|αβ2......的产生式，即某个非终结符存在多个候选式的前缀相同（也称为公共左因子），则可能造成虚假匹配（即当前的匹配可能是暂时的），即发现不能匹配后重新回溯重新选择一个候选式进行匹配，这样反复多次，使得在分析过程中可能需要大量的回溯。

     2）左递归

      导致分析过程无限循环。假如文法中存在形如：A->Aa的产生式（称为左递归），分析过程中又使用左推导，则就会使得分析过程陷入无限循环中，因此，使用自上而下分析时，文法应该不包含左递归。

3.3.4 回溯的消除

      回溯产生的根本原因在于某个非终结符的多个候选式存在公共左因子，如非终结符A的产生式如下：

A->αβ1|αβ2
           

     如果输入串中待分析的字前缀也为α，此时选择A的那个候选式就会不确定，可能就导致回溯。因此，要想进行确定的分析，必须保证文法G的每个非终结符的多个候选式均不包含公共左因子。

   1）改造方法：

改造的方法是提取公共左因子。使得文法的每个非终结符号的各个候选式的首终结符集两两不相交。

  2）案例

例1：条件（if）语句的文法有两个候选式如下：
    <IFS> -> if B then S1 else S2
    <IFS> -> if B then S1

上面存在问题：当输入的符号是if时，就不能立刻确定选用那个候选式，提取公共因子后：
    <IFS> -> if B then S1 P
        P -> else S2

例2：对A→δα1|δα2|…|δαn，提取公共左因子后为：
    A->δA'
    A'->α1|α2|…|αn
           

       对于例1，当S1匹配成功后，根据下一个输入符号是不是else，再决定是否选择P的候选式进行匹配。

3.3.5 左递归的消除

      左递归包括直接左递归和间接左递归。

直接左递归	若文法G中有形如A->Aα的产生式，则称该产生式对A直接左递归。
间接左递归	若文法G中没有形如A->Aα的产生式，但是A经过有限步骤推导可以得到A->Aα，则称该产生式 对A间接左递归。

     1）消除文法的直接左递归

       消除文法的直接左递归是通过对产生式进行改造来实现的。将各个产生式改造后使得各个非终结符不含左递归，如下所示：

案例1：
A的候选式为：A->Aα|β
改造后的非直接左递归形式：
    A->βA'
    A'->αA'|c（c为空字）
------------------------------------
案例2：如下所示文法G是含有左递归的文法
    E->E+T|T
    T->T*F|F
    F->i|(E)
消除左递归后如下所示：
    E->TE'
    E'->+TE'|c
    T->FT'
    T'->*FT'|c
    F->(E)|i
           

      实际上是将直接左递归改成了直接右递归，这样在最左推导中就不会陷入死循环。

      将上述结果推广，有以下消除直接左递归的形式：

假设文法中A的产生式如下：
    A->Aα1|Aα2|Aα3|......|Aαm|β1|β2|β3......|βn
则消除直接左递归如下所示：
    A->β1A'|β2A'|......|βnA'
    A->α1A'|α2A'|......|αmA'|c
           

     2）消除文法中的间接左递归

       有些文法中的左递归并不是直接的，如下所示：

S->Ac|c
A->Bb|b
B->Sa|a
存在推导：S->Ac->Bbc->Sabc
           

      从上面看出，间接的推导出现了左递归。对于间接左递归，可以采用先代入，然后再消除直接左递归的方法，如下所示：

对于文法如下消除左递归：
    S->Ac|c
    A->Bb|b
    B->Sa|a
1）代入：
    将产生式B->Sa|a代入A->Bb|b，有A->(Sa|a)b|b，即A->Sab|ab|b
    将产生式A->Sab|ab|b代入A->Ac|c，有S->(Sab|ab|b)c|c，即S->Sabc|abc|bc|c
2）消除S的直接左递归，得到：
    S->abcS'|bcS'|cS'
    S'->abcS'|c
    A->Bb|b
    B->Sa|a
           

3.3.6 LL(1)文法

       没有左递归和没有公共左因子并不能进行确定的自上而下的分析。如下所示：

有文法如下所示：
    S->Ac|Be
    A->db|b
    B->da|a
当输入字符串dbc，要求用S的候选式匹配d时，虽然S的两个候选式没有公共左因子，仍不能准确地选取S的候选式，
不能进行确定的分析。
           

    1）First集

      First(α)是文法G的符号串α的首终结符集，即由该候选式推导出的所有符号串中的第一个终结符或可能的c（空字）的集合，其中α可能是文法符号、c或者候选式，或候选式的一部分。定义为：First(α) = {a|α=>a....，a∈Vt}，其计算的方式如下所示：

1）若产生式形如A->aα，则First(A->aα)={a};
2）若产生式形如A->c，则First(A->c)={c};
3）产生式形如A->Xα，则把First(X)中非c元素加入到First(A->Xα)中去
4）若有产生式形如A->X1X2X3...Xkα,则有
    1.当X1X2X3...Xi=>c（有限步骤，1<=i<=k）时，则把First(Xi+1....Xk)的所有非c元素加入到First(A->X1X2X3...Xkα)中
    2.当X1X2X3...Xk=>c（有限步骤）时，则把First(α)加入到First(A->X1X2X3...Xkα)中
           

     由上面的定义可知：

若文法符号A为终结符（A∈Vt），则First（A）={A}

若文法符号为非终结符A（A∈Vn），求First集的方法就是将非终结符A的每个候选式的First集都加入到First（A）中。

      案例如下所示：

求下述各个候选式和非终结符的First集
    E->TE'
    E'->+TE'|c
    T->FT'
    T'->*FT'|c
    F->(E)|i
-------------------------------
各个候选式的First集:
    First(E->TE') = First(T) = First(F) = {(,i}
    First(E'->+TE') = {+}
    First(E'->c) = {c}
    First(T->FT') = First(F) = {(,i)}
    First(T'->*FT') = {*}
    First(T'->c} = {c}
    First(F->(E)) = {(}
    First(F->i) = {i}
各个非终结符的First集：
    First(E) = First(T) = First(F) = {(,i}
    First(E') = {+,c}
    First(T) = {(,i}
    First(T') = {*,c}
    First(F) = {(,i}
           

    2）Follow集

        表示非终结符A的后随符号集Follow（A），定义如下：

假设S是文法G的开始符号，对G的任何非终结符A：Follow(A)={a|S=>...Aa...，a∈Vt}
若S=>...A，则规定#∈Follow(A)，
           

     通俗来讲就是Follow(A)就是所有句型中出现在紧接A之后的终结符号或者#,#表示输入符号串的结束标记。

     利用Follow集的定义，使用c产生式进行自动匹配的过程是：当非终结符A面临输入符号a，且a不属于A的任一候选式的首终结符集，但是A的某个候选式的首终结符集含有c时，只有当a∈Follow(A)，才能用c产生式进行自动匹配。

     计算文法G的每个终结符A的Follow集使用如下算法来计算：

输入：文法G
输出：非终结符A的Follow集
步骤：
    1）如果A是开始符号，则#∈Follow(A)。
    2）如果有产生式B->αAaβ,a∈Vt,把a加入到Follow(A)中。
    3）如果有产生式B->αAXβ，X∈Vn，把First(Xβ)中非c元素加入到Follow(A)中。
    4）如果B->αA，或者B->αAβ且β=>c，把Follow(B)加入到Follow(A)中。
    5）对每一个非终结符，浏览每个产生式，连续使用上述规则，直到A的Follow集不再增大为止。
           

     案例如下所示：

例1：由如下文法：
    S->Ap
    S->Bq
    A->a
    A->cA
    B->b
    B->dB
则Follow集如下所示：
    Follow(S)={#}（规则1，因为是开始符号）
    Follow(A)={p}（规则2）
    Follow(B)={q}（规则2）

例2：有如下文法：
    1) E->TE'
    2) E'->+TE'
    3) E'->c
    4) T->FT'
    5) T'->*FT'
    6) T'->c
    7) F->(E)
    8) F->i
计算的各个非终结符的Follow集如下所示：
    1）Follow(E)={#,)}。E是开始符号，应用规则1；根据产生式7，应用规则2。
    2）Follow(E')=Follow(E)={#,)}
    3）Follow(T)=(First(E')-{c})∪Follow(E')={#,),+}（规则3，4）
    4）Follow(T')=Follow(T)={#,),+}
    5）Follow(F)=(First(T')-{c})∪Follow(T)={*,#,),+}
   
           

     3）文法的判别方法

1.检查是否含有左递归
2.如果没有左递归，则计算其First集，判别其First集是否相交，即是否有回溯
3.若存在某个A=>ε,求A的 Follow集，并判别条件 (3) 是否满足(是否可以使用ε-产生式进行匹配)
           

3.3.7 递归下降分析方法

     是进行语法分析的一种方法，要求文法是LL(1)文法。

     1）实现思想如下所示：

1）：分析程序由一组函数组成。每个函数对应于文法的一个非终结符号。
2）：每一个函数的功能是：判断选择该非终结符的哪个候选式，并按该候选式的要求处理完输入符号串。在该候选式的右部中
若遇到非终结符号，调用该非终结符号对应的过程来完成，若为终结符，判断是否和读入的符号相同。
           

     递归下降分析是直接以程序的方式模拟产生式产生语言的过程，即为每一个非终结符构造一个函数，每个函数的函数体按非终结符的候选式分情况展开，遇到终结符就进行比较，看是否与输入的符号相同；遇到非终结符就调用该非终结符对应的函数。 

     2）分析过程：

    从调用该文法开始符号对应的函数开始，直到所有非终结符都展开为终结符并得到匹配为止。如果分析到这一步则表示分析成功，否则表示输入符号串有错。

     3）实现方式

     对于每个非终结符U（假设U的候选式为U->U1|U2|U3|......|U4|）的函数有如下分析方法：

1）根据输入符号决定使用U的哪一个候选式进行分析
    void U( ){   
       token=当前符号;
	   if(token是First(u1)中的一个符号)  处理u1
	   else if(token是First(u2)中的一个符号)  处理u2		
       ......
	   else	error()    
    }
2）对应于某个候选式Ui（假设Ui是形如X1X2X3......Xn的候选式）的处理Ui(),就是通过顺序处理该候选式Ui的每个符号Xi来完成其功能的。
    void Ui(){
        处理X1的程序；
	    处理X2的程序；
	    ......
	    处理Xn的程序；
    }
3）对于每个符号Xi的处理
如果xi为终结符号：
    if (x == 当前输入符号串中的符号){  
        token = GetNextToken()；return;  }
    else
	    出错处理
如果xi为非终结符号，直接调用相应的过程：
    xi()
           

    4）案例如下：

     有如下文法:

E -> TE'
E' -> +TE'|c
T -> FT'
T' -> *FT'|c
F -> (E)|i
           

    编写对应的递归下降分析程序:

1）对于非终结符E，候选式为E->TE'
    void E(){
        T();
        E'();
    }
2）对于非终结符E',候选式为E'->+TE'|c
    void E'(){
        if(token=='+'){
            match('+');
            T();
            E'();
        }
    }
3）对于非终结符T，候选式为T->FT'
    void T(){
        F();
        T'();
    }
4）对于非终结符T',候选式为T'->*FT'|c
    void T'(){
        if(token=='*'){
            match('*');
            F();
            T'();
        }
    }
5）对于非终结符F,候选式为F->i|(E)
    void F(){
        if(token=='('){
            match('(');
            E();
            if(token==')'){
                match(')');
            }else{
                error();
            }
        }else if(token=='i'){
            match('i'); 
        }else{
            error();
        }
    }
           

    5）分析程序的接口如下所示：