代碼已經(jīng)調(diào)試通刹帕,直接從實(shí)驗(yàn)報(bào)告復(fù)制粘貼來(lái)的,可能會(huì)有中文編碼問(wèn)題库物,調(diào)成utf-8就行侨核。
【實(shí)驗(yàn)名稱】?? ???????????LR(0)分析表的構(gòu)造????????? ????
【實(shí)驗(yàn)?zāi)康摹?/p>
?結(jié)合書本上P135面LR(0)分析表構(gòu)造知識(shí),了解掌握LR(0)分析表構(gòu)造過(guò)程祈惶,從構(gòu)造閉包到構(gòu)造分析表雕旨。為后面LR系列的文法打下基礎(chǔ)扮匠。
【實(shí)驗(yàn)原理】
?假設(shè)構(gòu)造出來(lái)LR(0)項(xiàng)目規(guī)范族為C={I0,I1,IN},其中Ik為項(xiàng)目集名字,k為狀態(tài)名稱奸腺。S’->.S的項(xiàng)目的集合的Ik的下標(biāo)k為分析器初始狀態(tài)餐禁。分析表構(gòu)造如下
[if !supportLists](1)?[endif]若項(xiàng)目A->a.ab屬于Ik并且轉(zhuǎn)換函數(shù)GO(Ik,a)=Ij,當(dāng)a為終結(jié)符時(shí),置action[k,a]為Sj,動(dòng)作含義是將終結(jié)符號(hào)a移進(jìn)符號(hào)棧突照,狀態(tài)j進(jìn)入狀態(tài)棧(相當(dāng)于在狀態(tài)k時(shí)遇a轉(zhuǎn)向狀態(tài)j)帮非。
[if !supportLists](2)?[endif]若項(xiàng)目A->a.屬于Ik,則對(duì)任何終結(jié)符a與#號(hào)置ACTION[k,a]和ACTION[k,#]為rj,j為文法中某個(gè)歸約產(chǎn)生式的序號(hào)。動(dòng)作含義是用A規(guī)約a讹蘑。并把狀態(tài)棧指針后移|a|位
[if !supportLists](3)?[endif]若GOTO(Ik,A)=Ij,則置GOTO[k,A]為“j”,其中A為非終結(jié)符末盔,表示當(dāng)前狀態(tài)是“k”時(shí)候遇到文法符號(hào)A時(shí)應(yīng)該轉(zhuǎn)向j,因此A移入文法符號(hào)棧,j移入狀態(tài)棧座慰。
[if !supportLists](4)?[endif]若項(xiàng)目“S’->S”屬于Ik,應(yīng)置ACTION[k,#]為acc,表示接受
[if !supportLists](5)?[endif]凡不可用上述方法的陨舱,應(yīng)該報(bào)錯(cuò)。
【實(shí)驗(yàn)內(nèi)容】
1.首先要確定是LR(0)文法版仔,排除項(xiàng)目集中不應(yīng)該含有‘移進(jìn)-規(guī)約’或者‘歸約-規(guī)約’沖突游盲。這個(gè)自己設(shè)計(jì)一個(gè)簡(jiǎn)單文法就行
2. 從拓展文法之后的開始符開始,先求出閉包之后的項(xiàng)目集蛮粮,之后遍歷項(xiàng)目集找出所有活前綴點(diǎn)之后的非終結(jié)符與終結(jié)符益缎,找下一個(gè)項(xiàng)目集,如果有相同的非終結(jié)符然想,要把原來(lái)的項(xiàng)目集放入項(xiàng)目集族中莺奔,每次找下一個(gè)項(xiàng)目集都要檢驗(yàn)項(xiàng)目集是否已存在,直到遞歸找到所有非終結(jié)符的帶活前綴文法变泄。在此過(guò)程中令哟,檢驗(yàn)項(xiàng)目集中是否規(guī)約移進(jìn)同時(shí)存在,若存在會(huì)報(bào)錯(cuò)妨蛹。同時(shí)屏富,會(huì)把每個(gè)項(xiàng)目集之間的聯(lián)系記錄下來(lái),用于分析表的構(gòu)建蛙卤。
【小結(jié)或討論】
這次實(shí)驗(yàn)比較困難狠半,需要結(jié)合一些習(xí)題來(lái)熟悉構(gòu)造過(guò)程。還應(yīng)該和后面的SLR文法表窘,LR1文法典予,LALR1文法聯(lián)系起來(lái)看甜滨,其實(shí)LR(0)文法是一個(gè)理想化的情況乐严,因此文法構(gòu)建的就比較簡(jiǎn)單才能驗(yàn)證。
【實(shí)驗(yàn)截圖】
文法:
S’->S
S->A
A->aA
A->b
結(jié)果是正確的衣摩,在第一個(gè)產(chǎn)生式“S->A”中接受最后的規(guī)約昂验,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為開始符的文法捂敌,請(qǐng)輸入文法個(gè)數(shù):");
??? while ( ~scanf ( "%d" , &n ) )
??? {??? printf("請(qǐng)輸入文法:\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();
??? }
}