1、本科毕业设计第1页共43页1绪论编译技术是理论与实践并重的课程，在大学本科计算机科学与技术系的学生的培养教育中有非常重要的地位。而其实验课程要综合运用一年级、二年级和三年级所学的多门课程的内容和知识，用来完成一个小型编译程序的设计和实现。从而巩固和加强对词法分析、语法分析、语义分析、代码生成和报错处理等理论的认识和理解；培养在校大学生对一个完整的编译系统的独立分析和设计开发的能力，进一步的培养当代大学生动手实践能力以及独立自主的开发设计能力。完整的编译器设计开发和实现是一个非常复杂的过程，为了简洁明了的说明编译器的基本原理，本程序采用了自定义一种类高级语言的高级语言的方法，先定义了该类高级语言
2、的语法规则，然后再设计与实现了该语言的编译器前端，并且分别从词法分析，语法分析和语义分析等三个方面进行了详细的开发和设计。希望可以让学生可以更加清楚直观的认识和理解编译原理的各个方面的知识。从以往的日常教学经验来看，我们大学课程中接触和学习的最多的就是C语言和C语言。C语言是计算机科学与技术等信息类专业的基础必修课，大部分同学都掌握的比较扎实，所以，本程序所写的词法分析器，语法分析器，语义分析器大部分所用的语言都是C语言，C语言是面向过程的结构化语言，程序设计结构清晰，逻辑严谨，能让让学生很好的理解和接受。C语言也是计算机科学与技术等专业的基础课程，是C语言在面对对象思想方面的改进版，它继承了
3、C语言的结构化设计思路，逻辑层次感强，同时又具备了面向对象设计的能力，也是一门非常优秀的语言，很多学生对这门语言很感兴趣，所以本程序也设计了几个用C语言编写的词法分析器，语法分析器，语义分析器，以备那些在C语言方面熟练掌握的学生学习和借鉴。11选题背景21世纪是飞速发展的高科技时代。在日常的生活和工作中各行各业都离不开计算机技术的运用。学好计算机技术可以让你在以后的工作和生活中对电脑的使用得心应手。所以计算机科学与技术成为了在大学里非常热门的专业。但是大部分学生往往注重高级语言和软件设计运用方面的学习，对计算机的底层运用却不是特别在意，往往不求甚解，马马虎虎。其实这些都是不好的学习习惯，像计算
4、机原理，操作系统和编译原理都是非本科毕业设计第2页共43页常重要的课程，学好并且掌握它们能让你在遇到计算机硬件方面的问题的时候能够轻松解决，了解计算机的底层运行原理更可以帮助我们在设计和开发软件的时候避免一些很棘手的问题，使开发出来的软件更健壮，运行效率更高。所以，为了增强大家对编译原理课程的学习理解和动手实践能力，本课题整理和设计了一些和编译器有关的程序，方便大家学习和参考。12选题意义目前世界上的发达国家普遍都非常重视发展以计算机科学和通信技术为核心的信息技术、信息产业和信息技术的应用，大部分经济比较发达的国家的信息产业的发展都非常迅速。当前，我国正处于国民经济的高速发展时期。与此相伴随着
5、的，必然有信息技术应用方面的高速发展，各行各业都将面临着信息技术研究与发展的大课题以及信息化技术改造的大任务与大工程。所以，很多高校都非常重视学生在计算机科学技术方面的学习。信息技术基础更是成为了大部分学校的公共基础课。当然，编译原理作为一门比较复杂的计算机技术，对非计算机专业的学生要求不是那么高，但是计算机科学与技术专业的学生就应该好好学习和掌握。要求学生不但要学习课堂上的理论知识，也要加强动手实践能力，所以，编译原理的课程设计和实践就显得非常重要了，但是目前来说，很多学生的动手实践能力很差，实验课上设计的程序往往会遇见各种各样的问题，比如程序的语法总是有问题，或者逻辑不严谨，又或者经常报错
6、，结果不符合设计要求等等。在这个教学实践背景下，本课题决定整理和设计一些编译原理实践课程中常用的程序，方便学生更好的学习和理解编译原理这门课程，同时提高他们的动手实践的能力，能让他们在自己设计编译程序的时候少犯错误，少走弯路，更好的完成学校既定的教学任务和目标。希望同学们能把本课题设计的程序当做一个参考，更好的掌握编译原理这门课的精髓，更好的提高自己。13资料来源在设计过程之中曾多次对编译原理的课程设计和编译器的设计实现收集资料，在互联网上和图书馆中查找编译原理的相关信息，力求使本课题设计的程序能够充分的贴近现实，满足同学们的实践需求。由于在收集资料的时候很多资料的内容互相重复，有资料中的程序
7、也有互相借鉴，所以该课题所编写的程序代码可能有的也会互相类似，但是本科毕业设计第3页共43页这应该不会影响整个程序的可读性以及准确性。整个程序设计中的很多东西都有参考教科书，所以，教科书也是一个很重要的资料来源。14程序特点本课题做的这个套程序主要针对的是编译原理的实践教学和程序设计方面，所以各个程序之间相对比较独立，功能比较单一，主要就是三个功能，词法分析，语法分析以及语义分析。最后统一在VS2010下做了一个简单的界面，能把整个编译过程演示一下。本程序的主要特点为A界面简单本程序在开发的过程中，为了让学生更直观的学习和了解编译原理内部知识和编译器的结构，使操作界面简洁、统一，易学易用。采用
8、人机对话方式，交互性强。B操作简单本系统尽量使用DOS操作界面，风格一致，用户只需熟悉DOS界面的基本操作，就能基本学会本程序的使用。在数据输入过程中，本课题尽可能多地采用数据输入确认，减少数据输入错误,将键盘的录入错误量减至最少。最后统一的编译器程序界面也非常简单，只有两个按钮，一个编译一个运行，简单实用。C注释很详细程序内部源代码的注释非常详细，可以让学生简洁直观的判断每一行代码的功能以及作用，方便教学。本科毕业设计第4页共43页2开发环境21C语言简介C语言是由20世纪70年代中期UNIX操作系统的发明者DENNISRITCHIE在1970年于B语言的基础上设计和发明的。在1972年年初
9、，THOMPSON等人在早期简易的计算机PDP型计算机上运用C语言重写了UNIX操作的系统内部关键程序，可以这么说，C语言是伴随着UNIX操作系统的诞生而诞生的。20世纪80年代中期，C语言被程序员广泛使用，渐渐的演变成为个人计算机上非常流行和受欢迎的编程语言和工具。早在1983年7月，美国的国家标准委员会就对C语言进行了标准化得管理，发布了第一个C语言的标准草案，使得C语言广发传播。为了更好地适应大规模软件的生产和开发，在C语言的基础上，贝尔实验室BIARNESTROUSTRUP博士和她的同事们开始对它进行改进和扩充。将“类”的概念引入到了C语言当中。在1983年末构成了最早期的C语言。为了
10、让C语言可以适应软件的大规模的开发需求，计算机技术的先驱们又为C语言引入了多重继承的概念，运算符的重载技术以及引用和虚函数方法等许多全新的特性。美国国家标准委员会（ANSI）和国际标准化组织ISO一起进行了标准化工作，并且于1998年正式颁布了C语言的国际标准ISO/IEC199814882，从此刻开始，软件开发进入到了一个快速发展的新阶段。20世界90年代，美国的微软公司（MICROSOFT）为了减少和降低WINDOWS的应用程序开发成本，提高应用软件在软件市场当中的地位和价值，在1992年发布了包含MFC20在内的VISUALC10。一个创时代的可视化C集成的开发环境面世了。我们常说的MF
11、C其实就是一个常用的软件集合包（FRAMEWORK），就是利用面向对象的方法把WINDOWS的应用程序的接口封装起来。提高了WINDOWS的平台上的软件产品的开发效率。1998年，美国的微软公司（MICROSOFT）推出了目前最流行也是最受欢迎的VISUALC60版本。2002年末，又推出了VISUALC70，即是嵌入在VISUALSTUDIONET框架中的VISUALCNET2002。到目前为止，最新的版本已经更新到了VS2012了。尽管软件开发的环境一直在不换的更新发展，但是对于初学者来说，打好基础，学好C语言是非常重要的第一步。211C语言是一门中级语言C语言是一门非常基础的中级语言，也
12、就是说C语言具有“低级语言”的一些固有本科毕业设计第5页共43页特征允许程序自由访问计算机物理地址，可以进行位操作，能够对计算机的硬件接口直接访问，生成的目标代码的质量非常高，程序的执行效率也很高，同时它也兼顾了“高级语言”的固有特点语句简洁，紧凑，运算符特别灵活，数据类型丰富，具有结构化的控制语句，逻辑严谨，可移植性也很好。212C语言是结构式语言C语言的一个特别突出的特点就是C语言的代码和数据是分隔开的，它把各个子程序之间除去必要的信息交流之外的程序部分相互独立。这样的结构化程序设计方式可以使得程序代码的层次更加清晰，便于用户使用、程序的后期维护维护以及代码编写人员进行调试。C语言的很多方
13、法是用函数的方式提供给用户使用的，函数可以在C语言中非常方便的调用，并且C语言中具有多种循环控制结构、条件判断语句可以控制程序和数据信息的流向，从而使源代码完全结构化。213C语言的独有特点A）C语言是包含结构化程序设计以及递归功能的面向过程的中级语言。B）C语言的传递参数均是以值传递（PASSBYVALUE），也可以传递指针（APOINTERPASSEDBYVALUE）。C）在C语言中不同的变量类型能够用结构体（STRUCT）组合在一起。D）C语言只有32个保留字（RESERVEDKEYWORDS），这样变量、函数命名有更多的弹性。E）在C语言中部份的变量类型可以转换，比如整型和字符型变量。
14、F）使用指针的方式，C语言可以很轻松的对计算机中的存储器进行比较底层的控制。G预编译处理（PREPROCESSOR）让整个C语言的编译过程更具有弹性。22C简介C语言一门非常流行而且受欢迎的高级语言，C语言算是C语言当中的一个子集，C语言基本囊括了了C语言当中的的绝大多数思想以及内容。C的应用非常广泛。C可以支持多种编程范式面向对象编程、泛型编程以及过程化编程。目前最新的正式标准C14将于2014年8月18日发布。C语言在程序设计的领域使用的非常广泛，经常将之运用在各种系统开发以及引擎开发等众多的实际应用当中，是当本科毕业设计第6页共43页前社会上一门最受人们喜爱，使用人数最多的一门面向过程开
15、发的程序设计语言之一。它可以支持类、封装、重载等各种开发功能的实际应用。221C语言支持数据封装支持数据封装可以说就是支持数据抽象。在C语言中，类是支持数据封装的工具，对象是数据封装的实现。面向对象的程序设计思想与面向过程的程序设计思想在运用函数以及数据信息的关系和方法上是完全不一样的。在我们常用的面向过程的程序开发和设计的过程当中，数据通常只是被当做了一种静态结构，只能够等待程序的调用函数来对它们进行计算和处理等操作，但是在我们面对对象方式的程序开发设计过程当中，将要操作的数据以及可以对这个数据进行操作的调用函数一起封装，作为一个新生成的类的定义。另外，封装还可以提供一种对数据访问的控制机制
16、，保障程序的安全性。222C语言允许函数名和运算符重载函数名的重载和运算符的重载都是属于高级语言的多态性表现。函数的多态性指的是完全一样的语法结构可以用来代表不相同的实体或者对不相同的实体类型进行一些操作。C语言可以支持函数的多态性，C语言允许一个相同的运算符号或者一个完全一样的函数名称代表多个不相同的实现的函数，这个就被称之为运算符或者说是表示符的重载。当然，使用者可以根据自己的需要定义各种各样的函数重载或者运算符重载。223C语言支持动态联编在C语言当中可以定义虚函数。C语言通过定义虚函数的方法可以完全支持程序设计中的动态联编功能，动态联编可以说是高级语言多态性表现出来的一个非常明显的特点
17、，多态性形成的由父类以及子类来组成的一个简单的树形结构。在这个树形结构中的每一个子类都可以接受一个或者数个具有相同名字的消息和信息。23编译原理介绍编译程序算是计算机软件系统的最基本的组成部分之一了，而且目前市场上流行的大多数计算机系统都配置了不止一种高级程序设计语言（例如JAVA和C）的编译程序，对一些使用率较高的高级语言甚至准备了好几个不同性能的编译程序。从功能上来说，一个编译程序就好比一个语言的翻译器，它可以把一种语言书写的程序翻译成用另外一种语言编写的等价的程序。例如，汇编程序就是一个翻译程序。它可以把汇编语言程序翻译成由机器语言编写的程序。如果这个程序的设计语言是像C语言或者C语言这
18、类本科毕业设计第7页共43页的高级程序设计语言，而且程序的目标语言是像机器语言这样的低级程序设计语言，那么这个翻译过程的程序就可以称之为编译程序，这种翻译的原理则可以称之为编译原理。24编译器介绍编译是从源程序代码（一般是高级语言）到可以直接被计算机或者虚拟机执行的目标程序代码（一般为低级语言或机器语言）的翻译过程。但是，目前市场上也由把较低级的编程语言通过复杂的翻译过程翻译成较高级的编程语言的编译程序，在这一类型的编译器当中，那部分用来把由高级编程语言生成的低级语言代码重新翻译成由高级编程语言代码的程序被我们称为反编译器。也存在着从一种高级编程语言翻译为另外一种不同的高级编程语言的编译程序，
19、或者是生成另一种还需要计算机进一步处理的的中间代码的编译程序（又称之为级联）。本科毕业设计第8页共43页3程序设计前期分析31初步调查在编译原理的日常教学中，大部分学校的教学模式还是以课堂教学为主，学生主要通过在课堂上听老师讲解编译原理教科书上的理论知识来学习编译原理这门课。但是，课堂讲解的教学方式比较枯燥乏味，导致很多学生的学习积极性不高，学习效率较低，不能好好理解编译原理的关键内容。同时，学生在自己独立编写和设计编译程序的时候往往无从下手，动手实践能力很差，有的学生甚至连编译器的运行环境和平台都不了解，更不要说自己独立设计和实现一个完整地编译器程序了。所以，开展编译原理的实践教学课程势在必
20、行，在实践课上，学生可以系统的学习编译程序的开发过程，从一开始的需求分析，语法结构制定，词法分析，语法分析，四元式到最后完整的编译器。这些东西不自己动手练习是很难掌握的，通过实验教学，会使学生熟练地掌握编译程序设计和实现的各个步骤，而且还能激发学生探究编译原理更深层次的东西，增强学生对编译原理的学习兴趣。所以，一些好的、严谨的实验程序范例就显得十分重要了。本课题的研究正是为了给编译原理的日常教学提供一个更适合学生学习和成长的方式，给学生在动手实践的过程中提供一个示范，使越来越多的学生能对编译原理产生兴趣，希望继续研究下去。这样，老师们就再也不用担心学生的成绩啦。32可行性分析通过对编译原理课程
21、实际教学的初步调查后，发现目前编译原理课程的教学现状非常需要一门实验实践课程来辅助教学，并且现在掌握的资料和技术可以设计和编写一些实验实践程序。在对现有的人力、物力、财力和技术条件进行分析之后，确定开发该类高级语言编译系统的设计与实现课题，在经济上、技术上、时间上，法律上都已具备可行性。A）经济可行性即实现这个程序设计有没有什么经济效益。这个编译器程序设计是作为个人毕业设计而设计开发的，因为个人能力和设计水平不高，程序的结构以及功能都不够完整，正确性有待考究，内容也许没有太高的实际价值，该程序设计方案可能并没有太高的经济效益，但是作为一个毕业设计，却使得它具有了开发的价值。B）技术可行性即现有
22、的技术能否开发该程序，会有哪些困难。目前掌握的编译原本科毕业设计第9页共43页理和C语言知识还行，也有很多相关资料可以查阅，所以技术上应该是可行的。C）运行可行性即该平台规定的运行方式是否可行。本课题用的主要是VC60，和学校机房的操作环境一致，所以肯定是可以再学校机房运行的。D）法律可行性该程序的开发和设计应该不会触犯法律。因为该程序只是作为毕业设计与商业无关，又因为是自主开发设计，因此不会构成侵权，在法律上是可行的。通过以上的可行性分析，决定设计和实现这个编译器程序。在程序的设计和开发过程中，还应注意一下两点A）要注意程序的准确性和注释的完整性，只有完整的准确的注释才能为学生提供一个正确的
23、参考和借鉴。B）从全局出发注意程序设计的整体优化，还要注意程序的可扩展性和延伸性。33需求分析我们在软件开发中经常遇见关于需求分析的问题。需求分析，就是指对程序开发当中需要解决的问题和障碍进行的分析处理，搞明白要开发的程序软件的实际需求，包括程序要输入什么样的类型和种类的数据，期望得到怎样的运行结果，最终程序应该输出什么东西。可以说，在软件工程当中的“需求分析”就是确定程序要“做什么”。在程序设计开发的过程中，我们所说的需求分析指的是在建立一个全新的或改变一个已经存在的程序或者软件的时候描述新的程序的设计方法、范围、目的、功能和定义时所要进行的所有的工作的总称。需求分析是软件工程中的一个关键过
24、程。在需求分析的过程中，大部分的分析员以及高级软件工程师都会明确顾客的实际需要，只有在我们明确了顾客的这些实际需要以后，程序设计人员才能够分析出新的系统的解决方案和方法。基于需求分析的重要作用，查阅了图书馆书籍，浏览了网上的相关资料，从程序设计的方法，功能的实现，技术的要求以及可行性等多方面进行考虑完成了需求分析。现在很多高校都急需开展编译原理课程的实验实践课程，肯定需要一些和实验教学相关的参考程序，本课题设计的这些程序可以很好地满足他们的需求，所以本课题的这个设计还是很有市场的。本科毕业设计第10页共43页4总体设计41设计思想本程序采用分步设计方式设计，把整个编译器分解成三个主要部分，分别
25、是词法分析程序，语法分析程序，语义分析程序。各个部分的设计和实现相对独立，等把各个部分的功能设计和实现以后，在根据编译器的运行原来来进行组合，这样，一个完整的，结构层次清晰的编译器就开发完成了。首先需要设计的程序是词法分析器，第二步要做的是设计语法分析器，第三部要实现的部分是语义分析器。最后设计一个简单地前端，把上面三个功能组合一下，就实现了一个完整的编译器程序了。42主要任务由于本程序是用于给学校的实验课教学提供一个参考，所以，程序的准确性和平台适用性需要保障，要确定程序能够在学校机房的操作环境正常运行，同时要注意程序注释部分的完整性，要使学生能够清楚正确的理解程序的每个部分要实现的功能，要
26、让他们弄懂每一句代码的含义，由于编译原理词法分析，语法分析，语义分析的方法有很多，所以还要注意程序编译分析方法的多样性。由于每个学生擅长的编程语言各不相同，所以本课题选择了C语言和C语言作为程序开发的主要语言，因为C语言和C语言是计算机科学与技术系的专业必修课，每个学生都应该掌握的很不错。同时，C语言和C语言都很常用，二者代表了现如今最流行的两种程序设计语言的类型，分别体现了面向对象以及面向过程两种完全不同的编程思想，对学生的日常学习有非常多的帮助。43模块结构431词法分析词法分析的过程基本上是所有的编译程序的第一个处理过程，编译器一般可以使用两种完全不相同的设计方法来构造和设计开发词法分析
27、子程序。其中第一种就是根据对类高级程序设计语言中得各类单词和符号的某种描述以及定义，使用手工构造的策略（例如可以用C语言或者C语言）来开发词法分析子程序。通常来说，程序可以根据本科毕业设计第11页共43页已经定义好的文法规则或者已经画好的状态转换图来设计和开发相对应的状态矩阵，这个状态矩阵所有的控制语句一起控制程序就可以组成一个简单的编译程序的词法分析程序；也可以根据定义好的文法规则或状态转换图来直接设计和编写词法分析程序。另外的一种构造词法分析程序的途径就是所谓的词法分析程序的自动生成，即先使用正规式对类高级语言中的各个种类的单词和符号进行词型描述，并且分别指出在识别单词的过程中词法分析程序
28、应该进行的语义处理工作，然后用一个所谓的词法分析程序的构造程序对上述的信息进行进一步的加工。例如著名的美国BELL科学实验室研制和开发的LEX程序就是一个词法分析子程序的自动化生成工具。一般的情况下，当需要开发一种全新的编程语言的时候，因为该编程语言的单词和运算符号在不停地开发和修改，所以利用LEX这一类的工具生成的我们需要的词法分析程序相对于手工编写的方式来说会比较易于修改和维护。当然，如果一旦这种语言确定了，那么采用手工设计和编写词法分析程序的效率会更高。432语法分析语法分析的过程可以说是编译程序中最核心的部分了，语法分析的目的就是识别由词法分析程序所给出的单词或者符号序列是不是事先给定
29、文法的正确程序语句，目前大学教科书当中涉及的语法分析方法有自顶向下分析方法以及自底向上这两大类别，自顶向下的分析方法又包括了确定分析和不确定分析两个分支，自底向上分析方法则又包含了运算符优先分析方法以及LR分析方法，这些分析方法都有各自的优缺点。然而除去自顶向下的不确定分析方法外，都是目前编译程序构造的实用方法，本课题将在下一章着重介绍它们的实现原理和实践技术。433语义分析语法制导翻译的模式是在语法分析的基础上，增加语义操作来实现的。对于要求中给定文法当中的每一个产生式，开发和设计其相对应的语义子程序。在程序的语法分析过程当中，每当程序使用一个产生式来进行归约或者是推导的时候，语法分析程序不
30、但要执行相对应的语法分析动作，还需要调用相对应的语义子程序，以便程序可以顺利的完成包括生成中间代码、查找和填写相关的表格数据、检查并且报告源程序中的错误在内所有工作。每一个语义子程序都要求能够指明相对应的产生当中的每一个字符和符号的具体含义和内容，而且需要规定使用这个产生式来分析程序的时候所应该进行的语义动作。本科毕业设计第12页共43页5详细设计51词法分析器的设计和实现本程序用手工编码方式构造识别类高级语言的词法分析程序。该类语言中具有的单词包括了五个有代表性的关键字BEGIN、END、IF、THEN、ELSE；标识符；整型常数；六种关系运算符；一个赋值符和四个算术运算符。第一步，我们需要
31、做的是对单词进行简单的分类设计好上面所说的类高级语言中的每一类单词的符号以及分类码表。如下表51所示表51类高级语言中的各类单词符号及其分类码表单词符号类别编码类别码的助记符单词值BEGIN1BEGINEND2ENDIF3IFTHEN4THENELSE5ELSE标识符6ID字母打头的字母数字串整常数7INT数字串11NE12GT13GE14IS15PL16MI17MU/18DI然后就是关于本程序词法分析的详细处理过程了，在一个高级程序设计语言中，通常都会包含很多种类的单词符号。所以，本程序采用先为每个种类的单词符号建立一张完整的状态转换图，然后再把这些状态转换图一起组合成一张统一的状态图，就可
32、以得到一个有限的自动机，再进行一些必要的确定化以及状态数的最小化处理过程，最后再本科毕业设计第13页共43页根据这个程序的状态图来设计和编写词法分析程序。在这里，为了使得本程序的词法分析程序的设计结构更加清晰，而且要尽量避免一些不必要问题的烦恼，可以假设要编译的类高级语言当中，所有的关键字都算作是系统的保留字，开发人员不得将它们作为源程序中的标识符；在要分析的源程序的输入文本当中，标识符、关键字以及整常数之间，如果没有出现关系运算符、算术运算符以及赋值符号，那么程序至少需要使用一个空白的字符来加以分隔。作了这些限制以后，就可以把关键字和标识符的识别统一进行处理。每当程序开始识别一个单词的时候，
33、如果扫视到的第一个字符是字母的话，就会把后续输入的字母或者数字字符按顺序进行一一拼接，直到程序扫视到不是字母或者数字字符为止，以期望可以得到一个尽可能长的字母字符串或者数字字符串，然后程序再用这个字符串来查询所谓的保留字表，如果程序查到了这个字符串的话，就会取出相应的类别码；相反的，如果程序没有查到这个字符串，那么表明这个字符串应该做为一个标识符。在采用了上述的策略以后，可以针对上表51中的部分单词来设计一个如下图51所示那样的有限自动机。在图51里面添加了当程序进行状态转移的时候，该词法分析程序应该执行的语义动作。第三步，将表51里面的单词集中的整常数全部改为无符号常数，本程序把无符号常数的
34、单词分类码助记符记为UCON；其值为无符号常数的机内二进制表示。描述无符号数的BNF定义和状态转换图无符号数的文法G如下无符号数D余留无符号数无符号数小数部分无符号数D余留无符号数D余留无符号数余留无符号数十进小数余留无符号数E指数部分余留无符号数D余留无符号数十进小数E指数部分十进小数D十进小数十进小数D本科毕业设计第14页共43页小数部分D十进小数小数部分D指数部分D余留整指数指数部分整指数指数部分整指数指数部分D整指数D余留整指数整指数D余留整指数D余留整指数余留整指数D图51所表示的就是上述文法的状态转换图，下图当中编号0、1、2、3、4、5、6分别代表了非终结符号中的、以及。图51文
35、法G【】的状态转化图本程序用来实现无符号数识别的方法在计算机系统内部实现状态转换图的常用方法方法之一就是把状态图当中的各个状态作为行，把有可能输入的每一个输入符号做为列，组成了一个状态矩阵。在这个状态矩阵当中，矩阵内的元素用来表示下一个状态以及扫描器需要完成的语义动作（例如字符的拼接、数制之间的转换、填充的符号表和程序输出的单词在计算机内部的表示方法等）。下表52里面的第一列表示各状态SI的编号，表中的第二列则分别列出了在每一种状态下程序有可能扫视到的输入符号AJ，表中的第三列指出了当（SI,AJ）出现的时候程序应该执行的语义动作，最后一栏的内容用来指明下一个状态的编号（假如其后是NULL或者
36、是“结束”则表示没有后继状态）。4503261EEDDDDDDD|本科毕业设计第15页共43页表52包含语义处理过程的识别无符号数的状态矩阵当前状态扫视字符语义处理操作或接受动作后继状态0DN0P0E1WD1W0N0P0E13OTHER识别失败NULL1DWW10D12E4OTHER回送整常数ICONW结束2DNWW10D2E4OTHER回送整常数ICONWPOW10,3PN结束3DNWW10D2OTHER识别失败NULL4DPP10D63E1；5OTHER识别失败NULL5DPP10D6OTHER识别失败NULL6DPP10D6OTHER回送实常数FCONWPOW10，EPN结束图52和词法
37、分析程序中所出现的语义变量及语义函数的含义和功能说明如下。函数GETCHAR程序每调用一次该函数，就会把扫描指示器当中的现在所指示的源程序中的字符传送给字符变量CH，接着程序会把扫描指示器的位置前推一个字符位置。字符数组TOKEN用来依次存放一个单词词文中的各个字符。函数CAT程序每调用一次该函数，就会把当前CH中存储的字符拼接到TOKEN中所存储的字符串的右边。函数LOOKUP程序每调用一次该函数，就会用TOKEN中存储的字符串来查询保留字表，如果查到存在，该函数就会将相对应关键字的类别码赋值传给整型变量C；如果没有查到就将C置为零。函数RETRACT程序每调用一次该函数，就会把扫描指示器立
38、刻回退一个字符的位置（就是退掉刚才多读的那个字符）。函数OUT程序一般只有在进入终态的时候才会调用到这个函数，调用的形式一般是OUTC，VAL。在这里面，实参C作为相对应的单词的类别码或者是它的助记符。本科毕业设计第16页共43页图52如下所示D图52识别图51所列语言中的部分单词的DFA及相关的语义过程013510CATGETCHAR1D11DD1DSTART1DINIT1DCATGETCHAR1D21DD非1和DRETRACTLOOKUP当C等于0时，OUT（ID,TOKEN）当C不等于0时，OUT（C,“”）OUTLE,“”1DCATGETCHARD1DDD其他4D6789111213O
39、UT（INT,TOKEN）OUTNE,“”1DOUTLT,“”1DOUTEQ,“”1DOUTGE,“”1DOUTGT,“”1DGOTOSTARTERRORGETCHARGETCHARRETRACT非DRETRACT非和DDGETCHARCATGETCHAR1D非DRETRACT本科毕业设计第17页共43页该词法分析程序编译运行结果如图53所示图53词法分析程序运行界面图输入字符串BEGINX10IFX5THENX2X6/2END其运行结果如下图54所示图54词法分析程序测试结果一输入字符串HELLOEND其运行结果如下图55所示本科毕业设计第18页共43页图55词法分析程序测试结果一输入字符串
40、IFX5Y3END其运行结果如下图56所示图56词法分析程序测试结果三源程序如下所示INCLUDEINCLUDECHARPROG80,TOKEN6CHARCHINTSYN,P,M,N,SUMCHARRWTAB6“BEGIN“,“IF“,“THEN“,“WHILE“,“DO“,“END“/定义关键词MAINP0PRINTF“NPLEASEINTPUTSTRING“本科毕业设计第19页共43页DOCHGETCHARPROGPCHWHILECHP0DOSCANERSWITCHSYNCASE11PRINTF“D,DN“,SYN,SUMBREAKCASE1PRINTF“INPUTERRORN“BREAK
41、DEFAULTPRINTF“D,SN“,SYN,TOKENWHILESYN0GETCH/词法扫描程序/SCANERFORN0NA|CHAWHILECHA|CHA|CH0TOKENMCHCHPROGPTOKENM0CHPROGPSYN10FORN0N0SUM0WHILECH0SUMSUM10CH0CHPROGPCHPROGPSYN11ELSESWITCHCHCASESYN21TOKENMCHELSEIFCHSYN22TOKENMCHELSESYN20CHPROGPBREAKCASETOKENMCHCHPROGPIFCHSYN24TOKENMCH本科毕业设计第21页共43页ELSESYN23CHP
42、ROGPBREAKCASETOKENMCHCHPROGPIFCHSYN18TOKENMCHELSESYN17CHPROGPBREAKCASESYN13TOKEN0CHBREAK/判断符号“”。CASESYN14TOKEN0CHBREAK/判断符号“”。CASESYN15TOKEN0CHBREAK/判断符号“”。CASE/SYN16TOKEN0CHBREAK/判断符号“/”。CASESYN18TOKEN0CHBREAK/判断符号“”。CASESYN21TOKEN0CHBREAK/判断符号“”。CASESYN24TOKEN0CHBREAK/判断符号“”。CASESYN25TOKEN0CHBREAK
43、/判断符号“”。CASESYN26TOKEN0CHBREAK/判断符号“”。CASESYN27TOKEN0CHBREAK/判断符号“”。CASESYN28TOKEN0CHBREAK/判断符号“”。CASESYN0TOKEN0CHBREAK/判断符号“”。DEFAULTSYN152语法分析器的设计和实现通过设计和开发一个典型的语法分析程序,使学生能够实现并且进一步掌握日常教学中常常涉及的语法分析方法。本程序把下图文法G1所定义的算术表达式的赋值语句作为分本科毕业设计第22页共43页析对象，对输入语句的语法进行分析。G1|/|A|B|C|X|Y|Z|A|B|C|X|Y|Z0|1|2|9该语法分析程
44、序编译运行结果如图57所示图57语法分析程序运行结果界面输入字符串BEGINX3YEND其运行结果如下图58所示本科毕业设计第23页共43页图58语法分析程序测试结果一输入字符串X35END其运行结果如下图59所示图59语法分析程序测试结果二输入字符串BEGINX2334END其运行结果如下图510所示本科毕业设计第24页共43页图510语法分析程序测试结果三源程序如下所示INCLUDEUSINGNAMESPACESTDINCLUDEINCLUDEDEFINEMAX150/词法分析表的最大容量DEFINEMAXBUF255/缓冲区的最大缓冲量VOIDTERMVOIDLRPARSERVOIDST
45、ATEMENTVOIDYUCUVOIDEXPRESSIONVOIDFACTORCHARPROGMAXBUF,TOKENMAXCHARCHINTSYN,P,M,N,SUM,KKCHARRWTAB6“BEGIN“,“IF“,“THEN“,“WHILE“,“DO“,“END“/定义关键词VOIDSCANER/词法扫描程序FORM0MA|CHAWHILECHA|CHA|CH0TOKENMCH本科毕业设计第25页共43页CHPROGP/读取下一个字符TOKENM0CHPROGPSYN10FORN0N0SUM0WHILECH0SUMSUM10CH0CHPROGPCHPROGPSYN11ELSESWITCH
46、CHCASESYN21TOKENMCHELSEIFCHSYN22TOKENMCHELSESYN20本科毕业设计第26页共43页CHPROGPBREAKCASETOKENMCHCHPROGPIFCHSYN24TOKENMCHELSESYN23CHPROGPBREAKCASETOKENMCHCHPROGPIFCHSYN18TOKENMCHELSESYN17CHPROGPBREAKCASESYN13TOKEN0CHBREAK/判断符号“”。CASESYN14TOKEN0CHBREAK/判断符号“”。CASESYN15TOKEN0CHBREAK/判断符号“”。CASE/SYN16TOKEN0CHBRE
47、AK/判断符号“/”。CASESYN18TOKEN0CHBREAK/判断符号“”。CASESYN21TOKEN0CHBREAK/判断符号“”。CASESYN24TOKEN0CHBREAK/判断符号“”。CASESYN25TOKEN0CHBREAK/判断符号“”。CASESYN26TOKEN0CHBREAK/判断符号“”。CASESYN27TOKEN0CHBREAK/判断符号“”。CASESYN28TOKEN0CHBREAK/判断符号“”。CASESYN0TOKEN0CHBREAK/判断符号“”。DEFAULTSYN1本科毕业设计第27页共43页BREAKVOIDSTATEMENTIFSYN10
48、SCANER/读下一个单词符号IFSYN18SCANER/读下一个单词符号EXPRESSION/调用EXPRESSION函数ELSEPRINTF“ERROR“KK1ELSEPRINTF“ERROR“KK1RETURNVOIDEXPRESSIONTERMWHILESYN13|SYN14SCANERTERMRETURNVOIDTERMFACTORWHILESYN15|SYN16SCANERFACTOR本科毕业设计第28页共43页RETURNVOIDLRPARSERIFSYN1/BEGINSCANERYUCUIFSYN6/结束标志SCANERIFSYN0/语法检测通过ELSEIFKK1PRINTF“ERROR,LOSEENDN“/缺少END错误KK1ELSEPRINTF“ERROR,LOSEBEGINN“/缺少BEGIN错误KK1RETURNVOIDYUCUSTATEMENTWHILESYN26/SCANERSTATEMENTRETURNVOIDFACTORIFSYN10|SYN11SCANER/为标识符或整常数时，读下一个单词符号ELSEIFSYN27SCANER本科
