LR 分析方法程序设计原理与实现技术

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，否则则继续进行规约和移进，不进行结果输出，直至输出接受或出错。