LR 分析方法程序设计原理与实现技术1郑杰09274053本实验程序中的一些约定：在工程文件main.h中定义所有函数，和数据结构。

在符号方面，$S定义为拓广文法的新引入的起始符号，$START不能和$S一样，并且，为了方便，在原来的产生式上强行加上这么一条产生式$S $START，这一点在main.c中定义文法可以看出来，并且该产生式加在产生式集的首要位置。

状态栈的设计引用以前程序中的数据结构，但是栈操作在本程序中有所扩展。

下面按照程序编写过程顺序介绍各个模块：一．文法产生式扩展由原来的产生式拓展成为加’.’的文法，并且在这个过程中要引入新的起始符号，但是在程序中并没有在这个过程中这么做，原因是因为在原来的产生式集中已经引入新的符号以及产生式，根据原始产生式集计算所需要存储新的拓展产生式集的所需要的产生式个数，然后动态开辟内存空间，再对每个原始产生式的各个位置加'.'。

在本次程序中用来产生拓展文法产生式集的函数定义如下：PPRO ParseProArray(PPRO lpPriProArr,int iProLen,int *iParsedLen)//参数说明:lpPriProArr:PPRO原始产生式集iProLen:int原始产生式个数iParsedLen：int*;拓展产生式集的个数返回值//返回值:拓展产生式集的首地址二．CLOSURE闭包求取在介绍求一个项目集的闭包前，先介绍程序中存储项目集(状态)的数据结构：typedef struct _ITEM_COLLOECTION{int iCount;//项目集合中的产生式个数int iSeqNumber;//项目集合(状态)的状态号PPRO ProCollection[MAX_ITEM_COUNT];//产生式集合的引用数组struct _ITEM_COLLOECTION * nextCollection;//由于程序中项目集合之间存储组织是单向链表，因此有这个域struct _GO{//GOTO映射数组，byte Symbol;//经历当前符号struct _ITEM_COLLOECTION * DestStatus;//跳转的下一个状态(项目集合)的引用}GO_MAP[SYMBOL_COUNT];//由符号个数来定义这个数组的长度}ITEM_COLL,*PITEM_COLL;1编译原理第五次实验报告．求解一个项目集合的CLOSURE闭包的具体方法是1.对于给定的项目集I,对于I中的的每一个产生式属于2.对于现有的闭包集合中的产生式A-->a.Xb,其中X是非终结符，那么对于文法拓展的产生式X-->.Y均属于CLOSURE(I)。

迭代这个过程直到收敛为止。

程序中沿用之前程序中收敛方式,引入一下函数：int AddPro(PITEM_COLL pColl,PPRO ppro,int *iVar)//这个函数往项目集中加入产生式//iVar的值为在函数成功调用的时候返回加入产生式前后的变化//iVar==0说明这个函数在此次调用中并没有加入新的产生式，即该产生式重复//iVar==1说明加入的产生式为之前不存在的在上述求闭包的过程中进行一次完整的查找遍历时候，每次调用AddPro的时候，若都iVar==0，则说明可以收敛了。

产生CLOSURE闭包的函数定义如下:PITEM_COLL GetClosure(PPRO lpProArray,PITEM_COLL lpSrcColl,int iProLen)//参数说明:lpSrcColl:PPRO ，拓展文法产生式数组//lpSrcColl:PITEM_COLL源状态//iProLen:int//返回值:闭包集三.创建项目集规范族创建项目集规范族的过程也是一个收敛迭代过程，以状态(项目集)为单位，对于每一个符号S，在这个项目集中查找右部形如-->.Sb的产生式，获取其后继项目2,，对于所有满足条件的后继项目所组成的集合，当这个项目集不为空时，再获取其闭包，这个闭包就是项目集合，但是这个项目集合有可能与之前的项目集合重复3，因此不能在没有判断是否重复的情况下加入的项目集规范族。

程序中构建项目集规范族的函数在程序中如下定义：void ConstructItemCollFamily(PITEM_COLL lpCollHeader,PPRO lpProArray,int iProLen,PITEM_COLL lpInitStatus)//lpCollHeader：PITEM_COLL：项目族的链表头//lpProArray:PPRO原始产生式数组//iProLen:int 原始产生式数组长度//lpInitStatus:PITEM_COLL:初始状态函数返回后，以lpCollHeader为首的状态链表中蕴含了能够识别所有活前缀的有穷自动机。

状态变迁隐含在项目集族的每一个项目集中GO_MAP:struct _GO数组域中，数组的长度为2程序中获取后继项目的函数在程序中定义为:PPRO GetSubSeqItem(PPRO lpProArray,int iProLen,PPRO lpCurPro)3程序中判断项目集合产生式相等的函数定义：int BeEqualColl(PITEM_COLL Coll1,PITEM_COLL Coll2);int beEqualPro(PPRO lpPro1,PPRO lpPro2);文法中所有的除了拓广文法起始符号的所有符号。

四．构建LR(0)分析表(状态迁移函数)在程序中，建表的目的是为了提高程序处理速度，但是在本程序中为了处理方便和表中元素统一格式存储，并没有构造一张内存中真实的查找表，取而代之的是一个状态字获取函数，函数返回一个状态字4这个状态字有两个字节构成:状态字节和内容字节，下面是图示：状态字图示:程序中定义如下函数获取状态字：word GetStatusWord(PITEM_COLL lpCollHeader,PPRO lpProArray,int iProLen,byte bCurStatus,byte bSymbol)//参数描述4借鉴Window消息参数构造方式typedef unsigned char byte;typedef unsigned short word;并且定义三个字节重组字的宏和字拆分为字节的宏#define MAKEWORD(highbyte,lowbyte) ((word)((0xff&(highbyte))<<8|(0xff&(lowbyte))))#define HIBYTE(data) ((byte)((data)>>8))#define LOWBYTE(data) ((byte)data)例如:word wd=MAKEWORD(0xff,0x12)那么HIBYTE(wd)==0xff,LOWBYTE(wd)==0x12lpCollHeader：项目集规范族的链表首,DFA的表示lpProArray：原始产生式数组iProLen：产生式数组长度bCurStatus：当前状态bSymbol：遇到的符号**当前状态和符号用来在LR(0)分析表中作为索引查找ACTION或者GOTO元素**但是在程序中没有构造这张表，而是从DFA(项目集族中的)实时查找//返回值说明：由图示中可以看出，返回的状态字类型有五种1.遇到终结符号移进:return MAKEWORD(VS_FLAG,迁移的状态序号);2.遇到非终结符号移进return MAKEWORD(NS_FLAG,迁移的状态序号);3.遇到非终结符规约（规约产生式左部不是拓广文法起始符号遇到'#'）：return MAKEWORD(R_FLAG,规约产生式序号);4.当遇到"#"符号，并且规约产生式左部是拓广文法起始符号：return MAKEWORD(ACC_FLAG,0);5.其余情况:return MAKEWORD(ERR_FLAG,0);五.分析总控程序状态栈：状态栈的数据结构沿用之前程序中的定义，但是在每次试验中添加了新操作: byte Peek(LPSTACK lpStack);这个函数的作用是返回栈顶元素的内容，但是实际上并不做退栈工作。

在程序中只设置一个状态栈，没有设置符号栈下面是驱动程序的伪代码:Push(0);//入展初始状态//inPtr是输入符号指针while(1){StatusWord=GetStatusWord(CurStatus,szInput[inPtr]);switch(HIBYTE(StatusWord)){case VS_FLAG:Push(CurStatus=LOWBYTE(StatusWord));inPtr++;break;case ACC_FLAG:puts("Accept Successfully");return 1;break;case R_FLAG:lpProBuff=lpProArray+LOWBYTE(StatusWord);for(idx_buff=0;lpProBuff->rightTerArr[idx_buff];idx_buff++)Pop ();//以当前规约产生式的右部符号个数做POP操作StatusWord=GetStatusWord(Peek(&StatusStack),lpProBuff->leftNon Ter);//以当前栈顶的状态和规约产生式左部符号if(HIBYTE(StatusWord)!=NS_FLAG){ReportError();;return 0;}//在这种情况下应该标志NS_FLAGPush(CurStatus=LOWBYTE(StatusWord));break;case NS_FLAG:default:ReportError();return 0;}}分析函数的定义如下:int AnalyzeInput(PITEM_COLL lpCollHeader,PPRO lpProArray,int iProLen,byte bInputStr[]);//说明:1.bInputStr是待分析的符号数组，必须以$SHARP结尾2.分析成功返回1，错误返回0示例演示分析：1.项目集规范族和DFA的演示：在main.c中定义文法:定义如下产生式:PRO PrimitiveProArray[]={{$S,$START,0},//Should Exists In Every Grammer,in terms of Extending This Grammer{$E,$a,$A,0},{$E,$b,$B,0},// {$E,$B,0},//Used For Test Production{$A,$c,$A,0},{$A,$d,0},{$B,$c,$B,0},{$B,$d,0}};下面分别对两种情况中间结果进行罗列：不存在红色注释的产生式存在上述上产生拓广文法:(说明:图中的产生式均为main.h中宏定义码，其中$DOT==5,S'==81)0 .81-->5 821 .81-->82 52 .82-->5 1 833 .82-->1 5 834 .82-->1 83 55 .82-->5 2 846 .82-->2 5 847 .82-->2 84 58 .83-->5 3 839 .83-->3 5 8310.83-->3 83 511.83-->5 412.83-->4 513.84-->5 3 8414.84-->3 5 8415.84-->3 84 516.84-->5 417.84-->4 5 拓广文法:0 .81-->5 821 .81-->82 52 .82-->5 1 833 .82-->1 5 834 .82-->1 83 55 .82-->5 2 846 .82-->2 5 847 .82-->2 84 58 .82-->5 849 .82-->84 510.83-->5 3 8311.83-->3 5 8312.83-->3 83 513.83-->5 414.83-->4 515.84-->5 3 8416.84-->3 5 8417.84-->3 84 518.84-->5 419.84-->4 5项目集族和DFA0 .Collection Total Item:3(0)Item Pro:81--> 5 82(1)Item Pro:82--> 5 1 83(2)Item Pro:82--> 5 2 84 [0]Status Transit:--82-->1 0 .Collection Total Item:6(0)Item Pro:81--> 5 82(1)Item Pro:82--> 5 1 83(2)Item Pro:82--> 5 2 84(3)Item Pro:82--> 5 84(4)Item Pro:84--> 5 3 84[3]Status Transit:--1 -->2[4]Status Transit:--2 -->3 1 .Collection Total Item:1(0)Item Pro:81-->82 52 .Collection Total Item:3(0)Item Pro:82--> 1 5 83(1)Item Pro:83--> 5 3 83(2)Item Pro:83--> 5 4[1]Status Transit:--83-->4[5]Status Transit:--3 -->5[6]Status Transit:--4 -->6 3 .Collection Total Item:3(0)Item Pro:82--> 2 5 84(1)Item Pro:84--> 5 3 84(2)Item Pro:84--> 5 4[2]Status Transit:--84-->7[5]Status Transit:--3 -->8[6]Status Transit:--4 -->9 4 .Collection Total Item:1(0)Item Pro:82--> 1 83 5 5 .Collection Total Item:3(0)Item Pro:83--> 3 5 83(1)Item Pro:83--> 5 3 83(2)Item Pro:83--> 5 4[1]Status Transit:--83-->10[5]Status Transit:--3 -->5[6]Status Transit:--4 -->6 6 .Collection Total Item:1(0)Item Pro:83--> 4 57 .Collection Total Item:1(0)Item Pro:82--> 2 84 5 8 .Collection Total Item:3(0)Item Pro:84--> 3 5 84(1)Item Pro:84--> 5 3 84(2)Item Pro:84--> 5 4[2]Status Transit:--84-->11[5]Status Transit:--3 -->8[6]Status Transit:--4 -->9 9 .Collection Total Item:1(0)Item Pro:84--> 4 510 .Collection Total Item:1(0)Item Pro:83--> 3 83 5 11 .Collection Total Item:1(0)Item Pro:84--> 3 84 5 (5)Item Pro:84--> 5 4[0]Status Transit:--82-->1[2]Status Transit:--84-->2[3]Status Transit:--1 -->3[4]Status Transit:--2 -->4[5]Status Transit:--3 -->5[6]Status Transit:--4 -->6 1 .Collection Total Item:1(0)Item Pro:81-->82 52 .Collection Total Item:1(0)Item Pro:82-->84 53 .Collection Total Item:3(0)Item Pro:82--> 1 5 83(1)Item Pro:83--> 5 3 83(2)Item Pro:83--> 5 4[1]Status Transit:--83-->7[5]Status Transit:--3 -->8[6]Status Transit:--4 -->9 4 .Collection Total Item:3(0)Item Pro:82--> 2 5 84(1)Item Pro:84--> 5 3 84(2)Item Pro:84--> 5 4[2]Status Transit:--84-->10[5]Status Transit:--3 -->5[6]Status Transit:--4 -->6 5 .Collection Total Item:3(0)Item Pro:84--> 3 5 84(1)Item Pro:84--> 5 3 84(2)Item Pro:84--> 5 4[2]Status Transit:--84-->11[5]Status Transit:--3 -->5[6]Status Transit:--4 -->6 6 .Collection Total Item:1(0)Item Pro:84--> 4 57 .Collection Total Item:1(0)Item Pro:82--> 1 83 5 8 .Collection Total Item:3(0)Item Pro:83--> 3 5 83(1)Item Pro:83--> 5 3 83(2)Item Pro:83--> 5 4[1]Status Transit:--83-->12[5]Status Transit:--3 -->8[6]Status Transit:--4 -->9 9 .Collection Total Item:1(0)Item Pro:83--> 4 510 .Collection Total Item:1(0)Item Pro:82--> 2 84 5 11 .Collection Total Item:1(0)Item Pro:84--> 3 84 5 12 .Collection Total Item:1(0)Item Pro:83--> 3 83 5说明:1.上述每个单元分别代表一个状态(项目集)2.红色标注的是接收状态3.蓝色标记的是规约状态，可以看出其中项目产生式均是以"."结尾4.其余均为移进项目，状态迁移为:迁移说明:Status Transit:--4 -->9当前状态在遇到符号4(宏定义码)的时候移进并状态迁移到9,由前述可知当前情况下查表返回VS_FLAG标志的状态字。