第1页共34页lr分析器实验报告目录引言..............................................................1第一章概述....................................................21.1设计题目及内容.............................................21.2设计环境...................................................2第二章设计的基本原理..........................................32.1LR分析器的基本理..........................................32.2LR分析器工作过程算法......................................3第2页共34页第三章程序设计................................................53.1总体方案设计..............................................53.2各模块设计.................................................5第四章程序测试和结论以及心得..................................7参考文献..........................................................7附录程序清单................................................8第一章概述1.1设计题目及内容设计题目:根据LR分析表构造LR分析器内容:第3页共34页已知文法G:(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→(E)(6)F→ILR分析表:状态Action表GOTO表abc#SAB0S21231accept2S7353S7S484R1R1R1R15S66R3R3R3R37R4R4R4R48S9第4页共34页9R2R2R2R2注:sj表示把下一状态j和现行输入符号a移进栈rj表示按第j个产生式进行规约acc表示接受空格表示出错标志,报错根据以上文法和LR分析表,构造LR分析器,并要求输出LR工作过程。1.2设计环境硬件设备:一台PC机软件设备:Windows2000/XPOS,VC++6.0实现语言:C语言第二章设计的基本原理第5页共34页2.1基本原理1.LR方法的基本思想:在规范规约的过程中,一方面记住已移进和规约出的整个符号串,即记住“历史”,另一方面根据所用的产生式推测未来可能碰到的输入符号,即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈的顶端时,我们希望能够根据记载的“历史”和“展望”以及“现实”的输入符号等三个方面的材料,来确定栈顶的符号串是否构成相对某一产生式的句柄。2.LR分析器实质上是一个带先进后出存储器(栈)的确定有限状态自动机。3.LR分析器的每一步工作是由栈顶状态和现行输入符号所唯一决定的。4.为清晰说明LR分析器实现原理和模型:LR分析器的核心部分是一张分析表。这张分析表包括两个部分,一是“动作”(ACTION)表,另一是“状态转换”(GOTO)表。他们都是二维数组。ACTION(s,a)规定了当状态s面临输入符号a时应采取什么动作。GOTO(s,X)规定了状态s面对文法符号X(终结符或非终结符)时下一状态是什么。显然,GOTO(s,X)定义了一个以文法符号为字母表的DFA。第6页共34页每一项ACTION(s,a)所规定的动作不外是下述四种可能之一:(1)移进把(s,a)的下一个转态s’=GOTO(s,X)和输入符号a推进栈,下一输入符号变成现行输入符号。(2)规约指用某一产生式A→β进行规约。假若β的长度为r,规约的动作是A,去除栈顶的r个项,使状态Sm-r变成栈顶状态,然后把(Sm-r,A)的下一状态s’=GOTO(Sm-r,A)和文法符号A推进栈。规约动作不改变现行输入符号。执行规约动作意味着β(=Xm-r+1…Xm)已呈现于栈顶而且是一个相对于A的句柄。(3)接受宣布分析成功,停止分析器的工作。(4)报错发现源程序含有错误,调用出错处理程序。2.2LR分析器工作过程算法描述一个LR分析器的工作过程可看成是栈里的状态序列,已规约串和输入串所构成的三元式的变化过程。分析开始时的初始三元式为(s0,#,a1a2……an#)其中,s0为分析器的初态;#为句子的左括号;a1a2……an为输入串;其后的#为结束符(句子右括号)。分析过程每步的结果可表示为(s0s1……sm,#X1X2……Xmai,ai+1……an#)第7页共34页分析器的下一步动作是由栈顶状态sm和现行输入符号ai所唯一决定的。即,执行ACTION(sm,ai)所规定的动作。经执行每种可能的动作之后,三元式的变化情形是:(1)若ACTION(sm,ai)为移进,且s=GOTO(sm,ai),则三元式变成:(s0s1……sms,#X1X2……Xmai,ai+1……an#)(2)若ACTION(sm,ai)={A→β},则按照产生式A→β进行规约。此时三元式变为(s0s1……sms,#X1X2……XmA,aiai+1……an#)此处s=GOTO(Sm-r,A),r为β的长度,β=Xm-r+1……Xm。(3)若ACTION(sm,ai)为“接受”,则三元式不再变化,变化过程终止,宣布分析成功。(4)若ACTION(sm,ai)为“报错”,则三元式的变化过程终止,报告错误。一个LR分析器的工作过程就是一步一步的变换三元式,直至执行“接受”或“报错”为止。第8页共34页第9页共34页第三章程序设计3.1总体设计方案第10页共34页建模(1)分析表建模:构造一个int型二维数组table[13][9],用于存放LR分析表。并初始化。作者这样规定:0~11表示状态sj,其中0对应s0,1对应s1……21~26表示规约rj,其中21对应r1,22对应r2……12表示“接受”-1表示规约出错,报错(2)栈建模:建立一个int型状态栈,该栈为顺序栈。建立一个char型符号栈和一个char型输入串栈,该栈为顺序栈。(3)规约表达式建模:建立一个rule型结构,成员变量为char型非终结符和int型表示规约第几条表达式。程序设计关键注意环节(1)在输入串(句子)输入的过程中,涉及到一个压栈的问题。但是输入串压入的字符顺序刚好与原理中的字符串模型刚好相反,这样第11页共34页需要先弹出的反而在栈底。为了既要保证字符串输入,又要让输入的字符串存储顺序与输入的字符串相反。采取以下措施:先将输入的字符串压入符号栈symbol中,然后符号栈弹出的字符再压入输入串栈instr中,这样实现了输入串的倒序存储。(2)状态栈status_stack(status_p)和符号栈symbol_instr(symbol_p)输出(遍历)过程均采取自栈底到栈顶的顺序,而输入串栈symbol_instr(instr_p)则是采取自栈顶到栈底的顺序输出。3.2各模块设计栈设计构造一个int型“状态栈”status和一个char型“符号-输入串栈”symbol_instr。该栈包括初始化该栈init_status(),压栈push(),弹栈pop(),取栈顶元素get_top(),自栈底到栈顶遍历元素out_stack1()和自栈顶到栈底遍历元素out_stack2()。LR分析器工作过程算法设计构造一个状态转换函数实现状态转换第12页共34页intgoto_char(status*status_p,symbol_instr*instr_p)构造一个移进--规约函数实现移进规约动作voidaction(status*status_p,symbol_instr*symbol_p,symbol_instr*instr_p)构造一个打印LR分析器的工作过程函数实现输出voidprint(status*status_p,symbol_instr*symbol_p,symbol_instr*instr_p)第13页共34页流程图第14页共34页LR分析器设计流程图附录初始化状态栈,符号栈,输入串栈输入串各字符压栈求下一状态符号ii=goto_char(status_p,instr_p)规约出错!异常中止!i==-1?规约成功!退出i==12?规约动作:1.求出i对应规约规则右部字符串长度x=r[i-21].y2.在符号栈和状态栈中弹出x个字符。然后将该规约规则左部压入输入串栈i0&&i=11移进动作:1.将现状态i压栈push(status_p,i)2.将当前输入串字符压入符号栈a=pop(instr_p)push(symbol_p,a)打印该步工作过程第15页共34页程序源代码一:头文件lr.h//LR分析表#includestdio.h#includestdlib.h//0--11表示状态结点,21--26表示规约标号,//-1表示error(出错),12表示acc(接受)inttable[10][7]={{2,-1,-1,-1,1,-1,-1},\{-1,-1,-1,12,-1,-1,-1},\{-1,7,-1,-1,-1,3,5},\{-1,7,4,-1,-1,-1,8},\{21,21,21,21,-1,-1,-1},\{6,-1,-1,-1,-1,-1,-1},\{23,23,23,23,-1,-1,-1},\{24,24,24,24,-1,-1,-1},\{-1,9,-1,-1,-1,-1,-1},\{22,22,22,22,-1,-1,-1}}//规约规则第16页共34页structrule{charx;inty;}r[6]={{'E',3},{'E',1},{'T',3},{'T',1},{'F',3},{'F',1}};//输入字符charindex_char[9]={'i','+','*','(',')','#','E','T','F'};////获取index_char[9]中元素的位置intget_index_char(chari){for(intj=0;j9;j++){if(index_char[j]==i)returnj;}return-1;}二:头文件status_stack.h#includestdio.h第17页共34页#includestdlib.h#defineMAX20typedefstruct{intstack[MAX];inttop;}status;//初始化栈voidinit_stack(status*p){if(!p)printf(\n初始化状态栈出错!\n);p-top=-1;}//压栈voidpush(status*p,intx){if(p-topMAX-1){第18页共34页p-top++;p-stack[p-top]=x;}elseprintf(\n状态栈溢出!\n);}//弹栈intpop(status*p){intx;if(p-top!=0){x=p-stack[p-top];p-top--;returnx;}else{printf(\n状态栈1空!\n);return0;第19页共34页}}//取栈顶元素intget_top(status*p){intx;if(p-top!=-1){x=p-stack[p-top];returnx;}else{printf(\n状态栈2空!\n);return0;}}//遍历栈元素voidout_stack(status*p)第20页共34页{inti;if(p-top0)printf(\n状态栈3空!\n);for(i=0;i=p-top;i++){printf(%d,p-