里面内容仅供学习参考, 可以基于此代码进行修改加工
第五次编译原理实验内容:
1. LR语法分析
2. 语义计算
3. 代码优化
1. LR语法分析
2. 语义计算
3. 代码优化
LR(0)语法分析程序的设计
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
///表格数组 a b c d # E A B
char LR0[50][50][100] = {{"S2" ,"S3" ,"null", "null" ,"null" ,"1" ,"null" ,"null"},/// 0
{"null" ,"null" ,"null", "null" ,"acc " ,"null" ,"null" ,"null"},/// 1
{"null" ,"null" ,"S4" , "S10" ,"null" ,"null" ,"6" ,"null"},/// 2
{"null" ,"null" ,"S5" , "S11" ,"null" ,"null" ,"null" ,"7" },/// 3
{"null" ,"null" ,"S4" , "S10" ,"null" ,"null" ,"8" ,"null"},/// 4
{"null" ,"null" ,"S5" , "S11" ,"null" ,"null" ,"null" ,"9" },/// 5
{"r1" ,"r1" ,"r1" , "r1" ,"r1" ,"null" ,"null" ,"null"},/// 6
{"r2" ,"r2" ,"r2" , "r2" ,"r2" ,"null" ,"null" ,"null"},/// 7
{"r3" ,"r3" ,"r3" , "r3" ,"r3" ,"null" ,"null" ,"null"},/// 8
{"r5" ,"r5" ,"r5" , "r5" ,"r5" ,"null" ,"null" ,"null"},/// 9
{"r4" ,"r4" ,"r4" , "r4" ,"r4" ,"null" ,"null" ,"null"},/// 10
{"r6" ,"r6" ,"r6" , "r6" ,"r6" ,"null" ,"null" ,"null"},/// 11
};
char L[200]="abcd#EAB"; ///列判断依据
int del[10]={0,2,2,2,1,2,1};//0-6号文法每个文法长度
char head[20]={'S','E','E','A','A','B','B'};
stack<int>con; ///状态栈
stack<char>cmp; ///符号栈
char cod[300]="0";///初始状态栈对应输出数组
int cindex = 0;
char sti[300]="#";///初始符号栈对应输出数组
int sindex = 0;
int findL(char b)///对应列寻找
{
for(int i = 0; i <= 7; i++)
{
if(b==L[i])
{
return i;
}
}
return -1;
}
void error(int x, int y) ///报错输出
{
printf("第%d行%c列为空!",x,L[y]);
}
int calculate(int l, char s[])
{
int num = 0;
for(int i = 1; i < l; i ++)
{
num = num*10+(s[i]-'0');
}
return num;
}
void analyze(char str[],int len)///分析主体过程
{
int cnt = 1;
printf("步骤 状态栈 符号栈 输入串 ACTION GOTO\n");
int LR = 0;
while(LR<=len)
{
printf("(%d) %-10s%-10s",cnt,cod,sti);///步骤，状态栈，符号栈输出
cnt++;
for(int i = LR; i < len; i++)///输入串输出
{
printf("%c",str[i]);
}
for(int i = len-LR; i<10;i++)printf(" ");
int x = con.top();///状态栈栈顶
int y = findL(str[LR]);///待判断串串首
if(strcmp(LR0[x][y],"null")!=0)
{
int l = strlen(LR0[x][y]);///当前Ri或Si的长度
if(LR0[x][y][0]=='a')///acc
{
printf("acc \n");///ACTION与GOTO
return ;
}
else if(LR0[x][y][0]=='S')///Si
{
printf("%-10s \n",LR0[x][y]);///ACTION与GOTO
int t = calculate(l,LR0[x][y]);///整数
con.push(t);
sindex++;
sti[sindex] = str[LR];
cmp.push(str[LR]);
if(t<10)
{
cindex++;
cod[cindex] = LR0[x][y][1];
}
else
{
int k = 1;
cindex++;
cod[cindex] = '(';
while(k<l)
{
cindex++;
cod[cindex] = LR0[x][y][k];
k++;
}
cindex++;
cod[cindex] = ')';
}
LR++;
}
else if(LR0[x][y][0]=='r')///ri,退栈，ACTION和GOTO
{
printf("%-10s",LR0[x][y]);
int t = calculate(l,LR0[x][y]);
int g = del[t];
while(g--)
{
con.pop();
cmp.pop();
sti[sindex] = '\0';
sindex--;
}
g = del[t];
while(g>0)
{
if(cod[cindex]==')')
{
cod[cindex]='\0';
cindex--;
for(;;)
{
if(cod[cindex]=='(')
{
cod[cindex]='\0';
cindex--;
break;
}else
{
cod[cindex]='\0';
cindex--;
}
}
g--;
}else
{
cod[cindex] = '\0';
cindex--;
g--;
}
}///
cmp.push(head[t]);
sindex++;
sti[sindex] = head[t];
x = con.top();
y = findL(cmp.top());
t = LR0[x][y][0]-'0';
con.push(t);
cindex++;
cod[cindex] = LR0[x][y][0];
printf("%-10d\n",t);
}else
{
int t = LR0[x][y][0]-'0';
char ch = ' ';
printf("%-10c%-10d\n",ch,t);
con.push(t);
cindex++;
cod[cindex] = LR0[x][y][0];
sindex++;
sti[sindex] = 'E';
LR++;
}
}else
{
error(x,y);
return ;
///报错
}
}
}
void chart()///测试表函数
{
printf("-\ta\tb\tc\td\t#\tE\tA\tB\n");
for(int i = 0; i <= 11; i++)
{
printf("%d",i);
for(int j = 0 ; j <= 8; j++)
printf("\t%s",LR0[i][j]);
cout<<endl;
}
cout<<endl;
}
int main()
{
chart();
con.push(0);
cmp.push('#');
char str[200];///输入串
cout<<"请输入字符串（带#）："<<endl;
cin>>str;
int len = strlen(str);
analyze(str,len);
return 0;
}
/*
输入：bccd#
输出:
步骤 状态栈 符号栈 输入串 ACTION GOTO
(1) 0 # bccd# S3
(2) 03 #b ccd# S5
(3) 035 #bc cd# S5
(4) 0355 #bcc d# S11
(5) 0355(11) #bccd # r6 9
(6) 03559 #bccB # r5 9
(7) 0359 #bcB # r5 7
(8) 037 #bB # r2 1
(9) 01 #E # acc
输入：abc
输出：
步骤 状态栈 符号栈 输入串 ACTION GOTO
(1) 0 # abc S2
(2) 02 #a bc 第2行b列为空!
输入：abc#
输出：
步骤 状态栈 符号栈 输入串 ACTION GOTO
(1) 0 # abc# S2
(2) 02 #a bc# 第2行b列为空!
输入：E#
输出：
步骤 状态栈 符号栈 输入串 ACTION GOTO
(1) 0 # E# 1
(2) 01 #E # acc
输入：cabc#
输出：
步骤 状态栈 符号栈 输入串 ACTION GOTO
(1) 0 # cabc# 第0行c列为空!
输入：bccdd#
输出：
步骤 状态栈 符号栈 输入串 ACTION GOTO
(1) 0 # bccdd# S3
(2) 03 #b ccdd# S5
(3) 035 #bc cdd# S5
(4) 0355 #bcc dd# S11
(5) 0355(11) #bccd d# r6 9
(6) 03559 #bccB d# r5 9
(7) 0359 #bcB d# r5 7
(8) 037 #bB d# r2 1
(9) 01 #E d# 第1行d列为空!
*/
LR(0)文法分析法(算法描述和C++代码实现
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <sstream>
#define MAX 507
#define DEBUG
using namespace std;
class WF
{
public:
string left,right;
int back;
int id;
WF ( char s1[] , char s2[] , int x , int y )
{
left = s1;
right = s2;
back = x;
id = y;
}
WF ( const string& s1 , const string& s2 , int x , int y )
{
left = s1;
right = s2;
back = x;
id = y;
}
bool operator < ( const WF& a ) const
{
if ( left == a.left )
return right < a.right;
return left < a.left;
}
bool operator == ( const WF& a ) const
{
return ( left == a.left )&& ( right == a.right );
}
void print ( )
{
printf ( "%s->%s\n" , left.c_str() , right.c_str() );
}
};
class Closure
{
public:
vector<WF> element;
void print ( string str )
{
printf ( "%-15s%-15s\n" , "" , str.c_str());
for ( int i = 0 ; i < element.size() ; i++ )
element[i].print();
}
bool operator == ( const Closure& a ) const
{
if ( a.element.size() != element.size() ) return false;
for ( int i = 0 ; i < a.element.size() ; i++ )
if ( element[i] == a.element[i] ) continue;
else return false;
return true;
}
};
struct Content
{
int type;
int num;
string out;
Content(){ type = -1; }
Content ( int a , int b )
:type(a),num(b){}
};
vector<WF> wf;
map<string,vector<int> > dic;
string start = "S";
vector<Closure> collection;
vector<WF> items;
char CH = '$';
int go[MAX][MAX];
int to[MAX];
vector<char> V;
bool used[MAX];
Content action[MAX][MAX];
int Goto[MAX][MAX];
void make_item ( )
{
memset ( to , -1 , sizeof ( -1 ) );
for ( int i = 0 ; i < wf.size() ; i++ )
for ( int j = 0 ; j <= wf[i].right.length() ; j++ )
{
string temp = wf[i].right;
temp.insert ( temp.begin()+j , CH );
dic[wf[i].left].push_back ( items.size() );
if ( j )
to[items.size()-1] = items.size();
items.push_back ( WF ( wf[i].left , temp , i , items.size()) );
}
#ifdef DEBUG
puts("-------------------------项目表-------------------------");
for ( int i = 0 ; i < items.size() ; i++ )
printf ( "%s->%s\n" , items[i].left.c_str() , items[i].right.c_str() );
puts("--------------------------------------------------------");
#endif
}
void make_set ( )
{
bool has[MAX];
for ( int i = 0 ; i < items.size() ; i++ )
if ( items[i].left[0] == 'S' && items[i].right[0] == CH )
{
Closure temp;
string& str = items[i].right;
vector<WF>& element = temp.element;
element.push_back ( items[i] );
int x = 0;
for ( x = 0 ; x < str.length() ; x++ )
if ( str[x] == CH )
break;
/*if ( x != str.length()-1 )
{
string tt = str.substr(x+1,1);
vector<int>& id = dic[tt];
for ( int j = 0 ; j < id.size() ; j++ )
{
int tx = id[j];
//items[tx].print();
if ( items[tx].right[0] == CH )
element.push_back ( items[tx] );
}
}*/
memset ( has , 0 , sizeof ( has ) );
has[i] = 1;
if ( x != str.length()-1 )
{
queue<string> q;
q.push( str.substr(x+1,1) );
while ( !q.empty() )
{
string u = q.front();
q.pop();
vector<int>& id = dic[u];
for( int j = 0 ; j < id.size() ; j++ )
{
int tx = id[j];
if ( items[tx].right[0] == CH )
{
if ( has[tx] ) continue;
has[tx] = 1;
if ( isupper(items[tx].right[1] ) )
q.push ( items[tx].right.substr(1,1));
element.push_back ( items[tx] );
}
}
}
}
collection.push_back ( temp );
}
for ( int i = 0 ; i < collection.size() ; i++ )
{
map<int,Closure> temp;
for ( int j = 0 ; j < collection[i].element.size() ; j++ )
{
string str = collection[i].element[j].right;
int x = 0;
for ( ; x < str.length() ; x++ )
if ( str[x] == CH ) break;
if ( x == str.length()-1 )
continue;
int y = str[x+1];
int ii;
//cout << i << "previous: " << str << endl;
str.erase ( str.begin()+x);
str.insert ( str.begin()+x+1 , CH );
//cout << i <<"after: " << str << endl;
WF cmp = WF ( collection[i].element[j].left , str , -1 , -1 );
for ( int k = 0 ; k< items.size() ; k++ )
if ( items[k] == cmp )
{
ii = k;
break;
}
//string& str1 = items[ii].right;
memset ( has , 0 , sizeof ( has ) );
vector<WF>& element = temp[y].element;
element.push_back ( items[ii] );
has[ii] = 1;
x++;
/*if ( x != str.length()-1 )
{
string tt = str.substr(x+1,1);
vector<int>& id = dic[tt];
for ( int j = 0 ; j < id.size() ; j++ )
{
int tx = id[j];
//items[tx].print();
if ( items[tx].right[0] == CH )
element.push_back ( items[tx] );
}
}*/
if ( x != str.length()-1 )
{
queue<string> q;
q.push( str.substr(x+1,1) );
while ( !q.empty() )
{
string u = q.front();
q.pop();
vector<int>& id = dic[u];
for( int j = 0 ; j < id.size() ; j++ )
{
int tx = id[j];
if ( items[tx].right[0] == CH )
{
if ( has[tx] ) continue;
has[tx] = 1;
if ( isupper(items[tx].right[1] ) )
q.push ( items[tx].right.substr(1,1));
element.push_back ( items[tx] );
}
}
}
}
}
map<int,Closure>::iterator it = temp.begin();
for ( ; it != temp.end() ; it++ )
collection.push_back ( it->second );
for ( int i = 0 ; i < collection.size() ; i++ )
sort ( collection[i].element.begin() , collection[i].element.end() );
for ( int i = 0 ; i < collection.size() ; i++ )
for ( int j = i+1 ; j < collection.size() ; j++ )
if ( collection[i] == collection[j] )
collection.erase ( collection.begin()+j );
}
#ifdef DEBUG
puts ("-------------CLOSURE---------------------");
stringstream sin;
for ( int i = 0 ; i < collection.size() ; i++ )
{
sin.clear();
string out;
sin <<"closure-I" << i;
sin >> out;
collection[i].print ( out );
}
puts("");
#endif
}
void make_V ( )
{
memset ( used , 0 , sizeof ( used ) );
for ( int i = 0 ; i < wf.size() ; i++ )
{
string& str = wf[i].left;
for ( int j = 0 ; j < str.length() ; j++ )
{
if ( used[str[j]] ) continue;
used[str[j]] = 1;
V.push_back ( str[j] );
}
string& str1 = wf[i].right;
for ( int j = 0 ; j < str1.length() ; j++ )
{
if ( used[str1[j]] ) continue;
used[str1[j]] = 1;
V.push_back ( str1[j] );
}
}
sort ( V.begin() , V.end() );
V.push_back ( '#' );
}
void make_cmp ( vector<WF>& cmp1 , int i , char ch )
{
for ( int j = 0 ; j < collection[i].element.size() ; j++ )
{
string str = collection[i].element[j].right;
int k;
for ( k = 0 ; k < str.length() ; k++ )
if ( str[k] == CH )
break;
if ( k != str.length() - 1 && str[k+1] == ch )
{
str.erase ( str.begin()+k);
str.insert ( str.begin()+k+1 , CH );
cmp1.push_back ( WF ( collection[i].element[j].left , str , -1 , -1 ) );
}
}
sort ( cmp1.begin() , cmp1.end() );
}
void make_go ( )
{
memset ( go , -1 , sizeof ( go ) );
int m = collection.size();
/*for ( int i = 0 ; i < m ; i++ )
for ( int j = 0 ; j < collection[i].element.size() ; j++ )
{
string left = collection[i].element[j].left;
string str = collection[i].element[j].right;
int x = 0;
for ( ; x < str.length() ; x++ )
if ( str[x] == CH ) break;
if ( x == str.length()-1 )
continue;
int y = str[x+1];
//cout << "before : " << str << endl;
str.erase ( str.begin()+x);
str.insert ( str.begin()+x+1 , CH );
//cout << "after : " << str << endl;
WF cmp = WF ( collection[i].element[j].left , str , -1 , -1 );
for ( int k = 0 ; k < m ; k++ )
{
bool flag = false;
for ( int t = 0 ; t < collection[k].element.size() ; t++ )
{
if ( cmp == collection[k].element[t] )
{
flag = true;
break;
}
}
if ( flag )
{
go[i][y] = k;
}
}
}*/
for ( int t = 0 ; t < V.size() ; t++ )
{
char ch = V[t];
for ( int i = 0 ; i < m ; i++ )
{
vector<WF> cmp1;
make_cmp ( cmp1 , i , ch );
cout << cmp1.size() << endl;
if ( cmp1.size() == 0 ) continue;
for ( int j = 0 ; j < m ; j++ )
{
vector<WF> cmp2;
for ( int k = 0 ; k < collection[j].element.size() ; k++ )
{
string& str = collection[j].element[k].right;
int x;
for ( x = 0 ; x < str.length() ; x++ )
if ( str[x] == CH )
break;
if ( x && str[x-1] == ch )
cmp2.push_back ( WF( collection[j].element[k].left , str , -1 , -1 ) );
}
sort ( cmp2.begin() , cmp2.end() );
cout << cmp2.size() << endl;
bool flag = true;
if ( cmp2.size() != cmp1.size() ) continue;
cout << cmp1.size() << endl;
for ( int k = 0 ; k < cmp1.size() ; k++ )
if ( cmp1[k] == cmp2[k] ) continue;
else flag = false;
cout << "out " << endl;
if ( flag )
go[i][ch] = j;
}
//cout << "YES" << endl;
}
}
#ifdef DEBUG
puts ("---------------EDGE----------------------");
stringstream sin;
string out;
for ( int i = 0 ; i < m ; i++ )
for ( int j = 0 ; j < m ; j++ )
for ( int k = 0 ; k < MAX ; k++ )
if ( go[i][k] == j )
{
sin.clear();
sin << "I" << i << "--" <<(char)(k)<<"--I"<<j;
sin >> out;
printf ( "%s\n" , out.c_str() );
}
#endif
}
void make_table ( )
{
memset ( Goto , -1 , sizeof ( Goto ) );
/*memset ( used , 0 , sizeof ( used ) );
for ( int i = 0 ; i < wf.size() ; i++ )
{
string& str = wf[i].left;
for ( int j = 0 ; j < str.length() ; j++ )
{
if ( used[str[j]] ) continue;
used[str[j]] = 1;
V.push_back ( str[j] );
}
string& str1 = wf[i].right;
for ( int j = 0 ; j < str1.length() ; j++ )
{
if ( used[str1[j]] ) continue;
used[str1[j]] = 1;
V.push_back ( str1[j] );
}
}
sort ( V.begin() , V.end() );
V.push_back ( '#' );*/
//write s to the table
for( int i = 0 ; i < collection.size() ; i++ )
for ( int j = 0 ; j < V.size() ; j++ )
{
char ch = V[j];
int x = go[i][ch];
if ( x == -1 ) continue;
if ( !isupper(ch) )
action[i][ch] = Content ( 0 , x );
else
Goto[i][ch] = x;
}
//write r and acc to the table
for ( int i = 0 ; i < collection.size() ; i++ )
for ( int j = 0 ; j < collection[i].element.size() ; j++ )
{
WF& tt = collection[i].element[j];
if ( tt.right[tt.right.length()-1] == CH )
{
if ( tt.left[0] == 'S' )
action[i]['#'] = Content ( 2 , -1 );
else
for ( int k = 0 ; k < V.size() ; k++ )
{
int y = V[k];
//cout << "YES " << endl;
action[i][y] = Content ( 1, tt.back );
}
}
}
#ifdef DEBUG
puts ( "------------------------------------------LR(0)分析表--------------------------------------------------------" );
printf ( "%10s%5c%5s" , "|" , V[0] , "|");
for ( int i = 1 ; i < V.size() ; i++ )
printf ( "%5c%5s" , V[i] , "|" );
puts ("");
for ( int i = 0 ; i < (V.size()+1)*10 ; i++ )
printf ( "-" );
puts("");
stringstream sin;
for ( int i = 0 ; i < collection.size() ; i++ )
{
printf ( "%5d%5s" , i , "|" );
for ( int j = 0 ; j < V.size() ; j++ )
{
char ch = V[j];
if ( isupper(ch) )
{
if ( Goto[i][ch] == -1 )
printf ( "%10s" , "|" );
else
printf ( "%5d%5s" , Goto[i][ch] , "|" );
}
else
{
sin.clear();
if ( action[i][ch].type == -1 )
printf ( "%10s" , "|" );
else
{
Content& temp = action[i][ch];
if ( temp.type == 0 )
sin << "S";
if ( temp.type == 1 )
sin << "R";
if ( temp.type == 2 )
sin << "acc";
if ( temp.num != -1 )
sin << temp.num;
sin >> temp.out;
printf ( "%7s%3s" , temp.out.c_str() , "|" );
}
}
}
puts ("");
}
for ( int i = 0 ; i < (V.size()+1)*10 ; i++ )
printf ( "-" );
puts("");
#endif
}
void print ( string s1 , string s2 , string s3 , string s4 , string s5 , string s6 , string s7 )
{
printf ( "%-15s|%-15s%-15s%-20s|%-15s%-15s%-15s\n" , s1.c_str() , s2.c_str() , s3.c_str() ,s4.c_str(),s5.c_str(),
s6.c_str() , s7.c_str() );
}
string get_steps ( int x )
{
stringstream sin;
sin << x;
string ret;
sin >> ret;
return ret;
}
template<class T>
string get_stk ( vector<T> stk )
{
stringstream sin;
for ( int i = 0 ; i < stk.size() ; i++ )
sin << stk[i];
string ret;
sin >> ret;
return ret;
}
string get_shift ( WF& temp )
{
stringstream sin;
sin << "reduce(" << temp.left << "->" << temp.right <<")";
string out;
sin >> out;
return out;
}
void analyse ( string src )
{
print ( "steps","op-stack" ,"input","operation","state-stack" , "ACTION" , "GOTO" );
vector<char> op_stack;
vector<int> st_stack;
src+= "#";
op_stack.push_back ( '#' );
st_stack.push_back ( 0 );
int steps= 1;
for ( int i = 0 ; i < src.length() ; i++ )
{
char u = src[i];
int top = st_stack[st_stack.size()-1];
Content& act = action[top][u];
//cout << "YES : " << i << " " << u << " " << top << " " << act.type << endl;
if ( act.type == 0 )
{
print ( get_steps ( steps++ ) , get_stk ( op_stack ) , src.substr(i), "shift", get_stk( st_stack ) , act.out , "" );
op_stack.push_back ( u );
st_stack.push_back ( act.num );
}
else if ( act.type == 1 )
{
WF& tt = wf[act.num];
int y = st_stack[st_stack.size()-tt.right.length()-1];
int x = Goto[y][tt.left[0]];
//cout << y << " " << tt.left[0] << " " << x << endl;
print ( get_steps ( steps++ ) , get_stk ( op_stack ) , src.substr(i) , get_shift(tt) ,get_stk( st_stack),act.out,get_steps(x));
for ( int j = 0 ; j < tt.right.length() ; j++ )
{
st_stack.pop_back();
op_stack.pop_back();
}
op_stack.push_back ( tt.left[0] );
st_stack.push_back ( x );
i--;
}
else if ( act.type == 2 )
{
print ( get_steps( steps++ ), get_stk( op_stack ) , src.substr(i) , "Accept" , get_stk(st_stack) , act.out , "" );
//i--;
}
else continue;
}
}
int main ( )
{
int n;
char s[MAX];
while ( ~scanf ( "%d" , &n ) )
{
for ( int i = 0 ; i < n ; i++ )
{
scanf ( "%s" , s );
int len = strlen(s),j;
for ( j = 0 ; j < len ; j++ )
if ( s[j] == '-' ) break;
s[j] = 0;
wf.push_back ( WF ( s , s+j+2 ,-1 , -1 ) );
#ifdef DEBUG
wf[wf.size()-1].print();
#endif
}
make_item();
make_set();
make_V();
make_go();
make_table();
analyse ( "abbcde" );
}
}输入:
5
S->E
E->aAcBe
A->b
A->Ab
B->d 
LR(0)分析方法（c++实现）
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
using namespace std;
typedef long long LL;
const int INF=0x7fffffff;
const int MAX_N=10000;
int num_of_a,num_of_A,num_of_S,totalnum;
//小写字母个数、大写字母个数、推导式个数、最终结点总数
char a[50];//字母
char S[50][50];//推导式
bool pushed[100];//访问一个结点的时候，再往外拓展时记录非终结符是否已经被push过
int ans[100][100];
char analyse[50];//分析串
int stack1[50];
char stack2[50];
char stack3[50];
int L1,L2,L3;//三个栈的长度
map<char,int>M;
map<char,int>::iterator m;
struct node{//结点
int id;//编号
int num;//包含的推导式个数
char s[20][50];
};
queue<node>q;//结点型队列
node N[100];
int numN=0;
void outputnd(node k){//输出一个结点的s
for(int i=0;i<k.num;i++){
cout<<k.s[i]<<endl;
}
}
void outputlb(){//输出一个数组的s
cout<<"链表"<<endl;
for(int i=0;i<numN;i++){
outputnd(N[i]);
cout<<endl;
}
}
bool samenode(node x,node y){//比较两个node是否一样
if(x.num!=y.num)return 0;//如果两个node包含的s数量不同直接输出不同
for(int i=0;i<x.num;i++){//暴力比较
int flag=0;
for(int j=0;j<y.num;j++){
if(strcmp(x.s[i],y.s[j])==0){
flag=1;
break;
}
}
if(flag==0)return 0;
}
return 1;
}
void init(){//初始化
totalnum=0;//结点数量
while(!q.empty())q.pop();//情况队列
memset(S,0,sizeof(S));
for(int i=0;i<100;i++){
for(int j=0;j<100;j++){
ans[i][j]=-10000;
}
}
M.clear();//清空映射
}
void input(){//顾名思义，输入数据
printf("请输入终结符的个数：");
scanf("%d",&num_of_a);
printf("请输入%d个终结符（小写字母）：",num_of_a);
for(int i=0;i<num_of_a;i++){
scanf(" %c",&a[i]);
M.insert(make_pair(a[i],i));//建立映射
}
a[num_of_a]='#';
M.insert(make_pair(a[num_of_a],num_of_a));
printf("请输入非终结符的个数（不包含起始符）：");
scanf("%d",&num_of_A);
printf("请输入%d个非终结符（大写字母）：",num_of_A);
for(int i=0;i<num_of_A;i++){
scanf(" %c",&a[num_of_a+1+i]);
M.insert(make_pair(a[num_of_a+1+i],num_of_a+1+i));
}
printf("请输入初始推导式的个数：");
scanf("%d",&num_of_S);
printf("下面%d行每行请输入1个推导式：前后用下划线“_”链接（起始为S）:\n",num_of_S);
for(int i=0;i<num_of_S;i++){
scanf("%s",S[i]);
for(int j=strlen(S[i]);j>=3;j--){
S[i][j]=S[i][j-1];
}
S[i][2]='.';
}
}
node pushback(char p,node f){//node f里把所有p开头的推导式push进去
for(int i=0;i<num_of_S;i++){
if(S[i][0]==p){
strcpy(f.s[f.num++],S[i]);
}
}
return f;
}
void bfs(){//宽度优先搜索
node aa;//声明一个空的状态
aa.num=0;
aa.id=totalnum++;//初始化num和id
aa=pushback('S',aa);//把S开头的推导式放到这个起始结点里
memset(pushed,0,sizeof(pushed));//用于记录哪些字母被一次性push过，避免重复push
for(int j=0;j<aa.num;j++){//把需要push的大写字母开头的推导式push进去
if(aa.s[j][3]>='A'&&aa.s[j][3]<='Z'&&pushed[aa.s[j][3]]==0){
aa=pushback(aa.s[j][3],aa);
pushed[aa.s[j][3]]=1;
}
}
q.push(aa);//把起始点放入队列
N[numN++]=aa;//这个东西记录已经存在过的node
while(!q.empty()){//只要队列不为空，就一直运行，下面就是宽搜了
node cur=q.front();
q.pop();//取出头结点保存然后pop掉
for(int i=0;i<num_of_a+num_of_A+1;i++){//搜索所有字母
if(i==num_of_a)continue;//这个位置存储#，所以为了提高程序运行效率，直接过掉
node newnode;//声明一个可能要添加的新结点
newnode.num=0;
newnode.id=-1;
memset(pushed,0,sizeof(pushed));
for(int j=0;j<cur.num;j++){//搜索当前刚取出的队列头结点的所有推导式
for(int k=2;k<strlen(cur.s[j]);k++){//对于每个推导式从左到右爆搜
if(cur.s[j][strlen(cur.s[j])-1]=='.')continue;//如果最后一个位置是“.”直接continue
if(cur.s[j][k]=='.'&&cur.s[j][k+1]==a[i]){//如果“.”后面正好是当前要搜索的字母
if(newnode.id==-1)newnode.id=-2;//这个node可能要被添加了，一个字母加一遍就好，以前没加过就是-1
char news[50];//声明一个新的字符串
strcpy(news,cur.s[j]);//保留现场，先把找到的这条copy下来
swap(news[k],news[k+1]);//把“.”和它后面的字母互换位置
strcpy(newnode.s[newnode.num++],news);//把处理好的news粘贴到newnode里面
if(news[k+2]>='A'&&news[k+2]<='Z'&&pushed[news[k+2]]==0){//如果发现“.”后面的后面跟着大写字母还要麻烦一下
newnode=pushback(news[k+2],newnode);//把所有的以这个大写字母开头的推导式push到newnode里面
pushed[news[k+2]]=1;//之前没注释的memset(pushed,0,sizeof(pushed));此时派上了用场
}
}
}
}
if(newnode.id!=-1){//如果找到了可能需要push的结点
int flag=-1;//我还需要看看这个结点是否已经存在过，是不是形成了环
for(int p=0;p<numN;p++){//爆搜一下曾经的结点
if(samenode(newnode,N[p])==1){//比较一下是不是一样
flag=p;//如果找到一样的，就break，并且保留那个一样的结点的位置
break;
}
}
if(flag!=-1){//发现了一样的结点
ans[cur.id][i]=N[flag].id;//最终结果里体现一下
}
if(flag==-1){//没发现有一样的，那就是新的结点了，把他push到队列里面去
newnode.id=totalnum++;
q.push(newnode);
N[numN++]=newnode;
ans[cur.id][i]=newnode.id;
}
}
}
}
}
void build_table(){//处理表格
for(int i=0;i<totalnum;i++){
int flag=0;
for(int j=0;j<num_of_A+num_of_a+1;j++){
if(ans[i][j]!=-10000){
flag=1;
break;
}
}
if(flag==0){
char news[50];
strcpy(news,N[i].s[0]);
news[strlen(news)+1]='\0';
for(int k=strlen(news)-1;k>=3;k--){
news[k]=news[k-1];
}
news[2]='.';
for(int j=0;j<num_of_S;j++){
if(!strcmp(news,S[j])){
if(j!=0){
for(int k=0;k<num_of_a+1;k++){
ans[i][k]=-1*j;
}
break;
}
for(int k=0;k<num_of_a+1;k++){//r0 用-9999表示，s0用0表示
ans[i][k]=-9999;
}
break;
}
}
}
}
}
void output_action(int act){
if(act>=0)cout<<"S"<<setw(3)<<act;
else if(act==-10000){
cout<<setw(4)<<" ";
}
else if(act==-9999){
cout<<setw(4)<<"r0";
}
else{
cout<<"r"<<setw(3)<<-1*act;
}
}
void output_table(){//输出表格
cout<<left<<"项目 ";
for(int i=0;i<num_of_A+num_of_a+1;i++){
cout<<setw(4)<<a[i];
}cout<<endl;
for(int i=0;i<totalnum;i++){
cout<<setw(6)<<i;
for(int j=0;j<num_of_A+num_of_a+1;j++){
output_action(ans[i][j]);
}cout<<endl;
}
}
int step,action,GOTO;
void output_stacks(){
cout<<endl<<"步骤："<<step++<<endl;
cout<<"状态栈/符号栈/输入串：";
for(int j=0;j<L1;j++){
cout<<stack1[j]<<" ";
}cout<<" ";
for(int j=0;j<L2;j++){
cout<<stack2[j];
}cout<<" ";
for(int j=L3-1;j>=0;j--){
cout<<stack3[j];
}cout<<endl;
}
int judge(){
m=M.find(stack3[L3-1]);//用映射的方式找到要分析的字母是第几个,节省时间提升程序运行效率
if(m==M.end()){
return 0;
}
action=ans[stack1[L1-1]][m->second];
if(action==-10000)return 0;
if(action>=0){
GOTO=-10000;
return 1;
}
if(action<0&&action>-9999){
return 2;
}
if(action==-9999){
return 3;
}
return 0;
}
void solve(){
cout<<endl<<"分析字符串"<<endl;
char c;
while(1){
cout<<endl<<"输入一行字符串并且以#结尾:"<<endl;
memset(analyse,0,sizeof(analyse));
int i=0;
while(scanf(" %c",&c)&&c!='#'){
analyse[i++]=c;
}
step=1;
memset(stack1,0,sizeof(stack1));
memset(stack2,0,sizeof(stack2));
memset(stack3,0,sizeof(stack3));
L1=0,L2=0,L3=0;
stack1[L1++]=0;
stack2[L2++]='#';
stack3[L3++]='#';
for(int j=strlen(analyse)-1;j>=0;j--){
stack3[L3++]=analyse[j];
}
while(1){
int oprt=judge();
if(oprt==0){
cout<<"error!"<<endl;
break;
}
if(oprt==1){
output_stacks();
cout<<"ACTION:";
output_action(action);
cout<<" GOTO:blank"<<endl;
stack1[L1++]=action;
stack2[L2++]=stack3[--L3];
}
if(oprt==2){
output_stacks();
cout<<"ACTION:";
output_action(action);
int ct=0;
for(int j=strlen(S[action*-1])-1;j>=0;j--){
if(S[action*-1][j]!='.')ct++;
if(S[action*-1][j]=='.')break;
}
L1-=ct;
L2-=ct;
stack2[L2++]=S[-1*action][0];
m=M.find(stack2[L2-1]);
GOTO=ans[stack1[L1-1]][m->second];
stack1[L1++]=GOTO;
cout<<" GOTO:"<<GOTO<<endl;
}
if(oprt==3){
output_stacks();
if(L3==1){
cout<<"ACTION:acc!"<<endl;
}
else{
cout<<"error!"<<endl;
}
break;
}
}
}
}
int main(){
init();//初始化
input();//输入
bfs();//核心程序宽度优先搜索生成表格
build_table();
output_table();//输出表格
solve();
return 0;
}
//测试数据
/*
4
abcd
3
EAB
7
S_E
E_aA
E_bB
A_cA
A_d
B_cB
B_d
bccd#
4
abcd
3
EAB
7
S_E
E_aB
E_bA
B_bB
A_aA
B_d
A_c
5
abcde
3
EAB
8
S_E
E_aB
E_bB
B_cA
B_cB
A_dB
A_d
B_e
*/
LR(1)分析法设计与实现
代码优化
#include <iostream>
#include <cstdlib>
#include <string.h>
using namespace std;
int i=1;
int j=0,n=0;
int p;
int m=1;
int Ti=0;
char prog[100];
char ch;
char syn[20],sem[50][3];
void SEM(void)
{
int i,j;
for(i=0;i<50;i++)
for(j=0;j<3;j++)
sem[i][j]='\0';
}
struct quat//四元式结构
{
char result[8];
char ag1[8];
char op;
char ag2[8];
}quad[25],newquad[15];
struct Ni//节点结构
{
int pre[2];
char op;
char bz[25][8];
}N[25];
void newN(void)
{
int l,j;
i++;
for(j=0;j<25;j++)
{
for(l=0;l<8;l++)
{
N[i-1].bz[j][l]='\0';
}
}
for(j=0;j<2;j++)
N[i-1].pre[j]=0;
N[i-1].op='\0';
}
void dagt(void);
void newquat(void);
void fuzhi(void);
//递归语法分析生成中间代码
void E(void);
void T(void);
void F(void);
void pop0(char sz[]);
void push0(char sz[],char x);
void pop1(char sz[50][3]);
void push1(char sz[50][3],char x[3]);
void quat1(void);
void quat0(char w);
void print1(void);
void print2(void);
char *newT(void)
{
char *p;
char m[8];
p=(char *)malloc(8);
Ti++;
itoa(Ti,m,10);
strcpy(p+1,m);
p[0]='t';
return(p);
}
int main()
{
p=0;
syn[0]='#';
SEM();
sem[0][0]='#';
cout<<"请输入表达式："<<endl;
do
{
cin.get(ch);
if(ch != '\n') prog[p++]=ch;
}while(ch!='#');
p=0;
ch=prog[p++];
while(ch!='#')
{
fuzhi();
}
print1();
dagt();
newquat();
print2();
return 0;
}
void fuzhi(void)
{
char temp[3];
temp[0]='\0';
temp[1]='\0';
temp[2]='\0';
if((ch<='z'&&ch>='a')||(ch<='Z'&&ch>='A'))
{
temp[0]=ch;
push1(sem,temp);
ch=prog[p++];
if(ch=='=')
{
push0(syn,ch);
ch=prog[p++];
E();
if(m==0)
{
cout<<"错误1!"<<endl;
system("pause"); /////
return;
}
if(ch==';')
{
ch=prog[p++];
quat1();
}
else
{
cout<<"错误2!"<<endl;
system("pause");
return;
}
}
else
{
cout<<"错误3!"<<endl;
system("pause");
return;
}
}
else
{
cout<<"错误4!"<<endl;
printf("%d",ch);
system("pause");
return;
}
}
//E、T、F是递归下降子程序的语法分析
void E(void)
{
char w;
T();
while(ch=='+'||ch=='-')
{
push0(syn,ch);
w=syn[strlen(syn)-1];
ch=prog[p++];
T();
quat0(w);
}
}
void T(void)
{
char w;
F();
while(ch=='*'||ch=='/')
{
push0(syn,ch);
w=syn[strlen(syn)-1];
ch=prog[p++];
F();
quat0(w);
}
}
void F(void)
{
char temp[3];
temp[0]='\0';
temp[1]='\0';
temp[2]='\0';
if(ch=='(')
{
ch=prog[p++];
E();
if(ch==')')
{
ch=prog[p++];
}
else m=0;
}
else if((ch<='z'&&ch>='a')||(ch<='Z'&&ch>='A')||(ch<='9'&&ch>='0'))
{
temp[0]=ch;
push1(sem,temp);
ch=prog[p++];
}
else m=0;
}
void push0(char sz[],char x)
{
int top;
top=strlen(sz);
sz[top]=x;
top++;
sz[top+1]='\0';
}
void pop0(char sz[])
{
int top;
top=strlen(sz)-1;
sz[top]='\0';
}
void push1(char sz[50][3],char x[3])
{
int top=1;
while(sz[top][0])
top++;
strcpy(sz[top],x);
top++;
sz[top+1][0]='\0';
}
void pop1(char sz[50][3])
{
int top=1;
while(sz[top][0])
top++;
top--;
sz[top][0]='\0';
sz[top][1]='\0';
sz[top][2]='\0';
}
void quat0(char w)
{
int top=1,i;
char *p;
while(sem[top][0])
top++;
strcpy(quad[j].ag1,sem[top-2]);
strcpy(quad[j].ag2,sem[top-1]);
quad[j].op=w;
p=newT();
for(i=0;i<8;i++)
quad[j].result[i]=p[i];
pop1(sem);
top--;
pop1(sem);
top--;
for(i=0;i<3;i++)
sem[top][i]=quad[j].result[i];
sem[top][2]='\0';
j++;
}
void quat1(void)
{
char ag2[8];
int top,i;
top=1;
while(sem[top][0])
top++;
ag2[0]='_';
for(i=1;i<8;i++)
ag2[i]='\0';
strcpy(quad[j].ag1,sem[top-1]);
strcpy(quad[j].ag2,ag2);
quad[j].op='=';
strcpy(quad[j].result,sem[top-2]);
pop0(syn);
pop1(sem);
pop1(sem);
j++;
}
void print1(void)
{
int i;
cout<<"原来的四元组："<<endl;
for(i=0;i<j;i++)
cout<<(i+1)<<"、("<<quad[i].op<<","<<quad[i].ag1<<","<<quad[i].ag2<<","<<quad[i].result<<")"<<endl;
}
void dagt(void)
{
int m,n,top,l,tag=0,tag1=0,tag2=0;
char temp;
for(m=0;m<j;m++)
{
tag=0;
for(n=i;n>0;n--)
for(l=0;l<25;l++)
{
if(strcmp(quad[m].ag1,N[n-1].bz[l])==0)
{
tag=n;
break;
}
}
if(tag!=0)
{
tag1=tag-1;
if('0'<quad[m].ag1[0]&&quad[m].ag1[0]<'9')
goto N3;
else goto N3;
}
else
{
if('0'<quad[m].ag1[0]&&quad[m].ag1[0]<'9')
{
if(quad[m].ag2[0]!='_')
{
if('0'<quad[m].ag2[0]&&quad[m].ag2[0]<'9')
{
quad[m].ag1[0]=quad[m].ag1[0]-'0';
quad[m].ag2[0]=quad[m].ag2[0]-'0';
switch(quad[m].op)
{
case '+':temp=quad[m].ag1[0]+quad[m].ag2[0];break;
case '-':temp=quad[m].ag1[0]-quad[m].ag2[0];break;
case '*':temp=quad[m].ag1[0]*quad[m].ag2[0];break;
case '/':temp=quad[m].ag1[0]/quad[m].ag2[0];break;
default:break;
}
tag=0;
for(n=i;n>0;n--)
for(l=0;l<25;l++)
{
if(strcmp(quad[m].result,N[n-1].bz[l])==0)
{
tag=n;
break;
}
}
if(tag!=0)
continue;
else
{
newN();
N[i-1].bz[0][0]=temp+'0' ;
strcpy(N[i-1].bz[1],quad[m].result);
continue;
}
}
else
{
newN();
tag1=i-1;
strcpy(N[i-1].bz[0],quad[m].ag1);
goto N2;
}
}
else goto N1;
}
else
N1:
{
newN();
strcpy(N[i-1].bz[0],quad[m].ag1);
tag1=i-1;
N3:
if(quad[m].ag2[0]=='_')
{
tag=0;
for(n=i;n>0;n--)
for(l=0;l<25;l++)
{
if(strcmp(quad[m].result,N[n-1].bz[l])==0)
{
tag=n;
top=l;
break;
}
}
if(tag!=0)
{
for(l=top+1;l<25;l++)
{
strcpy(N[tag-1].bz[l-1],N[tag-1].bz[l]);
}
goto N5;
}
else
{
N5:
if(N[i-1].bz[0][1])
{
if(quad[m].result[1])
{
top=0;
while(N[tag1].bz[top][0])
top++;
strcpy(N[tag1].bz[top],quad[m].result);
continue;
}
else
{
temp=N[i-1].bz[0][1];
strcpy(N[i-1].bz[0],quad[m].result);
top=0;
while(N[tag1].bz[top][0])
top++;
N[i-1].bz[top][0]='t';
N[i-1].bz[top][1]=temp;
continue;
}
}
else
{
top=0;
while(N[tag1].bz[top][0])
top++;
strcpy(N[tag1].bz[top],quad[m].result);
continue;
}
}
}
else
N2:
{
tag=0;
for(n=i;n>0;n--)
for(l=0;l<25;l++)
{
if(strcmp(quad[m].ag2,N[n-1].bz[l])==0)
{
tag=n;
break;
}
}
if(tag!=0)
{
tag2=tag-1;
tag=0;
for(n=i;n>0;n--)
if((N[n-1].pre[0]==tag1)&&(N[n-1].pre[1]==tag2))
{
tag=n;
break;
}
if(tag!=0)
{
if(N[tag-1].op==quad[m].op)
{
if(!N[tag-1].bz[0][1])
{
top=1;
while(N[tag-1].bz[top][0])
top++;
strcpy(N[tag-1].bz[top],quad[m].result);
}
else if(!quad[m].result[1])
{
temp=N[tag-1].bz[0][1];
strcpy(N[tag-1].bz[0],quad[m].result);
top=1;
while(N[tag-1].bz[top][0])
top++;
N[tag].bz[top][0]='t';
N[tag].bz[top][1]=temp;
}
else
{
top=1;
while(N[tag-1].bz[top][0])
top++;
strcpy(N[tag-1].bz[top],quad[m].result);
}
continue;
}
else
{
newN();
N[i-1].op=quad[m].op;
strcpy(N[i-1].bz[0],quad[m].result);
N[i-1].pre[0]=tag1;
N[i-1].pre[1]=tag2;
}
continue;
}
else
{
newN();
N[i-1].op=quad[m].op;
strcpy(N[i-1].bz[0],quad[m].result);
N[i-1].pre[0]=tag1;
N[i-1].pre[1]=tag2;
continue;
}
}
else
{
newN();
strcpy(N[i-1].bz[0],quad[m].ag2);
tag2=i-1;
tag=0;
for(n=i;n>0;n--)
for(l=0;l<25;l++)
if(strcmp(quad[m].result,N[n-1].bz[l])==0)
{
tag=n;
top=l;
break;
}
if(tag==0)
{
newN();
strcpy(N[i-1].bz[0],quad[m].result);
N[i-1].op=quad[m].op;
N[i-1].pre[0]=tag1;
N[i-1].pre[1]=tag2;
continue;
}
else
{
for(l=top+1;l<25;l++)
{
strcpy(N[tag-1].bz[l-1],N[tag-1].bz[l]);
}
newN();
strcpy(N[i-1].bz[0],quad[m].result);
N[i-1].op=quad[m].op;
N[i-1].pre[0]=tag1;
N[i-1].pre[1]=tag2;
}
}
}
}
}
}
}
void newquat(void)
{
int l,top;
for(l=1;l<i;l++)
{
if(N[l].pre[1]==0&&N[l].pre[0]==0)
{
if(!N[l].bz[0][1])
{
if(('0'<N[l].bz[0][0])&&(N[l].bz[0][0]<'9'))
continue;
else
{
for(top=1;N[l].bz[top][1];top++)
{
if(!N[l].bz[top][0])
{
strcpy(newquad[n].ag1,N[l].bz[0]);
newquad[n].ag2[0]='_';
newquad[n].op='=';
strcpy(newquad[n].result,N[l].bz[top]);
n++;
}
}
}
}
else continue;
}
else if(N[l].pre[1]!=0||N[l].pre[0]!=0)
{
strcpy(newquad[n].ag1,N[N[l].pre[0]].bz[0]);
strcpy(newquad[n].ag2,N[N[l].pre[1]].bz[0]);
newquad[n].op=N[l].op;
strcpy(newquad[n].result,N[l].bz[0]);
n++;
if(!N[l].bz[0][1])
{
for(top=1;N[l].bz[top][0];top++)
{
if(!N[l].bz[top][1])
{
strcpy(newquad[n].ag1,N[l].bz[0]);
newquad[n].ag2[0]='_';
newquad[n].op='=';
strcpy(newquad[n].result,N[l].bz[top]);
n++;
}
}
}
}
}
}
void print2(void)
{
int i;
cout<<"优化后的代码:"<<endl;
for(i=0;i<n;i++)
cout<<(i+1)<<"、("<<newquad[i].op<<","<<newquad[i].ag1<<","<<newquad[i].ag2<<","<<newquad[i].result<<")"<<endl;
}
请输入表达式：
a=1+2-b;
b=3*5+c;
c=3/1*a;#
In.txt
T0:=3.14
T1:=2*T0
T2:=R+r
A:=T1*T2
B:=A
T3:=2*T0
T4:=R+r
T5:=T3*T4
T6:=R-a[B]
B:=T5*T6
Out.txt
T0:=3.14
T1:=6.28
T3:=6.28
T2:=R+r
T4:=T2
A:=6.28*T2
T5:=A
T6:=R-a[B]
B:=A*T6
#include <cstring>
#include <fstream>
#include <iostream>
#include<stdlib.h>
using namespace std;
struct DagNode
{
int fatherNum; //是否有父节点
bool isSingle; //是否是单分支
bool isLeaf;
bool isVal;
double value;
char opt;
int NodeNum; //该节点的编号
int RChild,LChild; //左右子节点的编号
int flagNum; //依附于该节点的变量数
string flags[20]; //依附于该节点的变量
DagNode()
{
isVal = false;
fatherNum = 0;
flagNum = 0;
isLeaf = false;
isSingle = false;
}
};
struct VarNode
{
string str;
int flagNode;
VarNode()
{
flagNode = 0;
}
};
DagNode *dag[100];
VarNode var[100];
int dagNum,varNum;
ifstream fin;
ofstream fout;
string str1,str2,str3;
char opt;
bool BisNew,CisNew;
void PrintStr(string str)
{
int i,l;
double k;
char s[100];
l = str.length();
if (l>0 && str[0]>=48 && str[0]<=57)
{
for(i=0; i<l; i++)
s[i] = str[i];
s[i] = '\0';
k = atof(s);
fout<<k;
return;
}
for (i=0; i<l; i++)
fout<<str[i];
}
bool isOpt(char ch)
{
switch (ch)
{
case '+': return true;
case '-': return true;
case '*': return true;
case '/': return true;
case '[': return true;
}
return false;
}
double Calc(double a, char op, double b)
{
switch (op)
{
case '+': return a+b;
case '-': return a-b;
case '*': return a*b;
case '/': return a/b;
}
return 0;
}
bool strEqual(string str1,string str2)
{
int i,l;
l = str1.length();
i = str2.length();
if (l!=i) return false;
for (i=0; i<l; i++)
if (str1[i]!=str2[i]) return false;
return true;
}
int findVar(string str)
{
double k;
int i;
char s[100];
string ss;
ss = str;
if (str.length()>0 && str[0]>=48 && str[0]<=57)
{
for(i=0; i<str.length(); i++)
s[i] = str[i];
s[i]='\0';
k = atof(s);
sprintf(s,"%lf",k);
ss="";
for (int i=0; i<strlen(s);i++)
ss+=s[i];
}
for (i=1; i<=varNum; i++)
{
if (strEqual(ss,var[i].str))
return i;
}
return 0;
}
void work4(int n)
{
int a,k;
int i;
char s[100];
a = findVar(str1);
if (a==0)
{
varNum++;
a = varNum;
var[a].str = str1;
var[a].flagNode = n;
dag[n]->flagNum++;
dag[n]->flags[dag[n]->flagNum] = str1;
}
else
{
k = var[a].flagNode;
if (!dag[k]->isLeaf)
{
for (i=1; i<=dag[k]->flagNum; i++)
if (strEqual(str1,dag[k]->flags[i]))
{
for (int j=i+1; j<=dag[k]->flagNum; j++)
dag[k]->flags[j-1] = dag[k]->flags[j];
break;
}
dag[k]->flagNum--;
}
var[a].flagNode = n;
dag[n]->flagNum++;
dag[n]->flags[dag[n]->flagNum] = str1;
}
}
void work32(int b,int c)
{
int i,k1,n,k2;
k1 = var[b].flagNode;
k2 = var[c].flagNode;
n = 0;
for (i=1; i<=dagNum; i++)
if (dag[i]->opt == opt && dag[i]->LChild ==k1 && dag[i]->RChild ==k2)
{
n = i;
break;
}
if (n==0)
{
dagNum++;
n = dagNum;
dag[n] = new DagNode();
dag[n]->LChild = k1;
dag[n]->RChild = k2;
dag[k1]->fatherNum++;
dag[k2]->fatherNum++;
dag[n]->opt = opt;
}
work4(n);
}
void work31(int b)
{
int i,k,n;
k = var[b].flagNode;
n = 0;
for (i=1; i<=dagNum; i++)
if (dag[i]->opt == opt && dag[i]->isSingle && dag[i]->RChild ==k)
{
n = i;
break;
}
if (n==0)
{
dagNum++;
n = dagNum;
dag[n] = new DagNode();
dag[n]->isSingle = true;
dag[n]->RChild = k;
dag[k]->fatherNum++;
dag[n]->opt = opt;
}
work4(n);
}
void work24(int b, int c)
{
double p;
int k;
int i;
char s[100];
string str;
p = Calc(dag[var[b].flagNode]->value,opt,dag[var[c].flagNode]->value);
if (CisNew)
{
varNum--;
delete(dag[dagNum]);
dagNum--;
}
if (BisNew)
{
varNum--;
delete(dag[dagNum]);
dagNum--;
}
sprintf(s,"%lf",p);
str = "";
for (i=0; i<strlen(s); i++)
str+=s[i];
k= findVar(str);
if (k ==0)
{
dagNum++;
varNum++;
k = varNum;
var[k].str = str;
var[k].flagNode = dagNum;
dag[dagNum] = new DagNode();
dag[dagNum]->isVal = true;
dag[dagNum]->value = p;
dag[dagNum]->flags[1] = str;
dag[dagNum]->flagNum = 1;
dag[dagNum]->isLeaf = true;
}
work4(var[k].flagNode);
}
void work23(int b)
{
double p;
int k;
int i;
char s[100];
string str;
p = Calc(0,opt,dag[var[b].flagNode]->value);
if (BisNew)
{
varNum--;
delete(dag[dagNum]);
dagNum--;
}
sprintf(s,"%lf",p);
str = "";
for (i=0; i<strlen(s); i++)
str+=s[i];
k= findVar(str);
if (k ==0)
{
dagNum++;
varNum++;
k = varNum;
var[k].str = str;
var[k].flagNode = dagNum;
dag[dagNum] = new DagNode();
dag[dagNum]->isVal = true;
dag[dagNum]->value = p;
dag[dagNum]->flags[1] = str;
dag[dagNum]->flagNum = 1;
dag[dagNum]->isLeaf = true;
}
work4(var[k].flagNode);
}
void work22(int b, int c)
{
if (dag[var[c].flagNode]->isVal && dag[var[b].flagNode]->isVal)
work24(b,c);
else
work32(b,c);
}
void work21(int b)
{
if (dag[var[b].flagNode]->isVal)
work23(b);
else
work31(b);
}
void work1()
{
string str;
bool isSin;
int i,b,c;
int ListType;
char st[100];
char s[100];
int len;
while(!fin.eof())
{
isSin = true;
fin.getline(st,80);
len = strlen(st);
if (len<1) break;
str = "";
i = 0;
while (st[i]!=':')
{
if (st[i]!=' ')
str += st[i];
i++;
}
str1 = str;
str = "";
i = i+2;
while (!isOpt(st[i])&& i<len)
{
if (st[i]!=' ')
str += st[i];
i++;
}
str2 = str;
if (i<len)
{
isSin = false;
opt = st[i];
if (opt=='[')
len--;
str = "";
i++;
while (i<len)
{
if (st[i]!=' ')
str += st[i];
i++;
}
str3 = str;
if (str2.length() ==0)
ListType = 1;
else
ListType = 2;
}
else
{
ListType = 0;
}
b= findVar(str2);
BisNew = false;
if (b ==0)
{
BisNew = true;
dagNum++;
varNum++;
b = varNum;
var[b].str = str2;
var[b].flagNode = dagNum;
dag[dagNum] = new DagNode();
if (str2[0]>=48 && str2[0]<=57)
{
dag[dagNum]->isVal = true;
for ( i=0; i<str2.length(); i++)
s[i] = str2[i];
s[i] = '\0';
dag[dagNum]->value = atof(s);
}
dag[dagNum]->flags[1] = str2;
dag[dagNum]->flagNum = 1;
dag[dagNum]->isLeaf = true;
}
switch(ListType)
{
case 0: work4(var[b].flagNode);
break;
case 1: work21(b);
break;
case 2:
{
c= findVar(str3);
CisNew = false;
if (c ==0)
{
CisNew = true;
dagNum++;
varNum++;
c = varNum;
var[c].str = str3;
var[c].flagNode = dagNum;
dag[dagNum] = new DagNode();
if (str3[0]>=48 && str3[0]<=57)
{
dag[dagNum]->isVal = true;
for ( i=0; i<str3.length(); i++)
s[i] = str3[i];
s[i] = '\0';
dag[dagNum]->value = atof(s);
}
dag[dagNum]->flags[1] = str3;
dag[dagNum]->flagNum = 1;
dag[dagNum]->isLeaf = true;
}
work22(b,c);
}
}
}
}
int main()
{
int k=0;
char s[100];
int i,j;
string str;
fin.open("In.txt",ios::in);
fout.open("Out.txt",ios::out);
work1();
for (i=1; i<=dagNum; i++)
{
if (dag[i]->flagNum==0 && dag[i]->fatherNum>0)
{
ltoa(k,s,10);
str = "Var";
j = 0;
while (s[j]!='\0')
{
str+=s[j];
j++;
}
dag[i]->flagNum = 1;
dag[i]->flags[1] = str;
k++;
}
}
for (i=1; i<=dagNum; i++)
{
if (dag[i]->isLeaf)
{
if (dag[i]->flagNum>1)
{
for (j=2; j<=dag[i]->flagNum; j++)
{
PrintStr(dag[i]->flags[j]);
fout<<":=";
PrintStr(dag[i]->flags[1]);
fout<<endl;
}
}
}
else
{
PrintStr(dag[i]->flags[1]);
fout<<":=";
if (!dag[i]->isSingle)
PrintStr(dag[dag[i]->LChild]->flags[1]);
fout<<dag[i]->opt;
PrintStr(dag[dag[i]->RChild]->flags[1]);
if (dag[i]->opt=='[')
fout<<']';
fout<<endl;
for (j=2; j<=dag[i]->flagNum; j++)
{
PrintStr(dag[i]->flags[j]);
fout<<":=";
PrintStr(dag[i]->flags[1]);
fout<<endl;
}
}
}
fin.close();
fout.close();
}
支付宝微信支付
镜旅博客-付费阅读
￥5
正在生成订单，请稍候
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
喜欢就支持以下吧
膜拜大佬，谢谢大佬帮我渡过最后一次实验