LR(0)分析法的实现编译原理课程设计

0课程设计成绩总成绩教师签名：《编译原理》课程设计报告LR(0)分析法的实现学院(系):从2007年12月17日到2007年12月29日1 4 4 2通过课程设计进一步理解高级语言在计算机中的执行过程，加深对编译原理中重点算法和编译技术的理解，提高自己的编程能力，培养好的程序设计风格。同时通过某种可视化编程语言的应用，具备初步的Windows环境下2.课程设计的内容及要求4.求出项目集规范族(即所有的状态)。6.给出LR(0)分析表。(1)总控程序，也可称驱动程序。对所有的LR分析器总控程序都是相同的。(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表(ACTION)和状(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。输出带总控程序分析表#3下推栈下推栈2)问题不在于"历史"与“现实",而是如何基于"历史"对未来“展3)一般只是使用简化了的"展望"信息，以便能构造一个可行的分析算6)下推栈内的每个状态都概括了从分析开始到归约阶段的全部“历史”#状态栈栈顶指针符号栈43.4LR分析器的总控程序总控程序的动作是根据当前栈顶状态Sm和读头下符号ai查表决定。分析器的动作就是由栈顶状态和当前输入符号所决定。(2)归约：action[i，a]=r：当在栈顶形成句柄时，则归约为相应的非k栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入3.6LR(0)分析表构造基本思想活前缀5在规范归约的句型中，不含有句柄以后任何符号的前缀称为活前缀。它有两种情况：归态活前缀和非归态活前缀。活前缀的尾部正好是句柄之尾，这时可以进行归约。归约之后又会成为句柄尚未形成，需要继续移进若干符号之后才能形成句柄。3.7构造LR(0)分析表的方法2)由于产生式右部的符号串就是句柄，若这些符号串都已进栈，则表示它已处于归态活前缀，若只有部分进栈，则表示它处于非归态活前缀。要想知道活前缀有多大部分进栈了，可以为每个产生式构造一个自动机，由它的状态来记住当前情况，这时，我们把“状态”称为“项目”。这些自动机的全体就是能识别所有活前缀的有限自动机。预期要归约的句柄是XYZ，但都未进栈预期要归约的句柄是XYZ，仅X进栈预期要归约的句柄是XYZ，仅XY进栈64)有一个唯一的初态和一个唯一的接受态，但有若干个归约态，表示有5)状态反映了识别句柄的情况，即句柄的多大部分已进栈，即知道了历6)手工构造文法的项目集规范3.7.4LR(0)项目集规范簇的自动构造2、定义和构造项目集的闭包}73.7.5LR(0)分析表的构造算法ACTION[k,a]=Sj;即：移进a,并转向Ij状态。2、若项目Aα→·∈Ik,则对任何终结符a(包括语句结束符#),置5、分析表中凡不能用步骤1至4填入信息的空白项，均置上“出错标弹出2*符号s'是现在的符号产生式非终结符号入栈输出产生式弹出2*符号s'是现在的符号产生式非终结符号入栈输出产生式输入容号t足当前输人符号)ip指向下二个输入符号8中的每个项中的每个项XY)非空有LRO项目集的构造否到项自集中abCdEABE9A->cAA->dB->cBB->d下面是你输入的文法G：G[E]:下面是生成的拓广文法G'：G'[E]:LR(0)项目规范族如下：I₇={8}文法的LR(0)分析表状态abCd#EAB0S₂S11243S74RR5bl6R₄R7R₂RR₂RR₂RR₂RR₂R89R₃RR₃R0XX文法开始符号Eab导入文法(I)保存文法(S)添加删除关闭添加删除EAB添加删除Q出非终结符号集合为：{E,A,B}终结符符号集合为：{a,b,c,d}X关闭1步骤栈输入串10#2#a3#ad#44#15并aco图四：生成树2归约的时候应该从状态栈和