递归分析器的自动生成论文.docx
- 文档编号:16915596
- 上传时间:2023-07-19
- 格式:DOCX
- 页数:27
- 大小:142.17KB
递归分析器的自动生成论文.docx
《递归分析器的自动生成论文.docx》由会员分享,可在线阅读,更多相关《递归分析器的自动生成论文.docx(27页珍藏版)》请在冰点文库上搜索。
递归分析器的自动生成论文
目录
前言3
第一章绪论4
1.1研究背景及意义4
1.2自动生成系统概述5
1.3本文的主要工作和创新点7
1.4本文的主要组织结构7
第二章自动生成系统9
2.1自动生成系统的分类9
2.2研究现状分析10
2.2.1Yacc10
2.2.2Lex13
2.3本章小结14
第三章递归下降分析法15
3.1语法分析15
3.1.1自顶向下分析法15
3.1.2自底向上语法分析方法16
3.2递归下降分析法18
3.3本章小结19
第四章递归下降分析器的自动生成系统20
4.1递归分析器的自动生成系统的工作模式及主要算法20
4.2各模块的主要功能21
4.3存在的问题22
第五章总结和展望23
5.1本文总结23
5.2后续工作和展望23
参考文献24
致谢26
摘要
编译程序是语言处理程序的一种,它通常由词法分析,语法分析,语义分析,中间代码生成,代码优化和目标代码生成五个阶段组成。
随着高级语言的出现,如何提高编译程序研制效率成为编译程序设计的重要环节之一。
在第一批编译程序问世不久,一些称为编译器的编译器或编译器的生成器软件相继产生,但它们大多是用面向某一特定语言的翻译器编写系统,缺乏统一性。
在20世纪70年代由BELL实验室提出的词法分析器LEX和语法分析器YACC在各种编译程序的实践中得到了广泛的应用。
本文主要研究是的递归分析器的自动生成系统,是通过递归子程序的方法,根据高级语言的巴科斯范式形式的文法自动生成一个分析器。
关键词:
递归下降;自动生成;语法分析器
Abstract
Thecompilerisalanguageoflanguageprocessingprogram,Itusuallyconsistsoflexicalanalysis,syntaxanalysis,semanticanalysis,intermediatecodegeneration,codeoptimizationandobjectcodegeneration.
Withtheemergenceofhigh-levellanguage,Howtoimprovetheefficiencyofthedevelopmentofacompilerdesignisoneofthemostimportantparts.Inthefirstbatchcompilersoon,Somecalledcompiler’scompilerorcompilergeneratorsoftwareproducedinsuccessionor,buttheyaremostlyusedforaparticularlanguagetranslatorwritingsystem,itlackofunity.Inthenineteenseventies,theLexicalanalyzer-lexandSyntaxanalyzer-yaccbytheBELLlaboratoryhasbeenwidelyusedin,inthevariouscompilerpractices.
ThissystemisconvertedtoformbytheBNFgrammartheparserautomaticallygeneratedbasedonrecursivesubroutinetechnologysystems.
Keywords:
Recursivedescent;Auto-generated;syntaxanalysis.
前言
软件开发从手工编写到自动生成,是软件开发产业化的重要进程,也是很多人花费很多精力所研究的内容。
人们利用计算机软件与硬件实现办公自动化、管理自动化的同时,也在考虑程序代码的自动生成。
早在20世纪50年代,IBM的JohnBackus带领一个研究小组对FORTRAN语言及其编译器进行开发。
但由于当时人们对编译理论了解不多,开发工作变得既复杂又艰苦。
与此同时,NoamChomsky开始了他对自然语言结构的研究。
他的发现最终使得编译器的结构异常简单,甚至还带有了一些自动化。
自动生成技术一直是人们追求和发展的方向之一,从目前的情况来看,软件开发的速度缓慢、代价高昂而又极易出错,常常会生产出存在大量缺陷的产品,在可用性、可靠性、性能、安全以及其他服务质量方面造成严重的问题。
怎样才能提供足够多的软件开发能力呢?
不用太多的分析就可以看出,必须对软件开发的方法和实践进行显著的改变。
就软件行业的机械化生产而言,就是自动生成技术。
本文主要研究是的递归分析器的自动生成系统,是通过递归子程序的方法,根据高级语言的巴科斯范式形式的文法自动生成一个分析器。
本文共分为五章。
第一章:
绪论本章介绍了课题的研究背景及意义;第二章主要介绍了递归下降分析法,分析了自底向上和自顶向下两种语法分析方法;第三章:
自动生成系统,阐述了现有的自动生成系统技术及其原理;第四章:
主要介绍了递归下降分析器的自动生成系统,对实验过程及结果进行描述;第五章:
总结全文,提出未来工作的设想与展望。
第一章绪论
本章首先介绍了自动生成技术的研究背景和意义,其次简单介绍了递归分析器的自动生成系统的组成部分和作用,并概述了本文所做的主要工作和贡献以及创新点,在本章的最后介绍了论文的组织结构。
1.1研究背景及意义
随着现代化信息环境日趋复杂,各种应用软件的开发难度随之加大,这需要更有技巧、更有方法地从事软件开发。
开发团队之间也必须更无障碍地沟通,否则极可能无法在有限的开发时间中完成任务。
由于时间上的压力,一般人只注重程序的编写速度,却忽略其完成后的实用性与维护性,加上大型程序多人共同参与开发,每个人都有各自的程序风格,容易造成严重的差异性,随着系统规模越来越大,这将造成系统完成后在测试及维护上沉重的负担。
因此,代码自动生成技术更显出了其显著的优越性。
尽管这些应用没有代码生成工具也能开发完成,但利用代码生成技术可以大大加速软件的开发进度,提高软件的质量。
可是,怎样才能提供足够多的软件开发能力呢?
不用太多的分析就可以看出,必须对软件开发的方法和实践进行显著的改变。
对于其他行业来说,提高生产能力的途经主要通过从手工作业过渡到机械生产。
在手工作业阶段,所有产品都是由个人或小组从无到有制造出来的,而在机械生产阶段,各种产品通过组装多家供应商生产的可重复利用的组件迅速生产出来,在这个过程中,许多机械琐碎的任务都是由机器自动完成的。
这些行业对工艺、设计和包装进行标准化,借助产品线实现系统性重复利用,并通过供应链分担成本和风险。
现在已有部分行业可以实现大规模定制,根据需求快速而经济地制造出各种产品,以满足不同客户的特定要求。
对于软件行业来说,机械化生产就是自动生成技术。
代码生成技术是关于自动生成程序的程序的技术。
其代码的质量只依赖于代码生成的模板、文件和模型。
因此提高了代码变更的能力,特别在需要大量更改代码的情况下,只需要更改模板并重新运行代码生成器即可。
尤其是大幅度提高了工作效率,因为运用代码生成技术可以将更多的时间花费在业务相关的设计和实现上,从而可以大大提高软件的开发效率和软件质量。
图1.1代码生成工作流程
从图1.1不难看出,因为在程序开发过程中加入的两个步骤,以及模版的使用,使得程序的机械化生成成为可能,为软件开发的产业化进程提供一个有力的支持,这就是本文所讨论的自动生成技术的意义所在。
1.2自动生成系统概述
图1.2典型的代码生成器模型
代码生成器的作用是读取工程的元数据,按照指定的设计模式,混合产生出规范的源代码。
典型的代码生成器模型如图1.2所示。
在图中,为自动生成程序代码,必需的三个关键要素是设计模式(所产生代码的模板文件)、领域元数据(在代码中需建模的拓扑结构,即定义文件,通常随开发折提供的特定数据增长)。
构建自己的代码生成器有2种方法,一是综合利用流行的代码生成器。
构建出适合自己的代码生成器;另一种方法是构造出一个全新的代码生成器。
无论哪种方法,在构建代码生成器都应该注意下面几个方面。
(1)使用纯文字样版,使用纯文字样版的好处除了编辑方便外,也能将程序代码定义逻辑和格式化逻辑分隔开来,使实作上更有弹性。
(2)编写正规表达式(RegularExpression),正规表达式是一种字符串的表示方式,使用它不仅扩大了字符串的表达能力,让使用者很容易进行字符串判断,也可避免撰写程序进行复杂字符串解析的麻烦,也自然使得数据处理的过程变得更为迅速便利。
(3)编译器原理,在对于文本文件的处理上,先利用扫描器(Scanner)扫描出其中的字符,再实作解析器(Parser)解析出所对应的语法,然后转换成所要产生的程序语
(4)文档输出入的处理,由于程序产生牵涉到大量的文档读写动作,需要定义合适的数据结构及缓冲区机制来提升文档存取的效率,另一方面来说,在编写样版文档时也需考量到对于存取效率上的负担[2]
代码生成技术是关于自动生成程序的程序的技术。
与手工书写代码相比,代码生成器提供了下面的一些好处:
(1)所有软件实体的一致的代码质量,代码的质量依赖且只依赖于代码生成的模板、文件和模型。
与此相比,手工经常采用的拷贝粘贴的方法为前后代码质量的一致性带来了隐患。
(2)提高了代码变更的能力,特别在需要大量更改代码的情况下,只需要更改模板并重新运行代码生成器即可。
(3)提高了修复软件Bug的能力,只需要修复模板的Bug然后重新运行生成器就可以修复所有的生成文件的Bug。
(4)提高了在不同框架之间的迁移能力,一个典型的情形是我们需要生成不同框架(如J2EE/.Net)的应用代码,代码生成技术将业务逻辑以语言无关的形式单独存放,通过为不同的框架提供代码模板可以基于同一逻辑生成不同框架的应用代码。
(5)灵活的同步机制,代码生成技术自动维护代码和数据模型的一致性,通过重新运行生成器,对模型的修改可以自动反映到代码中,这种同步机制对维护数据的一致性是非常必要的。
(6)大幅度提高了工作效率,运用代码生成技术可以将更多的时间花费在业务相关的设计和实现上,从而可以大大提高软件的开发效率和软件质量。
(7)是代码学习的导师,由于生成的代码具有良好的风格和100%的健壮性,程序开发者很容易模仿代码风格,从中学习。
1.3本文的主要工作和创新点
本文主要以递归下降分析器的自动生成系统为研究点,参考和对比一些其他的自动生成系统。
在深入了解递归下降分析法的基础上,结合代码自动生成技术,完成自动生成系统的设计与实现。
本文主要工作和创新点如下:
(1)通过自己定义C语言子集中的终结符和非终结符,完成对输入的巴科斯范式形式文法的规定,为下面的词法分析做准备。
(2)通过一定的词法分析程序,对输入文法进行分析,判断其中的终结符和非终结符。
(3)相比其他的分析器,本文研究的主要是基于递归下降分析法的自动生成系统的实现,所以是要基于递归下降分析法,对判断出的每一个非终结符生成相应的描述其右部结构的递归子程序的一种分析器的自动生成。
(4)将所生产的代码,以一定的方式整合过后,以文本的形式输出。
相比本文所研究的递归下降分析器的自动生成系统,BELL实验室也有过类似的自动生成系统的实现,就是Yacc(YetAnotherCompilerCompiler)。
Yacc的输入是巴科斯范式(BNF)表达的语法规则以及语法规约的处理代码,Yacc输出的是基于表驱动的编译器,包含输入的语法规约的处理代码部分。
Yacc是开发编译器的一个有用的工具,采用LALR
(1)语法分析方法。
Yacc最初由AT&T的StevenC.Johnson为Unix操作系统开发,后来一些兼容的程序如BerkeleyYacc,GNUbison,MKSyacc和Abraxasyacc陆续出现。
它们都在原先基础上做了少许改进或者增加,但是基本概念是相同的。
1.4本文的主要组织结构
本文共分为五章,各章内容安排如下:
第一章:
绪论。
本章介绍了课题的研究背景及意义、自动生成系统的概述、本文的主要工作及主要创新点,最后介绍了本文的组织结构。
第二章:
自动生成系统。
本章详细阐述了现有的自动生成系统技术及其原理,对比分析了各种技术的详细内容。
第三章:
主要介绍了递归下降分析法,深入分析了自底向上和自顶向下两种语法分析方法,以及LR(0)、SLR
(1)、LALR
(1)和LR
(1)四种分析方法的简述。
第四章:
主要介绍了递归下降分析器的自动生成系统,对其工作原理,以及各部件的主要功能给出了介绍,并总结了一下其中的不足。
第五章:
总结全文,提出未来工作的设想与展望。
第2章自动生成系统
本章首先简单介绍了自动生成系统的分类,继而研究了一下目前的技术现状,对目前比较成熟的语法分析自动生成器Yacc以及词法分析自动生成器Lex进行了简单描述。
2.1自动生成系统的分类
在技术领域一般我们可以将代码生成技术分为两大类:
被动模式和主动模式。
如图2.1所示,在被动模式下,代码生成器产生一系列的代码,然后软件开发者可以自由的修改、编辑这些代码,但代码生成器不再承担对代码的维护工作。
被动模式的代码生成技术有其应用的范围,但是被动模式的生成系统有天生的局限性。
生成器只运行一次,然后就不再承担对代码的维护工作。
与此相反,主动模式下的代码生成器则对生成的代码“长期”负责,可以通过改变生成器的输入参数并重新运行生成器来改变输出的代码。
如编译器生成器就是一种主动模式的代码生成器。
图2.1代码生成技术的两种模式
下面我们介绍几种常见的代码生成技术
(1)代码挑拣器,代码挑拣器的输入是源代码,通过拣取需要的信息可以生成各种文件,代码挑拣器的使用相当广泛,可以使用它来生成代码API文档(最著名的就是JavaDoc了)、获取常量和函数原型等。
(2)内联代码扩展器,内联代码扩展器的输入是带有特殊标记的源代码,这些特殊标记经过扩展器的处理后将被替换为相关的代码从而产生最终的生产源代码,内联代码扩展器的典型应用是将SQL语句嵌入到源代码中,其主要特点是使得底层结构和复杂的查询分开。
(3)混合代码生成器混合代码生成器与内联代码扩展器很像,它也是处理源代码中的特殊注释但是与内联代码扩展器不同,它的结果将直接输出到输入的源代码中。
这种方式的一个典型应用就是在对话框控件和它们代表的变量之间建立映射关系。
(4)部分类生成器部分类生成器的输入是模板文件和包含特定类所需信息的定义文件,这些信息经过生成器将产生应用的基类。
通过继承该基类可以完成剩余的工作。
Velocity是一个源代码开放的Java模版引擎。
(5)层第生成器层第生成器将生成一个多层应用的所有代码。
模型驱动的开发是这种生成器的一个很好例子。
通过UML模型输入和其余XML文件,生成器能够生成一个包含多个系统的完整应用,并且模型和代码之间可以单向乃至双向同步。
(6)完全领域语言完全领域语言是一个图灵完全的语言,可以直接使用来进行领域相关的操作。
一个典型的例子是Mathematica所使用的数学语言它可以简单的完成对矩阵运算的所有操作。
[2]
2.2研究现状分析
就目前而言,已有的自动生成系统五花八门,有网页的自动生成系统,软件的自动生成系统,而与本文研究方向相同的编译器的自动生成系统也有了一些。
像BELL实验室所研发的Yacc以及Lex。
本文研究的递归下降分析器的自动生成系统也参考了部分Yacc的实现方法。
2.2.1Yacc
Yacc工具是一种语法分析程序生成器,它可以将有关某种语言的语法说明书转换成相应的语法分析程序,由该程序完成对相应语言中语句的语法分析工作。
(1)Yacc程序结构
在使用Yacc工具前,必须首先编写Yacc程序,因为有关语法分析程序是根据Yacc程序生成的。
Yacc程序实际上是有关语法规则的说明书,它也是由定义部分、规则部分和子程序部分组成的。
Yacc程序的定义部分类似于Lex程序的定义部分,只是在其后可带有Yacc声明,其中包括词法单词、语法变量、优先级和结合性信息。
Yacc程序的规则部分由语法规则和相应的动作组成,子程序部分可以包括在前面规则部分用到的子程序定义。
接下来是main主程序,它调用yyparse子程序来对输入进行语法分析,而yyparse反复地调用yylex子程序来获得输入单词,在语法出错时可通过yyerror子程序来处理。
(2)Yacc工具的使用方法
实例:
我们将Yacc程序分成片段,把这些片段组合在一起就是Yacc程序。
我们要使用的语法规则是一个有关四则运算的语法规则,可用BNF范式描述
list:
expr/n
listexpr/n
expr:
NUMBER
expr+expr
expr-expr
expr*expr
expr/expr
(expr)
其含义是list是一个表达式序列,每个后面带有一个新行。
表达式是一个数值,或是由运算符连起来的两个表达式,以及用圆括号括起来的表达式。
下面是有关上述语法规则的yacc程序片段。
$vihoc.y
%{
#defineYYSTYPEdouble
%}
%tokenNUMBER
%left'+''-'
%left'*''/'
%%
list:
|list'/n'
|listexpr'/n'{printf("/t%.8g/n",$2);}
;
expr:
NUMBER{$$=$1;}
|expr'+'expr{$$=$1+$3;}
|expr'-'expr{$$=$1-$3;}
|expr'*'expr{$$=$1*$3;}
|expr'/'expr{$$=$1/$3;}
|'('expr')'{$$=$2;}
%%
上述Yacc程序片段实际上是它的定义部分和规则部分。
在Yacc声明部分,%tokenNUMBER表明了NUMBER是一个单词符号,%left则表明了运算符号的左结合性,并且'*'和'/'和优先级比'+'和'-'的优先级高。
在Yacc程序的规则部分,备用规则是用'|'隔开的,规则中的动作实际上是C语句序列,其中$n(即$1,$2等)是用来引用规则中的第几个成份,而$$则代表了整个规则的返回值。
下面的Yacc程序片段是main主程序
#include
#include
char*progname;
intlineno=1;
main(argc,argv)
intargc;
char*argv[];
{progname=argv[0];
yyparse();
}
main主程序调用yyparse子程序来处理输入,而yyparse又是通过yylex子程序来获得输入单词并通过yyerror子程序来报告出错信息。
下面是有关这两个子程序的yacc程序片段
yylex()
{intc;
while((c=getchar())==''||c=='/t');
if(c==EOF)
return0;
if(c=='.'||isdigit(c)){
ungetc(c,stdin);
scanf("%lf",&yylval);
returnNUMBER;
}
if(c=='/n')
lineno++;
returnc;
}
yyerror(s)
char*s;
{warning(s,(char*)0);
}
warning(s,t)
char*s,*t;
{fprintf(stderr,"%s:
%s",progname,s);
if(t)
fprintf(stderr,"%s",t);
fprintf(stderr,"nearline%d/n",lineno);
}
这样就完成了整个Yacc程序,接下来就使用Yacc将hoc.y转换成C语言程序:
$yacchoc.y
使用上述命令产生的C语言程序为y.tab.c,这时可以使用C编译程序将它编译成可执行程序hoc.
$ccy.tab.c-ohoc[3]
2.2.2Lex
Lex(LEXicalcompiler)是一个词法分析器(扫描器)的自动产生系统,它的示意图如图2.2所示。
图2.2lex示意图
Lex源程序是一种面向问题的语言写成的,这个语言的核心是正规表达式,用它描述输入串的词法结构。
在这个语言中用户还可以描述当某一个词形被识别出来时要完成的动作,例如在高级语言的词法分析中,当识别出一个关键字时,它应该向语法分析器返回该关键字的内部编码。
Lex并不是一个完整的语言,它只是某种高级语言的扩充,因此lex没有为描述动作设计新的语言,而是借助其宿主语言来描述动作。
Lex自动地把表示输入串词法结构的正规式及相应的动作转换成一个宿主语言的程序,即词法分析程序,它有个固定的名字yylex,在这里yylex是一个C语言的程序。
yylex将识别出输入串中的词形,并且在识别出某词形时完成指定动作。
2.3本章小结
就目前来看,已经有很多人在自动生成系统方面有了各种各样的尝试,但是不难看出,在这方面的发展还是不甚成熟的,Yacc的使用略显复杂,需要对其规则有一些了解才能上手,其对于输入文法的规则也比较严苛,而Lex则显得不那么完善,只是一个对于词法分析器的自动生成系统,所以,在这方面还是有很大的发展空间的。
这也是本文所研究的意义所在。
第3章递归下降分析法
语法分析是编译程序的核心部分。
语法分析的任务就是按照语言既定的语法规则对单词串形式的源程序进行语言检查,并识别出相应的语法成分。
本章对目前常用的语法分析方法自顶而下的分析方法和自底向上的分析方法,进行了相关描述。
3.1语法分析
语法分析是编译原理的核心部分。
语法分析的任务就是按照语言既定的语法规则对单词串形式的源程序进行语言检查,并识别出相应的语法成分,(即给定文法的正确句子或程序)。
目前语法分析常用的方法有自顶向下分析和自底向上分析两大类。
自顶向下分析包括确定分析和不确定分析,自底向上分析又包括算符优先分析法和LR分析,这些分析方法各有优缺点。
下面分别就自顶向下语法分析方法和自底向上语法分析方法展开描述.
3.1.1自顶向下分析法
自顶向下分析法也称面向目标的分析方法,也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子,若输入串是给定文法的句子,则必能推出,反之必然出错。
自顶向下的确定分析方法需对文法有一定的限制,但由于实现方法简答、直观,便于手工构造或自动生成语法分析器,因而仍是目前常用的方法之一。
而自顶向下的不确定分析方法是带回溯的分析方法,这种方法实际上是一种穷举的试探方法,因此效率低,代价高,因而极少使用。
自顶向下的确定分析方法,是从文法的开始符号出发,考虑如何根据当前的输
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 递归 分析器 自动 生成 论文