精华内容
下载资源
问答
  • SLR1文法输入串的分析,使用P101页文法和分析表
    2019-07-19 15:02:58
    #include "iostream"
    #include "string"
    #include "stack"
    #include "list"
    using namespace std;
    #define empty 100
    #define acc 0
    #define error 1000
    int get(char temp);
    int getGOTO(char temp);
    int main()
    {
    	//定义action表,正数表示移进项目,负数表示规约项目
    	//i第0列,+第1列,*第二列,(第三列,)第四列,#第五列
    	int action[12][6] = { {5,empty,empty,4,empty,empty,},
    						{ empty,6,empty,empty,empty,acc,},
    						{empty,-2,7,empty,-2,-2,},
    						{empty,-4,-4,empty,-4,-4,},
    						{5,empty,empty,4,empty,empty,},
    						{empty,-6,-6,empty,-6,-6,},
    						{5,empty,empty,4,empty,empty,},
    						{5,empty,empty,4,empty,empty,},
    						{empty,6,empty,empty,11,empty,},
    						{empty,-1,7,empty,-1,-1,},
    						{empty,-3,-3,empty,-3,-3,},
    						{empty,-5,-5,empty,-5,-5} };
    	//定义GOTO表,第0列表示E,第1列表示T,第二列表示F
    	int GOTO[12][3] = { {1,2,3,},
    						{empty,empty,empty,},
    						{empty,empty,empty,},
    						{empty,empty,empty,},
    						{8,2,3,},
    						{empty,empty,empty,},
    						{empty,9,3,},
    						{empty,empty,10,},
    						{ empty,empty,empty,},
    						{ empty,empty,empty,},
    						{empty,empty,empty,},
    						{empty,empty,empty,},
    	};
    	cout << "请输入字符串" << endl;
    	string a;
    	cin >> a;
    	list<int> state;//状态栈,list只从前面插入数据,模仿栈
    	state.push_front(0);//把0压栈
    	list<char> character;//符号栈
    	character.push_front('#');//把#压栈
    	list<char> str;//输入串栈
    	str.push_front('#');//把#压栈
    	for (int i = a.length() - 1; i >= 0; i--)
    	{
    		str.push_front(a[i]);//把输入串入栈
    	}
    	//输出初始状态
    	cout << "状态             符号              输入串      " << endl;
    	cout << 0 << "                 " << "#" << "                " << a + "#" << endl;
    	
    	while(str.size()>=1){
    	int tempstate = state.front();//获得状态栈栈顶元素
    	//cout << "栈顶元素" << tempstate << endl;
    	char tempstr = str.front();//获得输入串栈顶元素
    	int cha = get(tempstr);//将i,+,*,(,),#转为对应的列号
    	if (cha == 1000)
    	{
    		cout << "不能接收" << endl;
    		break;
    	}
    //	cout << cha << endl;
    	int tempAction = action[tempstate][cha];
    	//	cout << tempAction << endl;
    	if (tempAction > 0)//表明是移进项目
    	{
    		state.push_front(tempAction);
    		character.push_front(tempstr);
    		str.pop_front();
    		//输出状态栈
    		
    			for (list<int>::reverse_iterator i = state.rbegin(); i != state.rend(); i++)
    				cout << *i;
    			for (int k = state.size(); k < 6; k++)
    				cout << " ";
    		cout << "            ";
    		//输出符号栈
    		for (list<char>::reverse_iterator i = character.rbegin(); i != character.rend(); i++)
    			cout << *i;
    		for (int k = character.size(); k < 5; k++)
    			cout << " ";
    		cout << "            ";
    		//输出输入串
    		for (list<char>::iterator i = str.begin(); i != str.end(); i++)
    			cout << *i;
    		cout << endl;
    	}
    	else if (tempAction < 0)//表明是规约项目
    	{
    		//规约项目则要弹出状态栈元素,输入串元素不弹出,符串栈元素进行规约
    		state.pop_front();
    		//对于符号栈
    		switch (tempAction)
    		{
    		case -1://E->E+T
    		{
    			character.pop_front();
    			character.pop_front();
    			character.pop_front();
    			character.push_front('E');
    		}
    		break;
    		case -2://E->T
    		{
    			character.pop_front();
    			character.push_front('E');
    		}
    		break;
    		case -3://T->T*F
    		{
    			character.pop_front();
    			character.pop_front();
    			character.pop_front();
    			character.push_front('T');
    		}
    		break;
    		case -4://T->F
    		{
    			character.pop_front();
    			character.push_front('T');
    		}
    		break;
    		case -5://F->(E)
    		{
    			character.pop_front();
    			character.pop_front();
    			character.pop_front();
    			character.push_front('F');
    		}
    		break;
    		case -6://F->i
    		{
    			character.pop_front();
    			character.push_front('F');
    		}
    		break;
    		}
    		int statelength = state.size();//状态栈元素个数
    		int characterlength = character.size();//符号栈元素个数
    		if (statelength > characterlength)
    		{
    			int l1 = statelength - characterlength;//二者的差
    			for (int j = 0; j < l1; j++)
    			{
    				state.pop_front();//弹出多余的状态元素,让状态栈与符号栈平衡
    			}
    		}
    		else if (statelength < characterlength)
    		{
    			int l = state.front();//得到状态栈的栈顶元素
    			char l2 = character.front();//得到符号栈栈顶元素
    			int l3 = 0;
    			if (l2 == 'E')
    				 l3 = 0;
    			else if (l2 == 'T')
    				 l3 = 1;
    			else if (l2 == 'F')
    				 l3 = 2;
    			else {
    				cout << "不能接收哟" << endl;
    				break;
    			}
    			int l4 = GOTO[l][l3];
    			state.push_front(l4);//入栈
    		}
    		//输出状态栈
    		for (list<int>::reverse_iterator i = state.rbegin(); i != state.rend(); i++)
    			cout << *i;
    		for (int k = state.size(); k < 6; k++)
    			cout << " ";
    		cout << "            ";
    		//输出符号栈
    		for (list<char>::reverse_iterator i = character.rbegin(); i != character.rend(); i++)
    			cout << *i;
    		for (int k = character.size(); k < 5; k++)
    			cout << " ";
    		cout << "            ";
    		//输出输入串
    		for (list<char>::iterator i = str.begin(); i != str.end(); i++)
    			cout << *i;
    		cout << endl;
    
    	}
    	else if (tempAction == 0)//表明accept
    	{
    	cout << "accept" << endl;
    		break;
    	}
    }
    	system("pause");
    	return 0;
    }
    //对于i,+,*,(,),#转为对应的列号
    int get(char temp)
    {
    	if (temp == 'i')
    		return 0;
    	else if (temp == '+')
    		return 1;
    	else if (temp == '*')
    		return 2;
    	else if (temp == '(')
    		return 3;
    	else if (temp == ')')
    		return 4;
    	else if (temp == '#')
    		return 5;
    	else
    		return error;
    }

     

    更多相关内容
  • 编译原理实验之SLR1文法分析

    千次阅读 2018-06-14 09:47:00
    ---内容开始--- 这是一份编译原理实验报告,分析表是手动造的,可以作为借鉴。 基于 SLR(1) 分析法的语法制导翻译及中间...2 、目标任务[ 实验 项目] 完成以下描述赋值语句 SLR(1)文法语法制导生成中间代码四元式...

    ---内容开始---

    这是一份编译原理实验报告,分析表是手动造的,可以作为借鉴。

    基于  SLR(1) 分析法的语法制导翻译及中间代码生成程序设计原理与实现
    1 、理论传授
    语法制导的基本概念,目标代码结构分析的基本方法,赋值语句语法制导生成四元式的
    基本原理和方法,该过程包括语法分析和语义分析过程。


    2 、目标任务
    [ 实验 项目] 完成以下描述赋值语句 SLR(1)文法语法制导生成中间代码四元式的过程。
    G[A]:A→V=E
    E→E+T∣E-T∣T
    T→T*F∣T/F∣F
    F→(E)∣i
    V→i
     [ 设计说明 ] 终结符号 i 为用户定义的简单变量,即标识符的定义。
     [ 设计要求] 

    (1)构造文法的 SLR(1)分析表,设计语法制导翻译过程,给出每一产生式
    对应的语义动作;

    (2)设计中间代码四元式的结构;

    (3)输入串应是词法分析的输出二元式序列,即某赋值语句“专题 1”的输出结果,输出为赋值语句的四元式序列中间文件;

    (4)设计两个测试用例(尽可能完备),并给出程序执行结果四元式序列。
     

    3、 程序功能描述

    在第一次实验词法分析输出结果的基础上设计SLR1文法分析过程,并了解四元式的形成:

    1. 输入串为实验一的二元式序列
    2. 输出为对输入串的SLR(1)文法的判断结果
    3. 输出有针对输入串的SLR(1)文法的具体分析过程
    4. 有对输入串的四元式输出序列

    4、 主要数据结构描述

    二元组结构体,用来存储词法分析程序输出的二元组对 <类别,单词>:

    int count;

    struct eryuanzu

    {

    int a;

    char temp[COUNT];

    }m[COUNT];

     

    void out(int a,char* temp){// 打印二元组

     

    printf("< %d %s >\n",a,temp);

    m[count].a=a;

    strcpy(m[count].temp,temp);  //

    count++;

    }

     

    SLR1分析过程中所要用到的状态栈、符号栈等:

     

    stack<int> state;           //状态栈

    stack<char> sign;           //符号栈

    char st; //规约弹出时,状态栈顶元素

    int flag=0; //标志是否是SLR

    stack<string> place;        //变量地址栈

     

    ACTION表,二维数组表示:

    /* i  ( ) + - * / =  #

    1开头的百位数为s移进项,0error-1accept,其余的一位两位数是r规约项*/

    int ACTION[20][9]={{103,0,0,0,0,0,0,0,0},//0

    {0,0,0,0,0,0,0,0,-1},

    {0,0,0,0,0,0,0,104,0},

    {0,0,0,0,0,0,0,10,0},                                           

    {109,108,0,0,0,0,0,0},

    {0,0,0,110,111,0,0,0,1},//5 mnl;;huhyhjhjio

    {0,0,4,4,4,112,113,0,4},

    {0,0,7,7,7,7,7,0,7},

    {109,108,0,0,0,0,0,0,0},

    {0,0,9,9,9,9,9,0,9},

    {109,108,0,0,0,0,0,0,0},//10

    {109,108,0,0,0,0,0,0,0},

    {109,108,0,0,0,0,0,0,0},

    {109,108,0,0,0,0,0,0,0},

    {0,0,119,110,111,0,0,0,0},

    {0,0,2,2,2,112,113,0,2},//

    {0,0,3,3,3,112,113,0,3},

    {0,0,5,5,5,5,5,0,5},

    {0,0,6,6,6,6,6,0,6},

    {0,0,8,8,8,8,8,0,8}};//19

     

    ·GOTO表,二维数组表示:

    //A V E T F

    int GOTO[20][5]={{1,2,0,0,0},

    {0,0,0,0,0},//1

    {0,0,0,0,0},

    {0,0,0,0,0},

    {0,0,5,6,7},

    {0,0,0,0,0},//5

    {0,0,0,0,0},

    {0,0,0,0,0},

    {0,0,14,6,7},

    {0,0,0,15,7},

    {0,0,0,16,7},//10

    {0,0,0,0,17},

    {0,0,0,0,18},

    {0,0,0,0,0},

    {0,0,0,0,0},

    {0,0,0,0,0},//15

    {0,0,0,0,0},

    {0,0,0,0,0},

    {0,0,0,0,0},

    {0,0,0,0,0}};//19

     

    规约时所用到的函数,分别对应每一条规则:

    void R1();          //AV=E

    void R2();          //EE+T

    void R3();          //EE-T

    void R4();          //ET

    void R5();          //TT*F

    void R6();          //TT/F

    void R7();          //TF

    void R8();          //F(E)

    void R9();          //Fi

    void R10();         //Vi

     

    void R1() {

     

     

     

    sign.pop(); sign.pop(); sign.pop();       //弹出符号栈

     

    state.pop(); state.pop(); state.pop();    //弹出状态栈

     

    sign.push('A');                         //符号'A'入栈

     

    st=state.top();

     

    printf("r1\t");

     

    }

     

    void R2() {

     

     

     

    sign.pop(); sign.pop(); sign.pop();       //弹出符号栈

     

    state.pop(); state.pop(); state.pop();    //弹出状态栈

     

    sign.push('E'); st=state.top();                        //符号'E'入栈

     

    printf("r2\t\t");

     

    }

     

    void R3() {

     

     

     

    sign.pop(); sign.pop(); sign.pop();

     

    state.pop(); state.pop(); state.pop();

     

    sign.push('E');st=state.top();

     

    printf("r3\t\t");

     

    }

     

    void R4() {

     

    sign.pop();

     

    state.pop();

     

    sign.push('E');st=state.top();

     

    printf("r4\t\t");

     

    }

     

    void R5() {

     

     

     

    sign.pop(); sign.pop(); sign.pop();

     

    state.pop(); state.pop(); state.pop();

     

    sign.push('T');st=state.top();

     

    printf("r5\t\t");

     

    }

     

    void R6() {

     

     

     

    sign.pop(); sign.pop(); sign.pop();

     

    state.pop(); state.pop(); state.pop();

     

    sign.push('T');st=state.top();

     

    printf("r6\t\t");

     

    }

     

    void R7() {

     

    sign.pop();

     

    state.pop();

     

    sign.push('T');st=state.top();

     

    printf("r7\t\t");

     

    }

     

    void R8() {

     

    sign.pop(); sign.pop(); sign.pop();

     

    state.pop(); state.pop(); state.pop();

     

    sign.push('F');st=state.top();

     

    printf("r8\t\t");

     

    }

     

    void R9() {

     

    sign.pop();

     

    state.pop();

     

    sign.push('F');st=state.top();

     

    printf("r9\t\t");

     

    }

     

    void R10() {

     

    sign.pop();

     

    state.pop();

     

    sign.push('V');st=state.top();

     

    printf("r10\t\t");

     

    }

     

    SLR1分析处理函数:

     

    void SLR()

    {

    printf("输入串\t\t状态栈\t\t符号栈\t\tACTION\t\tGOTO   ");

    int i,j,k=1;

    state.push(0); //初始化

    sign.push('#');

    int which;  //对应表项内容

    char c; //输入符号串首

    int a; //坐标

    int b;

    do{

    printf("\n");

    c=m[k-1].temp[0]; //输入符号串首

    cout<<c<<' ';

    for(int j=k;j<=count;j++)

    printf("%s",m[j].temp);

    printf("\t\t");

    displayStack(state);

     

    displayStack1(sign);

    a=state.top(); //坐标

    b=isVt(c);

    /*if(isOp(c)!=-1)

    temp1=c;

    place.push(temp1);*/

    if(b!=-1)  //输入串首c是终结符

    {

     

    which=ACTION[a][b];

    if(which==-1)

    {

    printf(" acc,分析成功!\n");

    flag=1;

    break;

    }

    else if(which==0)

    { printf("error1\n ");break; }

    else if(which>=100) //移进

    {

    which=s_r(which);

    printf("s%d\t\t",which);

    sign.push(c);

    state.push(which);

    k++;

    }

    else

    {

    switch(which) //which整型,case不要加''

    {                                                                                                                                                                                                                                                        

    case 1:R1();break;

    case 2:R2();break;

    case 3:R3();break;

    case 4:R4();break;

    case 5:R5();break;

    case 6:R6();break;

    case 7:R7();break;

    case 8:R8();break;

    case 9:R9();break;

    case 10:R10();break;

    default:printf("which=%derror2\n ");break;

    }

    //状态转移 Vn

    int e=isVn(sign.top());

    if(e!=-1)

    {

    int convert=GOTO[st][e];

    state.push(convert);

    printf("GOTO[%d,%c]=%d",st,sign.top(),convert);

    }

    }

    }

    else   

    { printf("error_b ");break; }

     

    }while(which!=-1);//while

    }

     5、实验测试

    1.测试用例:i=(i-i*i)#,输入file.txt直接从文件读取输入串,得到结果如下:

     

    四元式结果输出:

     由于图片无法上传便罢

    6、 实验总结 

    本次实验是对理论课上所学知识的应用,重点是理解分析栈和符号栈,这里我采用自行造ACTION和GOTO表,这样SLR分析表就出来了,自动造表还是比较复杂。而且在造表的过程中经常出错,最后在大家的讨论中解决了。造完表后的分析过程并不复杂,按部就班分情况来处理。

    本次实验加深了我对SLR1的分析过程的理解,也加深了对四元式的认识。

     7、源代码

    分为两个CPP

    Siyuanshi.cpp   

    #include "stdafx.h"
    #include<stdlib.h>
    #include<fstream>
    #include<iostream>
    #include<stdio.h>
    using namespace std;
    
    #define MAX 100
    int mm=0,sum=0;//sum用于计算运算符的个数
                      //mm用于标输入表达式中字符的个数
    char JG='A';
    char str[MAX];//用于存输入表达式
    int  token=0;//左括号的标志
    
    /***********用于更改计算后数组中的值**************/
    void change(int e)
    {
        int f=e+2;
        char ch=str[f];    
        if(ch>='A'&&ch<='Z')
        {
            for(int l=0;l<mm+10;l++)
            {
                if(str[l]==ch)
                    str[l]=JG;
            }
        }
        
        if(str[e]>='A'&&str[e]<='Z')
        {
            for(int i=0;i<mm;i++)
            {
                if(str[i]==str[e])
                    str[i]=JG;
            }
        }    
    }
    
    
    void chengchuchuli(int i,int mm)
    {
        
        i++;
        for( ;i<=mm-1;i++)//处理乘除运算
        {
           if(str[i]=='*'||str[i]=='/') 
           {
               
               cout<<"("<<str[i]<<" "<<str[i-1]<<"  "<<str[i+1]<<"  "<<JG<<")"<<endl;
               change(i-1);
               str[i-1]=str[i]=str[i+1]=JG;
               sum--;
               JG=(char)(int)JG++;
           }
        }
    }
    
    void jiajianchuli(int j,int mm)
    {
        j++;
        for( ;j<=mm-1;j++)//处理加减运算
        {
           if(str[j]=='+'||str[j]=='-') 
           {
               cout<<"("<<str[j]<<" "<<str[j-1]<<"  "<<str[j+1]<<"  "<<JG<<")"<<endl;
               change(j-1);
               str[j-1]=str[j]=str[j+1]=JG;
               sum--;
               JG=(char)(int)JG++;
           }       
        }
    }
    
    /*扫描遍从文件中读入表达式*/
    void scan(FILE *fin)
    {   
            int p[MAX];
            char ch='a';
            int c=-1,q=0;
            while(ch!=EOF)
            {
                ch=getc(fin);
    
                while(ch==' '||ch=='\n'||ch=='\t') 
                    ch=getc(fin);//消除空格和换行符
                
                str[mm++]=ch;
                if(ch=='='||ch=='+'||ch=='-'||ch=='*'||ch=='/') 
                    sum++;
                else if(ch=='(') 
                {
                    p[++c]=mm-1;
                }
                else if(ch==')')
                {
                      q=mm-1;
                      chengchuchuli(p[c],q);//从左括号处理到又括号
                      jiajianchuli(p[c],q);                 
                      JG=(char)(int)JG--;
                      str[p[c]]=str[mm-1]=JG;
                      c--;
                      JG=(char)(int)JG++;      
                }
            }
    }    
    
    void siyuanshi()
    {
    
        for(int i=0;i<=mm-1;i++)//处理乘除运算
        {
           if(str[i]=='*'||str[i]=='/') 
           {
               
               cout<<"("<<str[i]<<"  "<<str[i-1]<<"  "<<str[i+1]<<"  "<<JG<<")"<<endl;
               change(i-1);
               str[i-1]=str[i]=str[i+1]=JG;
               sum--;
               JG=(char)(int)JG++;
           }
        
        }
    
        for(int j=0;j<=mm-1;j++)//处理加减运算
        {
           if(str[j]=='+'||str[j]=='-') 
           {
               
               cout<<"("<<str[j]<<"  "<<str[j-1]<<"  "<<str[j+1]<<"  "<<JG<<")"<<endl;
               change(j-1);
               str[j-1]=str[j]=str[j+1]=JG;
               sum--;
               JG=(char)(int)JG++;
           }
        
        } 
        
        for(int k=0;k<=mm-1;k++)//处理赋值运算
        {
           if(str[k]=='=') 
           {
               
               JG=(char)(int)--JG;
               cout<<"("<<str[k]<<"  "<<str[k+1]<<"  "<<"  "<<" "<<str[k-1]<<")"<<endl;
               sum--;
               change(k+1);
               str[k-1]=JG;
           }
        }
    
    }
    
    extern void MAIN(){
        char in[MAX]; //用于接收输入输出文件名
        FILE *fin; 
        cout<<"请输入源文件名(包括后缀名)"<<endl;
        cin>>in;;
        if ((fin=fopen(in,"r"))==NULL) 
        {
          cout<<"error"<<endl;
        }
        cout<<"*********四元式如下*********"<<endl;
        scan(fin);//调用函数从文件中读入表达式     
        siyuanshi();
        if(sum==0) printf("成功?");
        else printf("有错误");
        //关闭文件
        fclose(fin);
        system("pause");
    }

     

    Bianyi_5.cpp

    // bianyi_5.cpp : Defines the entry point for the console application.
    //
    
    #include "stdafx.h"
    #include <iostream>
    #include <string>
    #include <stack>
    #include <map>
    #include <string>
    #include <cstring>
    #include <iomanip>
    
    using namespace std;
    extern void MAIN();
    #define ADD 1
    #define SUB 2
    #define MUL 3
    #define FH 4
    #define SG 5
    #define ID 6
    #define INT 7
    #define LT 8
    #define LE 9
    #define EQ 10
    #define NE 11
    #define GT 12
    #define GE 13
    #define MHEQ 14
    #define XGMUL 15
    #define ZKH 16
    #define YKH 17
    #define DIV 18 
    #define EQ 19//=
    #define blz 00
    
    #define COUNT 40 
    char* keyword[]={"begin","end","if","then","else","for","do","and","or","not"};//保留字
    
    int count;
    struct eryuanzu
    {
        int a;
        char temp[COUNT];
    }m[COUNT];
    
    void out(int a,char* temp){// 打印二元组
    
        printf("< %d %s >\n",a,temp);
        m[count].a=a;
        strcpy(m[count].temp,temp);  //
        count++;
    }
    
    stack<int> state;           //状态栈
    stack<char> sign;           //符号栈
    char st; //规约弹出时,状态栈顶元素
    int flag=0; //标志是否是SLR
    stack<string> place;        //变量地址栈
    
                                
    /*                    i  ( ) + - * / =  #
    以1开头的百位数为s移进项,0为error,-1为accept,其余的一位或两位数是r规约项*/
    int ACTION[20][9]={{103,0,0,0,0,0,0,0,0},//0
                        {0,0,0,0,0,0,0,0,-1},
                        {0,0,0,0,0,0,0,104,0},
                        {0,0,0,0,0,0,0,10,0},                                                                                                                                                                                                                      
                        {109,108,0,0,0,0,0,0},
                        {0,0,0,110,111,0,0,0,1},//5 
                        {0,0,4,4,4,112,113,0,4},
                        {0,0,7,7,7,7,7,0,7},
                        {109,108,0,0,0,0,0,0,0},
                        {0,0,9,9,9,9,9,0,9},
                        {109,108,0,0,0,0,0,0,0},//10
                        {109,108,0,0,0,0,0,0,0},
                        {109,108,0,0,0,0,0,0,0},
                        {109,108,0,0,0,0,0,0,0},
                        {0,0,119,110,111,0,0,0,0}, 
                        {0,0,2,2,2,112,113,0,2},//
                        {0,0,3,3,3,112,113,0,3},
                        {0,0,5,5,5,5,5,0,5},
                        {0,0,6,6,6,6,6,0,6},
                        {0,0,8,8,8,8,8,0,8}};//19
    //A V E T F
    int GOTO[20][5]={{1,2,0,0,0},
                    {0,0,0,0,0},//1
                    {0,0,0,0,0},
                    {0,0,0,0,0},
                    {0,0,5,6,7},
                    {0,0,0,0,0},//5
                    {0,0,0,0,0},
                    {0,0,0,0,0},
                    {0,0,14,6,7},
                    {0,0,0,15,7},
                    {0,0,0,16,7},//10
                    {0,0,0,0,17},
                    {0,0,0,0,18},
                    {0,0,0,0,0},
                    {0,0,0,0,0},
                    {0,0,0,0,0},//15
                    {0,0,0,0,0},
                    {0,0,0,0,0},
                    {0,0,0,0,0},
                    {0,0,0,0,0}};//19
    
    void R1();          //A→V=E
    void R2();          //E→E+T
    void R3();          //E→E-T
    void R4();          //E→T
    void R5();          //T→T*F
    void R6();          //T→T/F
    void R7();          //T→F
    void R8();          //F→(E)
    void R9();          //F→i
    void R10();         //V→i
    
    int isOp(char a)  //判断二元运算符及二元运算符的优先级
    {
        int i;
        switch(a)
        {
        case '=':i=0;break;
        case '+':i=1;break;
        case '-':i=1;break;
        case '*':i=2;break;
        case '/':i=2;break;
        default:i=-1;break;
        }
        return i;
    }
    int isVt(char a)
    {
        int i;
        switch(a)
        {
        case 'i':i=0;break;
        case '(':i=1;break;
        case ')':i=2;break;
        case '+':i=3;break;
        case '-':i=4;break;
        case '*':i=5;break;
        case '/':i=6;break;
        case '=':i=7;break;
        case '#':i=8;break;
        default:i=-1;break;
        }
        return i;
    }
    int isVn(char a)
    {
        int i;
        switch(a)
        {
        case 'A':i=0;break;
        case 'V':i=1;break;
        case 'E':i=2;break;
        case 'T':i=3;break;
        case 'F':i=4;break;
        default:i=-1;break;
        }
        return i;
    }
    int s_r(int i)  //移进或者其他
    {
        int result;
        if(i/100==1)    //移进
            result=i-100;
        else
            result=i;  
        return result;
    }
    
    bool invertStack(stack<int> &one_stack) 
    {
        if (one_stack.empty())//if the stack is null,then don't invert it
        {
            return false;
        }
        else
        {
            //init a stack to save the inverted stack
            stack<int> invert;
            while (!one_stack.empty())
            {
                invert.push(one_stack.top());
                one_stack.pop();
            }
            //this moment the stack's inverted state is the stack invert ,so get it back
            one_stack = invert;
            return true;
        }
    }
    
    void displayStack(stack<int> one_stack) //打印输出
    {
        invertStack(one_stack);
        while (!one_stack.empty())
        {
            cout << one_stack.top();
            one_stack.pop();
        }
        cout << '\t' << '\t' ;
    }
    
    bool invertStack1(stack<char> &one_stack)
    {
        if (one_stack.empty())//if the stack is null,then don't invert it
        {
            return false;
        }
        else
        {
            //init a stack to save the inverted stack
            stack<char> invert;
            while (!one_stack.empty())
            {
                invert.push(one_stack.top());
                one_stack.pop();
            }
            //this moment the stack's inverted state is the stack invert ,so get it back
            one_stack = invert;
            return true;
        }
    }
    
    void displayStack1(stack<char> one_stack)
    {
        invertStack1(one_stack);
        while (!one_stack.empty())
        {
            cout << one_stack.top();
            one_stack.pop();
        }
        cout << '\t' << '\t';
    }
    
    void SLR()
    {
        printf("输入串\t\t状态栈\t\t符号栈\t\tACTION\t\tGOTO   ");
        int i,j,k=1;
        state.push(0); //初始化
        sign.push('#'); 
        int which;  //对应表项内容
        char c; //输入符号串首
        int a; //坐标
        int b;
    do{
        printf("\n");    
        c=m[k-1].temp[0]; //输入符号串首
        cout<<c<<' ';
        for(int j=k;j<=count;j++)
            printf("%s",m[j].temp);
        printf("\t\t");
        displayStack(state);
            
        displayStack1(sign);
        a=state.top(); //坐标
        b=isVt(c);
        /*if(isOp(c)!=-1)
            temp1=c;
        place.push(temp1);*/
        if(b!=-1)  //输入串首c是终结符
        {
            
            which=ACTION[a][b];
            if(which==-1)
            {
                printf(" acc,分析成功!\n");
                flag=1;
                break;
            }
            else if(which==0)
            {    printf("error项1\n ");break;    }
            else if(which>=100) //移进
            {
                which=s_r(which);
                printf("s%d\t\t",which);
                sign.push(c);
                state.push(which);
                k++;
            }
            else 
            {
                switch(which) //which整型,case不要加''
                {                                                                                                                                                                                                                                                        
                case 1:R1();break;
                case 2:R2();break;
                case 3:R3();break;
                case 4:R4();break;        
                case 5:R5();break;
                case 6:R6();break;
                case 7:R7();break;
                case 8:R8();break;
                case 9:R9();break;
                case 10:R10();break;
                default:printf("which=%derror项2\n ");break;
                }    
                //状态转移 Vn
                int e=isVn(sign.top());
                if(e!=-1)
                {
                int convert=GOTO[st][e];
                state.push(convert);
                printf("GOTO[%d,%c]=%d",st,sign.top(),convert);
                }
            }
        }
        else   
        {    printf("error_b ");break;    }
        
    }while(which!=-1);//while
    }
    
    void R1() {
        
        sign.pop(); sign.pop(); sign.pop();       //弹出符号栈
        state.pop(); state.pop(); state.pop();    //弹出状态栈
        sign.push('A');                         //符号'A'入栈
        st=state.top();
        printf("r1\t");
    }
    void R2() {
        
        sign.pop(); sign.pop(); sign.pop();       //弹出符号栈
        state.pop(); state.pop(); state.pop();    //弹出状态栈
        sign.push('E'); st=state.top();                        //符号'E'入栈
        printf("r2\t\t");
    }
    void R3() {
    
        sign.pop(); sign.pop(); sign.pop();
        state.pop(); state.pop(); state.pop();
        sign.push('E');st=state.top();
        printf("r3\t\t");
    }
    void R4() {
        sign.pop();
        state.pop();
        sign.push('E');st=state.top();
        printf("r4\t\t");
    }
    void R5() {
    
        sign.pop(); sign.pop(); sign.pop();
        state.pop(); state.pop(); state.pop();
        sign.push('T');st=state.top();
        printf("r5\t\t");
    }
    void R6() {
    
        sign.pop(); sign.pop(); sign.pop();
        state.pop(); state.pop(); state.pop();
        sign.push('T');st=state.top();
        printf("r6\t\t");
    }
    void R7() {
        sign.pop();
        state.pop();
        sign.push('T');st=state.top();
        printf("r7\t\t");
    }
    void R8() {
        sign.pop(); sign.pop(); sign.pop();
        state.pop(); state.pop(); state.pop();
        sign.push('F');st=state.top();
        printf("r8\t\t");
    }
    void R9() {
        sign.pop();
        state.pop();
        sign.push('F');st=state.top();
        printf("r9\t\t");
    }
    void R10() {
        sign.pop();
        state.pop();
        sign.push('V');st=state.top();
        printf("r10\t\t");
    }
    
    ///
    void scanner(FILE *p)
    {    
        char filein[40],fileout[40]; //文件名
        printf("请输入要打开的源文件名(包括路径)\n");
        scanf("%s",filein);
        //printf("请输入要输出的目标文件名(包括路径)\n");
        //scanf("%s",fileout);
        if((p=fopen(filein,"r"))==NULL) {printf("输入文件打开有错!\n");return;}
    //    if((q=fopen("fileout","rw"))==NULL) {printf("输出文件打开有错!\n");return;}
    
        char token[COUNT]; //输出数组
        int r=0,i=0;
        char ch;    
        ch=fgetc(p);
        while(!feof(p)) //没有读到文件末尾
    {
        if(isdigit(ch))
        {
            i=0;
            token[i]=ch;
            while(isdigit(ch=fgetc(p)))
            {
                i++;
                token[i]=ch;
            }
            token[i+1]='\0'; //整数结束。不要忘结束标志!
            fseek(p,-1,1); //重定向到当前位置的前一个!
            out(INT,token);
            //fprintf(q,"%d %s\n",INT,token);
        }
        else if(isalpha(ch))
        {
            i=0;
            int flag=0; //标志是否是保留字,默认不是
            token[i]=tolower(ch);
            while(isalpha(ch=fgetc(p)))
            {
                i++;
                token[i]=tolower(ch);
            }
            token[i+1]='\0'; 
            fseek(p,-1,1);
            for(r=0;r<8;r++)
            {
                if(!strcmp(token,keyword[r]))
                {
                    printf("<blz %s>\n",token);
                //    fprintf(q,"%d %s\n","保留字",token);
                    flag=1;
                    break;
                }
            }    
            if(!flag)
            {    out(ID,token);    
            //    fprintf(q,"%d %s\n",ID,token);
            }
        }
        else
        {
            i=0;
            switch(ch)
            {
            case '+':{    token[i]=ch;
                        token[i+1]='\0'; 
                        out(ADD,token);    
                        }break;
            case '-':{    token[i]=ch;
                        token[i+1]='\0'; 
                        out(SUB,token);}break;
            case '*':{    token[i]=ch;
                        token[i+1]='\0'; 
                        out(MUL,token);}break;
            case ';':{    token[i]=ch;
                        token[i+1]='\0'; 
                        out(FH,token);}break;
            case '|':{    token[i]=ch;
                        token[i+1]='\0'; 
                        out(SG,token);}break;
            case '(':{    token[i]=ch;
                        token[i+1]='\0'; 
                        out(ZKH,token);}break;
            case ')':{    token[i]=ch;
                        token[i+1]='\0'; 
                        out(YKH,token);}break;
            case '=':{    token[i]=ch;
                        token[i+1]='\0'; 
                        out(EQ,token);}break;
            case ' ':{    break;} //空格直接跳
            case '#':{    break;} //井号用作结尾            
            case '<':{token[i]=ch;
                    ch=fgetc(p);
                    if(ch=='='){
                        token[i+1]='=';
                        token[i+2]='\0'; 
                        out(LE,token);
                    }
                    else if(ch=='>'){
                        token[i+1]='>';
                        token[i+2]='\0';
                        out(NE,token);
                    }
                    else 
                    {    printf(" error \n");
                        fseek(p,-1,1);    //多读的要回退一个字符
                    }
                     }break;
                    
            case '>':{token[i]=ch;
                    ch=fgetc(p);
                    if(ch=='=')
                    {
                        token[i+1]='=';
                        token[i+2]='\0';
                        out(GE,token);
                    }
                    else 
                    {    printf(" error \n");
                        fseek(p,-1,1);    //多读的要回退一个字符
                    }
                    }break;
            case ':':{token[i]=ch;
                    ch=fgetc(p);
                    if(ch=='='){
                        token[i+1]='=';
                        token[i+2]='\0';
                        out(MHEQ,token);
                    }
                    else 
                    {    printf(" error \n");
                        fseek(p,-1,1);    //多读的要回退一个字符
                    }
                     }break;
        case '/':{token[i]=ch;
                    ch=fgetc(p);
                    if(ch=='*')
                    {    
                        token[i+1]='*';
                        token[i+2]='\0';
                        out(XGMUL,token);
                        while(1)    //注释部分的处理!
                        {
                            ch=fgetc(p);
                            if(ch=='*')
                            {
                                if((ch=fgetc(p))=='/')
                                    break;
                            }
                        }
                    }
                    else // 除号,修改第一次程序部分
                    {    /*printf(" error \n");
                        fseek(p,-1,1);    */
                        out(DIV,token);
                        fseek(p,-1,1);//多读的要回退一个字符
                    }
                    }break;
            default:{
                        printf(" error\n ");
                    }break;
                        
            }
        }
        ch=fgetc(p);
    }
        fclose(p);
    }
    int main(int argc, char* argv[])
    {
        printf("编译原理实验_5:SLR分析程序(待分析内容在文件file.txt中,以#结尾)\n");
        FILE *fin,*q;
        scanner(fin);
        strcpy(m[count].temp,"#");//! 
        count=count+1;
        //scanner(p,q);
        SLR();
        MAIN();
        return 0;
    }

     

     

    ---内容结束---

    转载于:https://www.cnblogs.com/yh-blog/p/9181603.html

    展开全文
  • LL1文法、LR(0)文法SLR文法、LR(1)文法、LALR文法

    千次阅读 多人点赞 2021-01-11 00:17:33
    文章目录自顶向下分析自底向上分析文法转换LL(1)文法S 文法ε产生式的使用非终结符的后继符号集产生式的可选集Q文法串首终结符集LL(1)文法SELECT集、FOLLOW集、FIRST集计算 自顶向下分析 自顶向下分析指的是最左...

    自顶向下分析

    自顶向下分析指的是最左推导,最右归约是最左推导的逆过程,在最左推导中,总是选择每个句型的最左非终结符进行替换


    自底向上分析

    自底向上分析指的是最右推导、最左归约是最右推导的逆过程,在最右推到中,总是选择每个句型的最右非终结符进行替换

    文法转换

    • 回溯问题
    • 直接左递归和间接左递归问题

    回溯是指:同一非终结符的多个候选式存在共同前缀。例如:S —> aAd | aBe 该文法存在回溯现象

    A —> Aa | β (a ≠ ε, β不以A开头)
    => Aaaaaaa
    =>  βaaaaaa
    消除直接左递归:
    A —>  βA'
    A' —> aA' | ε
    
    S —> Aa | b
    A —> Ac | Sd | ε
    消除间接左递归:
    A —> Ac | Aad | bd | ε
    消除间接左递归:
    A —> bdA' | A'
    A' —> cA' | adA' | ε
    

    LL(1)文法

    LL1文法可以解决回溯,被称为预测分析
    

    S 文法

    	S文法不含有ε产生式
    
    • 每个产生式的右部都以终结符开始
    • 同一非终结符的各个候选式的首终结符都不同

    ε产生式的使用

    ε产生式的使用取决于非终结符后面的终结符(这里的终结符可能是一个也可能是多个)
    

    如果当前非终结符A与要输入的符号a 不匹配时,若存在A—>ε,可以通过检查a是否可以出现在A的后面,来决定是否使用A—>ε (若文法中没有A—>ε,则应报错)

    非终结符的后继符号集

    紧接非终结符后面的终结符的集合称为非终结符的后继符号集,记为FOLLOW(该非终结符)
    

    产生式的可选集

    产生式的可选集也称为select集,指的是推导输入串时可用的产生式的集合
    
    SELECT(A—>) = { a }  a为首终结符
    SELECT(A—>ε) =  FOLLOW(A) 
    

    Q文法

    q文法不含右部以非终结符打头的产生式
    
    • 每个产生式的右部是以ε开始或者以终结符开始
    • 具有相同左部的产生式有不相交的可选集

    串首终结符集

    串首终结符是指产生式右部第一个终结符,串首终结符也可以是ε。串首终结符的集合称为串首终结符集也称First集
    
    如果ε ∉ First(α), 那么SELECT(A—>α) = First(α)
    如果ε ∈ FIRST(α),那么SELECT(A—>α) = (FIRST(α) - {ε})FOLLOW(A)
    

    LL(1)文法

    第一个L是从左向右扫描输入,第二个L是产生最左推导,1是指需要向前看一个输入符号来决定语法分析动作
    
    文法G是LL(1)的,当且仅当G的任意两个具有相同左部的产生式A —>α | β 满足:
    1.不存在终结符a使得α 和 β 都能够推导出以a开头的串 (相当于前缀要不一样)
    2.α 和 β至多有一个能推导出ε (如果都包含空串,SELECT集就像相交了)
    3.如果 β => ε,则FIRST(α)FOLLOW(A) = Φ
         α => ε,则FIRST(β)FOLLOW(A) = Φ
    保证同一非终结符的各个产生式的可选集互不相交
    
    

    SELECT集、FOLLOW集、FIRST集计算

    FIRST集计算

    First(X): 可以从X推导出的所有 串首终结符的集合 ,包括ε
    

    E —> TE’
    T ‘—> *FT’ | ϵ \epsilon ϵ
    E’ —> +TE’ | ϵ \epsilon ϵ
    F —> ( E ) | id
    T —> FT’
    求FIRST集:(找最左终结符)
    FIRST(E) = FIRST(T) = FIRST(F) = { ( id }
    FIRST(E’) = { + ϵ \epsilon ϵ }
    FIRST(T’) = { * ϵ \epsilon ϵ }

    如果产生式的右部遇到的不是终结符,是非终结符的话就从该非终结符产生式的右部找起
    

    FOLLOW集计算

    FOLLOW(A): 跟在非终结符A后面的总结符的集合,若A是文法的开始符,那么就需要把$或者#(代表结束符)加入到FOLLOW(A)中

    • 第一种就是该非终结符后面是终结符,那么该终结符属于该非终结符的FOLLOW集
    • 第二种是该非终结符在产生式最右边,该非终结符的FOLLOW集需要∪产生式左部非终结符的FOLLOW集
    • 第三种该非终结符的后面不是终结符而是一个非终结符则看此终结符的产生式,如果此终结符的产生式可以为空,那么该非终结符的FOLLOW集就是后面的非终结符的FIRST(此终结符) -ϵ ∪ FOLLOW(此终结符)

    E —> TE’
    T ‘—> *FT’ | ϵ \epsilon ϵ
    E’ —> +TE’ | ϵ \epsilon ϵ
    F —> ( E ) | id
    T —> FT’

    FOLLOW(E) = FOLLOW(E’) = {) #}
    FOLLOW(E‘) = FOLLOW(E) = { ) # } E’出现在最右部
    FOLLOW(T) = {FIRST(E’) - ϵ \epsilon ϵ} ∪ \cup FOLLOW(E’)} = { + ) # }
    FOLLOW(T’) = FOLLOW(T) = { +) # }
    FOLLOW(F) = { FIRST(T’) - ϵ \epsilon ϵ} ∪ \cup FOLLOW(T’) } = {* +) # }

    SELECT集计算

    SELECT集是针对产生式的,需要将具有相同产生式左部的产生式展开,根据公式计算SELECT集
    

    (1)E —> TE’
    (2)T ‘—> *FT’
    (3)T’ —> ϵ \epsilon ϵ
    (4)E’ —> +TE’
    (5)E’—> ϵ \epsilon ϵ
    (6)F —> ( E )
    (7)F—> id
    (8)T —> FT’

    SELECT(1) = {看的是T的终结符} = FIRST(T) = { ( id } 没有ε
    SELECT(2) = {公式SELECT(A—> aβ) = { a } a为首终结符} = {*}
    SELECT(3) = {公式SELECT(A—>ε) = FOLLOW(A)} = FOLLOW(T’) = {+ ) #}
    SELECT(4) = {公式SELECT(A—> aβ) = { a } a为首终结符} = {+}
    SELECT(5) = {公式SELECT(A—>ε) = FOLLOW(A)} = FOLLOW(E’)= { ) #}
    SELECT(6) = {公式SELECT(A—> aβ) = { a } a为首终结符} = {(}
    SELECT(7) = {公式SELECT(A—> aβ) = { a } a为首终结符} = {id}
    SELECT(8) = {看的是F的终结符} = FIRST(F) = {( id } 没有ε

    如果FIRST集里面有ε,就用公式ε ∈ FIRST(α),那么SELECT(A—>α) = (FIRST(α) - {ε}) ∪ FOLLOW(A)
    

    预测分析表

    根据SELECT集填表格,横向是终结符,纵向是非终结符
    
    -id+*()#
    EE —> TE’E —> TE’
    E’E’ —> +TE’F —> ( E )F —> ( E )
    TT —> FT’T —> FT’
    T’T’ —> ϵ \epsilon ϵT ‘—> *FT’T’ —> ϵ \epsilon ϵT’ —> ϵ \epsilon ϵT’ —> ϵ \epsilon ϵ
    FF—> idF —> ( E )

    例子

    S —> (L) | a
    L —> SL’
    L’ —> ,SL’ | ϵ

    FIRST(S) = {(,a}
    FIRST(L) = {(,a}
    FIRST(L’) = {, ϵ}

    FOLLOW(S) = {$,)}
    FOLLOW(L) = { ) }
    FOLLOW(L’) ={ ) }

    …略


    递归预测分析法

    递归预测分析法预测分析法是指:在递归下降分析中,编写每一个非终结符对应的过程,根据预测分析表进行产生式的选择


    非递归预测分析法

    非递归的预测分析不需要为每一个非终结符编写递归下降过程,而是根据预测分析表构造一个自动机,也叫表驱动的预测分析

    在这里插入图片描述
    在这里插入图片描述


    预测分析中的错误检测

    错误

    • 栈顶的终结符和当前输入符号不匹配
    • 栈顶非终结符与当前输入符号在预测分析表对应项中的信息为空

    处理

    恐慌模式:

    • 忽略输入中的一些符号,直到输入中出现由设计者选定的同步词法单元(synchromizing token)集合中的某个词法单元,同步集合的选取使得语法分析器能从实际遇到的错误中快速恢复,可以将FOLLOW(A)中的所有终结符放入非终结符A的同步记号集合

    • 如果终结符在栈顶而不能匹配,一个简单的办法就是弹出此终结符

    在这里插入图片描述


    自底向上的语法分析

    • 分析树的底部(叶节点)向顶部(根节点)方向构造分析树
    • 将输入串w规约为文法开始符号S的过程
    • 自顶向下语法分析采用最左推导方式, 自底向上语法分析采用最左规约方式(反向构造最右推导)
    • 自底向上语法分析的通用框架是:移入-规约分析

    移入-规约过程

    在这里插入图片描述

    堆栈内符号串 + 剩余输入 = 规范句型,规范句型相当于最右推导
    

    移入-规约分析中存在的问题

    每次规约的符号串是直接短语,造成错误的原因是错误的识别了句柄,也就是选错了产生式
    
    • 直接短语:直接短语一定是产生式的右部,产生式的右部不一定是直接短语,并且是高度为二子树的边缘
    • 句柄:句型的最左直接短语

    LR分析法概述

    可以用LR文法分析的文法叫做LR文法,LR文法是最大的、可以构造出相应移入-规约语法分析器的文法类
    
    • L:对输入进行从左到右的扫描
    • R:反向构造出一个最右推导序列
    • LR(k) 需要向前查看k个输入符号的LR分析,一般k = 0 或者 k = 1

    LR分析法的基本原理

    • 自底向上分析的关键问题是什么?
      如何正确的识别句柄
    • 句柄是逐步形成的,用“状态” 表示句柄识别的进展程度
      S—>bBB
      S—> •bBB (移进状态)
      S—>b•BB (待约状态)
      S—>bB•B (待约状态)
      S—>bBB• (规约状态)

    LR分析器(自动机)的总体结构

    在这里插入图片描述

    LR分析表的结构

    在这里插入图片描述


    LR(0)分析法

    右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目,一个产生式有k个符号,就会有k+1个项目
    

    增广文法

    就是引入一个符号,使文法开始符号只出现在一个产生式的左边,从而使得分析器只有一个接受状态
    

    文法中的项目

    • 初始项目:圆点在最左边
    • 规约项目:圆点在最右边
    • 后继项目:两个项目之间间隔一个圆点

    等价项目

    当圆点后面是一个非终结符的时候,就会存在等价项目
    

    在这里插入图片描述

    项目集闭包

    把所有的等价项目组成一个项目集(I),称为项目集闭包,每个项目集闭包对应着自动机的一个状态
    

    LR(0)自动机

    在这里插入图片描述

    LR(0)自动机构造LR(0)分析表

    根据上图的自动机得来的
    

    在这里插入图片描述

    LR(0)分析过程中的冲突

    移进-规约冲突

    无法确定是移进还是规约
    

    在这里插入图片描述

    规约-规约冲突

    在这里插入图片描述

    没有这两种冲突的文法是LR(0)文法,不是所有的上下文无关文法都可以用LR(0)文法分析
    

    SLR分析

    为了解决LR(0)分析过程中的冲突的问题(也就是识别句柄的问题),出现了SLR分析,也叫做SLR(1)分析,S是Simple的意思,简单的LR(1)
    

    SLR分析基本思想

    需要使用到FOLLOW集,在不知道是否移进或者规约时,向后查看一个输入符号,根据FOLLOW集的定义是:该终结符后面可以的跟的终结符的集合。

    • 看规约项目产生式左部的非终结符的FOLLOW集,如果下一个输入符号在FOLLOW集中就规约
    • 看移进项目的下一个终结符是和下一个输入符号一样,如果相同就移进
    • 详情看图

    在这里插入图片描述
    在这里插入图片描述

    例子

    在这里插入图片描述

    SLR分析中的冲突

    如果产生式符合SLR分析基本思想的两种规则,就无法判定到底是移进还是规约
    

    在这里插入图片描述


    LR(1)分析法

    SLR使用FOLLOW集可以排除一些问题,但是不能解决所有问题
    

    LR(1)分析法的提出

    产生式A—>a规约时,在不同的位置,要求有不同的后继符号,在特定位置时,A的后继符号集合是FOLLOW(A)的子集
    

    在这里插入图片描述

    LR(1)项目

    • 将一个形式为[A—>α• β ,a]的项称为LR(1)项,其中A—>α β 是一个产生式,a是一个终结符(这里将$视为一个特殊的终结符)它表示在当前状态下,A后面必须紧跟终结符,称为该项的展望符
    • LR(1)中的1指的是项的第二个分量的长度(就是向前查看一个符号)
    • 在形如[A—>α• β,a]且β≠ ε的项中,展望符a没有任何作用
    • 形如[A—>α•,a]的项在只有在下一个输入符号等于a时才可以安装A—>a进行规约,这样的a的集合总是FOLLOW(A)的子集,而且通常是一个真子集

    LR(1)等价项目

    在这里插入图片描述

    LR(1)自动机

    相比较LR(0)和SLR,多求了展望符,状态比较多
    

    在这里插入图片描述

    LR(1)分析表

    在这里插入图片描述


    展开全文
  • 输入文法的第一个产生式为文法开始符的产生式。 设置变量SIZE,代表非终结符的最大的数量。对终结符和非终结符进行编号,规定数值0为空串(&)。用1~SIZE的正整数对终结符和非终结符分别进行编号。为了在候选式中...

     

     

     

     

     

     

     

     

     

    1. 规定终结符用小写字母开头和后面接若干“`”表示例如a,b,i,i`,i``表示不同的终结符。非终结符用大写字母和后面接若干“`”表示非终结符例如A,B,T`,T``表示不同的非终结符。用“&”代表空串。连续输入的“-”“>”代表推导,分割产生式左右部。输入的文法的第一个产生式为文法开始符的产生式。
    2. 设置变量SIZE,代表非终结符的最大的数量。对终结符和非终结符进行编号,规定数值0为空串(&)。用1~SIZE的正整数对终结符和非终结符分别进行编号。为了在候选式中不发生冲突,候选式的终结符使用终结符的相反数。例如:编号A:1, B:2, a:1, b:2 。则二维数组{{1,2},{-1,2},{0} } 代表候选式 AB | aB | & 。FIRST和FOLLOW集合存储的是非终结符的编号和终结符的编号的相反数。
    3. 将候选式分开存储进pro结构体中,属性Vn表示产生式左部,candy数组表示产生式右部。都是存储符号的编号。每个pro的下标代表产生式的编号。项目集结构体中属性pro集合代表一对序偶一个代表产生式的编号,一个表示‘.’号的位置。集合v代表项目集的边。go集合也是一对序偶,第一个数表示边代表的字符编号,第二个数代表指向的项目集。

     

     

    #include <bits/stdc++.h>
    
    
    using namespace std;
    
    #include "definition.h"
    #include "Check.h"
    #include "Init.h"
    #include "getFirst.h"
    #include "getFollow.h"
    #include "Display.h"
    #include "getI.h"
    #include "getTable.h"
    #include "analyse.h"
    
    int main()
    {
    
        ifstream file;
        file.open("test/input3.txt");
        string str;
        while(getline(file, str)){  //输入一行,即一个非终结符的候选式
            cout<<str<<endl;
            init(str);  //初始化,将终结符和非终结符等进行编号等
        }
    
        getFIRST(); //获取FIRST集
        getFollow();    //获取FOLLOW集
    
        dispalyFirst(); //输出FIRST集
        dispalyFollow();    //输出FOLLOW集
    
        //displayPro2();
        displayPro();   //输出产生式
    
        getI(); //获取项目集(I)
    
        getActionGotoTable();   //获取Action和GOTO表
    
        ifstream in;
        in.open("test/inputa3.txt");    //输入串
        string inStr;
        while(getline(in,inStr)){
            getAns(inStr);
        }
    
        return 0;
    }
    

     

    #ifndef DEFINITION_H_INCLUDED
    #define DEFINITION_H_INCLUDED
    
    #define SIZE 100
    
    int idVt = 0;   //终结符编号
    int idVn = 1;   //非终结符编号,0号为扩展文法开始符
    int idPro = 1;   //产生式编号,0号为扩展文法开始符
    
    int JING;   //# 号
    int EMPTY = 5*SIZE;  //空串
    int startVt = -1;   //判断是否处理了开始符,只处理一次
    int ERROR = 4*SIZE; //出错标志
    int ACC = 5*SIZE;   //成功标志
    
    map<string,int>mpVn,mpVt;   //编号(字符,编号)
    map<int,string>rmpVn,rmpVt; //双向映射(编号,字符)
    
    //存储分开编号的产生式,下标为编号
    struct Pro {
        int Vn; //产生式左部 1 <=> A
        vector<int>candy;   //产生式右部{1,2,-1} 代表 A -> ABa
        Pro(){
            Vn =0 ;
            candy.clear();
        }
    }pro[SIZE];
    
    //项目集I
    struct Ix{
        set<pair<int,int> >pro;  //记录项目集拥有的产生式编号以及对应的‘.’ 号的位置  {idPro,dot} 例如: {  {0,0} , {1,1}   }  <=> { S`->.XX, E -> X.XX  }
        set<int>v;  //记录项目集的边的符号的编号如:a编号1。GOTO(a,I)、GOTO(b,I) 的a, b
        set<pair<int,int> >go;  //(idVt/idVn, numI)    对应的边以及其GOTO到的项目集
        void Clear(){
            pro.clear();
            v.clear();
            go.clear();
        }
    }I[SIZE];
    
    //每个非终结符对应一个结构体
    struct NoTml
    {
        vector<vector<int> > pro;   //候选式:例如 {{1,2},{-1,2},{0} } => AB | aB | &
        set<int> FIRST, FOLLOW; //FIRST集,FOLLOW集
        int proNum; //处理FIRST集时使用,判断以及完成的候选式
        bool FirstFinish;   //处理FIRST集时使用,判断是否全部候选式都完成
        NoTml(){
            FirstFinish = false;
            int proNum = 0 ;
            FIRST.clear();
            FOLLOW.clear();
            pro.clear();
        }
    }notml[SIZE];   //每个下标对应一个非终结符
    
    
    #endif // DEFINITION_H_INCLUDED
    
    #ifndef INIT_H_INCLUDED
    #define INIT_H_INCLUDED
    
    void init(string str){
        int len = str.length();
        int pos = 0;
        int idLeft = 0;
        string word="";
        vector<int>vec;
    
        //获取产生式左部
        while(pos<len){
            if(str[pos]==' '){  //过滤空格
                pos++;
            }
            else if(str[pos]>='A'&&str[pos]<='Z'){ //判断是否为大写字母开始,即是否为非终结符
                word="";
                word+=str[pos];
                pos++;
                while(pos<len&&str[pos]=='`') word+=str[pos],pos++;
                if(mpVn.count(word)==0){
                    mpVn[word]=idVn++;  //双向映射(编号,字符),(字符,编号)
                    rmpVn[idVn-1]=word;
                }
            }
            else if(str[pos]=='-'&&str[pos+1]=='>') {
                idLeft = mpVn[word];
                pos+=2;
                break;
            }
            else {
                errorG();   //文法输入错误
                return ;
            }
        }
    
        //扩展文法开始符
        if(startVt == -1){
            rmpVt[EMPTY]="&"; //& 代表空串
            mpVt["&"] = EMPTY;
    
            JING = idVt++;    //对 # 号进行编号
            rmpVt[JING]="#";
            mpVt["#"] = JING;
    
            ERROR = SIZE+1;
    
            startVt = idLeft;
            mpVn["S`"] = 0;
            rmpVn[0] = "S`";
            pro[0].candy.push_back(idLeft);
            pro[0].Vn = 0;
    
            notml[0].pro.push_back({idLeft});
    
    
        }
    
        //获取产生式右部
        while(pos<len){
            if(str[pos]==' '){
                pos++;
            }
            else if(str[pos]=='&'){ //空串
                vec.push_back(EMPTY);
                pos++;
            }
            else if(str[pos]=='|'){ //得到了一个候选式,
                if(!vec.empty()) {
                    pro[idPro].candy.assign(vec.begin(),vec.end());
                    pro[idPro++].Vn=idLeft;
    
                    notml[idLeft].pro.push_back(vec);
    
                }
                vec.clear();
                pos++;
            }
            else if(str[pos]>='A'&&str[pos]<='Z') {    //对非终结符编号
                word="";
                word+=str[pos];
                pos++;
                while(pos<len&&str[pos]=='`') word+=str[pos],pos++;
                if(mpVn.count(word)==0){
                    mpVn[word]=idVn++;
                    rmpVn[idVn-1]=word;
                }
                vec.push_back(mpVn[word]);
            }
            else if(!(str[pos]>='A'&&str[pos]<='Z')){    //对终结符编号
                word="";
                word+=str[pos];
                pos++;
                while(pos<len&&str[pos]=='`') word+=str[pos],pos++;
                if(mpVt.count(word)==0){
                    mpVt[word]=idVt++;
                    rmpVt[idVt-1]=word;
                }
                vec.push_back(-mpVt[word]);  //终结符在候选式内使用负数,防止和非终结符冲突
            }
            else {
                errorG();
            }
        }
        if(!vec.empty()) {
            pro[idPro].candy.assign(vec.begin(),vec.end());  //处理最后的候选式
            pro[idPro++].Vn = idLeft;
    
            notml[idLeft].pro.push_back(vec);  //处理最后的候选式
        }
        vec.clear();
    
        if(idVt>=SIZE||idVn>=SIZE) { //终结符或,非终结符超出范围,错误
            errorG();
            return ;
        }
    
    }
    
    #endif // INIT_H_INCLUDED
    

     

    #ifndef GETFIRST_H_INCLUDED
    #define GETFIRST_H_INCLUDED
    
    //输出FIRST集合
    void dispalyFirst(){
        cout<<"---------------FIRST start---------------------"<<endl;
        for(int i=0;i<idVn;i++){
            cout<<rmpVn[i]<<":  ";
            for(set<int>::iterator it=notml[i].FIRST.begin();it!=notml[i].FIRST.end();it++){
                cout<<rmpVt[abs(*it)]<<" ";
            }
            cout<<endl;
        }
    
        cout<<"---------------FIRST end---------------------"<<endl;
    }
    
    //获取FIRST集,和实验二LL分析器一样
    void getFIRST(){
    
        //规则(1) 即将候选式的首字符是非终结符的加入FIRST集合
        for(int i=0;i<idVn;i++){
            for(int j=0;j< notml[i].pro.size();j++){
                if(notml[i].pro[j][0]<=0){
                    notml[i].FIRST.insert(notml[i].pro[j][0]);
                    notml[i].proNum++;
                }
                //判断是否全部候选式都处理完
                if(notml[i].proNum == notml[i].pro.size()) notml[i].FirstFinish = true;
            }
        }
    
        //规则(2)的第一步,将X -> Y...的FIRST(Y)/{&}加入到FIRST(X)
        for(int i=0;i<idVn;i++){
            for(int j=0;j< notml[i].pro.size();j++){
                if(notml[i].pro[j][0]>0){   //判断首字符是否为非终结符
                    set<int>tmp;
                    int idk=notml[i].pro[j][0]; //获取首字符的编号
                    tmp.insert(notml[idk].FIRST.begin(),notml[idk].FIRST.end());
                    if(tmp.count(EMPTY)) tmp.erase(EMPTY);
                    notml[i].FIRST.insert(tmp.begin(),tmp.end());
                }
            }
        }
    
        //规则(2)第二步,每次有变化都要进行更新
        bool hasChange = true;
        int Empty=0;
        while(hasChange){
            hasChange = false;
            for(int i=0;i<idVn;i++){    //遍历非终结符,对还有候选式没有处理的进行处理
                if(!notml[i].FirstFinish){
                    for(int j=0;j<notml[i].pro.size();j++){ //遍历每个候选式
                        Empty=0;    //记录空串,判断是否整个字符串都有空串
                        bool ok = true;
                        for(int k=0;k<notml[i].pro[j].size();k++){  //遍历每个候选的每个字符
                            int id = notml[i].pro[j][k];
                            if(id>0&&!notml[id].FirstFinish){   //必须是已经处理完成的非终结符才能更新现在的非终结符
                                ok=false;
                                break;
                            }
                        }
                        if(ok){ //对非终结符进行更新
                            for(int k=0;k<notml[i].pro[j].size();k++){
                                int id = notml[i].pro[j][k];
                                if(id>0&&notml[id].FirstFinish){
                                    set<int> tmp;
                                    tmp.insert(notml[id].FIRST.begin(),notml[id].FIRST.end());  //将FIRST(Y)加入到FIRST(X)
                                    if(notml[id].FIRST.count(EMPTY)){   //判断空串
                                        Empty++;
                                        tmp.erase(EMPTY);
                                        notml[i].FIRST.insert(tmp.begin(),tmp.end());
                                        hasChange = true;
                                    }
                                    else {
                                        notml[i].FIRST.insert(tmp.begin(),tmp.end());
                                        hasChange = true;
                                        break;  //没有空串则停止
                                    }
                                }
                            }
                            if(Empty == notml[i].pro[j].size()){    //如果全部字符都有空串,则加入空串到FIRST(X)
                                notml[i].FIRST.insert(EMPTY);
                            }
                            notml[i].proNum++;  //记录已经处理候选式
                            if(notml[i].proNum == notml[i].pro.size()) notml[i].FirstFinish = true; //全部候选式处理完则该非终结符处理完
                        }
                    }
                }
            }
        }
    }
    
    
    #endif // GETFIRST_H_INCLUDED
    

     

    #ifndef GETFOLLOW_H_INCLUDED
    #define GETFOLLOW_H_INCLUDED
    
    //输出FOLLOW集合
    void dispalyFollow(){
        cout<<"---------------FOLLOW start---------------------"<<endl;
        for(int i=0;i<idVn;i++){
            cout<<rmpVn[i]<<":  ";
            for(set<int>::iterator it=notml[i].FOLLOW.begin();it!=notml[i].FOLLOW.end();it++){
                cout<<rmpVt[abs(*it)]<<" ";
            }
            cout<<endl;
        }
    
        cout<<"---------------FOLLOW end---------------------"<<endl;
    }
    
    //获取FOLLOW集,和实验二LL分析器一样
    void getFollow(){
        //规则(1)将 # 加入到文法开始符的FOLLOW集合
        notml[0].FOLLOW.insert(JING);
    
        //规则(2)A -> aBP 将FIRST(P)/{&} 加入到FOLLOW(B)
        for(int id=0;id<idVn;id++){ //遍历每个非终结符,获取位置进行处理
            for(int i=0;i<idVn;i++){    //三个for遍历每个非终结符的每个候选式的每个字符
                for(int j=0;j<notml[i].pro.size();j++){
                    for(int k=0;k<notml[i].pro[j].size();k++){
                        if((notml[i].pro[j][k]==id)&&(k+1<notml[i].pro[j].size())&&(notml[i].pro[j][k+1]<0)){
                            notml[id].FOLLOW.insert(notml[i].pro[j][k+1]);  //P不是终结符,终结符的FIRST集合是它本身,直接加入
                        }
                        else if((notml[i].pro[j][k]==id)&&(k+1<notml[i].pro[j].size())&&(notml[i].pro[j][k+1]>0)){
                            set<int>tmp;
                            int idk = notml[i].pro[j][k+1];
                            tmp.insert(notml[idk].FIRST.begin(),notml[idk].FIRST.end());
                            if(tmp.count(EMPTY))
                                tmp.erase(EMPTY);
                            notml[id].FOLLOW.insert(tmp.begin(),tmp.end()); //FIRST(P)/{&}加入FOLLOW(A)
                        }
                    }
                }
            }
        }
    
        //规则(3)A -> aB  或  A-> aBP
        queue<int>que;  //记录需要进行处理的非终结符
        for(int i=1;i<idVn;i++){
            que.push(i);
        }
        int id;
        while(!que.empty()){
            id=que.front(); //处理B
            que.pop();
            for(int i=0;i<idVn;i++){    //遍历A
                for(int j=0;j<notml[i].pro.size();j++){
                    for(int k=0;k<notml[i].pro[j].size();k++){
                        if((notml[i].pro[j][k]==id)&&(k+1==notml[i].pro[j].size())){    //候选式为 A -> aB
                            if(notml[i].FOLLOW.size()==0) que.push(id);
                            else notml[id].FOLLOW.insert(notml[i].FOLLOW.begin(),notml[i].FOLLOW.end());
                        }
                        else if((notml[i].pro[j][k]==id)&&(k+1<notml[i].pro[j].size())&&(notml[i].pro[j][k+1]>0)&&(notml[notml[i].pro[j][k+1]].FIRST.count(0)>0)){
                            //候选式为  A -> aBP
                            if(notml[i].FOLLOW.size()==0) que.push(id);
                            else notml[id].FOLLOW.insert(notml[i].FOLLOW.begin(),notml[i].FOLLOW.end());
                        }
                    }
                }
            }
        }
    }
    
    
    #endif // GETFOLLOW_H_INCLUDED
    

     

    #ifndef GETI_H_INCLUDED
    #define GETI_H_INCLUDED
    
    //处理项目集
    
    stack<int>st;   //记录需要增长的项目集
    bool vis[SIZE]; //标志每次扩展一个项目集的产生式,判断是否重复
    
    int numI = 0;   //项目集的数量
    Ix tmpI;    //项目集的临时变量
    
    //显示每个项目集
    void displayByIdI(int id){
        cout<<"-----------------start---------------------"<<endl;
        bool flag = false;
        cout<<"I["<<id<<"]:"<<endl;
        //cout<<id<<":"<<I[id].pro.size()<<endl;
        for(pair<int,int> x : I[id].pro){
            int idV = x.first;
            int dot = x.second;
            int idV2 = pro[idV].Vn;
            flag = false;
            cout<<rmpVn[idV2]<<"->";
            for(int j=0;j<pro[idV].candy.size();j++){
                if(j==dot){
                    flag = true;
                    cout<<".";
                }
                int value = pro[idV].candy[j];
                if(value>0){
                    cout<<rmpVn[value];
                }else {
                    cout<<rmpVt[-value];
                }
            }
            if(!flag) cout<<".";
            cout<<endl;
        }
    
        for(pair<int,int> x:I[id].go){
            cout<<"GOTO(";
            if(x.first>0){
                cout<<rmpVn[x.first];
            }else {
                cout<<rmpVt[-x.first];
            }
            cout<<", I["<<x.second<<"] )\n";
        }
        cout<<"-----------------end---------------------"<<endl;
    }
    
    //void displayI(){
    //    cout<<"--------------------I start-----------------------"<<endl;
    //    for(int i=0;i<=numI;i++){
    //        cout<<"------------"<<i<<"--------------"<<endl;
    //        cout<<"pro:"<<endl;
    //        for(pair<int,int> p:I[i].pro){
    //            cout<<p.first<<":"<<p.second<<endl;
    //        }
    //        cout<<"go"<<endl;
    //        for(pair<int,int> p:I[i].go){
    //            cout<<p.first<<":"<<p.second<<endl;
    //        }
    //        cout<<"------------"<<i<<"--------------"<<endl;
    //    }
    //    cout<<"--------------------I end-----------------------"<<endl;
    //}
    
    //DFS求项目集的闭包
    void Closure(int idV){
        for(int i=0;i<idPro;i++){
            if(vis[i]) continue;    //已经有的产生式跳过
            if(pro[i].Vn == idV){   //判断是否是相同的产生式左部
                vis[i] = true;         //标志该产生式
                tmpI.pro.insert({i,0});     //存储产生式
                tmpI.v.insert(pro[i].candy[0]);     //存储产生式右部第一个字符,作为一条边
                if(pro[i].candy[0]>0){
                    Closure(pro[i].candy[0]);   //根据第一个字符继续搜索
                }
            }
        }
    
    }
    
    //求项目集
    void GOTO(int idV,int dot){
        memset(vis, false, sizeof(vis));    //每次处理一个项目集要将产生式标志清零
        tmpI.pro.insert({idV, dot+1});      //存储产生式以及它的点‘.’位置
        if(dot+1<pro[idV].candy.size()){
            int idV2 = pro[idV].candy[dot+1];       //获取一条边
            tmpI.v.insert(idV2);
            Closure(idV2);      //求闭包
        }
    }
    
    //判断求得的项目集是否出现过,没则创建新的
    int getNext(){
        for(int i=0;i<=numI;i++){
            if(I[i].pro==tmpI.pro){
                return i;
            }
        }
        ++numI;
        I[numI].pro=tmpI.pro;
        I[numI].v=tmpI.v;
        I[numI].go=tmpI.go;
        st.push(numI);
        return numI;
    }
    
    //求项目集
    void getI(){
    
        memset(vis, false, sizeof(vis));
        tmpI.Clear();
        tmpI.pro.insert({0,0});
        Closure(1);                 //求初始项目集
        I[0].pro=tmpI.pro;
        I[0].v=tmpI.v;
        I[0].go=tmpI.go;
    
        //求初始项目集的边
        for(pair<int,int> x:I[0].pro){
            int idV = x.first;
            int dot = x.second;
            int Vn = pro[idV].candy[dot];
            I[0].v.insert(Vn);
        }
    
        //使用栈存储需要增长的项目集,从0号项目集开始
        st.push(0);
        while(!st.empty()){
            int idI = st.top();     //获取项目集编号
            st.pop();
            for(int x:I[idI].v){    //遍历项目集的出度边
                tmpI.Clear();       //初始化临时遍历,用来指定下一个扩展的节点
                for(pair<int,int> p:I[idI].pro){    //遍历项目集的产生式
                    int idV = p.first;
                    int dot = p.second;
                    int v = pro[idV].candy[dot];
                    if(x == v){                 //产生式的点‘.’后面的字符是出度的边的字符则边指向另一个项目集
                        GOTO(idV, dot);
                    }
                }
                I[idI].go.insert({x,getNext()});    //增加一条边
            }
        }
    
        //输出项目集
        for(int i=0;i<=numI;i++){
            displayByIdI(i);
            cout<<endl;
        }
    
        //displayI();
    
    
    
    
    }
    
    #endif // GETI_H_INCLUDED
    

     

    #ifndef GETACTION_H_INCLUDED
    #define GETACTION_H_INCLUDED
    
    //求ACTION和GOTO表
    
    int Action[SIZE][SIZE];     //第一维表示项目集编号,第二维表示终结符或非终结符
    int Goto[SIZE][SIZE];
    
    //显示表内容
    void displayTable(){
    
        cout<<"------------------------------LR Table-----------------------------"<<endl;
        cout<<"\t";
        for(int i=0;i<idVt;i++){
            cout<<rmpVt[i]<<"\t";
        }
        for(int i=0;i<idVn;i++){
            cout<<rmpVn[i]<<"\t";
        }
        cout<<endl;
    
        for(int i=0;i<=numI;i++){
            cout<<i<<"\t";
            for(int j=0;j<idVt;j++){
                if(Action[i][j] == ERROR){
                    cout<<"error\t";
                }else {
                    //cout<<Action[i][j]<<"\t";
                    if(Action[i][j]==ACC){
                        cout<<"acc\t";
                    }else if(Action[i][j]>=2*SIZE){
                        cout<<"r"<<Action[i][j]-2*SIZE<<"\t";
                    }else {
                        cout<<"S"<<Action[i][j]<<"\t";
                    }
                }
            }
            for(int j=0;j<idVn;j++){
                if(Goto[i][j] == ERROR){
                    cout<<"error\t";
                }else {
                    cout<<Goto[i][j]<<"\t";
                }
            }
            cout<<endl;
        }
    
        cout<<"------------------------------LR Table-----------------------------"<<endl<<endl;
    }
    
    //求ACTION和GOTO表
    void getActionGotoTable(){
    
        //初始化
        for(int i=0;i<SIZE;i++){
            for(int j=0;j<SIZE;j++){
                Action[i][j]= ERROR;
                Goto[i][j] = ERROR;
            }
        }
    
        for(int i=0;i<=numI;i++){       //遍历全部项目集
            int idP, dot;
            for(pair<int,int>p:I[i].pro){   //遍历其全部产生式
                idP = p.first;
                dot = p.second;
    
                if(pro[idP].candy.size()==dot&&idP==0){   //规则(3) 处理文法开始符,如S` -> S
                    Action[i][JING]=ACC;
                }
                else if(pro[idP].candy.size()==dot){    //规则(2) 处理点‘.’在产生式最右边  如A -> a .
                    for(int j=0;j<idVt;j++){//非终结符 a
                        int idV = pro[idP].Vn;  //产生式左部 A
                        if(notml[idV].FOLLOW.count(-j)){   //归约
                            Action[i][j] = idP+2*SIZE;      //产生式编号加两倍SIZE,和移进操作区分
                        }
                    }
                }else { //规则(1)(4)
                    for(pair<int,int> x:I[i].go){   //遍历每条边
                        int idt = x.first;  //边的字符 a
                        int idI = x.second; //边的指向项目集 I
                        if(idt>0){  //点‘.’后面是非终结符 如A -> a . Bp
                            Goto[i][idt] = idI;
                        }
                        else if(pro[idP].candy.size()>dot&&(pro[idP].candy[dot]==idt)){    //点‘.’后面是终结符  如A -> c . ap
                            Action[i][-idt] = idI;
                        }
                    }
                }
    
            }
    
    
        }
        displayTable();
    }
    
    #endif // GETACTION_H_INCLUDED
    

     

    #ifndef ANALYSE_H_INCLUDED
    #define ANALYSE_H_INCLUDED
    
    //输出ACTION动作
    void displayS(int inNum,int stzNum,int stfNum,int tableNum){
        cout<<"ACTION["<<stzNum<<","<<rmpVt[-inNum]<<"]=S"<<tableNum<<":";
        cout<<"将状态"<<tableNum<<"入栈"<<endl;
    }
    
    //输出归约动作
    void displayR(int stzT,int tableNum,int idP,int stznew){
        cout<<"r"<<tableNum-2*SIZE<<":"<<"用";
        cout<<rmpVn[pro[idP].Vn]<<"->";
        for(int i=0;i<pro[idP].candy.size();i++){
            int x=pro[idP].candy[i];
            if(x>0) cout<<rmpVn[x];
            else cout<<rmpVt[-x];
        }
        cout<<"归约且GOTO(";
        cout<<stzT<<","<<rmpVn[pro[idP].Vn]<<")=";
        cout<<stznew<<"入栈"<<endl;
    }
    
    //输出分析成功
    void displaySuccess(){
        cout<<"Acc:分析成功"<<endl;
    }
    
    //输出状态栈情况
    void displayStz(stack<int>st){
        vector<int>vec;
        while(!st.empty()){
            vec.push_back(st.top());
            st.pop();
        }
        for(int i=vec.size()-1;i>=0;i--){
            if(i==0) cout.width(20-2*vec.size());
            cout<<vec[i]<<" ";
        }
    }
    
    //输出符号栈情况
    void displayStf(stack<int>st){
        vector<int>vec;
        while(!st.empty()){
            vec.push_back(st.top());
            st.pop();
        }
        for(int i=vec.size()-1;i>=0;i--){
            if(i==0) cout.width(20-2*vec.size());
            if(vec[i]>0) cout<<rmpVn[vec[i]]<<" ";
            else cout<<rmpVt[-vec[i]]<<" ";
        }
    }
    
    //输出输入串情况
    void displayInput(int pos,vector<int> vec){
        for(int i=pos;i<vec.size();i++){
            if(i==vec.size()-1) cout.width(20-2*(vec.size()-pos));
            if(vec[i]>0) cout<<rmpVn[vec[i]]<<" ";
            else cout<<rmpVt[-vec[i]]<<" ";
        }
    }
    
    //分析输入串
    void getAns(string str){
    
        cout.setf(std::ios::left);
    
        cout<<"输入串:"<<str<<endl;
        cout<<"------------------------analyse start-----------------------"<<endl;
        cout<<"步骤\t状态栈\t\t符号栈\t\t\t输入串\t\t动作说明\n";
        int len = str.length();
        vector<int>input;
        for(int i=0;i<len;i++){ //将输入串转换成编号
            string tmp="";
            tmp+=str[i];
            input.push_back(-mpVt[tmp]);
        }
        input.push_back(-JING); //增加‘#’号
    
        stack<int>stz, stf; //状态栈和符号栈
    
        stz.push(0);
        stf.push(-JING);
    
        int pos = 0;
    
        int step = 1;
        while(1){
            cout.width(8);
            cout<<step++;   //输出第几步
            displayStz(stz);    //输出状态栈
            displayStf(stf);    //输出符号栈
            displayInput(pos,input);    //输出输入串
            int inNum = input[pos];
            if(stf.size()==0||stz.size()==0){   //状态栈或符号栈为空分析失败
                errorA();
                return ;
            }
            int stzNum = stz.top();
            int stfNum = stf.top();
            int tableNum;
            tableNum = Action[stzNum][-inNum];  //取Action表对应值
            //cout<<stzNum<<":"<<inNum<<":"<<tableNum<<":"<<stfNum<<endl;
            if(tableNum == ACC) break;
            if(tableNum == ERROR){
                errorA();
                return ;
            }
            if(tableNum>=2*SIZE){   //归约
                int idP = tableNum - 2*SIZE;
                for(int i=pro[idP].candy.size()-1;i>=0;i--){    //根据产生式右部进行出栈
                    if(pro[idP].candy[i]!=stf.top()) errorA();
                    if(stf.size()==0||stz.size()==0){
                        errorA();
                        return ;
                    }
                    stf.pop();
                    stz.pop();
    
                }
                stf.push(pro[idP].Vn);  //将产生式左部加进符号栈
                if(stf.size()==0||stz.size()==0){
                    errorA();
                    return ;
                }
                int stzT = stz.top();
                int stznew = Goto[stzT][pro[idP].Vn];   //取得对应的GOTO表值
                stz.push(stznew);   //将GOTO表的值加入状态栈
                displayR(stzT,tableNum,idP,stznew); //输出归约动作
            }else{     //移进
                stz.push(tableNum);
                stf.push(inNum);
                pos++;
                displayS(inNum,stzNum,stfNum,tableNum);
            }
            cout<<endl;
        }
        displaySuccess();
    
    
        cout<<"------------------------analyse end-----------------------"<<endl;
    
    }
    
    #endif // ANALYSE_H_INCLUDED
    

     

    #ifndef CHECK_H_INCLUDED
    #define CHECK_H_INCLUDED
    
    void errorG()
    {
        cout<<"输入的文法有误"<<endl;
        exit(0);
    }
    
    void errorA()
    {
        cout<<"分析错误"<<endl;
        cout<<"------------------------error start-----------------------"<<endl;
    }
    
    #endif // CHECK_H_INCLUDED
    
    #ifndef DISPLAY_H_INCLUDED
    #define DISPLAY_H_INCLUDED
    
    void displayPro2(){
        for(int i=0;i<idVn;i++){
            cout<<rmpVn[i]<<" -> ";
            for(int j=0;j< notml[i].pro.size();j++){
                 for(int k=0;k<notml[i].pro[j].size();k++){
                    if(notml[i].pro[j][k]>0)
                        cout<<rmpVn[notml[i].pro[j][k]]<<" ";
                    else cout<<rmpVt[abs(notml[i].pro[j][k])]<<" ";
                 }
                 cout<<"\t|\t";
            }
            cout<<endl;
        }
    }
    
    //输出产生式
    void displayPro(){
        cout<<"--------------------start----------------------"<<endl;
        for(int i=0;i<idPro;i++){
            cout<<i<<": ";
            cout<<rmpVn[pro[i].Vn]<<"->";
            for(int x : pro[i].candy){
                if(x>0){
                    cout<<rmpVn[x];
                }else {
                    cout<<rmpVt[-x];
                }
            }
            cout<<endl<<endl;
        }
        cout<<"--------------------end----------------------"<<endl;
    
    }
    
    #endif // DISPLAY_H_INCLUDED
    

     

    展开全文
  • JAVA实现SLR(1)文法的分析器

    千次阅读 2020-01-12 15:32:28
    (4)输入字符串,按照SLR分析法判断该字符串的语法是否正确,并给出判断过程 代码的思路: 将文法中的每一个句子的左部和右部进行分离。其中,右部的每一个终结符和非终结符也是单独保存的。 将左部和右部分离后...
  • SLR文法代码

    千次阅读 2016-11-28 20:56:54
    //遇见右括号,没有左括号,说明右括号错误 i++; cout 不匹配的右括号,将忽略该字符" ; break; } case '3':{ //期望遇见运算符,加进+ s.push(1); s.push(6); cout 缺少运算符,加入a" ; break; } case '4':{ //提前...
  • 要求: ...本次的题目和之前的功能很类似,都是基于SLR文法的,所有代码与之前有很多共同之处。 #include #include #include using namespace std; /* E->E+T E->T T->T*F T->F F->(E) F->id */ /
  • 完成以下描述赋值语句 SLR(1)文法语法制导生成中间代码四元式的过程。G[E]: S→V=E E →E+T∣E-T∣T T→T*F∣T/F∣F F→(E)∣i V=I 2.[设计说明] 终结符号i 为用户定义的简单变量,即标识符的定义。 3.[设计要求] (1...
  • 考完编译原理有一段时间了,记得当时都被以上这五种文法搞懵了,所以希望写篇文章帮助那些正在学习的人。以下内容是依据龙书中文版讲解的,由于老师不同可能某些地方...那为什么没有 LL(1)文法呢?因为它和上面的四.
  • SLR(1)分析法

    万次阅读 多人点赞 2019-05-26 09:52:11
    文章目录SLR分析法的基本思想SLR(1)分析表的构造 LR(0)文法要求文法的每一个LR(0)项目都不含有冲突的项目,这个条件比较苛刻。对于大多数程序设计语言来说,一般都不能满足LR(0)文法的条件。 例如: 不难看出在状态...
  • 证明下列文法是LL(1)文法但不是SLR(1)文法 S->AaAb|BbBa A->εB->ε  (1)首先该文法无左递归存在,没有公共左因子.  其次:对于S→AaAb|BbBa FIRST(AaAb)={a} FIRST(BbBa)={b}  FIRST(AaAb)∩FIRST(BbBa)=...
  • 编译原理 - SLR分析法设计与实现

    千次阅读 2020-06-18 20:56:08
    (1)由于LR(0)能分析的文法一般都很简单,而且文法构造出的活前缀的DFA的每个状态都不能含冲突项目。故本实验选择一个较为复杂的SLR分析方法。 (2)一般的项目集规范族中如若存在“移进-规约”冲突项目,是不能...
  • 程序功能描述完成以下描述赋值语句 SLR(1)文法语法制导生成中间代码四元式的过程。G[A]:A→V=EE→E+T∣E-T∣TT→T*F∣T/F∣FF→(E)∣iV→i[设计说明] 终结符号i为用户定义的简单变量,即标识符的定义。[设计要求](1...
  • 上节课的内容中,LR(0)存在冲突。这节课首先提出SLR进行解决。SLR的改进很简单,但还存在冲突。因此又引出LR(1)。 但是,LR(1)的状态过多,于是引出LALR化简、合并其状态。 最后,介绍了二义性与错误处理。
  • 第一步:改写为扩广文法,一般只是新加一个起始非终结符,并且将所有的产生式拆开即可,然后在所有文法的前面加从0开始的编号,以便构建LR(0)分析表的时候有用。 第二步:列出所有项目。这个比较简单,将所有的产生...
  • 使用c/c++实现SLR(1)语法分析器

    千次阅读 热门讨论 2020-11-13 22:59:01
    使用c/c++实现SLR1语法分析器一、前言二、具体实现1、结构体介绍analysis_table_cell.hcollection.hitem.hprodection_rule.hstate.hsymbol.h和word.h3、重要结构介绍3、重要函数介绍CLOSURE()GOTO()...
  • 输入文法,可以构造出LR1状态图 →可以对状态图用张力-斥力模型自动布局 →点击状态编号以高亮显示该状态 →状态超过20个,布局会变得很慢 →请勿输入格式错误的文法 ●LR1与LALR分析表构造 →输入...
  • LR(0)分析和SLR

    千次阅读 2020-06-04 11:25:01
    ①栈顶出现句柄时规约,否则移入。 ②移入项目、代约项目、归约项目 1.引入开始符,得到增广文法,并且给每个式子编号。(即如果文法开头不是一个非终结符到另一个非终结符的产生式则需要加入,如加入 S’->·S ...
  • LR(0), SLR(1)到LR(1)语法分析详解

    千次阅读 2020-04-27 12:59:07
    今天讲解LR(0)SLR(1)LR(1) 首先是自底向上分析过程: 为一个输入串构造语法分析树的过程 LR(k)分析技术: L:从左向右 R: 反向构造一个最右推导序列 k: 做出语法分析决定时向前看k个输入符号 当然在实践中我们只考虑k...
  • Python实现SLR(1)语法分析器 实验课前一天晚上肝了个SLR语法分析器,当时还发朋友圈语法分析器和我晚上总得走一个,从第二天状态来看,应该是我们俩一起走了(笑 编写的时间比较仓促,所以代码有些地方实现不是...
  • 编译原理——语法分析器(SLR

    千次阅读 2021-06-18 17:03:54
    编译原理——语法分析器(SLR) 识别语法结构: 变量声明(不含变量初始化) if单条件分支语句以及if else 双条件分支语句 for循环和while循环语句 赋值语句 ,四则运算,逻辑判断复合语句 函数声明 函数调用 文法...
  • 西安邮电大学编译原理LL文法分析器实验(java)《编译原理》实验报告题目: 语法分析器的制作学生姓名:班 级: 软件1202学 号:指导教师:成 绩:西安邮电大学计算机学院2015 年 6 月 7 日一:实验目的熟悉语法分析的过程;...
  • 上下文无关文法及分析3.1 分析过程3.2 上下文无关文法3.3 分析树与抽象语法树3.4 二义性3.5 扩展的表示法:EBNF和语法图3.6 上下文无关语言的形式特性3.7 TINY语言的语法 分析的任务是确定程序的语法,或称作结构,...
  • 本篇文章通过文法构造SLR分析表,然后构造LR分析器。然后通过编码将其实现(本篇主题)。用了两种风格代码实现,分别为java和JavaScript。
  • 怎么判断一个文法是LR(0)

    千次阅读 2020-12-23 12:39:44
    展开全部LR(0)分析就是LR(K)分析当K=0的情况,32313133353236313431303231363533e78988e69d8331333431366431亦即在分析的每一步,只要根据当前...当前分析栈中已移进或归约出的全部文法符号)就能确定应采取何种分析动作...
  • 测试SLR文法例子

    千次阅读 2005-06-14 20:28:00
    输入文法intifthenelsewhiledoandnottrueid(){};:=+*$##################################OPDASKCBRWULNETFMH[##################################O->PP->DD->D;DD->A:idD->id()D;SA->intS->id=K EC->if B thenR->...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 415
精华内容 166
关键字:

slr输入文法 没有结果显示