资源描述：
《算符优先分析器设计(1).doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、LR分析程序设计1实验目的(1)构造LR分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子；(2)了解LR分析方法是严格的从左向右扫描，和自底向上的语法分析方法。2实验内容和实验要求(1)LR分析器能够构造来识别所有能用上下文无关文法写的程序设计语言的结构。(2)LR分析方法是己知的最一•般的无回溯，移进-归约方法，它能够和其他移进-归约方法一样有效地实现。(3)LR方法能分析的文法类是预测分析法能分析的文法类的真超集。3待分析的语法描述E->vI:TI->I,i
2、iT->r4算法描述4.1LR分析法基本思想
3、LR分析法是一种能够根据分析栈屮的文法符号串(状态)和向右顺序查看第k个输入字符就能够唯一确定LR(k)分析器的动作是移进还是用哪一条产生式归约的分析方法。采用LR(0)分析法进行木次实验，即无需向前查看输入符号就能够确定分析器的动作。4.2实现方法LR(0)分析器由三个部分组成：(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(1)分析表，不同的文法分析表将不同，同一个文法采用的LR分析器不同吋，分析表将不同，分析表又可以分为动作表(ACTION)和状态转换(GOTO)表两个部分，它们都可用二维数组
4、表示。由于它是总控程序的依据，所以在程序的第一部分就已经定义好。(2)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和半前输入符号所决定。(3)LR分析器及吋察觉语法错误，快到自左向右扫描输入的最大可能。为了使一个文法是LR的，只要保证半句柄出现在栈顶吋，自左向右扫描的移进-归约分析器能够及吋识别它便足够了。半句柄出现在栈顶时，LR分析器必须要扫描整个栈就可以知道这一点，栈顶的状态符号包含了所需要的一切信息。如果仅知道栈内的文法符号就能确定栈顶是什么句柄。由于LR分析表的转移函数本质上就是
5、这样的有限自动机，因为，如果这个识别句柄的有限自动机自底向上读栈屮的文法符号的话，它达到的状态正是这吋栈顶的状态符号所表示的状态，所以，LR分析器可以从栈顶的状态确定它需要从栈屮了解的一切。4.3算法分析SP为栈指针,S[i]为状态栈,X[i]为文法符号栈。状态转换表用GOTO[i,X]二j表示，规定当栈顶状态为i,遇到为前文法符号为X时应转向状态j,X为终结符或非终结符。ACTIONEi,s]规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：(1)移进：actionti,a]=Sj：状态j移入到状态栈，把a移入到文法
6、符号栈，其屮i,j表示状态号。(2)归约：action[i,a]=rk：为在栈顶形成句柄吋，则归约为和应的非终结符A,即文法屮有A-B的产生式，若B的长度为R(即
7、B
8、二R),则从状态栈和文法符号栈小自顶向下去掉R个符号，即栈指针SP减去R,并把A移入文法符号栈内，j=GOTO[i,Al移进状态栈，其屮i为修改指针后的栈顶状态。(1)接受acc:半归约到文法符号栈屮只剩文法的开始符号S吋，并且输入符号串已结束即当前输入符是'#'，则为分析成功。(2)报错：为遇到状态栈顶为某一状态下出现不该遇到的文法符号吋，则报错，说明输入端不
9、是该文法能接受的符号串。5总控程序框图6程序清单和程序运行结果程序清单见磁盘程序运行结果如下:1.显示所要分析的文法，并且输入所要分析的句型:c「C:DocumentsandSettingsyukunMyDocumentsfi译实验语法分析计算机0304班33号余琨兴利用LIK0〉方法分析以下文法*E->uI：TI一>I.iI->iT->r输入所要分析的句型〈以井号结東〉:2.输入所要分析的句型(1)若所要分析的字符串不为该文法的句型，出错分析:例若为i—ii#,则出错显示如下:请输入所要分析的句型〈以"号结東〉:
10、•••AA1-11H分析过程分析失Sfc?(2)若正确输入该文法的句型如：vi,i:r#,则分析结果如下:输入所要分析的句型〈以”号结東〉:1I分析过程如下a1步骤!
11、;分析栈1■;<栈顶状态输入符1”剩余输入串I11.：1i
12、1：0:1:iAction[0..U]=s2移进u•111•12.!11
13、I：02:ttu1—S'ActionC2^i]=s4移进i•iI-B13.!1(
14、I：024:ttviIi:ActionC4,iJ=r4用I-〉i:归约goto<2,I>=3■1I1■14.!11I1：023:t
15、tul-!iAction(3^]=s6移进.i-•■i■15.：11
16、1：0236:#ul,Iiaa■Action[6,.i]=s9移逬i•iia!i：rtti16.!11
17、I102369:ttuUi1a!Action[9.iJ=r3用I->I.i；归约goto<2,I>=3
