编译原理课程设C语言子集的定义-Read

编译原理课程设计报告一.编译系统概述使用过现代计算机的人都知道，多数用户是应用高级语言来实现他们所需要的计算的。现在计算机系统一般都含有不只一个的高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序，供用户按不同需要进行选择。高级语言编译程序是计算机系统软件最主要的组成部分之一，也是用户最直接关系的工具之一。计算机上执行一个高级语言程序一般分为两步：第一，用一个编译程序把高级语言翻译成机器语言程序；第二，运行所得的机器语言程序求得计算结果。通常说的翻译程序是指能够把某一种语言程序转换成另一种语言程序（目标语言程序）。如果源语言诸如Fortran，Pascal，C，Ada或java这样的高级语言，而目标程序是诸如汇编语言或者机器语言这类的低级语言，这样的一个翻译程序就是称为编译程序。一个编译程序的工作过程一般可以划分为五个阶段：词法分析、语法分析、语义分析与中间代码生成、优化、目标代码生成。每个阶段都是从上一个阶段得到结果，对他进行分析，并且根据一些外部环境(例如符号表等)得到最终的输出结果。要构造一个编译程序，可以按照这样的阶段来分别构造，最后来连调。现在人们已经建立了多种编制部分编译程序或整个编译程序的有效工具。有些能用于自动生成扫描器(如LEX)，有些可以用于自动产生语法分析器(如YACC)，有些甚至可以用来自动产生整个的编译程序。这些构造编译程序的工具成为编译程序－编译程序、编译程序产生器或翻译程序书写系统，他们是按照编译程序和目标语言的形式描述而自动产生编译程序的。编译程序是一极其庞大而又复杂的系统，掌握它比较苦难。但是一旦对其掌握，对以后的程序语言设计，系统软件分析，系统软件设计，形式语言研究等方面都是非常有好处的。二.编译系统需求分析给出类C语言(C语言的子集)的词法和语法定义，并根据对应的语法定义写出一些属性文法和语法制导。根据词法和语法的定义，构造一个编译程序，它主要可以完成如下功能：1、读入某个已经编辑好的类C源程序文件，通过词法分析器，生成二元组，同时检查词法错误；2、语法分析器将产生的二元组作为输入，进行语法分析，同时检查语法错误；3、在语法分析同时，利用属性文法和语法制导技术，产生具体的语意动作，并对符号表进行操作；4、根据语义动作产生整个源程序的四元式序列；5、将产生的四元式序列连同符号表一起输出，作为编译程序的最终输出结果；6、对最后的代码优化和目标代码生成要有所考虑，必须留有一定的接口供以后扩展；7、增大程序的可移植性，努力做到整个系统方便移植。一些特殊要求由于做这样一个编译系统机会非常难的，不仅对自己的编译技术有些提高，而且对一些其他课程也是非常有帮助的，因此我想做一个较为标注的软件开发过程，提高自己的程序开发能力和经验。以下自我提出的是一些特殊要求，希望能够在开发过程种完成：1、整个系统的开发、测试、维护等工作都在Linux下完成。希望借此更加深刻的了解Linux系统的软件开发技术和工具的使用的方法；2、希望能够按照软件开发的全过程来完成这次的编译系统的开发。做好前期的设计工作和资料查询工作，然后着手开始编制代码。这样做既可以减少开发周期，提高开发效率，又可以了解一些有关的软件工程的知识；3、尽量采用正规的开发模式和开发方法，使用一些已经非常成熟的编译系统开发工具，例如FLEX和BISON等等，可以减少大量的不必要的人力工作；4、作好开发中间过程的总结工作，将发现的一些问题和总结出来的新方法及时的提取出来，这对以后的调试维护工作都是非常有好处的。三.C语言子集规定３.1C语言的简介ALGOL60是C语言的前身，它是由剑桥大学最先开发出来的一个语言。1967年，剑桥大学的MatinRichards对CPL语言进行的简化，于是产生了BCPL语言。1970年，美国贝尔实验室的KenThompson将BCPL进行的修改，并取名为“B语言”，并用它写出了第一个UNIX操作系统。到了1973年，D.M.RITCHIE在B语言的基础上最终设计出了一种新的语言，取名为C语言。1978年，BrianW.Kernighian和DennisM.Ritchie出版了著名的《TheCProgrammingLanguage》，从而使C语言成为目前世界上最为流行的高级程序语言。C语言之所以在目前世界上流行、使用广泛，这是因为它有非常多的优点。首先它简洁紧凑、灵活方便，有着非常丰富的运算符和数据结构。其次他是一个结构化的语言，便于使用、维护及调试。还有就是C语言允许直接对物理地址访问，可以直接对硬件操作。最后C语言生成的代码质量高，程序执行效率高，并且使用范围大，可移植性好，因此在多钟操作系统中均可以使用。由于C语言的流行，随之而来的是许许多多的编译软件和环境。其中TurboC、BorlandC编译器以及后来的VC＋＋可视化编程环境都是广大编程人员所钟爱的编程工具。为了对整个C语言的词法，语法，语义，编译等等方面有一个整体且深入的了解，因此这次的课程设计开发的编译器就以C语言为基础，对自己定义的类C的集合进行深入分析定义，设计出一个较为稳定可用的编译器。３.2C子集的定义本次设计的C语言的子集（便于叙述，以后称之为Cxx），是本着简单、易懂、易操作，而且能够完成一定功能的原则，尽量实现最基本的，人们最常用的部分，而抛弃那些不常使用的，或者难以实现的部分。这样考虑的目的是为了能过在短时间做出一个编译程序大的框架，并且开发出一个较为稳定的版本，来为以后的扩充更多的功能提供一定的接口和方便。这种设计是由里到外，逐步求精，也是符合一般设计的规律。下面就是我定义的Cxx的说明，由于与具体的编码有关，因此不可能使用形式化的语言，而只作简单的说明性的定义。稍后的详细设计报考中将会写出Lex词法定义和Yacc语法定义。1．Cxx以main函数做为主函数，且是整个语言唯一的函数。main函数是一个无参的，无返回类型的，不需要返回语句retrun的函数。所有的程序必须写在main函数里面；2．Cxx的程序是以一行或多行表达式和多个程序块构成，每行表达式的结尾以分号“；”做为标志，一个程序块以大括号{}做为区域定义标志；3．Cxx的表达包括变量定义表达式、赋值表达式、算术运算表达式、逻辑运算表达式；4．Cxx的程序块包括三大程序结构，即顺序、分支和循环；5．Cxx的变量定义只允许整型变量定义，并且可以赋初值，即类似inti＝5的定义；6．Cxx的赋值语句只允许使用等号“＝”将一个表达式的值付给一个整型变量，例如x=3*y;7．Cxx的算术表达式的符号包括＋,－,*,/,^,%。对应的操作为加法，减法，乘法，除法，乘方，求模；8．Cxx的逻辑表达式的符号包括&&,||,！,==,!=,,,=,=。对应的运算为逻辑与，逻辑或，逻辑非，等于，不等于，小于，大于，小于等于，大于等于;9．Cxx分支程序块包括if，if-else,if-elseif-…..-else的语句，其语法定语同AnsiC的定义；10．Cxx循环程序块包括while，do-while和for语句；３.3简单举例下面是一个简单的标准的Cxx的源程序：（其中/**/为说明部分，不作为程序的内容）main（）/*main函数定义*/{inti=0,x=10,y=20,z=30,a,b,c;/*整型变量定义*/a=x+y*z;/*赋值和算术表达式语句*/b=（3*z）%y;for（i;i=10;i=i+1）/*for循环语句*/{if（（（a||b）&&（x||y））!=0）/*if－else分支语句和逻辑运算语句*/c=a+b;elsec=a-b;}}四.编译系统设计原理４.1编译系统构成及原理编译程序的工作过程一般可以分为五个阶段：词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成。每一个阶段在功能上是相对独立的，它一方面从上一个阶段获取分析的结果来进行分析，另一方面由将结果传递给下一个阶段。由编译程序的五个阶段就对应了编译系统的结构。下图给出了编译系统的结构框图：其中词法分析器利用超前搜索、状态转换等方法，将源程序转化成为一个一个的单词符号二元式。一般程序语言的单词符号包括关键字、运算符、常数、标识符和界符。语法分析器将这些单词符号做为输入，对它进行语法分析。语法分析分为两种方法：自上而下分析法和自下而上分析法。针对不同程序语言的语法规则可以采取不同的分析方法，当然两种方法也可以同时使用。语法分析器把语法单元做为输入供语义分析器使用。一般的语义分析器主要采用的是语法制导方法，即在语法分析的同时进行语法分析，并产生一定的语义动作，来表格管理出错处理单词符号语法单元中间代码序中间代码目标代码语法分析器语义分析与中间代码生成器优化器目标代码生成器词法分析器源程序生成中间代码。上面三个过程可以与硬件无关，而接下来的优化器和目标代码生成器是针对某一种处理器而言的。代码优化是将语义分析生成的中间代码进行优化，产生执行效率更高的代码。目标代码生成器最终生成可以在某种机器上运行的机器语言或者汇编语言。在整个编译过程中还包括对表格的操作和对错误的处理，这些也都是非常重要的环节。４.2Flex和Bison的使用编译系统是一个非常复杂的系统，实现起来较困难和繁琐，而且有很多地方只是简单代码的堆积。这些都给编译系统的设计和实现带来很大的不便。为了提高开发的效率和周期，尽量避开词法分析和语法分析，把开发工作集中在语法制导和符号表操作过程中，我决定使用词法分析生成器Flex和语法分析生成器Bison做为编译系统开发的主要工具。5.2.1Flex的介绍FLex是Unix下的一种生成扫描器的工具。它是由Lex（LexicalAnalyzar）发展而来较为高级和常用的词法程序生成器。扫描器是一种识别文本中的词汇模式的程序。这些词汇模式（或者常规表达式）在一种特殊的句子结构中定义。一种匹配的常规表达式可能会包含相关的动作。这一动作可能还包括返回一个标记。当Flex接收到文件或文本形式的输入时，它试图将文本与常规表达式进行匹配。它一次读入一个输入字符，直到找到一个匹配的模式。如果能够找到一个匹配的模式，Flex就执行相关的动作（可能包括返回一个标记）。另一方面，如果没有可以匹配的常规表达式，将会停止进一步的处理，Flex将显示一个错误消息。Flex定义的一套自己的程序格式，用来实现从文法到翻译程序的转换。一般的Flex编程可以分为三步：1．以Lex可以理解的格式指定模式相关的动作。2．在这一文件上运行Lex，生成扫描器的C代码。3．编译和链接C代码，生成可执行的扫描器。除此只为，还可在Flex程序中定义一些附加的C语言程序，来完成用户特殊的要求。5.2.2Bison的介绍Yacc代表YetAnotherCompilerCompiler。Yacc的GNU版叫做Bison。它是一种工具，将任何一种编程语言的所有语法翻译成针对此种语言的Bison语法解析器。它用巴科斯范式(BNF,BackusNaurForm)来书写。按照惯例，Bison文件有.y后缀。编译行如下调用Bison编译器：$bisonoptionsfilenameendingwith.y用Bison来创建一个编译器包括四个步骤：1．通过在语法文件上运行Bison生成一个解析器。2．说明语法：a.编写一个.y的语法文件（同时说明C在这里要进行的动作）。b.编写一个词法分析器来处理输入并将标记传递给解析器。这可以使用Flex来完成。c.编写一个函数，通过调用yyparse()来开始解析。d.编写错误处理例程（如yyerror()）。3．编译Bison生成的代码以及其他相关的源文件。4．将目标文件链接到适当的可执行解析器库。在bison的源程序中也可以定义自己的C代码来完成语法制导和产生中间代码四元式。5.2.3Flex和Bison结合使用一个由Bison生成的解析器调用yylex()函数来获得标记。yylex()可以由Flex来生成或完全由自己来编写。对于由Flex生成的lexer来说，要和Bison结合使用