编译原理构造LR0分析表
代码已经调试通，直接从实验报告复制粘贴来的，可能会有中文编码问题，调成utf-8就行。
【实验名称】 LR（0）分析表的构造
【实验目的】
结合书本上P135面LR(0)分析表构造知识，了解掌握LR（0）分析表构造过程，从构造闭包到构造分析表。为后面LR系列的文法打下基础。
【实验原理】
假设构造出来LR(0)项目规范族为C={I0,I1,IN},其中Ik为项目集名字，k为状态名称。S’->.S的项目的集合的Ik的下标k为分析器初始状态。分析表构造如下
[if !supportLists]（1） [endif]若项目A->a.ab属于Ik并且转换函数GO（Ik,a）=Ij,当a为终结符时，置action[k,a]为Sj,动作含义是将终结符号a移进符号栈，状态j进入状态栈（相当于在状态k时遇a转向状态j）。
[if !supportLists]（2） [endif]若项目A->a.属于Ik,则对任何终结符a与#号置ACTION[k,a]和ACTION[k,#]为rj,j为文法中某个归约产生式的序号。动作含义是用A规约a。并把状态栈指针后移|a|位
[if !supportLists]（3） [endif]若GOTO（Ik,A）=Ij,则置GOTO[k,A]为“j”,其中A为非终结符，表示当前状态是“k”时候遇到文法符号A时应该转向j,因此A移入文法符号栈，j移入状态栈。
[if !supportLists]（4） [endif]若项目“S’->S”属于Ik,应置ACTION[k,#]为acc,表示接受
[if !supportLists]（5） [endif]凡不可用上述方法的，应该报错。
【实验内容】
1.首先要确定是LR（0）文法，排除项目集中不应该含有‘移进-规约’或者‘归约-规约’冲突。这个自己设计一个简单文法就行
2. 从拓展文法之后的开始符开始，先求出闭包之后的项目集，之后遍历项目集找出所有活前缀点之后的非终结符与终结符，找下一个项目集，如果有相同的非终结符，要把原来的项目集放入项目集族中，每次找下一个项目集都要检验项目集是否已存在，直到递归找到所有非终结符的带活前缀文法。在此过程中，检验项目集中是否规约移进同时存在，若存在会报错。同时，会把每个项目集之间的联系记录下来，用于分析表的构建。
【小结或讨论】
这次实验比较困难，需要结合一些习题来熟悉构造过程。还应该和后面的SLR文法，LR1文法，LALR1文法联系起来看，其实LR（0）文法是一个理想化的情况，因此文法构建的就比较简单才能验证。
【实验截图】
文法：
S’->S
S->A
A->aA
A->b
结果是正确的，在第一个产生式“S->A”中接受最后的规约，acc
代码：
#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
#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;
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;
str.erase ( str.begin()+x);
str.insert ( str.begin()+x+1 , CH );
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;
}
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 )
{
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 );
}
//closure
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("");
}
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 , inti , 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 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 );
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() );
bool flag = true;
if ( flag )
go[i][ch] = j;
}
}
}
}
void make_table ( )
{
memset( Goto , -1 , sizeof ( Goto ) );
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;
}
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];
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;
}
int main ( )
{
int n;
char s[MAX];
printf("输入以S为开始符的文法，请输入文法个数：");
while ( ~scanf ( "%d" , &n ) )
{ printf("请输入文法:\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 ) );
}
make_item();
make_set();
make_V();
make_go();
make_table();
}
}
