LR(0)分析表.doc

LR(0)分析表

自动生成LR（0）分析表
姓名：彦清 学号：E10914127
一、实验目的
输入：任意的压缩了的上下文无关文法。
输出：相应的LR（0）分析表。

二、实验原理
对于LR文法，我们可以自动构造相应的LR分析表。为了构造LR分析表，我们需要定义一个重要概念——文法的规范句型“活前缀”。
这种句柄之后不含任何符号的前缀称为活前缀。
在LR分析工作过程中的任何时候，栈里的文法符号（自栈底而上）X1X2…Xm应该构成活前缀，把输入串的剩余部分配上之后即应成为规范句型（如果整个输入串确实构成一个句子）。因此，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。
对于一个文法G，我们可以构造一个有限自动机，它能识别G的所有活前缀，然后把这个自动机转变成LR分析表，按照该LR分析表进行LR分析，就能保证在分析的过程中，如果分析的句子是正确的，栈里的文法符号（自栈底而上）始终构成活前缀。
假若一个文法G的拓广文法的活前缀识别自动机中的每个状态（项目集）不存在下述情况：（1）既含移进项目又含归约项目；（2）含有多个归约项目，则称G是一个LR（0）文法。该自动机的状态集合即为该文法的LR（0）项目集规范族。
构造识别文法活前缀DFA有3种方法：
（1）根据形式定义求出活前缀的正则表达式，然后由此正则表达式构造NFA再确定为DFA；
（2）求出文法的所有项目，按一定规则构造识别活前缀的NFA再确定化为DFA；
（3）使用闭包函数（CLOSURE）和转向函数(GO(I,X))构造文法G’的LR(0)的项目集规范族，再由转换函数建立状态之间的连接关系来得到识别活前缀的DFA。

符号串的前缀是指该符号串的任意首部，包括空串ε。例如，对于符号串abc，其前缀有ε，a，ab，abc。如果输入串没有错误的话，一个规范句型的活前缀是该句型的一个前缀，但它不含句柄之后的任何符号。之所以称为活前缀，是因为在该前缀后联接尚未输入的符号串可以构成一个规范句型。
活前缀与句柄的关系如下：
（1）活前缀已含有句柄的全部符号，表明产生式A→β的右部β已出现在栈顶。
（2）活前缀只含句柄的一部分符号，表明A→β1β2的右部子串β1已出现在栈顶，期待从输入串中看到β2推出的符号。
（3）活前缀不含有句柄的任何符号，此时期望A→β的右部所推出的符号串。
在文法G的每个产生式的右部（候选式）的任何位置上添加一个圆点，所构成的每个产生式称为LR（0）项目。如产生式A® xyz有如下项目：A®.xyz，A®x.yz，A®xy.z，A®xyz.。为刻划分析过程中的文法的每一个产生式的右部符号已有多大一部分被识别（出现在栈顶），可以用这种标有圆点的产生式来确定。
（1）A→β.刻划产生式A→β的右部β已出现在栈顶。
（2）A→β1.β2 刻划A→β1β2的右部子串β1已出现在栈顶，期待从输入串中看到β2推出的符号。
（3）A→.β 刻划没有句柄的任何符号在栈顶，此时期望A→β的右部所推出的符号串。
（4）对于A→ε的LR(0)项目只有A→．。
设文法G=（VT，VN，S，P）是一个上下文无关文法，若存在一个规范推导SAw12w（其中A12P），则称项目A12对活前缀=1是有效的，即LR(0) 有效项目。
从直观意义上讲，一个LR(0)项目指明了在分析过程中的某一步我们看到产生式的多大部分被识别，LR(0)项目中的圆点可看成是分析栈栈顶与输入串的分界线，圆点左边为已进入分析栈的部分，右边是当前输入或继续扫描的符号串。
不同的LR(0)项目，反映了分析栈顶的不同情况。我们根据LR(0)项目的作用不同，将其分为四类：
（1）归约项目：
表现形式：A→a.
这类LR(0)项目表示句柄a恰好包含在栈中，即当前栈顶的部分内容构成了所期望的句柄，应按A→a进行归约。
（2）接受项目：
表现形式：→a.
其中是文法惟一的开始符号。这类LR(0)项目实际是特殊的归约项目，表示分析栈中内容恰好为a，用→a进行归约，则整个分析成功。
（3）移进项目：
表现形式：A→a.（bVT）
这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前级，需将b移进分析栈。
（4）待约项目：
表现形式：A→α.Bβ （BVN）
这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前缀，应把当前输入字符串中的相应内容先归约到B。

在给出LR(0)项目的定义和分类之后，我们从这些LR(0)项目出发，来构造能识别文法所有前缀的有限自动机。其步骤是：首先构造能识别文法所有活前缀的非确定的有限自动机，再将其确定化和最小化，最终得到所需的确定的有限自动机。
由文法G的LR(0)项目构造识别文法G的所有活前缀的非确定有限自动机的方法：
（1）规定含有文法开始符号的产生式（设→A）的第一个LR(0)项目（即→.A）为NFA的惟一初态。
（2）令所有LR(0)项目分别对应NFA的一个状态且LR(0)项目为归约项目的对应状态为终态。
（3）若状态i和状态j出自同一文法G的产生式且两个状态LR(0)项目的圆点只相差一个位置，即：
若i为X→X1X2·…Xi-1·Xi…Xn， j为 X→X1X2…Xi·Xi+1…Xn，则从状态i引一条标记为Xi的弧到状态j。
（4）若状态i为待约项目（设X→α·Aβ），则从状态i引ε弧到所有A→·r的状态。

为了使“接受”状态易于识别，我们通常将文法G进行拓广。
假定文法G是一个以S为开始符号的文法，我们构造一个，它包含了整个G，但它引进了一个不出现在G中的非终结符，并加进一个新产生式→S，以→S为开始符号。那么，我们称是G的拓广文法。
这样，便会有一个仅含项目→S的状态，这就是惟一的“接受”态。
如果I是文法G＇的一个项目集，定义和构造I的闭包CLOSURE(I)如下：
（1） I的项目都在CLOSURE(I)中。
（2） 若A→a.Bb属于CLOSURE(I)，则每一形如B→.g的项目也属于CLOSURE(I)。
（3） 重复（2）直到CLOSURE(I)不再扩大。

定义转换函数如下：
GO（I，X）= CLOSURE（J）
其中：I为包含某一项目集的状态，X为一文法符号，J={ A→aX .b | A→a.X b∈I}。
圆点不在产生式右部最左边的项目称为核，惟一的例外是S′→.S，因此用GOTO（I，X）状态转换函数得到的J为转向后状态闭包项目集的核。
使用闭包函数（CLOSURE）和转换函数(GO(I,X))构造文法G’的LR(0)的项目集规范族，步骤如下：

（1） 置项目S′→.S为初态集的核，然后对核求闭包CLOSURE（{S′→.S}）得到初态的闭包项目集。
（2） 对初态集或其他所构造的项目集应用转换函数GO(I，X)= CLOSURE(J)求出新状态J的闭包项目集。
（3） 重复（2）直到不出现新的项目集为止。
计算LR（0）项目集规范族C={I0，I1 , ... In }的算法伪代码如下：
Procedure itemsets(G’);
Begin C := { CLOSURE ({S’®.S})}
Repeat
For C 中每一项目集I和每一文法符号X
Do if GO(I,X) 非空且不属于C
Then 把 GO(I,X) 放入C中
Until C 不再增大
End;
一个项目集可能包含多种项目，若移进和归约项目同时存在，则称移进-归约冲突，若
归约和归约项目同时存在，则称归约-归约冲突。
三、源程序由正规文法构造正规式
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
#define MAX_PRO_NUM 50
#define MAX_PRO_SET_NUM 20
#define MAX_P_NUM 20
#define MAX_VT_NUM 27
string vn;//非终结符集
string vt;//终结符集，包括#
struct Project
{//项目的数据结构
char left;
string inputed;
string uninputed;
bool operator == (Project cmp)
{
if(left == cmp.left && inputed == cmp.inputed && uninputed == cmp.uninputed)
return true;
else
return false;
}
};
struct Go
{
char input;
int nextProjectSet;
}go[MAX_PRO_SET_NUM][MAX_PRO_NUM];
int goLength[MAX_PRO_SET_NUM] = {0};//goLength[i]是第 i 状态共有多少条箭弧
struct PSet//产生式集合
{char left;//产生式左部
string right;//产生式右部
bool operator ==(Project t)//判断项目是否是由该产生式得到的
{
string temp;
if(left != t.left)
return false;
else
{if(t.inputed == "null")
temp = t.uninputed;
else if(t.uninputed == "null")
temp = t.inputed;
else
temp = t.inputed + t.uninputed;
}if(right == temp)
return true;
return false;
}
}pSet[MAX_P_NUM];
int pSetLength = 0;//产生式个数

class ProjectSet;
struct DFA//识别活前缀的DFA的项目集集合
{
ProjectSet* state[MAX_PRO_SET_NUM];
int stateLength;
}aDFA;
class ProjectSet//项目集
{private:
int projectNum;
Project pro[MAX_PRO_NUM];
int proLength;
int include[MAX_P_NUM];
public:
ProjectSet(Project in)//由一个项目构造项目集闭包
{
projectNum = aDFA.stateLength;
proLength = 1;
for(int i = 0;i < MAX_P_NUM;i++)
include[i] = 0;

pro[0].left = in.left;
pro[0].inputed = in.inputed;
pro[0].uninputed = in.uninputed;

for(int j = 0; j < proLength; j++)
{
char vn = pro[j].uninputed[0];
if(pro[j].uninputed == "null" || vn >= 'a' && vn <= 'z')
continue;
for(int i = 0; i < pSetLength; i++)
{
if(pSet[i].left == vn && include[i] == 0)
{
include[i] = 1;
pro[proLength].left = pSet[i].left;
pro[proLength].inputed = "null";
pro[proLength].uninputed = pSet[i].right;
proLength++;
}
}
}}
int getProjectNum()
{
return projectNum;
}

int getProLength()
{
return proLength;
}

Project getPro(int i)
{
return pro[i];
}
};
string actionTable[MAX_PRO_SET_NUM+1][MAX_VT_NUM];//ACTION表
string gotoTable[MAX_PRO_SET_NUM+1][MAX_VT_NUM];//GOTO表

void input();
int getActionIndex(char t);
int getGotoIndex(char t);
string intToString(int t);

void display()//显示LR(0)分析表
{
cout<<"\t\t\tACTION\t\t\t\tGOTO"<<endl;
cout<<endl;
for(int i = 0;i < aDFA.stateLength+1;i++)
{
if(i > 0)
cout<<i-1<<"\t";
else
cout<<"\t";
for(unsigned j = 0;j < vt.length();j++)
cout<<actionTable[i][j]<<'\t';
for( j = 0;j < vn.length();j++)
cout<<gotoTable[i][j]<<'\t';
cout<<endl;
}
}
int main()
{
input();
for(int i = 0; i < MAX_PRO_SET_NUM; i++)
aDFA.state[i] = NULL;
aDFA.stateLength = 0;

Project start;
start.left = pSet[0].left;
start.inputed = "null";
start.uninputed = pSet[0].right;

aDFA.state[0] = new ProjectSet(start);
aDFA.stateLength++;

int currState = 0;//当前分析的项目集
do{
for(int i = 0;i < aDFA.state[currState]->getProLength();i++)
{
string temp = aDFA.state[currState]->getPro(i).uninputed;
if(temp == "null")//归约项目
continue;
else
{
go[currState][goLength[currState]].input = temp[0];//当前状态currState的第goLength[currState]条箭弧 受uninputed[0]激发
go[currState][goLength[currState]].nextProjectSet = aDFA.stateLength;//默认到达一个新建的状态

Project aProject,t = aDFA.state[currState]->getPro(i);
aProject.left = t.left;
if(t.inputed == "null")
aProject.inputed = t.uninputed[0];
else
aProject.inputed = t.inputed + t.uninputed[0];
if(t.uninputed.length() == 1)
aProject.uninputed = "null";
else
aProject.uninputed = t.uninputed.substr(1,t.uninputed.length());

bool flag = false;
if(aProject == aDFA.state[currState]->getPro(0))//状态到达自身 置一条到达自身的箭弧
{
go[currState][goLength[currState]].nextProjectSet = aDFA.state[currState]->getProjectNum();
goLength[currState]++;
continue;
}
else
{
for(int iter = 0;iter < aDFA.stateLength;iter++)
{
if(aProject == aDFA.state[iter]->getPro(0))//与其他某一状态吻合 置一跳到达该状态的箭弧
{
go[currState][goLength[currState]].nextProjectSet = iter;
goLength[currState]++;
flag = true;
break;
}
}
}
if(flag == false)//均不满足时新建一个状态
{
go[currState][goLength[currState]].nextProjectSet = aDFA.stateLength;
aDFA.state[aDFA.stateLength] = new ProjectSet(aProject);
aDFA.stateLength++;
goLength[currState]++;
}
}
}
currState++;
}while(currState != aDFA.stateLength);
for( i = 0;i < vt.length();i++)
{
actionTable[0][i] = vt[i];
}
for( i = 0;i < vn.length();i++)
gotoTable[0][i] = vn[i];

//以状态号顺序填表
for( i = 0;i < aDFA.stateLength;i++)
{
Project t = aDFA.state[i]->getPro(0);
if(t.uninputed == "null")//是归约项目
{
if(t.left == 'Z' && t.inputed[0] == vn[0] && t.inputed.length() == 1)//接受状态 Z->S.
{actionTable[i+1][vt.length()-1] = "acc";
continue;
}
for(int iter = 0;iter < pSetLength;iter++)//扫描产生式以确定用哪一条产生式归约
{
if(pSet[iter] == aDFA.state[i]->getPro(0))
{
for(unsigned k = 0;k < vt.length();k++)
{
actionTable[i+1][k] = "r" + intToString(iter);
}
}
}
continue;}
for(int j = 0;j < goLength[i];j++)
{
if(go[i][j].input >= 'a' && go[i][j].input <= 'z')//终结符 移进
{
int index = getActionIndex(go[i][j].input);
actionTable[i+1][index] = "S" + intToString(go[i][j].nextProjectSet);
}
else if(go[i][j].input >= 'A' && go[i][j].input <= 'Z')//非终结符 跳转
{
int index = getGotoIndex(go[i][j].input);
gotoTable[i+1][index] = intToString(go[i][j].nextProjectSet);
}}
}
display();
getchar();
return 0;
}void input()
{char line[20];
char file[20];
cout<<"请输入文法导入文件的文件名:";
cin>>file;
getchar();
strcat(file,".txt");
ifstream myFile(file);
int i = 0;
myFile.getline(line,28);
vn = line;

myFile.getline(line,28);
vt = line;
myFile.getline(line,20);
while(line[0] != '\0')
{
pSet[i].left = line[0];
char sub[20];
int k = 3;
while(line[k] != '\0')
{
sub[k-3] = line[k];
k++;}
sub[k-3] = '\0';
pSet[i].right = string(sub);
pSet[++i].left = '\0';
pSetLength++;
myFile.getline(line,20);
}
}int getActionIndex(char t)//给出一个终结符 返回该终结符在ACTION表中是第几列
{
for(unsigned i = 0;i < vt.length();i++)
if(actionTable[0][i][0] == t)
return i;
return -1;
}

int getGotoIndex(char t)//给出一个非终结符 返回该非终结符在GOTO表中是第几列
{
for(unsigned i = 0;i < vn.length();i++)
if(gotoTable[0][i][0] == t)
return i;
return -1;
}

string intToString(int t)//整型转换成字符串类型
{
string temp;
while(t)
{
char array[2] = {'\0'};
array[0] = t%10 + 48;
temp += string(array);
t /= 10;
}
for(unsigned i = 0;i < temp.length()/2;i++)
{
char swap;
swap = temp[i];
temp[i] = temp[temp.length()-i-1];
temp[temp.length()-i-1] = swap;
}
return temp;
}
四、运行截图