编译原理课程设计--算术表达式的LR分析过程

武汉理工大学华夏学院课 程 设 计课程名称 编译方法课程设计题目算术表达式的LR分析过程专 班 学 姓 成业计算机应用级1071班号10210407107名蒋梦琴绩指导教师 何九周 段学东2009 年 6 月 29 日目录课程设计任务书31 设计目的 42 设计要求 43 设计内容 431 设计原则432 设计的题目433 在程序中表示文法5331 文法的输入与读取5332 文法的拓展5333 文法的保存格式5334SLR(1)文法的定义5335 SLR(1)_Action 表的构造6336SLR(1)_GoTo表的构造6337 程序算法的设计7124 上机调试 134.1 测试结果135 心得体会 146 参考文献14课程设计封底15课程设计任务书设计题目：算术表达式的 LR 分析过程设计目的1. 巩固和加深课堂所学知识；2. 学习掌握一般的软硬件的设计方法和查阅、运用资料的能力；3. 掌握高级语言词法分析、语义分析、语法分析方法；4. 运用高级语言编写质量高、风格好的应用程序。设计任务 （在规定的时间内完成下列任务）1. 写出符合该算术表达式的的文法和属性文法描述；2. 按照算术表达式的LR分析过程给出分析方法的思想设计算术表达式 文法；3. 完成算数表达式的LR分析的程序设计，用SLR （1）分析法实现对 算术表达式的分析；4. 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析 程序。时间安排消化资料、系统调查1 天系统分析、总体设计，实施计划、撰写报告3天演示、验收1 天具体要求1. 明确课程设计的目的和重要性，认真领会课程设计的题目，读懂课程设计指 导书的要求，学会设计的基本方法与步骤，学会如何运用前修知识与收集、 归纳相关资料解决具体问题的方法。严格要求自己，要独立思考，按时、独 立完成课程设计任务。2. 设计报告：要求层次清楚、整洁规范、不得相互抄袭，凡正文内容有整段完 全相同者一律以抄袭论处。设计报告正文字数不少于0.2万字（不包括附 录）。包含内容：设计题目。目录。正文：包括引言、需求分析、总 体设计及开发工具的选择，设计原则（给出语法分析方法及中间代码形式的 描述、文法和属性文法的设计），数据结构与模块说明（功能与流程图）、详 细的算法设计、软件调试、软件的测试方法和结果、有关技术的讨论、收获 与体会等。结束语。参考文献（按公开发表的规范书写）。附录：软 件清单（或者附盘）。3. 软件系统：界面友好，操作简单；交付的软件有必要的安装、使用说明。指 导 教师签 名：1勺孤/第2009年6月28日教研室主任（或责任教师）签名：2009 年 6 月 28 日算术表达式的 LR 分析过程1.设计目的课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相 辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题 要复杂，也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要 求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容， 选择合适的数据逻辑结构表示问题，然后编制算法和程序完成设计要求，从 而进一步培养学生独立思考问题、分析问题、解决实际问题的动手能力。通过设计调试词法分析程序，实现从源程序中分出各种单词的方法；加 深对课堂教学的理解；提高词法分析方法的实践能力。2设计要求明确课程设计的目的和重要性，认真领会课程设计的题目，读懂课程 设计指导书的要求，学会设计的基本方法与步骤，学会如何运用前修知识与 收集、归纳相关资料解决具体问题的方法。严格要求自己，要独立思考，按 时、独立完成课程设计任务。深入理解所学的编译原理相关知识，按照软件工程的设计方法进 行简要的分析与概要设计，进行总体设计，详细设计、系统实施、调试。运 用程序设计语言实现算法，编写相关程序。使用Visual C+编写程序，并 上机调试，确保程序能运行正确。学会正确运用语法规则，并能应用优先关系和结合性解决二义性和冲 突问题，有效而正确的利用各种分析方法和思想，合理使用出错处理程序， 上机调试通过。最后撰写课程设计报告。3.设计内容3.1 设计原则由于大多数适用的程序设计语言的文法不能满足LR(O)文法的条件，即 使是描述一个实数变量说明这样简单的文法也不一定是LR(0)文法。现举实型变量说明文法为例：V实型变量说明-realV标识符表V标识符表标识符表，iV标识符表i3.2 设计的题目算术表达式的文法：E T E +T | E -T | TT T T * F | T / F | FF T i |(E)设计算术表达式文法，用SLR (1)分析法实现对算术表达式的分析，给出一个 具体句子的分析过程。3.3 在程序中表示文法3.3.1 文法的输入和读取为了程序读取的方便，非/终结符相互间以空格分开。这里应该输入：E T E +T | E -T | TT T T * F | T / F | FF T i |(E)3.3.2 文法的拓展为了在 LR 分析时能够指示分析器正确停止并接受输入，一般在所有输入文 法前加上一个新的产生式，以上面文法为例，我们要保存的文法应该是如此： E T EE TE +T E TE- TE TTT T T* F T TT/ FT T FF T i F T(E)3.3.3 文法的保存格式设计一个类Grammar来对文法进行各种处理。每一个项是一个2元组，记录 了终结符，和产生式右部。其中非终结符可以用字符串(string )类型表示，产生 式右部可用字符串数组( vector )表示。而在保存的同时又可记录下文法 的所有非终结符(因为文法的产生式左部会出现所有的非终结符)，然后再对 已经记录的文法的产生式右部再扫描一遍，记录下所有的终结符。在本程序中，我虽然记录了原始的符号串，但是在具体过程处理时使用的 是符号串对应的下标来进行的，因此再对原始形式的文法再扫描一遍，生成对 应的以下标形式保存的文法。同时我对终结符号和非终结符号的保存位于不同 的数组中，于是下标就会产生冲突，我采用方式是建立一个下标数据结构 Index 来保存下标:struct Indexintindex;/ 非终结符或者终结符的下标boolteminal;/ 为真表示该下标保存的是终结符boolis_nonteminal();/ 返回 ! terminal3.3.4 SLR (1)文法的定义(1) 若状态s包含了格式A -a.Xb的任意项目，其中X是一个终结符，且X 是输入串中的下一个记号，则动作将当前的输入记号移进到栈中，且被压入到 栈中的新状态是包含了项目A -aX.b的状态。(2) 若状态s包含了完整项目A -g.,则输入串中的下一个记号是在Follow (A)中，所以动作是用规则A fg归约。用规则S¢ S归约与接受等价， 其中 S 是开始状态；只有当下一个输入记号是$时，这才会发生。在所有的其 他情况中，新状态都是如下计算的：删除串a和所有它的来自分析栈中的对应 状态。相对应地， DFA 回到 a 开始构造的状态。通过构造，这个状态必须包括 格式B fg. Ab的一个项目。将A压入到栈中，并将包含了项目B faA.b的 状态压入。(3) 若下一个输入记号都不是上面两种情况所提到的，则声明一个错误。若上 述的SLR(l)分析规则并不导致二义性，则文法为SLR(l)文法(SLR(l) grammar) 。SLR( 1)文法的投影函数1定义如下:1: StateSet(VTu #)f21 (S,a) =Reduce j|BfS,aFollow(B),BfPu (if存在XfaS且aVT then Shift)如果LRSM0中的每个状态S，对任意a VT，使得|1(S,a)|1，则称相应文法为SLR( 1)文法。3.3.5 SLR(1)_Action 表的构造若 1(S,#) = Shif t Ac tion( S, # )=Accep t若 1(S,a)二Shift 且 a # Action( S, a)二Shift若 1(S,a)=Reduce j Action( S, a) =Reduce j若 1(S,a)= Action( S, a) = Error3.3.6 SLR(1)_GoTo 表的构造GoTo( S, X) = S ， 当 LRSM0 中有 S SGoTo( S, X) = error，否则合并的SLR( 1)分析表，合并方法：Action ( S, a) = Shift i ,当 Act ion(S, a)= Shift 且 GoTo(S,a)=SiGoTo ( S, X) = Si ,当 GoTo(S,X)=Si 且 X VN3.3.8 程序算法设计#include#includechar *ac tion126 = S5#，NULL,NULL,S4#，NULL,NULL,/* ACTION 表*/NULL,S6#,NULL,NULL,NULL,acc,NULL,r2#,S7#, NULL,r2#,r2#,NULL,r4#,r4#, NULL,r4#,r4#,S5#,NULL,NULL, S4#,NULL,NULL,NULL,r6#,r6#, NULL,r6#,r6#,S5#,NULL,NULL, S4#,NULL,NULL,S5#,NULL,NULL, S4#,NULL,NULL,NULL,S6#,NULL, NULL,S11#,NULL,NULL,r1#,S7#, NULL,r1#,r1#,NULL,r3#,r3#, NULL,r3#,r3#,NULL,r5#,r5#, NULL,r5#,r5#;int goto1123 = 1,2,3,/*QOTO 表*/0,0,0, 0,0,0,0,0,0,8,2,3,0,0,0,0,9,3,0,0,10,0,0,0,0,0,0,0,0,0,0,0,0;char vt6=i,+,*,(,),#;/*存放终结符*/char vn3=E,T,F;/*存放非终结符*/char*LR7=M-E#,E-E+T#,E-T#,T-T*F#,T-F#,F-(E)#,F-i#;/*存放产生式*/int a20;/数组a实现状态栈char b20,c20,cl;/数组b实现符号栈，数组c存放输入的字符串int top1,top2,top3,top,m,n;void main()int g,h,i,j,k,l,p,y,z,count;char x,copy20,copy120;top1=0;top2=0;top3=0;top=0;a0=0;y=a0;b0=#;count=0;z=0;/输入要识别的字符串prin tf(请输入表达式n);doscanf(%c,&c1);ctop3=cl; /字符数组c10存放输入的字符串 top3=top3+l;/最后 top3=5while(c1!=#);/输出分析结果printf (“步骤t 状态栈tt 符号栈tt 输入串ttACTION、tGOTOn); doy=z;m=0;n=0;/*y,z 指向状态栈栈顶*/g=top;j=0;k=0;x=ctop;/将输入符号赋给 xcount+;prin tf(%dt ,coun t);/输出步骤序号 while(m=top1)/*输出状态栈*/printf(%d,am);m=m+1;printf(tt);while(n=top2)/*输出符号栈*/printf(%c,bn);n=n+1;printf(tt);while(g=top3)/* 输出输入串*/printf(%c,cg);g=g+1;printf(tt);while(x!=vtj&jS1S-BbB-a涉骤 状态栈符号栈输入串ACTION GOTO1 0kS-B#0 s-ser popPress any key tocontinue5.心得体会通过该课程设计，掌握了什么是编译程序，编译程序工作的基本过程及其 各阶段的基本任务，熟悉了编译程序总流程框图，了解了编译程序的生成过程、 构造工具及其相关的技术对课本上的知识有了更深的理解，课本上的知识师机 械的，表面的。通过把该算法的内容，算法的执行顺序在计算机上实现，把原 来以为很深奥的书本知识变的更为简单，对实验原理有更深的理解。通过把该算法的内容，算法的执行顺序在计算机上实现，知道和理解了该 理论在计算机中是怎样执行的，对该理论在实践中的应用有深刻的理解。通过 该课程设计，全面系统的理解了编译原理程序构造的一般原理和基本实现方法。 把死板的课本知识变得生动有趣，激发了学习的积极性。把学过的计算机编译 原理的知识强化，能够把课堂上学的知识通过自己设计的程序表示出来，加深 了对理论知识的理解。以前对与计算机操在这次课程设计中，我就是按照实验指导的思想来完成。加深了理解文件 系统的内部功能及内部实现，培养实践动手能力和程序开发能力的目的。通过该课程设计，全面系统的理解了编译原理程序构造的一般原理和基本 实现方法。把死板的课本知识变得生动有趣，激发了学习的积极性。把学过的 计算机编译原理的知识强化，能够把课堂上学的知识通过自己设计的程序表示 出来，加深了对理论知识的理解。以前对与计算机操作系统的认识是模糊的，概念上的，现在通过自己动手做实验，从实践上 认识了操作系统是如何处理命令的，如何协调计算机内部各个部件运行，对计 算机编译原理的认识更加深刻。课程设计中程序比较复杂，在调试时应该仔细， 在程序调试时，注意指针，将不必要的命令去除。在这次课程设计中，我就是按照实验指导的思想来完成。加深了理解文件 系统的内部功能及内部实现，培养实践动手能力和程序开发能力的目的。6.参考文献1 .编译原理，主编：胡伦俊、徐兰芳、骆婷，出版社：电子工业出版社，出版时间：2005 年 12月2 .程序设计语言编译原理（第 3 版）,主编：陈火旺、刘春林等,出版社：国防工业出版社,出版时间：2003 年 2 月3 .编译原理课程设计,主编：王雷、刘志成、周晶,出版社：机械工业出版社,出版时间：2005年3月设计过程中现场提问(或答辩)记载：1.什么是SLR (1)分析法？答：为了对语言句子进行确定性的分析，需要解决“移进一归约”或”归约 归约”冲突。我们采用对含有冲突的项目集向钱看一个输入符号的办法来解决 冲突，这种分析法成为简单的LR分析法，即SLR(1)分析法。2.SLR(1)与LR (0)文法有什么区别？答：LR和LR(0)具有相同的状态机，LR(0)只看分析栈的内容，不考虑当 前输入符SLR( 1)考虑输入符，用follow集来解决冲突，因此SLR( 1)要比LR(0) 分析能力强