递归下降法的实现

递归下降法的实现

(2012-11-24 19:02:35)

转载▼

标签： 杂谈

分类： 编译原理

【原始文法】

EàE and E

|E or E

|not E

|true

|false

|(E) 

【消除二义性】

Eà E or T

|T

TàT and F

   |F

Fànot F

   |(E)

   |true

   |false

【消除左递归】

EàTE’

E’à or TE’ | e

TàFT’

T’àand FT’ |e

Fànot F

  |(E)

  |true

  |false

 【为简化程序，将终结符用单字符代替】

EàTE’

E’à +TE’ | e

TàFT’

T’à*FT’ |e

Fà!F

Fà(E)

Fà1

Fà0

【例句】

1*！0+1  ==  true and not false or true

【求非终结符的首符号集】

First(F)={0,1,(,!}

First(T’)={*,e}

First(T)=First(F)={0,1,(,!}

First(E’)={+,e}

First(E)=First(T)={0,1,(,!}

 【求非终结符的后继符号集】

Follow(E)={$,)}

Follow(E’)={$,)}

Follow(T)={+,$,)}

Follow(T’)={+,$,)}

Follow(F)={*,+,$,)}

【总结】

(1)   通过设置运算的优先级和结合顺序消除语法中的二义性；

(2)   消除左递归

a)        直接左递归

b)       简接左递归

(3)   消除公共左因子

(4)   根据依赖关系对产生式进行拓扑排序

(5)   计算首字符集（从后往前）和后续字符集（从前往后）

(6)   编写递归下降语法分析程序；

【实现Recursive Descent算法】

#include

using namespace std;

char input[100];

char *lookhead=NULL;

//declare functions corresponding with nonterminal symbols

void E();

void E1();

void T();

void T1();

void F();

void error(){

     lookhead=input;

     }

void match(char c){

     if (*lookhead==c)

        lookhead=lookhead+1;

     else

     error();

     }

     

void E(){

     if ((*lookhead=='0')||(*lookhead=='1')||(*lookhead=='(')||(*lookhead=='!'))

        {

        T();

        E1();

        }                                                             

     else 

          error();

     }

void E1(){

     if (*lookhead=='+')

        {match('+');T();E1();}                                                             

     else 

         return;

     }

void T(){

     if ((*lookhead=='(')||(*lookhead=='!')||(*lookhead=='1')||(*lookhead=='0'))

        {

        F();

        T1();

        }                                                             

     else 

          error();

     

     }

void T1(){

     if (*lookhead=='*')

        {

        match('*');

        F();

        T1();

        }                                                             

     else 

          return;

     }

void F(){

     if (*lookhead=='!')

     {

     match('!');

     F();

     }                                                             

     else 

          if (*lookhead=='(')

          {

          match('(');

          E();

          match(')');

          }

          else 

               if (*lookhead=='0')

               {

               match('0');

               }

               else

                   if (*lookhead=='1')

                   {

                   match('1');

                   }

                   else

                       error();

     }

     

int main(void){

    while (1){

          

          

          cout<<"INPUT :";

          cin>>input;

          lookhead=input;

          

          E();

          if (*lookhead=='$')

             cout<<"YES."<<endl;    

          else

              cout<<"NO."<<endl; 

              

          cout<<endl<<endl;

          

    }

    return 0;

}