毕业设计（论文）C Minus 语言分析程序.doc

《毕业设计（论文）C Minus 语言分析程序.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）C Minus 语言分析程序.doc（35页珍藏版）》请在三一办公上搜索。

1、郑州航空工业管理学院毕 业 论 文（设 计）2012 届 网络工程 专业 0810071班级题 目C Minus语言分析程序 姓 名 学号 081007111 指导教师 职称 讲 师 2012 年 5 月 18 日C Minus 语言分析程序081007111 指导教师 内 容 提 要程序设计语言及其编译技术是普及计算机的关键，编译器也是程序员每天使用的工具。尽管编译器相关的各项技术经过近几十年的发展已日臻成熟，然而编译器的构造原理和技术依然是计算机专业人员的必备理论知识之一。本文实现一个编译器项目，即构造一个轻量级的类C语言（即C Minus语言）的分析器。尽管C Minus语言是一个试验项

2、目，但是通过该项目可以掌握基本的程序设计语言分析技术。本项中的C Minus 语言分析程序分两部分，即词法分析和语法分析。作为编译的第一阶段，词法分析器负责将字符流转化为记号流并提交给语法分析使用。语法分析负责分析记号流中的语法结构，为代码生成做好准备。关键字语法分析；BNF范式；词法分析；递归下降分析;创新点 本文的创新点在于通过编写词法分析与语法分析程序来实现C Minus 语言分析程序C Minus Language Analysis ProgramHuang Meng Wang Chu-YangAbstract Programming design language and compi

3、ling theories are critical to the wide application of computers and compilers are also programmers use everyday tools. Although the compiler related all technology and the development of the last several decades has mature gradually, but the compilers structure principle and technology is still comp

4、uter professionals for one of the theoretical knowledge. This paper realize a compiler projects, namely constructing a lightweight class C language (namely C Minus language) analyzer. Although C Minus language is a pilot project, but through this project can grasp the basic programming language anal

5、ysis technique. This project C Minus language analysis program is divided into two parts, namely the lexical analysis and grammatical parser. As the first phase of the compiling phase, lexical analyzer is responsible for changing characters into token flow then and forward tokens to the parser. Gram

6、mar parser responsible for recognizing the grammar structure condtructs, for code generation . Key wordsGrammar analysis; BNF paradigm; Lexical analysis; Recursive descent analysis InnovationThis paper is the innovation points by writing and grammatical analysis program lexical analysis to achieve C

7、 Minus language analysis program 目 录第1章 开发背景- 1 -第2章 词法分析- 1 -2.1目的及意义- 1 -2.2词法分析器的作用- 1 -2.3设计分析- 2 -2.4设计要求- 3 -2.4.1 待分析的简单的词法- 3 -2.4.2 各种单词符号对应的种别码：- 3 -2.4.3 词法分析程序的功能：- 4 -2.5词法分析程序的算法思想- 5 -2.5.1 主程序示意图- 5 -2.5.2 扫描子程序的算法思想：- 6 -2.5.3词法分析程序的C语言代码- 7 -2.6结果分析- 12 -2.7总结- 13 -第3章 语法分析- 14 -3.

8、1语法分析器的作用- 14 -3.2设计分析- 15 -3.3设计要求- 15 -3.3.1 待分析的简单语言的语法- 15 -3.3.2 实验要求说明- 16 -3.3.3 语法分析程序的酸法思想- 16 -3.4语法分析程序的C语言代码- 19 -3.5结果分析- 25 -3.6总结- 26 -第4章 结束语- 27 -致 谢- 28 -参考文献- 29 -C minus 语言分析程序081007111 黄盟 指导教师 王初阳 第1章 开发背景C语言是在70年代初问世的。一九七八年由美国电话电报公司(AT&T)贝尔实验室正式发表了C语言。C语言的表现能力和处理能力极强。它不仅具有丰富的运算

9、符和数据类型，便于实现各类复杂的数据结构。C Minus是一种适合编译器设计方案的语言，它比T I N Y语言更复杂，包括函数和数组。本质上它是C的一个子集，但省去了一些重要的部分，因此得名。编译器是一种相当复杂的程序，其代码的长度可从10000行到1000 000行不等。编写甚至读懂这样的一个程序都非易事，大多数的计算机科学家和专业人员也从来没有编写过一个完整的编译器。但是，几乎所有形式的计算均要用到编译器，而且任何一个与计算机打交道的专业人员都应掌握编译器的基本结构和操作。除此之外，计算机应用程序中经常遇到的一个任务就是命令解释程序和界面程序的开发，这比编译器要小，但使用的却是相同的技术。

10、因此，掌握这一技术具有非常大的实际意义。纵观国外的大型编译器生产商，在不断的完善自己的产品。在自己领先的领域内不断地巩固自己的地位。以VS2010为例，Visual Studio是微软公司推出的开发环境。是目前最流行的Windows平台应用程序开发环境。Visual Studio 2010版本于2010年4月12日上市，其集成开发环境（IDE）的界面被重新设计和组织，变得更加简单明了。Visual Studio 2010同时带来了 NET Framework 4.0、Microsoft Visual Studio 2010 CTP( Community Technology Preview-C

11、TP)，并且支持开发面向Windows 7的应用程序。除了Microsoft SQL Server，它还支持 IBM DB2和Oracle数据库。在Windows平台程序开发环境中，VS目前已经奠定下了强大的基础。 本次毕业设计通过编写词法分析与语法分析程序来实现C Minus 语言分析程序第2章 词法分析2.1目的及意义 词法分析代表了一类问题的集合，即如何对输入字符串中的特定模式进行具备特定动作的匹配。解决此类问题，不仅对于编译器开发中的阶段抽象具有重要意义，更对应用领域中有关字符处理的需求具有深刻价值。设计和实现词法分析器，要用到词素、记号、正则表达式、输入字符双缓冲区、符号表、状态转换

12、图设计等概念。抽象地阐述这些概念往往晦涩难懂，而结合某一具体编译器的前端实现来分析探讨，则容易使概念条理清晰，目的明确。因此，从设计一个轻量级语言开始，根据语言编译的要求设计和实现词法分析器，将原理与实践结合，将是研究此类问题的最佳途径。2.2词法分析器的作用词法分析器的主要任务是读入输入字符，产生记号序列，提交给语法分析使用。这种交互通常可以通过使词法分析器作为语法分析器的子程序或协作程序来实现。如下图所示：词法分析器语法分析器记 号 取下一个记号 符 号 表源程序图2-1 词法分析器与语法分析器的交互 在C的实践中，将词法分析器的主体定义为一个函数，函数声明为token nexttoken

13、()。函数可以又语法分析器调用，返回给语法分析器一个记号。记号类由两个整型值组成，int tokentype表示记号的类型(如ID、NUM、分号、左括号等等)，int lexeme表示记号的属性（用来区分一类记号不同的个体差异。如ID表示标识符，但某一具体标识符的名字，即词素信息，则包含在lexeme中）。语法分析器可以根据返回的记号类型及记号属性，根据语法定义选择合适的产生式进行语法分析。另外，词法分析器还可以发现词法分析阶段源程序词法级错误，并做出相应的错误处理和提示。2.3设计分析设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。2.4设计要求2.4.1 待分析的简单的词法（1

14、）关键字： begin if then while do end所有的关键字都是小写。（2）运算符和界符： = + - * / = = = ; ( ) #（3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义：ID = letter (letter | digit)*NUM = digit digit*（4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。2.4.2 各种单词符号对应的种别码：表2-1 各种单词符号对应的种别码单词符号种别码 单词符号种别码bgin1：17If2：=18Then320wile421do5

15、23lettet（letter|digit）*10=24dight dight*11=25+13；2614(27*15)28/16#02.4.3 词法分析程序的功能：输入：所给文法的源程序字符串。输出：二元组（syn,token或sum）构成的序列。其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。例如：对源程序begin x:=9: if x9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列：(1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)2.5词法分析程序的算法思想算法的基本任务是从字符串表示

16、的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。2.5.1 主程序示意图主程序示意图如图2-2所示。其中初始包括以下两个方面： 关键字表的初值。关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下：Char *rwtab6 = “begin”, “if”, “then”, “while”, “do”, “end”,;置初值调用扫描子程序输出单词二元组输入串结束 否 是结束 图2-2 主程

17、序示意图（2）程序中需要用到的主要变量为syn,token和sum2.5.2 扫描子程序的算法思想：首先设置3个变量：token用来存放构成单词符号的字符串；sum用来整型单词；syn用来存放单词符号的种别码。扫描子程序主要部分流程如图2-3所示。变量初始化忽略空格是否文件结束？ 返回 是 是否字母拼字符串 数字 其他拼数运算符、 符号界符等符号是否关键字？ 否对不同符号给出相应的syn值报错syn=10 是syn=1111syn为对应关键字的单词种别码返回图 2-3 扫描子程序2.5.3词法分析程序的C语言代码#include #include #include#include Char p

18、rog80, token8, ch;int syn, p, m, n, sum;char *rwtab6=begin,if,then,while,do,end;void scaner();void main()int p=0;printf(n please input a string(end with #):/n);doscanf(%c, &ch);progp+=ch;while(ch! = #);p=0;doscaner();switch(syn) case 11:printf( %-10d%5d )n, sum, syn);break;case -1:printf(you have in

19、put a wrong stringn);getch();exit(0);default: printf( %-10s%5d )n, token, syn);break; while(syn != 0);getch(); void scaner() sum=0;for(m=0;m8; m+)tokenm+=NULL;ch=progp+;m=0;while(ch = )|(ch = n)ch=progp+;if(ch = a)|(ch = A) while(ch=a)|(ch=A)|(ch=0)&(ch=9) tokenm+=ch;ch=progp+; p-;syn=10;for(n=0;n=

20、0)&(ch = 0)&(ch = 9) sum = sum*10+ch-0;Ch = progp+; p-;syn = 11; else switch(ch) case :tokenm+ = ch;ch=progp+;if(ch = =) syn=24;tokenm+ = ch; else syn = 23;p-; break;case +: tokenm+ = ch;ch = progp+;if(ch = +) syn = 17;tokenm+ = ch; else syn = 13;p-; break;case -:tokenm+ = ch;ch = progp+;if(ch = -)

21、syn = 29;tokenm+ = ch; else syn = 14;p-; break;case !:ch=progp+;if(ch= = =) syn=21;tokenm+=ch; else syn=31;p-; break;case =:tokenm+=ch;ch=progp+;if(ch=) syn=25;tokenm+=ch; else syn=18;p-; break;case *: syn=15;tokenm+=ch;break;case /: syn=16;tokenm+=ch;break;case (: syn=27;tokenm+=ch;break; case ): s

22、yn=28;tokenm+=ch;break; case : syn=5;tokenm+=ch;break; case : syn=6;tokenm+=ch;break;case ;: syn=26;tokenm+=ch;break;case : syn=30;tokenm+=ch;break;case #: syn=0;tokenm+=ch;break;case :syn=17;tokenm+=ch;break;default: syn=-1;break; tokenm+=0; 2.6结果分析输入begin x:=9: if x9 then x:=2*x+1/3; end # 后经词法分析输

23、出如下序列：(begin 1)(x 10)(：17)(= 18)(9 11)(；26)(if 2) 如图2-4所示图2-4 运行结果2.7总结词法分析的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。通过本试验的完成，更加加深了对词法分析原理的理解。 第3章 语法分析3.1语法分析器的作用 在编译器中，语法分析器接受词法分析器提供的记号串，检测它们能否由源程序语言的文法产生，如下图3-1所示，词法分析器语法分析器记 号取下一个记号符 号 表源程序语法树前端的其余部分中间表示图3-1 语法分析器在编译器中的位置

24、典型的文法的语法分析器有三类。一类是通用的语法分析方法，如Cocke-Younger-Kasami算法和Earley算法，这些方法能分析任何文法。然而这些方法在生成编译器时的效率太低。编译器常用的是自顶向下和自底向上的方法。正如其名，自顶向下语法分析器沿着从根向叶的方向建立分析树，而自底向上语法分析器则沿着从叶向根的方向建立分析树。不论采用哪一种方法，语法分析器都是自左向右地扫描输入记号流，每一步匹配一个记号。最有效的自顶向下和自底向上分析方法只能处理文法的一些子类。然而这些子类中的某些文法，如LL文法和LR文法，足以描述程序设计语言的大部分语法结构。LL文法的语法分析器常由手工实现，大多数L

25、R文法的语法分析器则常利用自动生成工具来构造。本文重点讨论基于LL文法手工构造语法分析器的原理和相关的实践细节。本文假设语法分析器的输出是对词法分析器产生的记号流的分析树的某种表示。事实上，在分析过程中编译器还可以同时完成很多其他任务。例如，把与各种记号有关的信息收集到符号表中、进行类型检查和其他一些语义分析检查、产生中间代码等等。语法分析器相当于一个框架，我们可以遍历这个体现了语言结构的框架，并在遍历的过程中实现相应的功能。在实践中，为了追求效率，通常在语法分析的过程中不显式构造分析树。语法分析器中程序的流向本身就是遍历分析树的过程。不显式构造分析树的好处，在于能够把语法分析，语义分析，类型

26、检查，中间代码生成集成为一遍，既节省空间又节省时间。3.2设计分析编制一个递归下降分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。3.3设计要求利用C语言编制递归下降分析程序，并对简单语言进行语法分析。3.3.1 待分析的简单语言的语法用扩充的BNF表示如下：=beginend：=；：=：=ID：=：=+ | -：=* | /：=ID | NUM | （）3.3.2 实验要求说明输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印“success”，否则输出“error”。例如： 输入 begin a:=9; x:=2*3; b:=a+x end # 输出 s

27、uccess！ 输入 x:=a+b*c end # 输出 error3.3.3 语法分析程序的酸法思想（1）主程序示意图如图3-2所示。置初值调用scaner读下一个单词符号调用lrparser结束图3-2 语法分析主程序示意图（2）递归下降分析程序示意图如图3-3所示。（3）语句串分析过程示意图如图3-4所示。是否begin?调用statement函数否是调用scaner是否 ；?否调用语句串分析程序是 调用scaner是否end? 否调用statement函数是调用scaner出错处理syn=0&kk=0?否 图3-4 语句串分析示意图出错处理 是 打印分析成功图3-3 递归下降分析程序示

28、意图 （4）statement语句分析程序流程如图3-5、3-6、3-7、3-8所示。是否标识符?调用term函数否调用scaner是否：=?调用scaner调用expression函数是否+ , -?否否是调用scaner调用term函数出错处理出错处理图3-5 statement语句分析函数示意图 图3-6 expression表达式分析函数示意图调用factor函数是否* , /?调用scaner调用factor函数出错处理是否标识符?是否否是否整常数?是是否是否（?否是调用scaner是否）?调用expression函数图 3-7 term分析函数示意图否出错处理是调用scaner调用

29、scaner图3-8 factor分析过程示意图3.4语法分析程序的C语言代码#include stdio.h#include string.hchar prog100,token8,ch;char *rwtab6=begin,if,then,while,do,end;int syn,p,m,n,sum;int kk;factor();expression();yucu();term();statement();lrparser();scaner();main()p=kk=0;printf(nplease input a string (end with #): n);do scanf(%c,

30、&ch);progp+=ch; while(ch!=#);p=0;scaner();lrparser();getch();lrparser()if(syn=1) scaner(); /*读下一个单词符号*/yucu(); /*调用yucu()函数；*/if (syn=6) scaner();if (syn=0)&(kk=0)printf(success!n);else if(kk!=1) printf(the string havent got a end!n);kk=1; else printf(havent got a begin!n);kk=1; return;yucu() statem

31、ent(); /*调用函数statement();*/while(syn=26) scaner(); /*读下一个单词符号*/if(syn!=6) statement(); /*调用函数statement();*/ return;statement() iif(syn=10) scaner(); /*读下一个单词符号*/if(syn=18) scaner(); /*读下一个单词符号*/expression(); /*调用函数statement();*/ else printf(the sing := is wrong!n);kk=1; else printf(wrong sentence!n)

32、;kk=1; return;expression() term();while(syn=13)|(syn=14) scaner(); /*读下一个单词符号*/term(); /*调用函数term();*/ return;term()factor();while(syn=15)|(syn=16) scaner(); /*读下一个单词符号*/factor(); /*调用函数factor(); */ return;factor() if(syn=10)|(syn=11) scaner();else if(syn=27) scaner(); /*读下一个单词符号*/expression(); /*调用

33、函数statement();*/if(syn=28) scaner(); /*读下一个单词符号*/else printf(the error on (n);kk=1; else printf(the expression error!n);kk=1; return;scaner() sum=0;for(m=0;m8;m+)tokenm+=NULL;m=0;ch=progp+;while(ch= )ch=progp+;if(ch=a)|(ch=A) while(ch=a)|(ch=A)|(ch=0)&(ch=9) tokenm+=ch;ch=progp+; p-;syn=10;tokenm+=0

34、;for(n=0;n=0)&(ch=0)&(ch=9) sum=sum*10+ch-0;ch=progp+;p-;syn=11; else switch(ch) case ) syn=21; else if(ch = =) syn=22; else syn=20;p-; break;case : m=0;ch=progp+;if(ch=) syn=24; else syn=23;p-; break;case : m=0;ch=progp+;if(ch=) syn=18; else syn=17;p-; break;case +: syn=13; break;case -: syn=14; br

35、eak;case *: syn=15; break;case /: syn=16; break;case (: syn=27; break;case ): syn=28; break;case =: syn=25; break;case ;: syn=26; break;case #: syn=0; break;default: syn=-1; break; 3.5结果分析输入 begin a:=9; x:=2*3; b:=a+x end # 后输出success！ 如图3-9所示：图3-9 正确运行结果输入 x:=a+b*c end # 后输出 error 如图3-10所示：图3-10 错误

36、运行结果3.6总结通过本次试验，了解了语法分析的运行过程，主程序大致流程为：“置初值”调用scaner函数读下一个单词符号调用IrParse结束。递归下降分析的大致流程为：“先判断是否为begin”不是则“出错处理”，若是则“调用scaner函数”调用语句串分析函数“判断是否为end”不是则“出错处理”，若是则调用scaner函数“判断syn=0&kk=0是否成立”成立则说明分析成功打印出来。不成立则“出错处理”。 第4章 结束语本次开发设计是对C语言课程、数据结构、编译原理等一系列的课程的回顾学习。在开发基于C语言小型编译器中，还是用系统分析、系统设计的思路。一个好的系统分析、设计工作，会使以后的系统实施顺利高效的进行，从而达到事半功倍的效果，这也是我的一点心得体会吧。本毕业设计程序界面十分简便，在对C语言语法理解的基础上，建立一个能够既能够分