表達式文法分析——預測分析法

表達式文法分析——預測分析法
           

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

預測分析法是自頂向下分析的一種方法，一個預測分析程式是由三個部分組成：

(1) 預測分析程式

(2) 先進後出棧

(3) 預測分析表

現給出表達式文法：

E→TG

G→+TG | ε

T→FS

S→*FS | ε

F→(E) | i
           

該表達式文法是LL(1)文法，其預測分析表為：

請根據該預測分析表構造預測分析程式，完成對表達式的文法分析，對給定的輸入串，判斷其是否為合法表達式，給出所使用的産生式序列。

Input

給定輸入串（長度不超過50個符号，以#号結束，符号保證是終結符或#）。

例如：

i+i*i# 是合法表達式

i+i*(i+i)# 是合法表達式

ii+i*i# 不是合法表達式

i*(i+i# 不是一個合法的表達式。

Output

要求輸出分析過程中使用的所有産生式，産生式按使用順序各占一行，每行有兩個資料，使用順序号（從1開始編号）及産生式本身，中間用一個空格分開，最後一行表示文法分析是否成功結束，如果成功分析結束輸出acc!，表示該輸入串是合法表達式，否者輸出error!，表示該輸入串不是合法表達式。

注：其中^符号代表文法中的ε符号。

針對輸入串i+i*i#，因為分析過程使用了11次産生式，且該輸入串是合法表達式，輸出如下：

1 E->TG

2 T->FS

3 F->i

4 S->^

5 G->+TG

6 T->FS

7 F->i

8 S->*FS

9 F->i

10 S->^

11 G->^

acc!

針對輸入串i*(i+i#，因為分析過程使用了14次産生式後，發現文法錯誤，該輸入串不是合法表達式，輸出如下：

4 S->*FS

5 F->(E)

6 E->TG

7 T->FS

8 F->i

9 S->^

10 G->+TG

11 T->FS

12 F->i

13 S->^

14 G->^

#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
    string a[200][200];
    string b,s;
    b="#E";
    int i=2,l=1;
    a['E']['i']="E->TG";
    a['E']['(']="E->TG";
    a['G']['+']="G->+TG";
    a['G'][')']="G->^";
    a['G']['#']="G->^";
    a['T']['i']="T->FS";
    a['T']['(']="T->FS";
    a['S']['+']="S->^";
    a['S']['*']="S->*FS";
    a['S'][')']="S->^";
    a['S']['#']="S->^";
    a['F']['i']="F->i";
    a['F']['(']="F->(E)";
    cin>>s;
    int sl=s.length(),sl1=0;
    while(b[i-1]!='#'||s[sl1]!='#')
    {
        if(b[i-1]>='A'&&b[i-1]<='Z')
        {
        if(a[b[i-1]][s[sl1]]!="")
        {
            cout<<l++<<" "<<a[b[i-1]][s[sl1]]<<endl;
            if(b[i-1]=='E'&&(s[sl1]=='i'||s[sl1]=='('))
                {
                    b[i-1]='G';
                    b[i++]='T';
                }
                else if(b[i-1]=='G'&&s[sl1]=='+')
                {
                  b[i-1]='G';
                  b[i++]='T';
                  b[i++]='+';

                }
                else if(b[i-1]=='G'&&(s[sl1]==')'||s[sl1]=='#'))
                {
                  i--;
                }
                else if(b[i-1]=='T'&&(s[sl1]=='i'||s[sl1]=='('))
                {
                    b[i-1]='S';
                    b[i++]='F';
                }
                else if(b[i-1]=='S'&&s[sl1]=='*')
                {
                   b[i-1]='S';
                   b[i++]='F';
                   b[i++]='*';
                }
                else if(b[i-1]=='S'&&(s[sl1]=='+'||s[sl1]==')'||s[sl1]=='#'))
                {
                   i--;
                }
                else if(b[i-1]=='F'&&s[sl1]=='i')
                {
                   b[i-1]='i';
                }
                else if(b[i-1]=='F'&&s[sl1]=='(')
                {
                   b[i-1]=')';
                   b[i++]='E';
                   b[i++]='(';
                }
        }
        else
        {
            cout<<"error!"<<endl;
            break;
        }
        }
        else
        {
            if(b[i-1]==s[sl1])
            {
                i--;
                sl1++;
            }
            else
          {
              cout<<"error!"<<endl;
          break;
          }
        }
    }
    if(b[i-1]=='#'&&s[sl1]=='#')
    {
      cout<<"acc!"<<endl;
    }

}