编译原理结课作业-编译原理之词法分析.docx

编译原理结课作业 学院名称：计算机与信息工程学院专业名称： 网络工程指导教师： 学 号：姓 名： 目录编译原理之词法分析2一：历史背景2二：编译程序结构52.1词法分析52.2语法分析52.3语义分析和中间代码的产生62.4优化62.5目标代码生成7三：词法分析73.1词法分析器的自动生成83.2注释：9四：自上而下分析104.1算法10五：绿色编译及评估模型11六：总结13七：参考文献13 编译原理之词法分析一：历史背景随着信息技术的迅猛发展及其应用领域的不断深化，多数专业的研究与应用都离不开信息技术，开设编译原理课程成为必然。信息化浪潮对高等教育也带来非常直接的变化，各专业课程设置无不将计算机知识教育作为其课程设置的组成部分。各个专业的大学毕业生，都要求掌握基本的计算机操作技能，非计算机专业学生需要通过计算机等级考试，而一些和信息技术密切相关的专业，如电子信息、信息管理、电子商务等，课程设置上与计算机专业更是大量重叠，计算机知识教育在各专业中的渗透程度日渐加剧。 然而编译原理作为一门综合性专业基础课程，主要以系统的原理性知识为内容，通过实验操作与训练是学生掌握基本的应用技能。计算机专业的理论基础对培养学生的计算机专业素养具有非常重要的作用。在众多的原理性学习课程中，编译原理主要承担了语言实现原理、方法和技术的介绍。人们借助计算机减轻自己的劳动强度，提高生产率，完成一些人类无法进行的危险、高难度工作。然而所有这些工作都必须借助程序设计语言书写的程序来指挥计算机。非机器语言程序功能的实现必须由翻译程序来完成。正是有了编译程序、解释程序、汇编程序等翻译程序，人们才可以使用自己习惯的语言将需要计算机做的事情描述成程序，并通过这些翻译程序的工作让计算机理解并执行。目前计算机的广泛普及是建立在编译原理的基础上。编译原理主要包括编译程序在内的翻译程序承担了实现语言的功能，它所涉及的知识包括形式语言、自动机理论等语言定义、翻译与实现的基础知识，这些知识可以让学生领悟到计算机理论的精髓，可以让学生从实现的角度重新审视软件的开发，有助于学生对软件的真正认识、语言开发平台、编译系统甚至操作系统开发流程。编译原理是许多课程的一个综合性的实践，它进一步加深了学生对程序设计语言课程中语言基本单位的定义和作用的理解。例如，编译程序使用的一些数据结构和算法是“离散数学”、“数据结构”以及“算法设计与分析”等课程相关知识的典型应用；编译方式，以更好地适应社会的需求。主要面向计算机专业相关学生、对计算机感兴趣的学生、及相关技术的从业人员等。对于相关专业的学生来说，学习好编译原理这门课，不但可以理解和掌握编译编译课程本身，而且对于其他相关课程的学习也会有很好的帮助。而对于计算机相关技术的从业人员，学习编译原理相关知识，不但可以深刻理解程序设计语言的设计和实现原理，而且在工作中往往要设计新的领域专用语言及其编译器，因此，这部分知识也是必须的。二：编译程序结构编译程序的工作过程一般可以分为5个阶段： 2.1词法分析词法分析的任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词（定义符、标识符、运算符、界符、常数）。在词法分析阶段的工作中所依循的是语言的语法规则（或称构词规则）。描述语法规则的有效工具是正规式和有限自动机。2.2语法分析语法分析的任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单元（语法范畴）（短语、子句、句子、程序段、程序），并确定整个输入串是否构成语法上正确的程序。语法分析所依循的是语言的语法规则；语法规则通常用上下文无关文法描述；词法分析是一种线性分析，而语法分析是一种层次结构分析。2.3语义分析和中间代码的产生这一阶段的任务是：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。这一阶段通常包含两个方面的工作。1. 对每种语法范畴进行静态语义的检查，例如，变量是否定义、类型是否正确等等。 2. 如果语义正确则进行中间代码的翻译。所依循的是语言的语义规则，通常使用属性文法描述语义规则。2.4优化对于代码（主要是中间代码）进行加工变换，以期能够产生更为高效（省时间和空间）的目标代码。优化的主要方面有：公共子表达式的提取、循环优化、删除无用代码等等。此外，优化所依循的是程序的等价变换规则。2.5目标代码生成该阶段的任务是：把中间代码（经过优化处理之后的）变换成特定机器上的低级语言代码（绝对指令、可重定位指令、汇编指令）。三：词法分析词法分析器的功能输入源程序，按照构词规则分解成一系列单词符号。单词是语言中具有独立意义的最小单位，包括关键字、标识符、运算符、界符和常量等。编译简单是把源程序转化为另一种形式的程序,而其中关键的部分就是理解源程序所要表达的意思，才能转化为另一种源程序。编译器也一样，它的输入是语言的源文件（一般可以是文本文件）对于输入的文件，首先要分离出这个输入文件的每个元素（关键字、变量、符号）然后根据语言的文法，分析这些元素的组合是否合法，以及这些组合所表达的意思。程序设计语言和自然语言不一样，都是用符号来描述，每个特定的符号表示特定的意思，而且程序设计语言是上下文无关的。上下文无关就是某一个特定语句所要表达的意思和它所处的上下文没有关系，只有它自身决定。而词法分析，也就是把输入的符号串整理成特定的词素。词法分析器所输出单词符号常常表示成如下的二元式： (单词种别，单词符号的属性值)单词种别通常用整数编码。标识符一般统归为一种。常数则宜按类型（整、实、布尔等）分种。关键字可将其全体视为一种。运算符可采用一符一种的方法。界符一般用一符一种的方法。对于每个单词符号，除了给出了种别编码之外，还应给出有关单词符号的属性信息。单词符号的属性是指单词符号的特性或特征。词法分析是编译过程中的一个阶段，在语法分析前进行。词法分析作为一遍，可以简化设计，改进编译效率，增加编译系统的可移植性。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。3.1词法分析器的自动生成把一个正规编译（转换）为一个NFA进而转换为DFA，而这个NFA或DFA正是识别该正规式所表示的语言(正规集)的识别器。基于这种方法可以构造出词法分析程序(扫描器)，这就是扫描器的自动生成原理。LEX是一个广泛使用的工具，它用于构造各种各样语言的词法分析程序。LEX编译系统的作用如图:3.2注释：LEX程序由三部分组成：说明部分、转换规则和辅助过程，它们之间用%做间隔，其一般格式为：辅助定义部分 %识别规则部分 %用户子程序部分 1.辅助定义部分包括变量的说明、常量说明和正规式定义，所谓正规式定义是形如如下形式的一系列定义： d1r1 d2r2 dnrn 其中， di是代表这个正规式的简名，ri是d1,d2, ,di-1上的正规式，即在ri中允许出现字母表中的字符和前面定义的简名（d1,d2, ,di-1）2.识别规则部分是LEX源程序的核心。它是一张表，左边一列是正规式，右边一列是相应的动作。 P1 action1 P2 action2 Pm actionm 其中，每个Pi是d1,d2, ,di-1上的正规式，称之为词形。3.用户子程序部分是在action的执行过程中用到的过程或函数 。四：自上而下分析自上而下语法分析定义：从文法的开始符号开始，反复使用不同产生式进行推导以谋求与输入符号串相匹配。注：此处的输入符号串是指词法分析结果的一串二元式。一般方法主要包括：基本构成：设下推栈的初始状态包括两个符号：#S，其中#为栈底，S为文法开始符号。整个分析过程在语法分析程序控制下进行。在语法分析中用到的文法产生的表，称为语法表。4.1算法：i.若栈顶符号x是非终结符，查询语法表，找出一个以x为左部的产生式，x出栈，并将其右部反续入栈，且输出带上记下产生式编号推导。ii.若栈顶符号x是终结符，且读头下的符号也是x，则x出栈，读头指向下一个符号匹配。iii.若栈顶符号x是终结符，但读头下的符号不是x，则匹配失败。这说明可能前面推导时选错了候选式，退回到上次推导现场（包括栈顶符号、读头的指针和输出带上信息）回溯。iv.回溯后选取另一候选式进行推导，若没有候选式可选，则进一步回溯。若回溯到开始符号又已无候选式可选，则识别失败。v.若栈内仅剩下“#”，且读头也指向“#”，则识别成功。c)带回溯的自上而下分析法的缺陷i.如果文法存在左递归，语法分析会无限循环下去。ii.若产生式存在多个候选式，选择哪个进行推导完全是盲目的。iii.回溯会引起时间和空间的大量耗费。iv.如果被识别的语句是错的，算法无法指出错误的确切位置五：绿色编译及评估模型现有的编译技术主要以实现不同层次代码之间的正确转换为主，其评估的是指标集中在转换之后代码的执行速度以及功能性错误检测和定位的能力，对绿色需求中能耗，电子垃圾产生的速度（即设备损耗速度）及能耗错误的检测和定位能力考虑较为缺乏。为提高系统的的绿色需求，需要从整个计算机系统对软硬件进行优化处理，编译器作为软件生成的重要工具，对于提高这个系统的绿色指标具有不容忽视的作用。绿色编译优化框架主要包括绿色编译器，绿色评估器，绿色分配器以及绿色管理、绿色调度等五部分组成。在编译器内部，需要选择合理的优化位置和接口，使其能够在对高级语言进行正确转换的前提下，通过对源代码的分析，很好的实施各项绿色编译优化技术，以提高整个系统的绿色性能。并在传统编译器的基础上，结合系统运行的反馈信息（主要包括系统运行时的功耗信息、能耗信息、工作时间信息等）针对添加了绿色约束信息如:峰值功能约束，性能约束，时间约束的终端程序以及服务器程序进行相关的优化，最终达到提高设备使用时间的目的。六：总结 计算机系统高级语言翻译是一个涉及到计算机语言学、人工智能、计算机应用等理论和技术的多学科的复杂系统工程。从而正确识别出从源程序中分解出的二元式码形式的单词串,以供语法分析阶段使用。词法分析的基本任务是从字