编译原理LALR分析表构造
代码可以直接运行。如果不能就去notepad中调整一下字符编码。
【实验名称】 LALR预测分析表的构造
【实验目的】
根据书本P148页，LALR预测分析内容，理解LALR（1）和前面LR文法的区别与联系。
【实验原理】
在LALR（1）文法中，引入了一个新的概念，同心集。
同心集是指前面产生式相同，只是后面的超前搜索字符不一样。同心集合并后产生式不变，超前搜索字符变为合并前几个产生式的合集。
LALR（1）与LR（1）的不同之处就是有合并同心集这一操作。其余的实现步骤就要查看LR（1）文法的实现。LR（1）文法与LR（0）文法的不同又是携带了超前搜索字符。超前搜索字符的算法，在书本P145有如下定义
[if !supportLists]1. [endif]假定I是一个项目集合，I的任何项目集合都属于CLOSURE（I）
[if !supportLists]2. [endif]如果有项目A->a.Bp.a属于CLOSURE（I），B->y是文法产生式，p属于终结符集合，b属于First(pa),那么B->.y,b也属于CLOSURE（I）
[if !supportLists]3. [endif]重复第二步，直到CLOSURE（I）不再增大。
【实验内容】
由上面的原理分析可得。从之前的实验‘LR（0）’分析表入手，给每一个产生式带上超前搜索字符。注意，在第一个产生式“S’->S”的超前搜索字符初始化为#。再根据上面的步骤来求出每个产生式的搜索字符。最后合并同心集，把超前搜索字符做合集。那么新的预测分析表和以前的LR（0）不同之处在于，一个终结符对应的下一个状态可能有多个。比如（S5，S7），那么就需要选一个代表一下就OK。
【小结或讨论】
这两次实验都是针对第六章LR家族来做的，一个是最简单的LR（0），一个是最后限制性较强的LALR（1）。一共四个LR家族的分析方法，LR（0）不可以出现“规约-规约”与“规约-移进”冲突，一旦出现就要考虑是否可以用SLR（1）的方法来解决冲突，限定为SLR（1）方法。LR（1）方法加入了超前搜索字符，对于一样的规约式，超前搜索字符不一样，那么就是不同的状态，比前两者更为精确。LALR（1）在LR（1）的基础上，为了简化闭包运算，就引入同心集合并。
这一部分内容很多，题目也很多。运算量感觉很大，有时候理解了，却又记不住方法，需要多加练习，还涉及到离散数学的相关知识。收获很多。
【实验截图】
文件中存放的文法
实验结果：（这个例子举得不好，没有体现合并同心集）
第二个文法：
实验结果：
代码：
#include
<cstdio>
#include
<cstring>
#include
<map>
#include
<vector>
#include
<queue>
#include
<algorithm>
#include
<iostream>
#include
<string>
#include
<stdio.h>
using namespace std;
#define INF 0x3f3f3f3f
struct grammar{
char vn, s[10];
}g[100];
int g_num;
map<char, int> vn_map;
map<char, int> vt_map;
int vn_num, vt_num;
char vn[20], vt[20];
int first[20][20];
struct project{
grammar g;
int k, pre[20];
};
vector<project> closure[100];
int closure_num;
struct Edge{
int u, v;
int next;
char ch;
}edge[1000];
int go[100];
int edge_num;
int belong[100];
int merge_num;
int lalr1_action[100][20], lalr1_goto[100][20];
void read() {
g_num= 0;
int i, j, len, flag;
char ch, str[20];
grammar temp;
while( gets(str) ) {
if( str[0] == '@' )
break;
len= strlen(str);
flag= 0;
if( len < 4 ) flag = 1;
else if( str[0] < 'A' || str[0] > 'Z' || str[1] != '-' || str[2] != '>' )
flag= 1;
else
{
temp.vn = str[0];
for(i = 3; i < len; i++) {
if( str[i] == ' ' ) break;
temp.s[i-3] = str[i];
}
temp.s[i-3] = '\0';
if( i < len )
flag= 1;
}
if( flag ) {
printf("产生式%s不符合文法规则，已忽略。\n", str);
continue ;
}
else {
g[ ++g_num ] = temp;
}
}
if( g_num == 0 ) {
printf("未成功输入产生式\n");
return;
}
printf("共输入%d条产生式\n", g_num);
g[0].vn = '$';
g[0].s[0] = g[1].vn;
g[0].s[1] = '\0';
printf("\n拓广文法:%c->%s\n", g[0].vn, g[0].s);
for(i = 1; i <= g_num; i++) {
printf("\t %c->%s\n", g[i].vn, g[i].s);
}
vn_num= vt_num = 0;
if( vt_map['@'] == 0 ) {
vt_map['@'] = ++vt_num;
vt[vt_num] = '@';
}
for(i = 0; i <= g_num; i++) {
ch= g[i].vn;
if( vn_map[ch] == 0 ) {
vn_map[ch] = ++vn_num;
vn[vn_num] = ch;
}
len= strlen( g[i].s );
for(j = 0; j < len; j++) {
ch= g[i].s[j];
if( ch >= 'A' && ch <= 'Z' ) continue;
if( vt_map[ch] == 0 ) {
vt_map[ch] = ++vt_num;
vt[vt_num] = ch;
}
}
}
if( vt_map['#'] == 0 ) {
vt_map['#'] = ++vt_num;
vt[vt_num] = '#';
}
return;
}
void dfs(char ch,int acc[],int vis[],int val[]) {
int i, j, k, c = vn_map[ch];
if( acc[c] ) {
for(i = 1; i <= vt_num; i++)
val[i] = first[c][i];
return;
}
int value[20];
memset(value,0,sizeof(value));
for(i = 0; i <= g_num; i++) {
if( vis[i] ) continue;
vis[i] = 1;
if( g[i].vn != ch ) continue;
int len = strlen( g[i].s );
for(j = 0; j < len; j++) {
char sh = g[i].s[j];
if( vn_map[sh] ) {
dfs(sh,acc,vis,value);
for(k = 2; k <= vt_num; k++) {
if( value[k] ) val[k] = 1;
}
if( value[1] == 0 ) break;
}
else {
c= vt_map[sh];
val[c] = 1;
break;
}
}
if( j == len ) val[1] = 1;
}
return;
}
void solve_first() {
int acc[20], vis[20], value[20];
int i, j, k;
memset(first,0,sizeof(first));
memset(acc,0,sizeof(acc));
for(i = 1; i <= vn_num; i++) {
if( acc[i] ) continue;
memset(vis,0,sizeof(vis));
memset(value,0,sizeof(value));
dfs(vn[i],acc,vis,value);
for(j = 1; j <= vt_num; j++)
first[i][j] = value[j];
acc[i] = 1;
}
return;
}
int Equal(grammar u,grammar v) {
if( u.vn != v.vn ) return 0;
if( !strcmp(u.s,v.s) ) return 1;
return 0;
}
int Equal(project u,project v) {
if( !Equal(u.g,v.g) ) return 0;
if( u.k != v.k ) return 0;
for(int i = 1; i <= vt_num; i++)
if( u.pre[i] != v.pre[i] ) return 0;
return 1;
}
int Equal(int x,int y) {
int i, j;
if( closure[x].size() != closure[y].size() ) return 0;
for(i = 0; i < closure[x].size(); i++) {
project u= closure[x][i];
for(j = 0; j < closure[y].size(); j++) {
project v= closure[y][j];
if( Equal(u,v) ) break;
}
if( j == closure[y].size() ) break;
}
if( i == closure[x].size() ) return 1;
return 0;
}
project newproject() {
project temp;
memset(temp.pre,0,sizeof(temp.pre));
return temp;
}
int addproject(project temp,int c) {
for(int i = 0; i < closure[c].size(); i++) {
project old= closure[c][i];
if( Equal(old.g,temp.g) && old.k == temp.k ) return i;
}
return -1;
}
int solve_closure(int c){
int i, j, k, l;
for(i = 0; i < closure[c].size(); i++) {
project old= closure[c][i];
int len = strlen( old.g.s );
if( old.k == len ) continue;
char vn = old.g.s[ old.k ];
if( vt_map[vn] ) break;
for(j = 0; j <= g_num; j++) {
if( g[j].vn != vn ) continue;
project temp= newproject();
temp.g = g[j];
temp.k = 0;
for(k = 0; k < strlen( g[j].s ); k++) {
if( g[j].s[k] == '@' ) temp.k++;
else break;
}
char ch = old.g.s[old.k+1];
if( ch == '\0' ) {
for(k = 1; k <= vt_num; k++)
temp.pre[k] = old.pre[k];
}
else if( vn_map[ch] ) {
for(k = 1; k <= vt_num; k++)
temp.pre[k] = first[ vn_map[ch] ][k];
}
else
temp.pre[ vt_map[ch] ] = 1;
int flag = addproject(temp,c);
if( flag == -1 ) closure[c].push_back(temp);
else {
for(k = 1; k <= vt_num; k++)
if( temp.pre[k] ) closure[c][flag].pre[k] = 1;
}
}
}
for(i = 1; i < c; i++) {
if( Equal(i,c) ) return i;
}
return c;
}
void addedge(int u,int v,char ch) {
edge[edge_num].u = u;
edge[edge_num].v = v;
edge[edge_num].ch = ch;
edge[edge_num].next = go[u];
go[u] = edge_num++;
}
void solve_projects() {
project temp= newproject();
closure_num= 0;
temp.g = g[0];
temp.k = 0;
temp.pre[ vt_map['#'] ] = 1;
closure[closure_num+1].clear();
closure[closure_num+1].push_back(temp);
int c = solve_closure(closure_num+1);
if( c == closure_num+1 ) {
closure_num++;
}
int i, j, k;
memset(go,-1,sizeof(go));
edge_num= 0;
for(i = 1; i <= closure_num; i++) {
printf("项目集%d包含:\n", i);
for(j = 0; j < closure[i].size(); j++) {
project old= closure[i][j];
printf("\t%c->", old.g.vn);
for(k = 0; k <= strlen( old.g.s ); k++) {
if( k == old.k ) printf(".");
printf("%c", old.g.s[k]);
}
// printf("\t");
for(k = 1; k <= vt_num; k++)
if( old.pre[k] ) {
printf(","); printf("%c ", vt[k]);}
printf("\n");
}
int vis[100];
memset(vis,0,sizeof(vis));
for(j = 0; j < closure[i].size(); j++) {
if( vis[j] ) continue;
project old= closure[i][j];
int len = strlen(old.g.s);
if( old.k == len ) continue;
closure[ closure_num+1 ].clear();
for(k = j; k < closure[i].size(); k++) {
project oldd= closure[i][k];
if( oldd.g.s[ oldd.k ] == old.g.s[ old.k ] ) {
vis[k] = 1;
project temp= oldd;
temp.k++;
closure[ closure_num+1 ].push_back(temp);
}
}
if( closure[ closure_num+1 ].size() == 0 ) continue;
c= solve_closure(closure_num+1);
if( c == closure_num+1 ) {
closure_num++;
}
addedge(i,c,old.g.s[ old.k ]);
}
}
return;
}
int findgrammar(grammar temp) {
for(int i = 0; i <= g_num; i++) {
if( Equal(temp,g[i]) ) return i;
}
}
int Equalproject(int x,int y) {
if( closure[x].size() != closure[y].size() ) return 0;
int i, j, k;
for(i = 0; i < closure[x].size(); i++) {
project u= closure[x][i];
for(j = 0; j < closure[y].size(); j++) {
project v= closure[y][j];
if( u.k == v.k &&Equal(u.g,v.g) ) break;
}
if( j == closure[y].size() ) return 0;
}
return 1;
}
void project_merge() {
int i, j, k;
merge_num= 0;
int vis[100];
memset(vis,0,sizeof(vis));
for(i = 1; i <= closure_num; i++) {
if( vis[i] ) continue;
belong[i] = ++merge_num;
vis[i] = 1;
for(j = i+1; j <= closure_num; j++) {
if( Equalproject(i,j) ) {
belong[j] = merge_num;
vis[j] = 1;
}
}
}
printf("\n项目集合并:\n");
for(i = 1; i <= merge_num; i++) {
printf("新项目集%d包含项目集:", i);
for(j = 1; j <= closure_num; j++)
if( belong[j] == i ) printf("%d ", j);
printf("\n");
}
}
void solve_lalr1() {
int flag = 0;
memset(lalr1_action,INF,sizeof(lalr1_action));
memset(lalr1_goto,INF,sizeof(lalr1_goto));
int i, j, k;
for(i = 1; i <= closure_num; i++) {
for(j = 0; j < closure[i].size(); j++) {
project old= closure[i][j];
char ch = old.g.s[ old.k ];
int c = findgrammar(old.g);
if( ch == '\0' ) {
for(k = 1; k <= vt_num; k++) {
if( old.pre[k] ) {
if( lalr1_action[ belong[i] ][k] == INF || lalr1_action[ belong[i] ][k] == c )
lalr1_action[ belong[i] ][k] = c;
else flag = 1;
}
}
}
}
for(j = go[i]; j != -1; j = edge[j].next) {
int u = belong[edge[j].u], v = belong[edge[j].v];
char ch = edge[j].ch;
if( vn_map[ch] ) {
if( lalr1_goto[u][ vn_map[ch] ] == INF || lalr1_goto[u][ vn_map[ch] ] == -v )
lalr1_goto[u][ vn_map[ch] ] = -v;
else flag = 1;
}
else {
if( lalr1_action[u][ vt_map[ch] ] == INF || lalr1_action[u][ vt_map[ch] ] == -v )
lalr1_action[u][ vt_map[ch] ] = -v;
else flag = 1;
}
}
}
if( flag ) {
printf("出现冲突，该文法不是LALR(1)文法\n");
return;
}
printf("\nLALR(1)分析表：\n");
printf("状态\t");
for(i = 1; i <= vt_num; i++)
printf("%c\t", vt[i]);
for(i = 1; i <= vn_num; i++)
printf("%c\t", vn[i]);
printf("\n");
for(i = 1; i <= merge_num; i++) {
printf("%d\t", i);
for(j = 1; j <= vt_num; j++) {
k= lalr1_action[i][j];
if( k == INF ) printf("\t");
else if( k < 0 ) printf("S%d\t", -k);
else printf("r%d\t", k);
}
for(j = 1; j <= vn_num; j++) {
k= lalr1_goto[i][j];
if( k == INF ) printf("\t");
else if( k < 0 ) printf("%d\t", -k);
else printf("r%d\t", k);
}
printf("\n");
}
return ;
}
int main() {
freopen("LALR(1).txt","r",stdin);
read();
solve_first();
solve_projects();
project_merge();
solve_lalr1();
return 0;
}
