上から下への構文解析–再帰的降下解析–式評価

以下の内容はacmolのブログから転載します.
まず、適切な正しい生成式を見つけて、生成式で非終端記号ごとに再帰関数を書けばいいです.
たとえば、式の評価では、次の式を生成できます.

Expression->Term|Expression+Term|Expression-Term

Term->Factor|Term*Factor|Term/Factor

Factor->(Expression)| number

この生成または式構文を正しく表すことができます.
この生成式には左再帰(E−>E+Tのような形式)が含まれているため,直接再帰降下解析法でプログラムを書くとデッドサイクルに陥る.
本手法では,E−>E+TとE−>T+Eで生成された言語のすべての文が同じ(あるいは2つの文法は等価)であるため,この手法を直接に:

Expression->Term|Term+Expression|Term-Expression

Term->Factor|Factor*Term|Factor/Term

Factor->(Expression)| number

最後に、プログラムが作成された後のテストで、1-2-3という式の結合性に問題があり、上の生成式で得られた結果は:2.結果として2-3=-1を先に算出するからである.
結論を得る:2つの文法が等価であるというわけではなく、2つの文法がいつでも自由に交換できることを説明することができる.
次に、通常の左再帰を除去する方法で生成式を書きます.

E->TE2
E2->+TE2 | -TE2 | ε
T->*FT2
T2->*FT2 | /FT2 |ε
F->(E) | i

そして、プログラムは書きやすいです.次のプログラムでは、入力が1桁の場合のみ処理されます.

#include<cstdio> 
char expr[100]="(1+8)/(5-2)-2*3-1"; 
int start=0; 
double T(); 
double T2(); 
double F(); 
double E2(); 
double E() 
{   return T()+E2(); 
} 
double E2() 
{   switch(expr[start])     
    {   case '+':start++;return T()+E2();     
        case '-':start++;return -T()+E2();     
        default:return 0;     
    } 
} 
double T() 
{   return F()*T2(); 
} 
double T2() 
{   double a,b;     
    switch(expr[start])     
    {   case '*':start++;return F()*T2();     
        case '/':start++;a=F(),b=T2();         
        return b/a;     
        default:return 1;     
    }   
} 
double F() 
{   if(expr[start]=='(')     
    {   double a;         
        start++;a=E();start++;         
        return a;     
    }     
    return expr[start++]-'0'; 
} 
int main() 
{   printf("%f
",E()); 
}

ここでコードは例示にすぎず、1桁の数字しか処理されていないことに注意してください.
同じ方法で接尾辞式の接尾辞を完成するコードは以下の通りである.

#include<iostream> 
#include<cstdio> 
#include<string> 
using namespace std; 
char expr[1010];
int start=0;
string T();
string T2();
string F();
string E2(); 
string E() 
{   string a=T(),b=E2();     
    return a+b; 
} 
string E2() 
{   string a,b;     
    switch(expr[start])     
    {   case '+':start++;a=T();b=E2();return a+"+"+b;     
        case '-':start++;a=T();b=E2();return a+"-"+b;     
        default:return "";     
    } 
} 
string T() 
{   string a=F(),b=T2();     
    return a+b; 
} 
string T2() 
{   string a,b;     
    switch(expr[start])     
    {   case '*':start++;a=F();b=T2();return a+"*"+b;     
        case '/':start++;a=F();b=T2();return a+"/"+b;     
        default:return "";     
    } 
} 
string F() 
{   if(expr[start]=='(')     
    {   string a;         
        start++;a=E();start++;         
        return a;     
    }     
    return string(1,expr[start++]); 
} 
int main() 
{   scanf("%s",expr);     
    start=0;     
    cout<<E()<<endl; 
}