下载文档原格式
1、LR文法(上下文无关)：自左向右扫描，最右推导的逆过程2、LR方法1)思想：在规范规约过程中，一方面记住已移近和规约出的整个符号串，另一方面根据所用的产生式推测出未来可能碰到的输入符号。
2)优点：不其他技术相比，适应范围更广，能力更强，识别效率相当，尤其在自左向右扫描输入串时就能发现其中错误，并能准确指出出错位置。
缺点：若用手工构造分析程序，工作量太大，且容易出错，所以必须使用自劢产生这种分析程序的产生器。
3、产生器作用：⏹应用产生器产生一大类上下文无关文法的LR分析程序⏹对二义性文法或难分析的特殊文法，施加一些限制，使乊能用LR分析。
4、LR分析器：从逻辑上说，LR分析器包括两部分：●总控程序：或称为语法分析程序●分析表●注：后面学习的所有LR分析器的总控制程序都相同，仅仅是他们的分析表丌同。
5、总控制程序的作用：●查分析表：根据分析表的内容做出若干简单劢作，如读头后移，入栈，出栈等。
●注：由于总控制程序很简单，所以产生器的任务就是产生分析表。
6、分析表：一个文法的LR分析器常常对应着若干丌同的分析表，所有分析表都恰好识别文法所差生的所有语句。
LR(0)分析表：分析能力有限，但这是建立其他LR分析法的基础。
LR(1)(规范LR分析表)需要看读头下一个符号，它能力最强，但实现代价过高，分析表尺寸太大。
SLR分析表：简单LR分析表构造法，是一种容易实现又有实用价值的方法，但存在一些文法构造丌出SLR分析表。
LALR分析表向前看LR分析表构造法，也是一种常用方法。
注：实际上，SLR和LALR分别是对LR(0)和规范LR的改进。
7、LR分析法的基本思想在规范规约时，当一串貌似句柄的符号串呈现于栈顶时，LR分析法根据三方面的信息找句柄。
●历史：记录在栈内的符号串移进、规约的历史情况。
●展望：预测句柄乊后可能出现的信息●现实：读头下的符号8、LR分析器一个LR分析器实际上是带有下推栈的确定有限状态的自劢机。
实验四 LR分析方法的设计与实现（8学时）一、实验目的通过LR分析方法的实现，加深对自下而上语法分析方法及语法分析程序自动生成过程的理解。
二、实验要求输入上下文无关文法，对给定的输入串，给出其LR分析过程及正确与否的判断。
三、实验步骤1．参考数据结构typedef struct{/*文法*/char head;//产生式左部符号char b[20];//用于存放产生式int point;int lg;//产生式的长度}regular;typedef struct{int l; //文法数量int m; //vn 数量int n; //vt 数量regular re[20];nfinal vn[20];//非终结符final vt[20];//终结符}condition;condition cd[20];//项目regular first[20];//产生式2. 使用闭包函数（CLOSURE）和转换函数(GO(I,X))构造文法G’的LR(0)的项目集规范族。
计算LR（0）项目集规范族C={I0,I1,...,I n}算法描述如下：Procedure itemsets(G’);Begin C = { CLOSURE ({S’→.S})}RepeatFor C 中每一项目集I和每一文法符号XDo if GO(I,X) 非空且不属于CThen 把 GO(I,X) 放入C中Until C 不再增大End;定义转换函数如下：GO（I，X）= CLOSURE（J）其中：I为包含某一项目集的状态，X为一文法符号，J={A→aX.b|A→a.X b∈I}。
3. 构造LR（0）分析表对于LR（0）文法，我们可以直接从它的项目集规范族C和活前缀识别自动机的状态转换函数GO构造出LR分析表。
算法描述如下：beginif A→α•aβ∈ I k and GO(I k,a) = I j (a∈V T) then置ACTION[k,a] = sj;If A→α•∈ I k then对任意终结符a（包括#）置ACTION[k,a] = rj;If S’→S•∈ I k then置ACTION[k,#] = acc;If GO(I k,A) = I j (A∈V N) then置 GOTO（k,A） = j;else ERROR //出错4. LR分析算法描述对给定的输入串，给出其分析过程及正确与否的判断将S0移进状态栈，#移进符号栈，S为状态栈栈顶状态begina=getsym() //读入第一个符号给awhile(ACTION[S,a]!=acc)If ACTION[S,a]=si thenPUSH i,a(分别进栈)；输出进栈信息a=getsym()；//读入下一个符号给aelse if ACTION[S,a] = rj (第j条产生式为A→β) then输出归约信息将状态栈和符号栈分别弹出|β|项； push（A）;将GOTO[S’,A]移进状态栈（S’为当前栈顶状态）；else error;输出分析结果，接受或出错End5、对给定输入串输出其准确与否的分析过程。
LR分析器一、目的和要求通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。
1、选择最有代表性的语法分析方法，如LL(1) 语法分析程序、算符优先分析程序和LR 分析分析程序，并至少完成两个题目。
2、选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。
⑴实验前的准备按实验的目的和要求，编写语法分析程序，同时考虑相应的数据结构。
⑵调试调试例子应包括符合语法规则的算术表达式，以及分析程序能够判别的若干错例。
⑶输出对于所输入的算术表达式，不论对错，都应有明确的信息告诉外界。
⑷扩充有余力的同学，可适当扩大分析对象。
譬如：①算术表达式中变量名可以是一般标识符，还可含一般常数、数组元素、函数调用等等。
②除算术表达式外，还可扩充分析布尔、字符、位等不同类型的各种表达式。
③加强语法检查，尽量多和确切地指出各种错误。
⑸编写上机实习报告。
二、背景知识※自下而上分析技术－LR(K)方法LR(K)方法是一种自下而上的语法分析方法，是当前最广义的无回溯的“移进- 归约”方法。
它根据栈中的符号串和向前查看的k(k 0)个输入符号，就能唯一确定分析器的动作是移进还是归约，以及用哪个产生式进行归约。
优点：文法适用范围广；识别效率高；查错能力强；可自动构造。
逻辑组成：总控程序＋LR分析表LR分析器的结构：一个LR分析器实际是一个带先进后出存储器（栈）的确定下推自动机，它由一个输入串、一个下推栈和一个带有分析表的总控程序组成。
栈中存放着由“历史”和“展望”材料抽象而来的各种“状态”。
任何时候，栈顶的状态都代表了整个的历史和已推测出的展望。
为了有助于明确归约手续，我们把已归约出的文法符号串也同时放进栈里。
LR分析器的每一动作都由栈顶状态和当前输入符号所唯一确定。
LR分析器模型图分析器的任何一次移动都是根据栈顶状态S m和当前输入符号a i，去查看ACTION表并执行ACTION（S m，a i）规定的动作，直至分析成功或失败。
合肥工业大学计算机与信息学院课程设计课程：编译原理专业班级：计算机科学与技术09-2班学号：姓名：一：设计题目题目： LR分析器总控程序的实现设计内容及要求：对P.101中的文法，按图5.5LR分析表构造LR分析器。
要求程序按P.102例5.7那样，对于输入串i*i+i，输出LR分析器的工作过程。
改进：可以自行输入输入串，能按重新按钮重新开始，外加了一个计时器。
二：设计目的进一步了解了LR分析器的整个工作过程，将LR分析器以图形界面的形式展现了出来，有利加深了对LR分析过程的掌握。
三：实验原理本程序是用windows编的，大体的思想是这样的：通过建立一个符号栈，状态栈，输入栈（结构体类型定义的）分别用来存放符号，状态，输入串，将LR 分析表构造成为一个二维数组table[13][9]，其中0--11表示状态结点，21－－26表示规约标号，-1表示error（出错），12表示acc（接受），在acation函数里面通过i等于多少来判断到底是规约还是移进。
在Main_OnCommand（）函数中通过switch....case..来判断每次及下一步所要执行的操作。
运行的时候，首先要输入一个以#结尾的输入串，然后单击开始——>下一步.....,如果规约成功，则弹出一个规约成功的对话框，否则弹出一个规约失败的对话框。
当然在运行的过程中如果出现什么差错，都可以单击重新开始按钮重新输入输入串重新开始。
四：实验代码#include "stdAfx.h"#include <windows.h>#include <windowsx.h>#include "resource.h"#include "MainDlg.h"char *str2[6]={"E->E+T","E->T","T->T*F","T->F","F->(E)","F->i"};int flag=0;#define MAX 20typedef struct{int stack1[MAX];int top1;}status;typedef struct{char stack2[MAX];int top2;}symbol_instr;char index_char[9]={'i','+','*','(',')','#','E','T','F'};//为二维数数组的纵坐标//LR分析表//0--11表示状态结点，21－－26表示规约标号，//-1表示error（出错），12表示acc（接受）int table[13][9] = {{ 5,-1,-1, 4,-1,-1, 1, 2, 3},\{-1, 6,-1,-1,-1,12,-1,-1,-1},\{-1,22, 7,-1,22,22,-1,-1,-1},\{-1,24,24,-1,24,24,-1,-1,-1},\{ 5,-1,-1, 4,-1,-1, 8, 2, 3},\{-1,26,26,-1,26,26,-1,-1,-1},\{ 5,-1,-1, 4,-1,-1,-1, 9, 3},\{ 5,-1,-1, 4,-1,-1,-1,-1,10},\{-1, 6,-1,-1,11,-1,-1,-1,-1},\{-1,21, 7,-1,21,21,-1,-1,-1},\{-1,23,23,-1,23,23,-1,-1,-1},\{-1,25,25,-1,25,25,-1,-1,-1}};//规约规则struct rule{char x;int y;}r[6]={{'E',3},{'E',1},{'T',3},{'T',1},{'F',3},{'F',1}}; //后面的代表A—>@中@的长度BOOL WINAPI Main_Proc(HWND hWnd, UINT uMsg, WPARAM wParam, LPARAM lParam) {switch(uMsg){HANDLE_MSG(hWnd, WM_INITDIALOG, Main_OnInitDialog);HANDLE_MSG(hWnd, WM_COMMAND, Main_OnCommand);HANDLE_MSG(hWnd,WM_CLOSE, Main_OnClose);}return FALSE;}void init_stack1(HWND hwnd,status *p){if( !p)MessageBox(hwnd,TEXT("出错"),TEXT("警告"),MB_OK|MB_ICONHAND);p->top1 = -1;}void push1(HWND hwnd,status *&p,int x){if(p->top1 < MAX-1){p->top1++;p->stack1[p->top1] = x;}else MessageBox(hwnd,TEXT("出错"),TEXT("警告"),MB_OK|MB_ICONHAND);}int pop1(HWND hwnd,status *p){int x;if(p->top1 != 0){x = p->stack1[p->top1];p->top1--;return x;}else{MessageBox(hwnd,TEXT("状态栈为空"),TEXT("警告"),MB_OK|MB_ICONHAND);//printf("\n状态栈1空!\n");return 0;}}void out_stack(HWND hwnd,status *p){if(p->top1 <0)MessageBox(NULL,TEXT("状态栈为空"),TEXT("警告"),MB_OK|MB_ICONHAND);//printf("\n状态栈3空!\n");int i;TCHAR str[256];for(i=0;i<=p->top1;i++)wsprintf(&str[i],"%d",p->stack1[i]);SetDlgItemText(hwnd,IDC_EDIT1,str);}int get_top1(HWND hwnd,status *p){int x;if(p->top1 != -1){x = p->stack1[p->top1];return x;}else{MessageBox(hwnd,TEXT("状态栈为空"),TEXT("警告"),MB_OK|MB_ICONHAND);//printf("\n状态栈2空!\n");return 0;}}void init_stack2(HWND hwnd,symbol_instr *p){if( !p)MessageBox(hwnd,TEXT("出错"),TEXT("警告"),MB_OK|MB_ICONHAND);p->top2= -1;}void push2(HWND hwnd,symbol_instr *p,char x){if(p->top2 < MAX-1){p->top2++;p->stack2[p->top2] = x;p->stack2[p->top2+1]='\0';}else MessageBox(hwnd,TEXT("出错"),TEXT("警告"),MB_OK|MB_ICONHAND);}char pop2(HWND hwnd,symbol_instr *p){char x;if(p->top2 != -1){x = p->stack2[p->top2];p->top2--;p->stack2[p->top2+1]='\0';return x;}else{MessageBox(hwnd,TEXT("符号栈为空"),TEXT("警告"),MB_OK|MB_ICONHAND);//printf("\n符号栈1空!\n");return 0;}}void out_stack1(HWND hwnd,symbol_instr *p){if(p->top2 <0)MessageBox(hwnd,TEXT("符号栈为空"),TEXT("警告"),MB_OK|MB_ICONHAND);//printf("\n状态栈3空!\n");SetDlgItemText(hwnd,IDC_EDIT2,p->stack2);}void out_stack2(HWND hwnd,symbol_instr *p){if(p->top2 <0)MessageBox(hwnd,TEXT("符号栈为空"),TEXT("警告"),MB_OK|MB_ICONHAND);//printf("\n状态栈3空!\n");SetDlgItemText(hwnd,IDC_EDIT3,p->stack2);}char get_top2(HWND hwnd,symbol_instr *p){char x;if(p->top2 != -1){x = p->stack2[p->top2];return x;}else{MessageBox(hwnd,TEXT("符号栈为空"),TEXT("警告"),MB_OK|MB_ICONHAND);//printf("\n符号栈2空!\n");return 0;}}void print(HWND hwnd,status *status_p,symbol_instr *symbol_p,symbol_instr *instr_p){out_stack(hwnd,status_p); //输出状态栈的内容out_stack1(hwnd,symbol_p); //输出符号栈的内容out_stack2(hwnd,instr_p); //输出输入串}int get_index_char(char i){for(int j=0;j<9;j++){if(index_char[j] == i)return j;}return -1;}int goto_char(HWND hwnd,status *status_p,symbol_instr *instr_p){char x;int y,z;x = get_top2(hwnd,instr_p); //输入栈的内容y = get_top1(hwnd,status_p); //状态栈栈顶内容z = get_index_char(x); //得到i，*等相当于二维数组return table[y][z];}void action(HWND hwnd,status *status_p,symbol_instr *symbol_p,symbol_instr *instr_p){int i,j,x;char a;i = goto_char(hwnd,status_p,instr_p);//规约出错if(i == -1)MessageBox(hwnd,TEXT("规约出错!"),TEXT("结束"),MB_OK|MB_ICONEXCLAMATION);//规约成功if(i == 12){MessageBox(hwnd,TEXT("规约成功!"),TEXT("结束"),MB_OK|MB_ICONEXCLAMATION);flag=1;}//移进动作if(i>=0 && i<=11){push1(hwnd,status_p,i);a = pop2(hwnd,instr_p);push2(hwnd,symbol_p,a);print(hwnd,status_p,symbol_p,instr_p);}//规约动作if(i>=21 && i<=26){x = r[i-21].y;for(j=0;j<x;j++){pop1(hwnd,status_p);pop2(hwnd,symbol_p);}push2(hwnd,instr_p,r[i-21].x);SetDlgItemText(hwnd,IDC_EDIT4,str2[i-21]);}}void CALLBACK TimerProc(HWND hwnd,UINT message,UINT iTimerID,DWORD dwTime) {SYSTEMTIME stLocal;TCHAR buf[256];GetLocalTime(&stLocal);wsprintf(buf,"%d年%d月%d 日%d:%d:%d",stLocal.wYear,stLocal.wMonth,stLocal.wDay,stLocal.wHour,stLocal.wM inute,stLocal.wSecond);SetDlgItemText(hwnd,IDC_EDIT5,buf);}BOOL Main_OnInitDialog(HWND hwnd, HWND hwndFocus, LPARAM lParam){SetTimer(hwnd,0,1000,TimerProc);return TRUE;}status *status_p=new status;symbol_instr *symbol_p=new symbol_instr;symbol_instr *instr_p=new symbol_instr ;void Main_OnCommand(HWND hwnd, int id, HWND hwndCtl, UINT codeNotify){switch(id){case IDC_BUTTON1:{init_stack1(hwnd,status_p); //初始化各栈init_stack2(hwnd,symbol_p);init_stack2(hwnd,instr_p);//压进栈初始元素push1(hwnd,status_p,0);push2(hwnd,symbol_p,'#');char x;TCHAR msg[256];GetDlgItemText(hwnd,IDC_EDIT3,msg,sizeof(msg));unsigned int i;for(i=0;i < strlen(msg);i++)push2(hwnd,symbol_p,msg[i]);//然后由符号栈弹出，压进输入栈while( symbol_p->top2 != 0){x = pop2(hwnd,symbol_p);push2(hwnd,instr_p,x);}print(hwnd,status_p,symbol_p,instr_p);//打印初始分析表*/ }break;case IDC_BUTTON2:{action(hwnd,status_p,symbol_p,instr_p);}break;case IDC_BUTTON3:{SetDlgItemText(hwnd,IDC_EDIT1,TEXT(""));SetDlgItemText(hwnd,IDC_EDIT2,TEXT(""));SetDlgItemText(hwnd,IDC_EDIT3,TEXT(""));SetDlgItemText(hwnd,IDC_EDIT4,TEXT(""));}break;default:break;}}void Main_OnClose(HWND hwnd){EndDialog(hwnd, 0);}四：实验结果（1）当输入i*i+i#时最终弹出规约成功的对话框：（2）当输入ii*i#时，最终会弹出规约出错的对话框如下：。
实验五、LR分析法实验报告计算机与信息技术学院程序功能描述通过设计、编写和构造LR（0）项目集规范簇和LR 分析表、对给定的符号串进行LR 分析的程序，了解构造LR（0）分析表的步骤，对文法的要求，能够从文法G 出发生成LR（0）分析表，并对给定的符号串进行分析。
要求以表格或图形的方式实现。
G[E]:E→aA∣bBA→cA∣dB→cB∣d设计要求：（1）构造LR（0）项目集规范簇；要求输入LR(0)文法时，可以直接输入，也可以读取文件，并能够以表格的形式输出项目集规范簇集识别活前缀的有穷自动机（2）构造LR（0）分析表。
要求要求输入LR(0)文法时，可以直接输入，也可以读取文件；输出项目集规范簇，可以调用前一处理部分的结果，输出为LR(0)分析表（3）LR(0)分析过程【移进、归约、接受、报错】的实现。
要求调用前一部分处理结果的分析表，输入一个符号串，依据LR（0）分析表输出与句子对应的语法树，或直接以表格形式输出分析过程。
主要数据结构描述程序结构描述1.首先要求用户输入规则，并保存，分析出规则的数目，规则里的非终结符号和终结符号等信息，为下一步分析备用。
2.根据产生式构造分析表，首先分析每个状态里有哪些产生式，逐步将状态构造完整，最后的规约状态数应该等于产生式的个数。
3.在构造状态的时候，首先将所有的内容均填为出错情况，在每一步状态转换时可以将移进项目填进action表中，对于最后的规约项目，则再用规约覆盖掉之前填的移进。
4.要求用户输入分析串，并保存在输入序列数组中。
5.每一步根据当前的状态栈栈顶状态和输入符号查分析表，若是移进，则直接将符号和相应的状态添进栈中，否则弹出与产生式右部相同个数的字符和状态，并用剩下的状态和产生式的左部在goto表中进行查找，将非终结符和得到的状态压入两个栈内。
6.无论是规约还是移进都要输出当前三个栈内保存内容的情况。
7.如果碰到acc则输出accept，若碰到error则输出error，否则则继续进行规约和移进，不进行结果输出，直至输出接受或出错。
LR分析程序构造LR分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR分析方法是严格的从左向右扫描，和自底向上的语法分析方法。
1)实验原理LR分析器由三个部分组成：(1)总控程序，也可以称为驱动程序。
对所有的LR分析器总控程序都是相同的。
(2)分析表:分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。
(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。
分析器的动作就是由栈顶状态和当前输入符号所决定。
LR分析器结构：其中:SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。
状态转换表用GOTO[i，X]=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。
ACTION[i，a]规定了栈顶状态为i时遇到输入符号a应执行。
动作有四种可能：(1)移进：action[i，a]= Sj：状态j移入到状态栈，把a移入到文法符号栈，其中i,j表示状态号。
(2)归约：action[i，a]=rk：当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有A-B 的产生式，若B的长度为R(即|B|=R)，则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i为修改指针后的栈顶状态。
(3)接受acc:当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是'#'，则为分析成功。
(4)报错:当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。
2)、实验过程(1):数据结构:动作表（ACTION）和状态转换（GOTO）表用二维数组表示.(2)).使用文法E->E+TE->TT->T*FT->FF->(E)F->i3)程序思路（1）建立LR分析表（2）控制部分：从键盘输入一个表达式符号串；利用LR分析算法进行表达式处理：根据LR分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。
编译原理LR分析法编译原理中的LR分析法是一种自底向上的语法分析方法，用于构建LR语法分析器。
LR分析法将构建一个识别句子的分析树，并且在分析过程中动态构建并操作一种非常重要的数据结构，称为句柄(stack)。
本文将详细介绍LR分析法的原理、算法以及在实际应用中的一些技巧。
1.LR分析法的原理LR分析法是从右向左(Right to Left)扫描输入串，同时把已处理的输入串的右侧部分作为输入串的前缀进行分析的。
它的核心思想是利用句柄来识别输入串中的语法结构，从而构建分析树。
为了实现LR分析法，需要识别和操作两种基本的语法结构：可规约项和可移近项。
可规约项指的是已经识别出的产生式右部，可以用产生式左部进行规约。
可移近项指的是当前正在处理的输入符号以及已处理的输入串的右侧部分。
2.LR分析法的算法LR分析法的算法包括以下几个步骤：步骤1: 构建LR分析表，LR分析表用于指导分析器在每个步骤中的动作。
LR分析表包括两个部分：动作(Action)表和状态(Goto)表。
步骤2: 初始化分析栈(stack)，将初始状态压入栈中。
步骤3:从输入串中读取一个输入符号，并根据该符号和当前状态查找LR分析表中的对应条目。
步骤4:分析表中的条目可能有以下几种情况：- 移进(shift)：将输入符号移入栈中，并将新的状态压入栈中。
- 规约(reduce)：将栈中符合产生式右部的项规约为产生式左部，并将新的状态压入栈中。
- 接受(accept)：分析成功，结束分析过程。
- 错误(error)：分析失败，报告错误。
步骤5:重复步骤3和步骤4，直到接受或报错。
3.LR分析法的应用技巧在实际应用中，为了提高LR分析法的效率和准确性，一般会采用以下几种技巧：-使用LR分析表的压缩表示：分析表中的大部分条目具有相同的默认动作（通常是移进操作），因此可以通过压缩表示来减小分析表的大小。
-使用语法冲突消解策略：当分析表中存在冲突时，可以使用优先级和结合性规则来消解冲突，以确定应该选择的操作。
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)。
实验题目：语法分析程序设计与实现(LR)一．实验内容：编写语法分析程序，实现对算数表达式的语法分析。
要求所分析算数表达式由如下的文法产生。
E->E+T|E-T|TT->T*F|T/F|FF->id|(E)|num二．实现要求：在对输入表达式进行分析的过程中，输出所采用的产生式。
方法3：编写语法分析程序实现自底向上的分析，要求如下：1)构造识别所有或前缀的DFA2)构造LR分析表3)编程实现算法4.3，构造LR分析程序三．程序设计说明1.拓广文法。
加入产生式 S->·E。
2.构造项目集规范族（由于作图能力有限，DFA不在此进行显示）。
该过程中考虑到文法是通过字符串数组存储的，故分析过程是一个字符一个字符进行的，所以如果出现类似num,id多个字符构成一个整体的形式，难以处理，程序中对于这种情况采取只取第一个字符的方式处理，也就是用n代替num,i代替id。
对生成式进行编号后：0. S->E1.E->E+T 4.T->T*F 7.F->i2.E->E-T 5.T->T/F 8.F->(E)3.E->T 6.T->F 9.F->nI0 =closure({S′→·E})={ S′→·E，E→·E+T，E→·E-T，E→·T，T→·T*F，T→·T/F，T→·F，F→·i，F→·(E)，F→·n}从I0出发的转移有I1=go(I0 ,E)=closure({S→E·}, {E→E·+T}，{E→E·-T})={S→E·，E→E·+T，E→E·-T}I2=go(I0 ,T)=closure({E→T·}, { T→T·*F}, {T→T·/F})={ E→T·，T→T·*F，T→T·/F }I3=go(I0 ,F)=closure({T→F ·})={ T→F ·}I5=go( I0,( )= closure({F→(·E)})={ F→(·E), E→·E+T，E→·E-T，E→·T，T→·T*F，T→·T/F，T→·F，F→·i，F→·(E)，F→·n }I6=go(I0,n)= closure({F→n· })={ F→n· }从I1出发的转移有I7=go(I1,+)= closure({E→E+·T })={E→E+·T，T→·T*F，T→·T/F，T→·F，F→·i，F→·(E)，F→·n }I8=go(I1, -)= closure({E→E-·T })={ E→E-·T ，T→·T*F，T→·T/F，T→·F，F→·i，F→·(E)，F→·n }从I2出发的转移有I9=go(I2, *)= closure({T→T*·F })={ T→T*·F，F→·i，F→·(E)，F→·n } I10=go(I2, /)= closure({T→T/·F })={ T→T/·F，F→·i，F→·(E)，F→·n }从I5出发的转移有I11=go(I5, E)= closure({F→(E·)}, { E→E·+T}, {E→E·-T })={F→(E·), E→E·+T, E→E·-T }go(I5, T)=I2 go(I5, i)=I4 go(I5, ( )=I5 go(I5, n)=I6从I7出发的转移有I12=go(I7, T)= closure({E→E+T·}，{T→T·*F}，{T→T·/F })={ E→E+T·，T→T·*F, T→T·/F }go(I7, F)=I3 go(I7, i)=I4 go(I7, ( )=I5 go(I7, n)=I6从I8出发的转移有I13=go(I7, T)= closure({E→E-T·}，{T→T·*F}，{T→T·/F })={ E→E-T·，T→T·*F, T→T·/F }go(I8, F)=I3 go(I8, i)=I4 go(I8, ( )=I5 go(I8, n)=I6从I9出发的转移有I14=go(I9,F)= closure({T→T*F· })={ T→T*F· }go(I9, i)=I4 go(I9, ( )=I5 go(I9, n)=I6从I10出发的转移有I15= go(I10,F)= closure({T→T/F· })go(I10, i)=I4 go(I10, ( )=I5 go(I10, n)=I6 从I11出发的转移有I16= go(I11, ))= closure({F→(E) ·})={F→(E) ·} go(I11, +)=I7 go(I11, - )=I8从I12出发的转移有go(I12, *)=I9 go(I12, / )=I10从I13出发的转移有go(I13, *)=I9 go(I13, / )=I103.构造分析表4. 根据算法4.3，构造LR预测分析程序。
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标志的状态字。
