ll(1)wenfa.cpp

LL(1)文法的实现方法,有需要的可以

#include<iostream>
#include<stdio.h>
#include <string>
#include <stack>
using namespace std;

void showstack(stack< char > st)
{
 int i,j;
 char ch[100];
 j=st.size();
 for(i=0;i<j;i++)
 {
        ch[i]=st.top();
  st.pop();
 }
    for(i=j-1;i>=0;i--)
 {
  cout<<ch[i];
  st.push(ch[i]);
 }
}

bool find(char c,char array[])                     //查找函数，返回布尔值
{ 
 int i;
 bool flag=false;
 for(i=0;i<100;i++)
 {
  if(c==array[i])
   flag=true;
 }
 return flag;
}

int location(char c,char array[])                  //定位函数,指出字符所在位置
{
 int i;
 for(i=0;i<100;i++)
 {
  if(c==array[i])
    return i;
 }
return 0;
}

void error()
{
   cout<<"                    出错!"<<endl;
}

void analyse(char Vn[],char Vt[],string M[100][100]) //分析函数
{
   int i,j,m,p,q,length,t,h;//,记录栈顶指针位置(j),记录产生式右部的长度(length),记录分析步骤数(h)
   char w,X;                //w用于记录剩余输入串的第一个元素,x记录分析栈的栈顶元素
   string str;   //记录要分析的字符串
OPT0:
   cin>>str;         //输入要分析的字符串，且以#结束
   for(i=0;i<str.size();i++)
   {
    if(!find(str[i],Vt))
    {  
	 cout<<"输入字符串有误!请重新输入!"<<endl;
     goto OPT0;
     break;
	}
   }
   stack <char> st;
   st.push('#');                                  
   st.push(Vn[0]);                  //#与识别符号入栈
   j=0;
   h=1;
   w=str[0];
   cout<<"步骤            "<<"分析栈                "<<"剩余输入串           "<<" 所用产生式"<<endl;
OPT1:
   cout<<h<<"                ";                    //显示步骤
   h++;
   showstack(st);                                   //显示分析栈中内容
   cout<<"                      ";
   for(t=j;t<str.size();t++)
   {
    cout<<str[t];                              //显示剩余字符串
   }
   X=st.top();                             //上托栈顶符号放入X
   st.pop();
   if(find(X,Vt)&& X!='#')
   {
     if(X==w)                                    //分析栈的栈顶元素和剩余输入串的第一个元素相比较
     {     
      cout<<"                   "<<X<<"匹配"<<endl;
      j++;
      w=str[j];
      goto OPT1;
     }
     else 
       error();
   }
   else 
   {
    if(X=='#')
    {
       if(X==w)
	   { 
         cout<<"                    "<<"接受!"<<endl<<endl;       
	   }
       else
         error();
    }
    else  
    {
       p=location(X,Vn);
       q=location(w,Vt);
       string S1("NULL"),S2("null");
       if(M[p][q]==S1 || M[p][q]==S2)                          //查找二维数组中的产生式
          error();
       else
	   {   
         string str0=M[p][q]; 
         cout<<"                  "<<X<<"-->"<<str0<<endl;       //显示对应的产生式
         if(str0=="$")
            goto OPT1;
         else
		 {
			length=str0.size();                                //逆序进栈
            for(m=length-1;m>=0;m--)
			{
              st.push(str0[m]);
			}
            goto OPT1;
		 }
	   }
	}
   }
}

main()
{   
 int i,k,cVn,cVt;
 char Vn[100],Vt[100],select;
 string M[100][100];           //用于记录各非终结符的右部
    cout<<"* 文件名称: 语法分析"<<endl;
    cout<<"* 摘    要: 对任意输入LL(1)文法的分析表及字符串，本程序能自动判断所给字符串是"<<endl;
    cout<<"*           否为该文法的句子，并能给出分析过程。"<<endl;
    cout<<"*--------------------------------------------------------------------*"<<endl;
    cout<<endl<<endl;
SELECT2: 
 cout<<"请输入非终结符个数:";
 cin>>cVn;
 cout<<"请输入各终结符(#号表示结束)Vt[i]:";
 for(i=0;i<100;i++)
 {
  cin>>Vt[i];
  if(Vt[i]=='#')
  {
   cVt=i;
   break;
  }
 }
 for (i=0;i<cVn;i++)
 {
  cout<<"请输入非终结符Vn["<<i<<"]:";
  cin>>Vn[i];
  cout<<"请输入此非终结符对应各终结符的产生式右部(null或NULL表示出错;$表示空串):"; 
  for(k=0;k<=cVt;k++)
  {
   cin>>M[i][k];
  }
 }
SELECT3:
    cout<<"请输入要分析的字符串，且以#结束:";
    analyse(Vn, Vt, M);
    cout<<"             ************************请选择***********************"<<endl;
    cout<<"                                  1: 输入字符串"                  <<endl;
    cout<<"                                  2: 输入新分析表"                <<endl;
    cout<<"                                  0: 退  出"                      <<endl;
SELECT4:
    cin>>select;
    switch(select)
	{
        case '1': {goto SELECT3;break;}
        case '2': {goto SELECT2;}
        case '0': {break;}
        default:  {
			cout<<"输入错误!请重新选择:"<<endl;
            goto SELECT4;
            break;}
	}
    return 0;
}