表达式语法分析——预测分析法

小鱼儿 2022-05-25 11:42 248阅读 0赞

表达式语法分析——预测分析法

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次产生式后，发现语法错误，该输入串不是合法表达式，输出如下：

1 E->TG

2 T->FS

3 F->i

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->^

error!

Sample Input  
i+i\*i\#  
Sample Output  
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!  
Hint

Source

#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;
        }
    
    }