// 栈的类定义头文件
// Stack.h: interface for the Stack class.
//
//////////////////////////////////////////////////////////////////////
#if !defined(AFX_STACK_H__AA8994AF_8B3A_477C_A4CC_6F18499CA9BE__INCLUDED_)
#define AFX_STACK_H__AA8994AF_8B3A_477C_A4CC_6F18499CA9BE__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
class Stack
{
public:
Stack();
~Stack();
void push(char token);
char pop();
bool isEmpty();
private:
char *_stack;
int _top;
int _bottom;
};
#endif // !defined(AFX_STACK_H__AA8994AF_8B3A_477C_A4CC_6F18499CA9BE__INCLUDED_)
// 栈的实现文件
// Stack.cpp: implementation of the Stack class.
//
//////////////////////////////////////////////////////////////////////
#include <iostream>
#include "Stack.h"
using namespace std;
const int InitStackSize=50;
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
Stack::Stack()
{
_stack=new char [InitStackSize];
_top=_bottom=-1;
}
Stack::~Stack()
{
_top=_bottom=-1;
delete _stack;
}
//////////////////////////////////////////////////////////////////////
// Attributes
//////////////////////////////////////////////////////////////////////
void Stack::push(char token)
{
if(_top>=InitStackSize-1)
{
cerr<<"Stack is overflow!"<<endl;
exit(1);
}
_top++;
_stack[_top]=token;
}
char Stack::pop()
{
if(_top<0)
{
cerr<<"Stack is empty!"<<endl;
exit(1);
}
_top--;
return _stack[_top+1];
}
bool Stack::isEmpty()
{
if(_top==_bottom)
return true;
else
return false;
}
// 分析表的构造
#include "Stack.h"
#include <iostream>
using namespace std;
const int NonterminalNum=5;
const int TerminalNum=6;
char nonterminal[]={'E', 'P', 'T', 'Q','F'};
char terminal[]={'i', '+', '*', '(', ')'};
Stack stack;
//////////////////////////////////////////////////////////////////////
// Event Declarations, Construct LL(1) Parsing Table
//////////////////////////////////////////////////////////////////////
void Event1();
void Event2();
void Event3();
void Event4();
void Event5();
void Event6();
void Event7();
void Error();
typedef void (*Action)();
Action ParseTable[NonterminalNum][TerminalNum]={
{Event1, Error, Error, Event1, Error, Error},
{Error, Event2, Error, Error, Event3, Event3},
{Event4, Error, Error, Event4, Error, Error},
{Error, Event3, Event5, Error, Event3, Event3},
{Event6, Error, Error, Event7, Error, Error}
};
//////////////////////////////////////////////////////////////////////
// Define Events
//////////////////////////////////////////////////////////////////////
void Event1()
{
stack.push('P');
stack.push('T');
};
void Event2()
{
stack.push('P');
stack.push('T');
stack.push('+');
};
void Event3()
{
};
void Event4()
{
stack.push('Q');
stack.push('F');
};
void Event5()
{
stack.push('Q');
stack.push('F');
stack.push('*');
};
void Event6()
{
stack.push('i');
};
void Event7()
{
stack.push(')');
stack.push('E');
stack.push('(');
};
//////////////////////////////////////////////////////////////////////
// Error Process
//////////////////////////////////////////////////////////////////////
void Error()
{
cerr<<"---------------------Syntax Error!----------------------\n";
exit(1);
};
//////////////////////////////////////////////////////////////////////
// Judge the Token is a Terminal or a Nonterminal
//////////////////////////////////////////////////////////////////////
bool isVt(char ch)
{
for(int i=0; i<5; i++)
{
if(terminal[i]==ch)
return true;
else
continue;
}
return false;
}
//////////////////////////////////////////////////////////////////////
// Push in Stack
//////////////////////////////////////////////////////////////////////
void pushTogether(char nonterminal, char terminal)
{
switch(nonterminal)
{
case 'E':
switch(terminal)
{
case 'i': ParseTable[0][0](); break;
case '+': ParseTable[0][1](); break;
case '*': ParseTable[0][2](); break;
case '(': ParseTable[0][3](); break;
case ')': ParseTable[0][4](); break;
case '#': ParseTable[0][5](); break;
default: break;
}
break;
case 'P':
switch(terminal)
{
case 'i': ParseTable[1][0](); break;
case '+': ParseTable[1][1](); break;
case '*': ParseTable[1][2](); break;
case '(': ParseTable[1][3](); break;
case ')': ParseTable[1][4](); break;
case '#': ParseTable[1][5](); break;
default: break;
}
break;
case 'T':
switch(terminal)
{
case 'i': ParseTable[2][0](); break;
case '+': ParseTable[2][1](); break;
case '*': ParseTable[2][2](); break;
case '(': ParseTable[2][3](); break;
case ')': ParseTable[2][4](); break;
case '#': ParseTable[2][5](); break;
default: break;
}
break;
case 'Q':
switch(terminal)
{
case 'i': ParseTable[3][0](); break;
case '+': ParseTable[3][1](); break;
case '*': ParseTable[3][2](); break;
case '(': ParseTable[3][3](); break;
case ')': ParseTable[3][4](); break;
case '#': ParseTable[3][5](); break;
default: break;
}
break;
case 'F':
switch(terminal)
{
case 'i': ParseTable[4][0](); break;
case '+': ParseTable[4][1](); break;
case '*': ParseTable[4][2](); break;
case '(': ParseTable[4][3](); break;
case ')': ParseTable[4][4](); break;
case '#': ParseTable[4][5](); break;
default: break;
}
break;
default:
Error();
break;
}
}
// LL（1）分析程序
#include <iostream>
#include "Stack.h"
#include "Parse.h"
using namespace std;
//////////////////////////////////////////////////////////////////////
// The LL(1) arithematic
//////////////////////////////////////////////////////////////////////
void LL1Parse()
{
stack.push('#');
stack.push('E');
char a;
cout<<"Please input a language(end with a token '#'):"<<endl;
a=getchar();
bool flag=true;
while(flag)
{
char X=stack.pop();
if(isVt(X))
{
if(X==a) //match
a=getchar();
else
Error();
}
else if(X=='#')
{
if(X==a) //parse successfully
flag=false;
else
Error();
}
else //reverse, push into stack
pushTogether(X, a);
}
if(stack.isEmpty())
cout<<"------------------Compile successfully!----------------"<<endl;
}
// 主程序
#include <iostream>
#include "LL1.h"
using namespace std;
void main()
{
cout<<"=★=Simple Integer Arithmatic Expression Grammer Parsing Unit=★=\n";
cout<<"=★= According to the LL(1) Arithmatic =★=\n";
cout<<"=★==========================================================★=\n";
cout<<endl;
cout<<"\t\tThe grammer descirbed as bellow:\n";
cout<<"\t\t\t E→TP\n";
cout<<"\t\t\t P→+TP｜ε\n";
cout<<"\t\t\t T→FQ\n";
cout<<"\t\t\t Q→*FQ｜ε\n";
cout<<"\t\t\t F→(E)｜i\n";
cout<<endl;
cout<<"-----------☆--------Welcome to My System--------☆------------\n";
LL1Parse();
}
