编译原理实验二(LL1分析法)

// ll1.h
#include <iostream>
using namespace std;

#ifndef LL1_H
#define LL1_H


#define LEN_VT 8
#define LEN_VN 5

struct stack
{
    char ch;
    stack *next;
    stack *front;
};
// 双链表模拟栈

class LL1
{
    public:
        LL1(char input[], int len); // 构造函数
        void stack_pop(char *ch);   // 弹栈, 将栈顶元素弹出
        void stack_push(char ch);  // 压栈，将压到栈顶
        bool isVn(char ch); // 判断非终结符
        int getIndex(char ch, char table[], int len); // 查找数组下标

        void Atable();  // 分析表处理
        void show(int step, char *in, string CA, string action); // 输出分析结果
    private:
        stack *bp,*sp; //栈低、栈顶指针
        char X, Y; // 临时存放从栈顶取出的字符和从输入缓冲中取出的字符
        char Vt[8] = {'i', '(', ')', '*', '/', '+', '-', '#'}; // 终结符和‘#’
        char Vn[5] = {'E', 'G', 'T', 'S', 'F'}; // 非终结符
        char input[10]; // 输入缓冲区
         /*
        E->TG
        G->+TG|-TG
        G->~  
        T->FS
        S->*FS|/FS
        S->~  
        F->(E)
        F->i
        */
       /*
        ***************FIRST***********************
        FIRST(E)={(,i}
        FIRST(F)={(,i}
        FIRST(G)={+,-,~}
        FIRST(S)={*,/,~}
        FIRST(T)={(,i}
        ****************FOLLOW**********************
        FOLLOW(E)={#,)}
        FOLLOW(F)={#,),*,+,-,/}
        FOLLOW(G)={#,)}
        FOLLOW(S)={#,),+,-}
        FOLLOW(T)={#,),+,-}
        */
        string vTable[5][8] = {
            {"E->TG",  "E->TG",  "Error",  "Error",   "Error",   "Error",   "Error",  "Error"},// E
            {"Error",  "Error",  "G->~",   "Error",   "Error",   "G->+TG",  "G->-TG", "G->~"},// G
            {"T->FS",  "T->FS",  "Error",  "Error",   "Error",   "Error",   "Error",  "Error"},// T
            {"Error",  "Error",  "S->~",   "S->*FS",  "S->/FS",  "S->~",    "S->~",   "S->~"},// S
            {"F->i",   "(E)",    "Error",  "Error",   "Error",   "Error",   "Error",  "Error"} // F
        };  //预测分析表
};

#endif

//ll1.cpp
#include "ll1.h"
#include<cstring>
#include <algorithm>

void LL1::show(int i, char *in, string CA, string action)
{
    string a_stack;
    stack *p;
    p = bp;
    do{
        a_stack += p->ch;
        p = p->next;
    }while(p != NULL);
    cout<<i<<"\t\t"<<a_stack<<"\t\t"<<in<<"\t\t"<<CA<<"\t\t"<<action<<endl;
}

void LL1::Atable()
{
    printf("Step\t\tStack\t\tInput\t\tC-A\t\tAction\n");
    char *p = input;
    int i=0;    // 记录步数
    char sp_value; // 临时记录弹出的栈顶符号
    stack_push('E');
    show(i++, p, "", "init");
    X = sp->ch;
    Y = *p;
    while(X != '#' && Y != '#'){ // 分析结束条件
        X = sp->ch;
        Y = *p;
        if(X == Y && X!= '#' && Y != '#'){
            stack_pop(&sp_value);    // 栈顶元素弹出
            p++;    // 指向下一个字符
            show(i++, p, "","GETNEXT(I)");
        }else if(isVn(X)){
            string temp;
            temp = vTable[getIndex(X,Vn,5)][getIndex(Y,Vt,8)];
            if(temp != "Error"){
                if(temp[3] == '~'){
                    stack_pop(&sp_value);
                    X = sp->ch;
                    show(i++, p, temp, "POP");
                }else{
                    string t = temp;
                    temp = temp.substr(3,temp.length()-3); // 截取产生式右部
                    reverse(temp.begin(), temp.end());
                    stack_pop(&sp_value);
                    for(int j=0; j<temp.length(); j++)
                        stack_push(temp[j]);
                    X = sp->ch;
                    show(i++, p, t, "POP,PUSH("+t.substr(3,t.length()-3)+")");
                }
            }else{
                // M[X,a]对应位置为Error的情况
                cout<<"Error:Input string is invalid"<<endl;
                break;
            }

        }else{
            cout<<"Error:wrong input!"<<endl;
            break;
        }
    }
}

int LL1::getIndex(char ch, char table[], int len)
{
    int i=0;
    for(i; i<len;i++)
        if(ch == table[i])
            return i;
        else
            continue;
    return -1; //查找失败
}

bool LL1::isVn(char ch)
{
    for(int i=0; i<LEN_VN; i++){
        if(ch == Vn[i])
            return true;
        else
            continue;
    }
    return false;
}

void LL1::stack_pop(char *ch)
{
    stack *p;
    p = sp;
    *ch = p->ch;
    sp = sp->front;
    sp->next = NULL;
    p->front = NULL;
    delete p;
}

void LL1::stack_push(char ch)
{
    /*
    模拟压栈操作
    */
   stack *q;
   q = new stack;
   q->ch = ch;
   q->next = NULL;
   q->front = sp;
   sp->next = q;
   sp = q;
}

LL1::LL1(char in[], int len)
{
    // 初始化栈
    sp = new stack;
    sp->ch = '#';
    sp->front = NULL;
    sp->next = NULL;
    bp = sp;

    for(int i=0; i<=len ; i++) // 初始化缓冲半区
        input[i] = in[i];
}

//main.cpp
#include "ll1.h"

int main()
{
    cout<<"Only the following characters are supported:"<<endl;
    cout<<"'i', '(', ')', '*', '/', '+', '-'\n"<<endl;
    // 主调函数获取输入写入缓冲区
    char input[10]="i+i*i#";
    start:
    cout<<"Enter a string ending in #: ";
    cin>>input;
    int i = 0;
    char ch;
    while((ch=input[i]) != '#'){
        if(ch == 'i' || ch == '(' \
        || ch == ')' || ch == '*' \
        || ch == '/' || ch == '+' || ch == '-')
            if(i<10){
                input[i] = ch;
                i++;
                continue;
            }
            else{
                cout<<"input too long"<<endl;
                goto start;
            }
        else{
            cout<<"wrong input!"<<endl;
            goto start;
        }
    }
    LL1 L(input, i);
    L.Atable();
}