二---十进制的语法分析及语义分析程序设计(算符优先分析法)

武汉理工大学《编译原理》课程设计1/18Ni学号：0121210680***课程设计题目二---十进制的语法分析及语义分析程序设计（算符优先分析法）学院计算机科学与技术学院专业软件工程班级软件sy1201班姓名***指导教师饶文碧2015年1月14日武汉理工大学《编译原理》课程设计2/18课程设计任务书学生姓名：***专业班级：软件sy1201班指导教师：饶文碧工作单位：计算机科学与技术学院题目:二-十进制的语法分析及语义分析程序的设计1．目的通过设计、编制、调试一个语**法及语义分析程序，加深对语法及语义分析原理的理解。2.设计内容及要求设计一个二-十进制的语法分析及语义分析程序。（1）选择算符优先分析法完成以上任务。（2）写出符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。（3）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。3.课程设计进度安排序号阶段内容所需用时间1给出语法分析方法及中间代码形式的描述、文法和属性文法的设计；或者词法分析方法及符号表和TOKEN代码的设计。1天2简要的分析与概要设计、算法设计与程序设计3天3撰写课程设计报告书1天合计5天武汉理工大学《编译原理》课程设计3/18目录目录..................................................................................................................................................31.系统描述.............................................................................................................41．2设计内容及步骤.....................................................................................42．翻译方法概述...................................................................................................42.1词法分析...................................................................................................42.2语法分析..................................................................................................52.3中间代码生成...........................................................................................52.4属性文法...................................................................................................53．算符优先分析法...............................................................................................64．文法...................................................................................................................74.1文法形式...................................................................................................74.2文法分类...................................................................................................74.3类型说明...................................................................................................75.系统的详细设计...............................................................................................85.1文法设计..................................................................................................85.2构造算符优先关系矩阵...........................................................................95.3算法设计...................................................................................................95.4运行结果................................................................................................146.总结及体会.......................................................................................................157.源代码.............................................................................................................16武汉理工大学《编译原理》课程设计4/18二-十进制的语法分析及语义分析程序设计----算符优先分析法1.系统描述通过设计、编制、调试一个二-十进制的语法分析及语义分析程序，加深对语法及语义分析原理的理解。1．2设计内容及步骤（1）设计算符优先文法：G=（Vn,Vt,P,S）（2）构造算符优先关系矩阵（3）设计语法分析程序，对输入的数据进行语法分析（4）将输入的合法二进制数转化为十进制数2．翻译方法概述2.1词法分析词法分析是计算机科学中将字符序列转换为单词（Token）序列的过程。进行语法分析的程序或者函数叫作词法分析器（Lexicalanalyzer，简称Lexer），也叫扫描器（Scanner）。词法分析器一般以函数的形式存在，供语法分析器调用。词法分析是编译过程中的第一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。简化设计、改进编译效率、增加编译系统的可移植性。词法分析是编制一个读单词的过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。单词的分类主要分为五类：1.关键字：由程序语言定义的具有固定意义的标识符。也称为保留字或基本字。2.标识符：用来表示程序中各种名字的字符串。3.常数：常数的类型一般有整型、实型、布尔型、文字型。武汉理工大学《编译原理》课程设计5/184.运算符：如+、－、*、/等。5.界限符：如逗号、分号、括号等。由于该程序不需进行词法分析，故在设计程序时省去了词法分析这一步骤。2.2语法分析语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等。语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述。语法分析器（Parser）通常是作为编译器或解释器的组件出现的，它的作用是进行语法检查、并构建由输入的单词组成的数据结构（一般是语法分析树、抽象语法树等层次化的数据结构）。语法分析器通常使用一个独立的词法分析器从输入字符流中分离出一个个的“单词”，并将单词流作为其输入。实际开发中，语法分析器可以手工编写，也可以使用工具（半）自动生成。语法分析器的任务主要是确定是否可以以及如何从语法的起始符号推导出输入符号串（输入文本）。2.3中间代码生成中间代码，也称中间语言，是复杂性介于源程序语言和机器语言的一种表示形式。为了使编译程序有较高的目标程序质量，或要求从编译程序逻辑结构上把与机器无关和与机器有关的工作明显的分开来时，许多编译程序都采用了某种复杂性介于源程序语言和机器语言之间的中间语言。中间代码（语言）是一种特殊结构的语言，编译程序所使用的中间代码有多种形式。按其结构分常见的有逆波兰式（后缀式）、三地址代码（三元式、四元式）和树形表示（抽象语法树）、DAG表示。2.4属性文法对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。所谓语法制导的翻译指的是在语法分析过程中，完成这些语义规则描述的动作，从而武汉理工大学《编译原理》课程设计6/18实现语义处理。一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上。3．算符优先分析法算符文法：即它的任一产生式的右部都不含两个相继的非终结符的文法。如果G是一个不含空字符的算法文法，那么只要它的任一对终结符都之多只满足，=，的关系的其中一种，则称G是一个算符优先文法。p=!--的关系的一种，则称G是一个算符优先文法。对于一个算符优先文法，只要能够造出它的算符优先表，就可以利用算符优先分析方法，分析一个句子是否符合这个文法的定义。那么定义FirstVT(P)={a|P-a、、、或P-Qa、、、，a属于终结字符集，而Q属于非终结字符集}LastVT（P）={a|P-...a或P-...aQ，a属于终结字符集，而Q属于非终结字符集}由以下两条规则来构造FirstVT集：(1)若有产生式P-〉a…、或P-Qa…，则a属于FirstVT（P）；(2)若有a属于FirstVT（Q），且有产生式P-〉Q…，则a属于FirstVT(P);类似的有构造LastVT集的规则：(1)若有产生式P-…a或P-…aQ，则a属于LastVT集。(2)若a属于LastVT（Q），且有产生式P-〉…Q，则a属于LastVT集。假定Ｇ是一个不含空字符产生式的算符文法。对于任何一对终结符ａ,ｂ,(1)a=b,当且仅当Ｇ中含有形如Ｐ－…ab…或Ｐ－…aQb…的产生式；(2)ab,当且仅当Ｇ中含有形如Ｐ－…aR…的产生式,而Ｒ－〉ｂ…或Ｒ-Qb…；(3)ab,当且仅当Ｇ中含有形如Ｐ－…Rb…的产生式,而Ｒ－…a或Ｒ-…aQ；这样再结合上次的FirststVT和LastVT集的概念便可以由文法自动构造出算符优先表。武汉理工大学《编译原理》课程设计7/184．文法4.1文法形式在计算机科学中，文法是编译原理的基础，是描述一门程序设计语言和实现其编译器的方法。文法的描述多用BNF(巴克斯范式)，而另一个重要的概念:正则表达式，也是文法的另一种形式。4.2文法分类自从乔姆斯基(Chomsky)于1956年建立形式语言的描述以来，形式语言的理论发展很快。这种理论对计算机科学有着深刻的影响，特别是对程序设计语言的设计、编译方法和计算复杂性等方面更有重大的作用。乔