自动生成LR 〔0〕分析表
口舌生疮怎么办姓名：彦清
一、实验目的
输入：任意的压缩了的上下文无关文法。
输出：相应的LR 〔0〕分析表。
二、实验原理
对于LR 文法，我们可以自动构造相应的LR 分析表。为了构造LR 分析表，我们需要定义一个重要概念——文法的标准句型“活前缀〞。
1X 2…X m 应该构成活前缀，把输入串的剩余局部配上之后即应成为标准句型〔如果整个输入串确实构成一个句子〕。因此，只要输入串的已扫描局部保持可归约成一个活前缀，那就意味着所扫描过的局部没有错误。
假假设一个文法G 的拓广文法G '的活前缀识别自动机中的每个状态〔工程集〕不存在下述情况：〔1〕
既含移进工程又含归约工程；〔2〕含有多个归约工程，那么称G 是一个LR 〔0〕文法。该自动机的状态集合即为该文法的LR 〔0〕工程集标准族。
构造识别文法活前缀DFA 有3
〔1〕根据形式定义求出活前缀的正那么表达式，然后由此正那么表达式构造NFA 再确定为DFA ；
〔2〕求出文法的所有工程，按一定规那么构造识别活前缀的NFA 再确定化为DFA ；
CLOSURE 〕(GO(I,X))构造文法G’的LR(0)DFA 。
εabc ，其前缀有ε，a ，ab ，abc
活前缀与句柄的关系如下：
A →β的右部β已出现在栈顶。
A →β1β2的右部子串β1已出现在栈顶，期待从输入串中看到β2
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=〔V T ，V N ，S ，P 〕是一个上下文无关文法，假设存在一个标准推导S *
rm ⇒αAw rm ⇒αβ1β2w 〔其中A →β1β2∈P 〕，那么称工程A →β1•β2对活前缀γ=αβ1
是有效的，即LR(0) 有效工程。
从直观意义上讲，一个LR(0)工程指明了在分析过程中的某一步我们看到产生式的多大局部被识别，LR(0)
不同的LR(0)工程，反映了分析栈顶的不同情况。我们根据LR(0)工程的作用不同，将其分为四类：
〔1〕归约工程：
表现形式：A→a.
这类LR(0)工程表示句柄a恰好包含在栈中，即当前栈顶的局部内容构成了所期望的句柄，应按A→a进行归约。
〔2〕接受工程：
表现形式：S→a.
其中S(0)工程实际是特殊的归约工程，表示分析栈中内容恰好为a，用S→a 进行归约，那么整个分析成功。
〔3〕移进工程：
表现形式：A→a.βb〔b∈V T〕
这类LR(0)工程表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前级，需将b移进分
析栈。
〔4〕待约工程：
表现形式：A→α.Bβ〔B∈V N〕
这类LR(0)工程表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前缀，应把当前输入字符串中的相应内容先归约到B。
在给出LR(0)工程的定义和分类之后，我们从这些LR(0)工程出发，来构造能识别文法所有前缀的有限自动机。其步骤是：首先构造能识别文法所有活前缀的非确定的有限自动机，再将其确定化和最小化，最终得到所需确实定的有限自动机。
由文法G的LR(0)
如果蜗牛有爱情电视剧全集免费观看S'→A〕的第一个LR(0)工程〔即S'→.A〕为NFA的惟一初态。狐狸列那的故事
(0)工程分别对应NFA的一个状态且LR(0)工程为归约工程的对应状态为终态。
酒色成人〔3〕假设状态i和状态j出自同一文法G的产生式且两个状态LR(0)工程的圆点只相差一个位置，即：
假设i为X→X1X2·…X i-1·X i…X n，j为X→X1X2…X i·X i+1…X n，那么从状态i引一条标记为X i的弧到状态j。
〔4〕假设状态i为待约工程〔设X→α·Aβ〕，那么从状态i引ε弧到所有A→·r的状态。
为了使“接受〞状态易于识别，我们通常将文法G进行拓广。
绿豆排骨汤G'，它包含了整个G，但它引进了一个不出现在G中的非终结符S'，并加进一个新产生式S'→S，以S'→S G'G'是G的拓广文法。
这样，便会有一个仅含工程S'→S的状态，这就是惟一的“接受〞态。
如果I是文法G＇的一个工程集，定义和构造I的闭包CLOSURE(I)如下：
（1）I的工程都在CLOSURE(I)中。
（2）假设A→α.Bβ属于CLOSURE(I)，那么每一形如B→.γ的工程也属于
CLOSURE(I)。
（3）重复〔2〕直到CLOSURE(I)不再扩大。
：
GO〔I，X〕= CLOSURE〔J〕
其中：I为包含某一工程集的状态，XJ={ A→αX .β | A→α.X β∈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 itemts(G’);
Begin C := { CLOSURE ({S’→.S})}
Repeat
For C 中每一工程集IX
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;
el
return fal;
}
};
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 fal;
el
{if(t.inputed == "null")
temp = t.uninputed;
el if(t.uninputed == "null")
temp = t.inputed;
el
一股清香
temp = t.inputed + t.uninputed;
}if(right == temp)
return true;
return fal;
}
}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;
}
