LR(0)语法分析

淮阴工学院编译原理课程设计报告选题名称：LR(0)语法分析系（院）：计算机工程学院专业：计算机科学与技术班级：计算机1075(单招)姓名：赵俊丽学号：1071308114指导老师：于长辉王文豪高丽夏森学年学期：2009～2010学年第2学期设计任务书课题名称LR(0)语法分析设计目的LR(0)分析法是一种移进-规约过程，能根据当前分析栈中的符号串，同时也不用向右查看输入串的符号就可唯一确定分析器的动作。通过对给定的文法构造LR(0)分析表和实现某个符号串的分析掌握LR(0)分析法的基本思想。实验环境WindowsXP操作系统，VisualC++6.0以上编译环境任务要求1.录入合法的LR(0)文法2.构造并输出LR(0)分析表3.对输入的符号串进行语法分析工作进度计划序号起止日期工作内容109.12.14-09.12.14选定题目，明确题目要求209.12.15-09.12.15课题深入调研、细化工作，系统方案设计309.12.16-09.12.17程序录入、调试、整合409.12.18-09.12.20上机演示，课程设计分组答辩，完成课程设计报告指导教师（签章）：年月日编译原理课程设计报告1摘要：编译程序是现代计算机系统的基本组成部分之一，语法分析是编译程序的核心部分，识别由语法分析给出的单词符号序列是否是给定文法的正确句子，把词法记号流按语言的语法结构层次地分组，以形成语法短语。一个编译程序的工作过程一般可以划分为五个阶段：词法分析、语法分析、语义分析与中间代码生成、优化、目标代码生成。LR（0）是一种自底向上的语法分析方法，是已知的最一般的无回溯的移近—归约方法，这一方法能够识别所有能用上下文无关文法描述的程序语言的结构。本文主要讨论LR（0）语法分析的构造。着重分析LR(0)分析器的一般原理、实现思想、基本设计方法以及主要实现技术和工具。操作员录入合法的LR(0)文法，则自动生成LR(0)分析表，并对任一输入串进行分析。判断其是否是给定文法的句子。还可以对输入的句子进行语法分析。关键词：自底向上分析；移进；规约目录1课题综述......................................................................................................................................11．1课题来源.........................................................................................................................11．2意义.................................................................................................................................11．3预期目标.........................................................................................................................11．4面对的问题.....................................................................................................................22系统分析......................................................................................................................................32．1涉及的基础知识.............................................................................................................32．2总体方案.........................................................................................................................53系统设计......................................................................................................................................53．1算法描述.........................................................................................................................63．3详细流程图.....................................................................................................................94代码编写....................................................................................................................................105程序调试....................................................................................................................................15总结............................................................................................................................................19致谢.........................................................................................................................................20参考文献.........................................................................................................................................21编译原理课程设计报告11课题综述1．1课题来源编译器设计的编译程序涉及到编译五个阶段中的三个，即词法分析器、语法分析器和中间代码生成器。编译程序的输出结果包括词法分析后的二元式序列、变量名表、状态栈分析过程显示及四元式序列程序。整个编译程序分为三部分：词法分析部分、语法分析处理及四元式生成部分、输出显示部分。一个程序设计语言就是一个记号系统，如同自然语言一样，它的完整的定义应包括语法和语义两个方面。所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序。目前广泛使用的手段是上下文无关文法，即用上下文无关文法作为程序设计语言语法的描述工具。自底向上分析方法是一种移进-规约过程，当分析的栈顶符号串形成句柄时就采取归约动作，因而自底向上分析法的关键问题是在分析过程中如何确定句柄。LR分析法正是给出一种能根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输人串的k个(k=0)符号就可惟一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能惟一地确定句柄。LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程。1．2意义LR（0）分析方法虽然对文法的限制比较大，对绝大多数高级语言的语法分析器不能适用，然而他是构造其他LR类分析器的基础，学习和掌握LR（0）分析的原理和方法是我们掌握更高级语言语法分析的基础。归纳起来，大体上可分为两大类，即自顶向下分析方法和自底向上分析方法。自底向上分析方法是一种移进-规约过程，当分析的栈顶符号串形成句柄时就采取归约动作，因而自底向上分析法的关键问题是在分析过程中如何确定句柄。LR分析法正是给出一种能根据当前分析栈中的符号串(通常以状态表示)和向右顺序查看输人串的k个(k=0)符号就可惟一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能惟一地确定句柄。LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程。1．3预期目标编译原理课程设计报告2本次课程设计的目标即是利用所学过的编译原理的知识，利用LR(0)分析法，用C语言写出一个简单的LR(0)语法分析器。该语法分析器所要完成的功能是，对录入的文法判断它是否为LR(0)文法，如果是输出LR(0)分析表；在给定文法的情况下，能够利用LR(0)分析表，对用户输入的一串字符串用LR(0)分析法进行分析，判断该字符串是否为符合给定文法的一个句子，建立文法及其LR分析表表示的数据结构，设计并实现一个LR(0)的分析器。1．4面对的问题(1)分析表的构造。(2)归约还是移进的判断。(3)接受acc的判断。(4)编程结果的输出。在本次课程设计中，主要的是面对的文法的确定，以及分析其工作过程如何进行。对于文法确定的问题，必须找到一个符合LR(0)规范的文法，并且该文法不易太复杂，否则对于初次编写语法分析器的我们来说会比较复杂，否则容易出错。第二个就是分析过程的问题，目前，我们只是了解了理论上LR(0)的分析过程，但如何将该过程用程序去实现，并且能够对一个输入串进行实时的分析是比较复杂的。这涉及到对一个字符串进行一个字符一个字符的读取和操作，并且还要对几个连在一起的字符进行合并等操作，要求比较的高，对我们而言比较困难。在规范规约的过程中，一方面记住已移进和规约出的整个符号串，另一方面根据所用的产生式推测未来可能碰到的输入符号。当一串句柄的符号串呈现于分析栈的顶端时，希望能够根据上面过程中的数据来确定栈顶的符号串是否构成相对某一产生式的句柄。能正确初始化状态栈，对栈内元素的进栈和出栈，取栈顶元素以及遍历栈元素，LR分析方法是一种自底向上的分析方法，是一种个移进-归约的过程。当分析的栈顶符号串形成句柄时就采取归约动作，因而自底向上分析法的关键问题是在分析过程忠如何确定句柄。LR（0）分析器是在分析过程中不需要察看输入符号，因而它对文法的限制较大，对绝大多数高级语言的语法分析器是不能使用的，然而，他是构造其他LR类分析器的基础。1.5需解决的关键技术编译原理课程设计报告3（1）词法编译器。（2）交互式面向对象的词法编译器基本功能是。（3）根据规约规则对字符进行归约。（4）符合条件时采取移进动作。2系统分析2．1涉及的基础知识2.1.1词法编译器功能（1）导入任意文法，也可以自己输入。（2）输出文法的分析过程，以及判断是否为LR(0)文法，输出分析表。（3）输入句子，进行语法分析。（4）输出结构树。2.1.2词法分析器的设计方法有如下四个步骤：(1)写出该语言的词法规则。(2)把词法规则转换为相应的状态转换图。(3)把各转换图的初态连在一起，构成识别该语言的自动机。(4)设计扫描器；把扫描器作为语法分析的一个过程，当语法分析需要一个单词时，就调用扫描