编译原理（九）LR（0）⽂法分析法（算法描述和C++代码实现）
后期DEBUG发现make_t函数和make_go存在问题，于2015年12⽉4⽇更新了代码，见谅
概念梳理
最左推导：每⼀步替换最左边的⾮终结符
最右推导：每⼀步替换最右边的⾮终结符，最右推导称为规范推导
短语：令G是⼀个⽂法，S是⽂法的开始符号，假定αβδ是⽂法G的⼀个句型，如果有
则称 β是相对于⾮终结符A的, 句型αβδ的 短语。
直接短语：令G是⼀个⽂法，S是⽂法的开始符号，假定αβδ是⽂法G的⼀个句型，如果有
在长春
则称 β是相对于⾮终结符A的, 句型αβδ的 直接短语。
注意：短语和直接短语的区别在于第⼆个条件, 直接短语中的第⼆个条件表⽰有⽂法规则 Aβ ，因此，每个直接短语都是某规则右部。
句柄：⼀个句型的最左直接短语称为该句型的 句柄。
生菜句柄特征：
(1) 它是直接短语，即某规则右部。
(2) 它具有最左性。
规范归约：⽂法的最右推导为规范推导，⾃底向上分析是⾃顶向下最右推导的逆过程，叫规范归约
活前缀：指规范句型的⼀个前缀，这种前缀不含句柄之后任何符号。之所以称为活前缀，是因为在右边添加⼀些符号之⾸，就可以使它称为⼀个规范句型。
项⽬：对于⼀个⽂法G，我们⾸先要构造⼀个NFA，它能识别G的所有活前缀。这个NFA的每⼀个状态是下⾯定义的⼀个“项⽬”。 项⽬分类：
归约项⽬
凡圆点在最右的项⽬，如A→α·称为⼀个“归约项⽬”
接受项⽬
献血的条件和标准对⽂法的开始符号S’的归约项⽬，如S’→α·称为“接受”项⽬。
移进项⽬
形如A→α·aβ的项⽬，其中a为终结符，称为“移进”项⽬。
待约项⽬
形如A→α·Bβ的项⽬，其中B为⾮终结符，称为“待约”项⽬。
项⽬规范族：假定I是⽂法G’的任⼀项⽬集，定义和构造I的闭包CLOSURE(I)的办法是：
I的任何项⽬都属于CLOSURE(I)；
若A→α·Bβ属于CLOSURE(I)，那么，对任何关于B的产⽣式B→γ，项⽬B→·γ也属于CLOSURE(I)；
LR(0)⽂法：假如⼀个⽂法G的拓⼴⽂法G’的活前缀识别⾃动机的每个状态（项⽬集）不存在下述情况：既含移进项⽬⼜含归约项⽬。
含多个归约项⽬。
则称G是⼀个LR(0)⽂法。换⾔之，LR(0)⽂法规范族的每个项⽬集不包含任何冲突项⽬。
拓⼴⽂法：假定⽂法G是⼀个以S为开始符号的⽂法，我们构造⼀个⽂法G’，它包含整个G，但它引进了⼀个不出现在G中的⾮终结符S’，并加进⼀个新产⽣式S’→S，⽽这个S’是G’的开始符号。那么我们称G’是G的拓⼴⽂法。
函数GO(I,X)：函数GO(I,X)是⼀个状态转换函数。
第⼀个变元I是⼀个项⽬集，
第⼆个变元X是⼀个⽂法符号。
函数值GO(I,X)定义为GO(I,X)=CLOSURE(J)，其中J={任何形如A→αX·β的项⽬ | A→α·Xβ属于I}
算法描述
项⽬集构造算法
枚举每个规范句型，然后枚举””的位置，获得所有的项⽬
项⽬集规范族构造算法
假定I是⽂法G’的任⼀项⽬集，定义和构造I的闭包CLOSURE(I)的办法是：
致青春电影
I的任何项⽬都属于CLOSURE(I)；
若A→α·Bβ属于CLOSURE(I)，那么，对任何关于B的产⽣式B→γ，项⽬B→·γ也属于CLOSURE(I)；
重复执⾏上述两步骤直⾄CLOSURE(I)不再增⼤为⽌。
Go(I,a)函数构造算法
遍历所有的项⽬，如果任意两个项⽬之间存在边（有向），那么这两个项⽬所在的项⽬规范族之间连上对应的有向边。
LR(0)分析表构造算法
假定项⽬集规范族C={I0,I1,…,In}。令每⼀个项⽬集Ik的下标k作为分析器的状态。分析表的ACTION⼦表和GOTO⼦表可按如下⽅法构造令那个包含项⽬S’→·S的集合Ik的下标k为分析器的初态。
若项⽬A→α·aβ属于Ik且GO(Ik , a)= Ij,a为终结符，置ACTION[k,a]为“把(j,a)移进栈”，简记为“sj”。
若项⽬A→α·属于Ik，对任何终结符a(或结束符#)，置ACTION[k,a]为“⽤产⽣式A→α进⾏归约”，简记为“rj”（假定产⽣式A→α是⽂法G’的第j个产⽣式）。
若项⽬S’→S·属于Ik，则置ACTION[k,#]为“接受”，简记为“acc”。
若GO(Ik , A)= Ij，A为⾮终结符，则置GOTO[k,A]=j。
分析表中凡不能⽤规则1⾄4填⼊信息的空⽩格均填上“报错标志”。
LR(0)分析法的分析过程
遍历输⼊字符串，对于每⼀个字符，获取当前状态栈的顶部的状态值，通过查询action表获取的当前的操作是移进、规约还是接受 如果当前操作是移进，将新的状态放⼊状态栈当中，当移⼊的字符放⼊符号栈中。
如果当前操作是规约，那么将需要规约的部分的状态从状态栈中弹出，将规约后的状态放⼊状态栈，将规约后的左部放⼊符号栈，当前的字符不向下推进
如果接收，则结束
代码实现
#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;
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 ) {
314是什么节日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 fal;
for ( int i = 0 ; i < a.element.size() ; i++ )
if ( element[i] == a.element[i] ) continue;
el return fal;
return true;
}
};
struct Content
{
int type;
int num;
string out;
Content(){ type = -1; }
Content ( int a , int b )
:type(a),num(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 ud[MAX];
离园活动有哪些Content action[MAX][MAX];
int Goto[MAX][MAX];
void make_item ( )
{
memt ( 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.inrt ( 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_t ( )
{
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] );
}
}*/
memt ( has , 0 , sizeof ( has ) );
has[i] = 1;
if ( x != str.length()-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.inrt ( 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;
memt ( 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] );
}
