编译原理-实验二-LL(1)语法分析程序的设计

一、实验目的

         了解LL(1)分析器的基本构成及用自顶向下的LL(1)方法对表达式进行语法分析的方法，掌握LL(1)语法分析程序的构造方法。

二、实验内容

         根据LL(1)语法分析算法的基本思想，设计一个对给定文法进行LL(1)语法分析的程序，并用C、C++或Java语言编程实现。要求程序能够对从键盘输入的任意字符串进行分析处理，判断出该输入串是否是给定文法的有效句子，并针对该串给出具体的LL(1)语法分析过程。

三、实验要求​​​​​​

对给定文法G[S]：

S->AT      

A->BU    

T->+AT|$     

U->*BU|$   

B->(S)|m

其中，$表示空串。

1、手工判断上述文法G[S]是否LL(1)文法，若不是，将其转变为LL(1)文法；

2、对转变后的LL(1)文法手工建立LL(1)分析表；

3、根据清华大学出版编译原理教材上算法思想，构造LL(1)分析程序；

4、用LL(1)分析程序对任意键盘输入串m+m*m#进行语法分析，并根据栈的变化状态输出给定串的具体分析过程。

四、运行结果示例

       从任意给定的键盘输入串：

               m+m*m#；

       输出：

                                                      用LL(1)分析法分析符号串m+m*m#的过程

五、实验提示

       本实验重点有两个：一是如何用适当的数据结构实现LL(1)分析表存储和使用；二是如何实现各规则右部串的逆序入栈处理。

建议：使用结构体数组。

六、分析与讨论

1、若输入串不是指定文法的句子，会出现什么情况？

2、总结LL(1)语法分析程序的设计和实现的一般方法。

个人实验代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;

//表格数组
char LL1[50][50][100] = {{\"->AT\",\"->AT\" ,\"null\",\"null\" ,\"null\",\"null\" },
                         {\"->BU\",\"->BU\" ,\"null\",\"null\" ,\"null\", \"null\"},
                         {\"null\",\"null\" ,\"->$\" ,\"->+AT\",\"null\",\"->$\"  },
                         {\"null\",\"null\" ,\"->$\" ,\"->$\"  ,\"->*BU\",\"->$\"  },
                         {\"->m\" ,\"->(S)\",\"null\",\"null\" ,\"null\",\"null\" } };
char H[200]=\"SATUB\";
char L[200]=\"m()+*#\";
stack<char>cmp;

int findH(char a)
{
    for(int i = 0; i < 5; i++)//找到对应行
    {
        if(a==H[i])
        {
            return i;
        }
    }
    return -1;
}
int findL(char b)
{
    for(int i = 0; i < 6; i++)//找到对应列
    {
        if(b==L[i])
        {
            return i;
        }
    }
    return -1;
}
int error(int i,int cnt, int len, char p[],char str[])
{
    printf(\"%d\\t%s\\t\",cnt,p);
    for(int q = i; q<len;q++)
    {
        cout<<str[q];
    }
    printf(\"\\t报错\\n\");
    return len;
}
void analyze(char str[],int len)
{
    int cnt = 1;//输出Step专用
    int i = 0;
    char p[200] = \"#S\";//输出stack专用
    int pindex = 2;
    printf(\"Step\\tStack\\tString\\tRule\\n\");
    while(i<len)
    {
        int x,y;
        char ch = cmp.top();
        if(ch>=\'A\'&&ch<=\'Z\')
        {
            cmp.pop();
            x = findH(ch);
            y = findL(str[i]);
            if(x!=-1&&y!=-1)
            {
                int len2 = strlen(LL1[x][y]);
                if(strcmp(LL1[x][y],\"null\")==0)
                {
                    i = error(i,cnt,len,p,str);
                    continue;
                }
                printf(\"%d\\t%s\\t\",cnt,p);
                if(p[pindex-1] != \'#\')
                {
                    p[pindex] = \'\\0\';
                    pindex--;
                }
                if(LL1[x][y][2]!=\'$\')
                {
                    for(int q = len2-1; q>1; q--)
                    {
                        p[pindex++] = LL1[x][y][q];
                        cmp.push(LL1[x][y][q]);
                    }
                }else
                {
                    p[pindex] = \'\\0\';
                    pindex--;
                }
                for(int q = i; q<len;q++)
                {
                    cout<<str[q];
                }
                printf(\"\\t%c%s\\n\",ch,LL1[x][y]);
            }else
            {
                i = error(i,cnt,len,p,str);
                continue;
                ///未找到，报错
            }

        }else
        {
            if(ch==str[i])
            {
                cmp.pop();
                printf(\"%d\\t%s\\t\",cnt,p);
                if(ch==\'#\'&&str[i]==\'#\')
                {
                    printf(\"#\\t接受\\n\");
                    return ;
                }
                for(int q = i; q<len;q++)
                {
                    cout<<str[q];
                }
                printf(\"\\t%c匹配\\n\",ch);
                pindex--;
                p[pindex] = \'\\0\';
                i++;
            }else
            {
                i = error(i,cnt,len,p,str);
                continue;
                ///报错
            }
        }
        cnt++;
    }


}
int main()
{
    //cout<<H[0]<<H[4]<<endl;
    //cout<<L[0]<<L[5]<<endl;
    /*for(int i = 0; i < 5; i++)
    {
        for(int j = 0 ; j < 6; j++)
            printf(\"%5s\",LL1[i][j]);
            cout<<endl;
    }*/
    char str[200];
    cin>>str;
    int len = strlen(str);
    cmp.push(\'#\');
    cmp.push(\'S\');
    analyze(str,len+1);
    return 0;
}
/*
输入串：m+m*m#
输出
Step    Stack   String  Rule
1       #S      m+m*m#  S->AT
2       #TA     m+m*m#  A->BU
3       #TUB    m+m*m#  B->m
4       #TUm    m+m*m#  m匹配
5       #TU     +m*m#   U->$
6       #T      +m*m#   T->+AT
7       #TA+    +m*m#   +匹配
8       #TA     m*m#    A->BU
9       #TUB    m*m#    B->m
10      #TUm    m*m#    m匹配
11      #TU     *m#     U->*BU
12      #TUB*   *m#     *匹配
13      #TUB    m#      B->m
14      #TUm    m#      m匹配
15      #TU     #       U->$
16      #T      #       T->$
17      #       #       接受

输入：m#
输出
Step    Stack   String  Rule
1       #S      m#      S->AT
2       #TA     m#      A->BU
3       #TUB    m#      B->m
4       #TUm    m#      m匹配
5       #TU     #       U->$
6       #T      #       T->$
7       #       #       接受

输入：S#
输出
Step    Stack   String  Rule
1       #S      S#      报错

输入：m*m#
输出
Step    Stack   String  Rule
1       #S      m*m#    S->AT
2       #TA     m*m#    A->BU
3       #TUB    m*m#    B->m
4       #TUm    m*m#    m匹配
5       #TU     *m#     U->*BU
6       #TUB*   *m#     *匹配
7       #TUB    m#      B->m
8       #TUm    m#      m匹配
9       #TU     #       U->$
10      #T      #       T->$
11      #       #       接受
*/