精华内容
下载资源
问答
  • 编译原理 词法分析 绝对符合课程要求 已经调试运行 编译原理 词法分析 绝对符合课程要求 已经调试运行 编译原理 词法分析 绝对符合课程要求 已经调试运行
  • 编译原理

    千次阅读 2016-07-07 16:49:22
    编译原理 编辑词条 B 添加义项  ? 编译原理是计算机专业的一门重要专业课,旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成...

    编译原理 编辑词条

    编译原理计算机专业的一门重要专业课,旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。 编译原理是计算机专业设置的一门重要的专业课程。虽然只有少数人从事编译方面的工作,但是这门课在理论、技术、方法上都对学生提供了系统而有效的训练,有利于提高软件人员的素质和能力。 目前各个大学使用的教材机械工业出版社、国防工业出版社出版的《编译原理》。

    基本信息

    • 书名

      编译原理

    • 装帧

      平装

     
    • 开本

      16

    • 页数

      542

    编译原理计算机专业的一门重要专业课,旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。 编译原理是计算机专业设置的一门重要的专业课程。虽然只有少数人从事编译方面的工作,但是这门课在理论、技术、方法上都对学生提供了系统而有效的训练,有利于提高软件人员的素质和能力。 目前各个大学使用的教材机械工业出版社、国防工业出版社出版的《编译原理》。

    折叠编辑本段基本概念

    编译器 是将汇编或高级计算机语言翻译为二进制机器语言代码的计算机程序。编译器将源程序(source language) 编写的程序作为输入,翻译产生目标语言(target language )机器代码的等价程序。通常地,源程序为高级语言(high-level language ),像C或C + +、汉语语言程序等,而目标则是机器语言的目标代码 (object code,有时也称作机器代码(machine code )),也就是可以在计算机硬件中运行的机器代码软件程序。这一过程可以表示为:

    源程序→编译器 →目标机器代码程序

    折叠编辑本段编译原理课程

    这门课程关注的是编译器方面的产生原理和技术问题,似乎和计算机的基础领域不沾边,可是编译原理却一直作为大学本科的 必修课程,同时也成为了研究生入学考试的必考内容。编译原理及技术从本质上来讲就是一个算法问题而已,当然由于这个问题十分复杂,其解决算法也相对复杂。 我们学的数据结构与算法分析也是讲算法的,不过讲的基础算法,换句话说讲的是算法导论,而编译原理这门课程讲的就是比较专注解决一种的算法了。在20世纪 50年代,编译器的编写一直被认为是十分困难的事情,第一Fortran的编译器据说花了18年的时间才完成。在人们尝试编写编译器的同时,诞生了许多跟 编译相关的理论和技术,而这些理论和技术比一个实际的编译器本身价值更大。就犹如数学家们在解决著名的哥德巴赫猜想一样,虽然没有最终解决问题,但是其间 诞生不少名著的相关数论。

    折叠编辑本段发展历程

    在20世纪40年代,由于冯·诺伊曼在存储-程序编译原理实验程序编译原理实验程序计算机方面的先锋作用,编写一串代码或程序已成必要,这样计算机就可以执行所需的计算。开始时,这些程序都是用机器语言 (machine language )编写的。机器语言就是表示机器实际操作的数字代码,例如:

    C7 06 0000 0002 表示在IBM PC 上使用的Intel 8x86处理器将数字2移至地址0 0 0 0 (16进制)的指令。

    但编写这样的代码是十分费时和乏味的,这种代码形式很快就被汇编语言(assembly language )代替了。在汇编语言中,都是以符号形式给出指令和存储地址的。例如,汇编语言指令 MOV X,2 就与前面的机器指令等价(假设符号存储地址X是0 0 0 0 )。汇编程序(assembler )将汇编语言的符号代码和存储地址翻译成与机器语言相对应的数字代码。

    汇编语言大大提高了编程的速度和准确度,人们至今仍在使用着它,在编码需要极快的速度和极高的简洁程度时尤为如此。但是,汇编语言也有许多缺点:编写起来也不容易,阅读和理解很难;而且汇编语言的编写严格依赖于特定的机器,所以为一台计算机编写的代码在应用于另一台计算机时必须完全重写。

    发展编程技术的下一个重要步骤就是以一个更类似于数学定义或自然语言的简洁形式来编写程序的操作,它应与任何机器都无关,而且也可由一个程序翻译为可执行的代码。例如,前面的汇编语言代码可以写成一个简洁的与机器无关的形式 x = 2。

    在1954年至1957年期间,IBM的John Backus带领的一个研究小组对FORTRAN语言及其编译器的开发,使得上面的担忧不必要了。但是,由于当时处理中所涉及到的大多数程序设计语言的翻译并不为人所掌握,所以这个项目的成功也伴随着巨大的辛劳。几乎与此同时,人们也在开发着第一个编译器, Noam Chomsky开始了他的自然语言结构的研究。他的发现最终使得编译器结构异常简单,甚至还带有了一些自动化。Chomsky的研究导致了根据语言文法(grammar ,指定其结构的规则)的难易程度以及识别它们所需的算法来为语言分类。正如现在所称的-与乔姆斯基分类结构(Chomsky hierarchy )一样-包括了文法的4个层次:0型、1型、2型和3型文法,且其中的每一个都是其前者的专门化。2型(或上下文无关文法(context-free grammar ))被证明是程序设计语言中最有用的,而且今天它已代表着程序设计语言结构的标准方式。

    分析问题( parsing problem ,用于限定上下文无关语言的识别的有效算法)的研究是在20世纪60年代和70年代,它相当完善地解决了这一问题, 现在它已是编译理论的一个标准部分。它们与乔姆斯基的3型文法相对应。对它们的研究与乔姆斯基的研究几乎同时开始,并且引出了表示程序设计语言的单词(或称为记号)的符号方式。

    人们接着又深化了生成有效的目标代码的方法,这就是最初的编译器,它们被一直使用至今。人们通常将其误称为优化技术(optimization technique ),但因其从未真正地得到过被优化了的目标代码而仅仅改进了它的有效性,因此实际上应称作代码改进技术(code improvement technique )。

    这些程序最初被称为编译程序-编译器,但更确切地应称为分析程序生成器 (parser generator ),这是因为它们仅仅能够自动处理编译的一部分。这些程序中最著名的是 Yacc (yet another compiler- compiler),它是由Steve Johnson在1975年为Unix系统编写的。

    类似地,有穷自动机的研究也发展了另一种称为扫描程序生成器 (scanner generator )的工具,Lex (与Yacc同时,由Mike Lesk为Unix系统开发的)是这其中的佼佼者。在20世纪70年代后期和80年代早期,大量的项目都关注于编译器其他部分的生成自动化,这其中就包括代码生成。这些尝试并未取得多少成功,这大概是因为操作太复杂而人们又对其不甚了解。

    编译器设计最近的发展包括:首先,编译器包括了更为复杂的算法的应用程序,它用于推断或简化程序中的信息;这又与更为复杂的程序设计语言(可允许此类分析)的发展结合在一起。其中典型的有用于函数语言编译的Hindle y - Milner类型检查的统一算法。

    其次,编译器已越来越成为基于窗口的交互开发环境(interactive development environment,IDE )的一部 分,它包括了编辑器、链接程序、调试程序以及项目管理程序。这样的IDE的标准并没有多少, 但是已沿着这一方向对标准的窗口环境进行开发了。

    折叠编辑本段相关程序

    折叠解释程序

    解释程序(interpreter):解释程序是如同编译器的一种语言翻译程序。它与编译器的不同之处在于:它立即执行源程序而不是生成在翻译完成之后才执行的目标代码。从原理上讲,任何程序设计语言都可被解释或被编译,但是根据所使用的语言和翻译情况,很可能会选用解释程序而不用编译器。例如, 我们经常解释BASIC语言而不是去编译它。类似地,诸如LISP 的函数语言也常常是被解释的。

    解释程序也经常用于教育和软件的开发,此处的程序很有可能被翻译若干次。而另一方面,当执行的速度是最为重要的因素时就使用编译器,这是因为被编译的目标代码比被解释的源代码要快得多,有时要快10倍或更多。但是,解释程序具有许多与编译器共享的操作,而两者之间也有一些混合之处。

    折叠汇编程序

    汇编程序(assembler):汇编程序是用于特定计算机上的汇编语言的翻译程序。正如前面所提到的,汇编语言是计算机的机器语言的符号形式,它极易翻译。有时,编译器会生成汇编语言以作为其目标语言, 然后再由一个汇编程序将它翻译成目标代码。

    折叠连接程序

    连接程序(linker):编译器和汇编程序都经常依赖于连接程序,它将分别在不同的目标文件中编译或汇编的代码收集到一个可直接执行的文件中。在这种情况下,目标代码,即还未被连接的机器代码,与可执行的机器代码之间就有了区别。连接程序还连接目标程序和用于标准库函数的代码,以及连接目标程序和由计算机的操作系统提供的资源(例如,存储分配程序及输入与输出设备)。连接程序现在正在完成编译器最早的一个主要活动(这也是"编译"一词的用法, 即通过收集不同的来源来构造)。连接过程对操作系统和处理器有极大的依赖性。

    折叠装入程序

    装入程序(loader):编译器、汇编程序或连接程序生成的代码经常还不完全适用或不能执行,但是它们的主要存储器访问却可以在存储器的任何位置中且与一个不确定的起始位置相关。这样的代码被称为是可重定位的(relocatable ),而装入程序可处理所有的与指定的基地址或起始地址有关的可重定位的地址。装入程序使得可执行代码更加灵活,但是装入处理通常是在后台(作为操作环境的一部分)或与连接相联合时才发生,装入程序极少会是实际的独立程序。

    折叠预处理器

    预处理器(preprocessor ):预处理器是在真正的翻译开始之前由编译器调用的独立程序。预处理器可以删除注释、包含其他文件以及执行宏(宏macro是一段重复文字的简短描写)替代。预处理器可由语言(如 C )要求或以后作为提供额外功能(诸如为FORTRAN提供Ratfor预处理器)的附加软件。

    折叠编辑器

    编辑器(editor):编译器通常接受由任何生成标准文件(例如ASCII文件)的编辑器编写的源程序。现在, 编译器已与另一个编辑器和其他程序捆绑进一个交互的开发环境-IDE中。此时,尽管编辑器仍然生成标准文件,但会转向正被讨论的程序设计语言的格式或结构。这样的编辑器称为基于结构的(structure based ),且它早已包括了编译器的某些操作;因此,程序员就会在程序的编写时而不是在编译时就得知错误了。从编辑器中也可调用编译器以及与它共用的程序,这样程序员无需离开编辑器就可执行程序

    折叠调试程序

    调试程序(debugger ):调试程序是可在被编译了的程序中判定执行错误的程序,它也经常与编译器一起放在IDE 中。运行一个带有调试程序的程序与直接执行不同,这是因为调试程序保存着所有的或大多数源代码信息(诸如行数、变量名和过程)。它还可以在预先指定的位置(称为断点(breakpoint )) 暂停执行,并提供有关已调用的函数以及变量的当前值的信息。为了执行这些函数,编译器必须为调试程序提供恰当的符号信息,而这有时却相当困难,尤其是在一个要优化目标代码的编译器中。因此,调试又变成了一个编译问题。

    折叠描述器

    描述器(profiler):描述器是在执行中搜集目标程序行为统计的程序。程序员特别感兴趣的统计是每一个过程的调用次数和每一个过程执行时间所占的百分比。这样的统计对于帮助程序员提高程序的执行速度极为有用。有时编译器也甚至无需程序员的干涉就可利用描述器的输出来自动改进目标代码。

    折叠项目管理程序

    项目管理程序(project manager):软件项目通常大到需要由一组程序员来完成,这时对那些由不同人员操作的文件进行整理就非常重要了,而这正是项目管理程序的任务。例如,项目管理程序应将由不同的程序员制作的文件的各个独立版本整理在一起,它还应保存一组文件的更改历史,这样就能维持一个正在开发的程序的连贯版本了(这对那些由单个程序员管理的项目也很有用)。项目管理程序的编写可与语言无关,但当其与编译器捆绑在一起时,它就可以保持有关特定的编译器和建立一个完整的可执行程序的链接程序操作的信息。在Unix系统中有两个流行的项目管理程序:sccs (source code control system )和rcs (revision control system )。

    折叠编辑本段步骤

    编译器内部包括了许多步骤或称为阶段源代码(phase),它们执行不同的逻辑操作。将这些阶段设想为编译器中一个个单独的片断是很有用的, 尽管在应用中它们是经常组合在一起的,但它们扫描程序确实是作为单独的代码操作来编写的。

    折叠扫描程序

    扫描程序(scanner):在这个阶段编译器实际阅读源程序(通常以分析程序字符流的形式表示)。扫描程序执行词法分析注释树符号表 (Lexical analysis ):它将字符序列收集到称作记号错误处 (token )的有意义单元中,记号同自然语言,如英源代码理器语中的字词相似。因此可以认为扫描程序执行与优化程序拼写相似的任务。中间代码例如在下面的代码行(它可以是C程序的一部分)中:代码生成器 a [index] = 4 + 2 这个代码包括了1 2个非空字符,但只有 8个目标代码记号:a 标识符目标代码优化程序 [ 左括号 i n d e x 标识符 ] 右括号 = 赋值目标代码 4 数字编译器的阶段 + 加号 2 数字 每一个记号均由一个或多个字符组成,在进一步处理之前它已被收集在一个单元中。扫描程序还可完成与识别记号一起执行的其他操作。例如,它可将标识符输入到符号表中, 将文字(litral)输入到文字表中(文字包括诸如3 . 1415926535的数字常量,以及诸如"Hello,world ! "的引用字符串)。

    折叠语法分析

    语法分析(parser ):语法分析程序从扫描程序中获取记号形式的源代码,并完成定义程序结构的语法分析 (syntax analysis ),这与自然语言中句子的语法分析类似。语法分析定义了程序的结构元素及其关系。通常将语法分析的结果表示为分析树(parse tree)或语法树(syntax tree)。例如,还是那行C代码,它表示一个称为表达式的结构元素,该表达式是一个由左边为下标表达式、右边为整型表达式的赋值表达式组成。这个结构可按下面的形式表示为一个分析树:请注意,分析树的内部节点均由其表示的结构名标示出,而分析树的叶子则表示输入中的记号序列(结构名以不同字体表示以示与记号的区别)。分析树对于显示程序的语法或程序元素很有帮助,但是对于表示该结构却显得力不从心了。分析程序更趋向于生成语法树,语法树是分析树中所含信息的浓缩(有时因为语法树表示从分析树中的进一步抽取,所以也被称为抽象的语法树(abstract syntax tree ))。下面是一个C赋值语句的抽象语法树的例子:请注意,在语法树中,许多节点(包括记号节点在内)已经消失。例如,如果知道表达式是一个下标运算,则不再需要用括号"["和"]"来表示该操作是在原始输入中。

    折叠语义分析

    语义分析(semantic analyzer ):程序的语义就是它的"意思",它与语法或结构不同。程序的语义确定程序的运行,但是大多数的程序设计语言都具有在执行之前被确定而不易由语法表示和由分析程序分析的特征。这些特征被称作静态语义(static semantic),而语义分析程序的任务就是分析这样的语义(程序的"动态"语义具有只有在程序执行时才能确定的特性,由于编译器不能执行程序,所以它不能由编译器来确定)。一般的程序设计语言的典型静态语义包括声明和类型检查。由语义分析程序计算的额外信息(诸如数据类型)被称为属性(attribute),它们通常是作为注释或"装 饰"增加到树中(还可将属性添加到符号表中)。在正运行的C表达式 a [index] = 4 + 2 中,该行分析之前收集的典型类型信息可能是:a是一个整型值的数组,它带有来自整型子范围的下标;index则是一个整型变量。接着,语义分析程序将用所有的子表达式类型来标注语法树,并检查赋值是否使这些类型有意义了,如若没有,则声明一个类型匹配错误。在上例中, 所有的类型均有意义,有关语法树的语义分析结果可用以下注释了的树来表示。

    折叠优化程序

    优化程序(source code optimizer):编译器通常包括许多代码改进或优化步骤。绝大多数最早的优化步骤是在语义分析之后完 成的,而此时代码改进可能只依赖于源代码。这种可能性是通过将这一操作提供为编译过程中的单独阶段指出的。每个编译器不论在已完成的优化种类方面还是在优化阶段的定位中都有很大的差异。在上例中,我们包括了一个源代码层次的优化机会,也就是:表达式4 + 2可由编译器计算先得到结果6 (这种优化称为常量合并(constant folding ))。当然,还会有更复杂的情况。还是在上例中,通过将根节点右面的子树合并为它的常量值,这个优化就可以直接在(注释)语法树上完成:尽管许多优化可以直接在树上完成,但是在很多情况下,优化接近于汇编代码线性化形式的树更为简便。这样节点的变形有许多,但是三元式代码(three-address code )(之所以这样称呼是因为它在存储器中包含了3个(或3个以上)位置的地址)却是标准选择。另一个常见的选 择是P -代码(P - code ),它常用于Pascal编译器中。在前面的例子中,原先的C表达式的三元式代码应是:t = 4 + 2 a [ index] = t (请注意,这里利用了一个额外的临时变量t 存放加法的中间值)。这样,优化程序就将这个代码改进为两步。首先计算加法的结果:t = 6 a [index] = t 接着,将t替换为该值以得到三元语句 a [index] = 6 ,指出源代码优化程序可能通过将其输出称为中间代码(intermediate code )来使用三元式代码。中间代码一直是指一种位于源代码和目标代码(例如三元式代码或类似的线性表示)之间的代码表示形式。但是,我们可以更概括地认为它是编译器使用的源代码的任何一个内部表示。此时,也可将语法树称作中间代码,源代码优化程序则确实能继续在其输出中使用这个表示。有时,这个中间代码也称作中间表示(intermediate representation,IR)。

    折叠代码生成

    代码生成(code generator):代码生成器得到中间代码(IR),并生成目标机器的代码。正是在编译的这个阶段中,目标机器的特性成为了主要因素。当它存在于目标机器时,使用指令不仅是必须的而且数据的形式表示也起着重要的作用。例如,整型数据类型的变量和浮点数据类型的变量在存储器中所占的字节数或字数也很重要。在上面的示例中,现在必须决定怎样存储整型数来为数组索引生成代码。例如,下面是所给表达式的一个可能的样本代码序列(在假设的汇编语言中):

    M O V R0,index ;;

    value of index -> R0 M U L R0,2 ;;

    double value in R0 M O V R1,&a ;;

    address of a -> R1 A D D R1,R0 ;;

    add R0 to R1 M O V *R1,6 ;;

    constant 6 -> address in R1

    在以上代码中,为编址模式使用了一个类似C的协定,因此& a是a的地址(也就是数组的基地址),* R1则意味着间接寄存器地址(因此最后一条指令将值6存放在R1包含的地址中)。这个代码还假设机器执行字节编址,并且整型数占据存储器的两个字节(所以在第2条指令中用2作为乘数)。

    折叠目标代码

    目标代码(target code optimizer ):在这个阶段中,编译器尝试着改进由代码生成器生成的目标代码。这种改进包括选择编址模式以提高性能、将速度慢的指令更换成速度快的,以及删除多余的操作。在上面给出的样本目标代码中,还可以做许多更改:在第2条指令中,利用移位指令替代乘法(通常地,乘法很费时间),还可以使用更有效的编址模式(例如用索引地址来执行数组 存储)。使用了这两种优化后,目标代码就变成:

    MOV R0,index ;;

    value of index -> R0 SHL R0 ;;

    double value in R0 MOV &a[R0],6 ;;

    constant 6 -> address a + R0

    到这里就是编译原理的简要描述,但还应特别强调编译器在其结构细节上差别很大。

    折叠编辑本段数据结构

    编译原理一直是计算机学习的必修课.

    当然,由编译器的阶段使用的算法与支持这些阶段的数据结构之间的交互是非常强大的。编译器的编写者尽可能有效实施这些方法且不引起复杂性。理想的情况是:与程序大小成线性比例的时间内编译器,换言之就是,在0 ( n )时间内,n是程序大小的度量(通常是字符数)。本节将讲述一些主要的数据结构,它们是其操作部分阶段所需要的,并用来在阶段中交流信息。

    折叠记号

    记号(token):当扫描程序将字符收集到一个记号中时,它通常是以符号表示这个记号;这也就是说,作为一个枚举数据类型的值来表示源程序的记号集。有时还必须保留字符串本身或由此派生出的其他信息(例如:与标识符记号相关的名字或数字记号值)。在大多数语言中,扫描程序一次只需要生成一个记号(这称为单符号先行(single symbol lookahead))。在这种情况下,可以用全程变量放置记号信息;而在别的情况(最为明显的是FORTRAN)下,则可能会需要一个记号数组。

    折叠语法树

    语法树(syntax tree):如果分析程序确实生成了语法树,它的构造通常为基于指针的标准结构,在进行分析时动态分配该结构,则整棵树可作为一个指向根节点的单个变量保存。结构中的每一个节点都是一个记录,它的域表示由分析程序和之后的语义分析程序收集的信息。例如,一个表达式的数据类型可作为表达式的语法树节点中的域。有时为了节省空间,这些域也是动态分配或存放在诸如符号表的其他数据结构中,这样就可以有选择地进行分配和释放。实际上,根据它所表示的语言结构的类型(例如:表达式节点对于语句节点或声明节点都有不同的要求),每一个语法树节点本身都可能要求存储不同的属性。在这种情况下,可由不同的记录表示语法树中的每个节点,每个节点类型只包含与本身相关的信息。

    折叠符号表

    符号表(symbol table):这个数据结构中的信息与标识符有关:函数、变量、常量以及数据类型。符号表几乎与编译器的所有阶段交互:扫描程序、分析程序或将标识符输入到表格中的语义分析程序;语义分析程序将增加数据类型和其他信息;优化阶段和代码生成阶段也将利用由符号表提供的信息选 出恰当的代码。因为对符号表的访问如此频繁,所以插入、删除和访问操作都必须比常规操作更有效。尽管可以使用各种树的结构,但杂凑表却是达到这一要求的标准数据结构。有时在一个列表或栈中可使用若干个表格。

    折叠常数表

    常数表(literal table):常数表的功能是存放在程序中用到的常量和字符串,因此快速插入和查找在常数表中也十分重要。但是,在其中却无需删除,这是因为它的数据全程应用于程序而且常量或字符串在该表中只出现一次。通过允许重复使用常量和字符串,常数表对于缩小程序在存储器中的大小显得非常重要。在代码生成器中也需要常数表来构造用于常数和在目标代码文件中输入数据定义的符号地址。

    折叠中间代码

    中间代码(intermediate code):根据中间代码的类型(例如三元式代码和P -代码)和优化的类型,该代码可以是文本串的数组、临时文本文件或是结构的连接列表。对于进行复杂优化的编译器,应特别注意选择允许简单重组的表示。

    折叠临时文件

    临时文件(temporary file):计算机过去一直未能在编译器时将整个程序保留在存储器中。这一问题已经通过使用临时文件来保存翻译时中间步骤的结果或通过"匆忙地"编译(也就是只保留源程序早期部分的足够信息用以处理翻译)解决了。存储器的限制现在也只是一个小问题了,现在可以将整个编译单元放在存储器之中,特别是在可以分别编译的语言中时。但是偶尔还是会发现需要在某些运行步骤中生成中间文件。其中典型的是代码生成时需要反填(backpatch)地址。例如,当翻译如下的条件语句时 if x = 0 then ... else ... 在知道else部分代码的位置之前必须由文本跳到else部分:

    CMP X,0 JNE NEXT ;;

    location of NEXT not yet known < code for then-part > NEXT : < code for else-part >

    通常,必须为NEXT的值留出一个空格,一旦知道该值后就会将该空格填上,利用临时文件可以很容易地做到这一点。

    如果想利用上面的编译原理开发一套属于自己的编程语言,或者想在一个产品中嵌入编程语言,可以参考zengl开源网开发的zengl编程语言,该编程语言为国人使用C语言开发,里面包含两个部分,一个是编译器,一个是解释执行中间代码的虚拟机。编译器包含了词法扫描,语法分析,中间代码输出等,虚拟机则类似JAVA一样解释执行中间代码。作者将所有的版本都公布出来,好让读者可以由浅入深的做研究,并且为了证明该编程语言的实用性,还结合SDL游戏开发库开发了一款图形界面和命令行界面的21点扑克小游戏 。

    zengl编程语言目前适用平台为windows和linux (最开始在Linux下使用gcc开发,后来移植到windows平台)

    折叠编辑本段其他问题

    可从许多不同的角度来观察编译器的结构,还有其他一些可能的观点:编译器的物理结构、操作的顺序等等。由于编译器的结构对其可靠性、有效性、可用性以及可维护性都有很大的影响,所以编译器的编写者应熟悉尽可能多的有关编译器结构的观点。

    折叠分析和综合

    在这个观点中,已将分析源程序以计算其特性的编译器操作归为编译器的分析(analysis) 部分,而将生成翻译代码时所涉及到的操作称作编译器的综合(synthesis )部分。当然,词法分析、语法分析和语义分析均属于分析部分,而代码生成却是综合部分。在优化步骤中,分析和综合都有。分析正趋向于易懂和更具有数学性,而综合则要求更深的专业技术。因此,将分析步骤和综合步骤两者区分开来以便发生变化时互不影响是很有用的。

    折叠前端和后端

    本观点认为,将编译器分成了只依赖于源语言(前端(front end ))的操作和只依赖于目标语言(后端(back end ))的操作两部分。这与将其分成分析和综合两部分是类似的:扫描程序、分析程序和语义分析程序是前端,代码生成器是后端。但是一些优化分析可以依赖于目标语言,这样就是属于后端了,然而中间代码的综合却经常与目标语言无关,因此也就属于前端了。在理想情况下,编译器被严格地分成这两部分,而中间表示则作为其间的交流媒介。这一结构对于编译器的可移植性(portability)十分重要,此时设计的编译器既能改变源代码(它涉及到重写前端),又能改变目标代码(它还涉及到重写后端)。在实际中,这是很难 做到的,而且称作可移植的编译器仍旧依赖于源语言和目标语言。其部分原因是程序设计语言和机器构造的快速发展以及根本性的变化,但是有效地保持移植一个新的目标语言所需的信息 或使数据结构普遍地适合改变为一个新的源语言所需的信息却十分困难。然而人们不断分离前端和后端的努力会带来更方便的可移植性。

    折叠

    编译器发现,在生成代码之前多次处理整个源程序很方便。这些重复就是( pass)。首遍是从源中构造一个语法树或中间代码,在它之后的遍是由处理中间表示、向它增加信息、更换结构或生成不同的表示组成。遍可以和阶段相应,也可无关-遍中通常含有若干个阶段。实际上,根据语言的不同,编译器可以是一遍(one pass )-所有的阶段由一遍完成,其结果是编译得很好,但(通常)代码却不太有效。Pascal语言和C 语言均允许单遍编译。(Modula - 2语言的结构则要求编译器至少有两遍)。大多数带有优化的编译器都需要超过一遍:典型的安排是将一遍用于扫描和分析,将另一遍用于语义分析和源代码层优化,第3遍用于代 码生成和目标层的优化。更深层的优化则可能需要更多的遍:5遍、6遍、甚至8遍都是可能的。

    折叠语言定义和编译器

    程序设计语言的词法和语法结构通常用形式的术语指定,并使用正则表达式和上下文无关文法。但是,程序设计语言的语义通常仍然是由英语(或其他的自然语言)描述的。这些描述(与形式的词法及语法结构一起)一般是集中在一个语言参考手册(language reference manual )或语言定义(language definition)之中。因为编译器的编写者掌握的技术对于语言的定义有很大的影响,所以在使用了一种新的语言之后,语言的定义和编译器同时也能够得到开发。类似地,一种语言的定义对于构造编译器所需的技术也有很 大的关系。编译器的编写者更经常遇到的情况是:正在实现的语言是众所周知的并已有了语言定义。有时这个语言定义已达到了某个语言标准(language standard )的层次,语言标准是指得到诸如美国国家标准协会(American National Standards Institute ,ANSI )或国际标准化组织 (International Organization for Standardization,ISO )的官方标准组织批准的标准。FORTRAN、 Pascal和C语言就具有ANSI标准,Ada有一个通过了美国政府批准的标准。在这种情况下,编译器的编写者必须解释语言的定义并执行符合语言定义的编译器。通常做到这一点并不容易, 但是有时由于有了标准测试程序集(测试组(test suite )),就能够测试编译器(Ada有这样一个测试组),这又变得简单起来了。有时候,一种语言可从数学术语的形式定义(formal definition )中得到它的语义。现在人们已经使用了许多方法,尽管一个称作表示语义(denotational semantics )的方法已经成为较为常用的方法,在函数编程共同体中尤为如此,但现在仍然没有一种可成为标准的方法。当语言有一个形式定义时,那么在理论上就有可能给出编译器与该定义一致的数学证明,但是由于这太难了,而几乎从未有人做过。无论怎样, 运行时环境的结构和行为是尤其受到语言定义影响的编译器构造的一个方面。

    展开全文
  • 编译原理:语法分析

    万次阅读 多人点赞 2019-04-29 17:01:40
    通过设计、编制、调试一个典型的语法分析程序(任选有代表性的语法分析方法,如LL(1)、递归下降分析法、LR、算符优先分析法)等,作为编制语法分析程序的依据,对词法分析所提供的单词序列进行语法检测和结构分析...

    语法分析程序



    一、作业目的和要求

    通过设计、编制、调试一个典型的语法分析程序(任选有代表性的语法分析方法,如LL(1)、递归下降分析法、LR、算符优先分析法)等,作为编制语法分析程序的依据,对词法分析器所提供的单词序列进行语法检测和结构分析,实现并进一步掌握常用的语法分析方法。


    二、作业内容

    选择对各种常见高级程序设计语言都较为通用的语法结构作为分析对象(例如表达式、if、while、for等等),给出其文法规则描述(注意,文法规则的描述要符合所选分析方法的要求,比如用LL(1)分析法,文法必须是LL(1)文法),设计并实现一个完整的语法分析程序。

    • 输入:源程序以文件的形式输入。
    • 输出:对于输入的源程序,如果输入源程序是给定文法定义的合法程序,则输出”success”,如果不是,即输入源程序有错误,则输出“Error”,并且尽可能指出出错位置和原因。

    三、作业要求

    1、说明语法分析的源语言是什么?
    能分析的语法成分有哪些(比如if、while、表达式、switch等等)。
    给出每个语法规则的文法描述。(可以自定义语法成分,设计合理的语法规则。)

    运用的Java语言写成的语法分析程序,
    语法成分包括:if选择结构,while循环结构,for循环结构。

    2、说明选择的语法分析方法是哪种?描述总体设计思路和主要的流程图。

    语法分析的方法是LL(1)文法。

    • 设计思路:

    • 1.构造单个文法符号X的first集:
      如果X为终结符,First(X)=X;
      如果X->ε是产生式,把ε加入First(X);
      如果X是非终结符,如X->YZW。从左往右扫描产生式右部,把First(Y)加入First(X); 如果First(Y)不包含ε,表示Y不可为空,便不再往后处理;如果First(Y)包含ε,表示Y可为空,则处理Z,依次类推。
      构造文法符号串的first集,如:X->YZW;求YZW的first集
      从左往右扫描该式,加入其非空first集:把First(Y)加入First(YZW)
      若包含空串,处理下一个符号:如果First(Y)包含空串,便处理Z;不包含就退出;处理到尾部,即所有符号的first集都包含空串 把空串加入First(YZW)。

    • 2.在计算First(X)集之后的基础上:
      (1)$属于FOLLOW(S),S是开始符;
      (2)查找输入的所有产生式,确定X后紧跟的终结符;
      (3)如果存在A->αBβ,(α、β是任意文法符号串,A、B为非终结符),把first(β)的非空符号加入follow(B);
      (4)如果存在A->αB或A->αBβ 但first(β)包含空,把follow(A)加入follow(B)。

    • 3.构造预测分析表:
      对于每个产生式A->α,first(α)中的终结符a,把A->α加入M[A,a]。
      如果空串在first(α)中,说明可为空,找它的follow集,对于follow(A)中的终结符b,把A->α加入M[A,b];
      如果空串在first(α)中,且 “$”也在follow(A)中,说明A后可以接终结符,故把A->α加入M[A,$]中。

    • 4.执行分析:
      输入一个串,文法G的预测分析表,输出推导过程:
      $ 和 开始符S入栈,栈顶符号X,index指向分析串的待分析符号a。
      栈非空执行以下循环:
      如果X==a,表示匹配,符号栈弹出一个,index++指向下一个符号;
      否则,如果X是终结符,出错;
      否则,如果查表为error,出错;
      否则,查表正确,弹出栈顶符号,把其右部各个符号进栈,令X为栈顶符号。

    • 流程图:
      在这里插入图片描述
      在这里插入图片描述

    3、编程实现,程序中编写的各种函数,需要给出注释,说明函数的作用。
    通过实现接口中的方法来完成语法分析的功能。

    package Try;
    
    interface MyAnalyseFun {
        void Init();//初始化
        void getVnVt();//获取非终结符和终结符的集合
        void getFirst(Character c);//first集
        void getFirst(String s);//任意字符的first集
        void getFollow(char c);//follow集
        void createTable();//构造表
        void analyzeLL();//LL(1)分析过程
        String find(char X, char a);//查找
        void insert(char X, char a,String s);//插入
        void displayLL();//输出分析过程
        void ouput();//其他输出信息
    }
    

        package Try;
        
        import java.io.*;
        import java.util.*;
        
        public class MyAnalyse implements MyAnalyseFun{
            /**
             * 几个比较重要的参数
             * @param MyfirstSet 终结符的first集合
             * @param MyfirstSetX 任意符号的first集合
             * @param start 文法的开始符
             * @param MyfollowSet follow集
             * @param VnSet 终结符的集合
             * @param VtSet 终结符的集合
             * @param inputStrings 文法拓展的输入
             * @param outputSet 输出的集合
             * @param table 分析表
             * @param MyAnaStatck 分析栈
             * @param strInput 需要使用预测分析器的输入串
             * @param MyAction 分析动作
             * @param Index 分析的索引值
             */
            //从文件中读入时后台无法识别空串ε,因此用符号&代替空串ε
    
        //first集是终结符的first集
        protected HashMap<Character, HashSet<Character>> MyfirstSet = new HashMap<>();
        //firstX集是指任意符号串的first集
        protected HashMap<String, HashSet<Character>> MyfirstSetX = new HashMap<>();
        //文法的开始符
        protected Character start = 'S';
        //follow集
        protected HashMap<Character, HashSet<Character>> MyfollowSet = new HashMap<>();
    
        //存储非终结符的结合
        protected HashSet<Character> VnSet = new HashSet<>();
        //存储终结符的结合
        protected HashSet<Character> VtSet = new HashSet<>();
        protected HashMap<Character, ArrayList<String>> outputSet = new HashMap<>();
        //输入文法
        //S->a|^|(T)
        //T->SU
        //U->,SU|&
    //    protected String [] inputStrings = {   "S->a",
    //                                        "S->^",
    //                                        "S->(T)",
    //                                        "T->SU",
    //                                        "U->,SU",
    //                                        //"U->ε",
    //                                        "U->&"   };
        //定义分析表
        protected String [][] table;
        //分析栈
        protected Stack<Character> MyAnaStatck = new Stack<>();
        //定义要分析的输入串
        protected String strInput = "(a,a)$";
        //对动作的初始化
        protected String MyAction = "";
        int Index = 0;
    
        //从文件中读入
        protected String[] inputStrings = getSource();
    
        protected MyAnalyse() {
        }
    
        public static void main(String[] args){
            MyAnalyse test = new MyAnalyse();
    
            test.getVnVt();
            test.Init();
            test.createTable();
            test.analyzeLL();
            test.ouput();
            
        }
    
        //从文件中读入文法的方法
        public  static  String[] getSource(){
            StringBuffer temp = new StringBuffer();
            FileInputStream fis= null;
            try {
                fis = new FileInputStream("E:\\readin.txt");
                byte[] buff=new byte[1024];
                int len=0;
                while((len=fis.read(buff))!=-1){
                    temp.append(new String(buff,0,len));
                }
            } catch (Exception e) {
                e.printStackTrace();
            } finally {
                try {
                    fis.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return temp.toString().split("\n");
        }
    
        //初始化
        @Override
        public void Init() {
            for (String s1 : inputStrings) {
                //"S->a",
                //"S->^",
                //"S->(T)",
                //"T->SU",
                //"U->,SU",
                //"U->&"
                String[] str = s1.split("->");//通过符号“->”分隔每行的文法
                char c = str[0].charAt(0);//取得左边的非终结符
                ArrayList<String> list = outputSet.containsKey(c) ? outputSet.get(c) : new ArrayList<>();
                list.add(str[1]);//添加文法右边的内容到集合中
                outputSet.put(c, list);
            }
            //求非终结符的first集
            for (Character c1 : VnSet)
                getFirst(c1);
    
            for (Character c2 : VnSet) {
                ArrayList<String> l = outputSet.get(c2);
                for (String s2 : l)
                    getFirst(s2);
            }
            //求出follow集
            getFollow(start);
            for (Character c3 : VnSet) {
                getFollow(c3);
            }
        }
    
        @Override
        public void getVnVt() {//取出终结符和非终结符的集合
            for (String s3 : inputStrings) {
                String[] str = s3.split("->");
                VnSet.add(str[0].charAt(0));
            }
            for (String s4 : inputStrings) {
                String[] str = s4.split("->");
                String right = str[1];
                for (int i = 0; i < right.length(); i++)
                    if (!VnSet.contains(right.charAt(i)))
                        VtSet.add(right.charAt(i));
            }
        }
    
        @Override
        public void getFirst(Character c) {
            ArrayList<String> list = outputSet.get(c);
            HashSet<Character> set = MyfirstSet.containsKey(c) ? MyfirstSet.get(c) : new HashSet<Character>();
            // c为终结符 直接添加
            if (VtSet.contains(c)) {
                set.add(c);
                MyfirstSet.put(c, set);
                return;
            }
            // c为非终结符 处理其每条产生式
            for (String s5 : list) {
                // c 推出空串 直接添加
                if (s5 == Character.toString('&')) {
                    set.add('&');
                }
                // X -> Y1Y2Y3… 情况
                else {
                    // 从左往右扫描生成式右部
                    int i = 0;
                    while (i < s5.length()) {
                        char tn = s5.charAt(i);
                        //先处理防止未初始化
                        getFirst(tn);
                        HashSet<Character> tvSet = MyfirstSet.get(tn);
                        // 将其first集加入左部
                        for (Character tmp : tvSet)
                            set.add(tmp);
                        // 若包含空串 处理下一个符号
                        if (tvSet.contains('&'))
                            i++;
                            // 否则退出 处理下一个产生式
                        else
                            break;
                    }
                }
            }
            MyfirstSet.put(c, set);
        }
    
        @Override
        public void getFirst(String s) {
            HashSet<Character> set = (MyfirstSetX.containsKey(s))? MyfirstSetX.get(s) : new HashSet<Character>();
            // 从左往右扫描该式
            int i = 0;
            while (i < s.length()) {
                char tn = s.charAt(i);
                HashSet<Character> tvSet = MyfirstSet.get(tn);
                // 将其非空 first集加入左部
                for (Character tmp : tvSet)
                    if(tmp != '&')
                        set.add(tmp);
                // 若包含空串 处理下一个符号
                if (tvSet.contains('&'))
                    i++;
                    // 否则结束
                else
                    break;
                // 到了尾部 即所有符号的first集都包含空串 把空串加入
                if (i == s.length()) {
                    set.add('&');
                }
            }
            MyfirstSetX.put(s, set);
        }
    
        @Override
        public void getFollow(char ch) {
            ArrayList<String> list = outputSet.get(ch);
            HashSet<Character> setA = MyfollowSet.containsKey(ch) ? MyfollowSet.get(ch) : new HashSet<Character>();
            //如果是开始符 添加 $
            if (ch == start) {
                setA.add('$');
            }
            //查找输入的所有产生式,确定c的后跟 终结符
            for (Character cha : VnSet) {
                ArrayList<String> l = outputSet.get(cha);
                for (String s : l)
                    for (int i = 0; i < s.length(); i++)
                        if (s.charAt(i) == ch && i + 1 < s.length() && VtSet.contains(s.charAt(i + 1)))
                            setA.add(s.charAt(i + 1));
            }
            MyfollowSet.put(ch, setA);
            //处理c的每一条产生式
            for (String s : list) {
                int i = s.length() - 1;
                while (i >= 0 ) {
                    char tn = s.charAt(i);
                    //只处理非终结符
                    if(VnSet.contains(tn)){
                        // 都按 A->αB&  形式处理
                        //若&不存在   followA 加入 followB
                        //若&存在,把&的非空first集  加入followB
                        //若&存在  且 first(&)包含空串   followA 加入 followB
    
                        //若&存在
                        if (s.length() - i - 1 > 0) {
                            String right = s.substring(i + 1);
                            //非空first集 加入 followB
                            HashSet<Character> setF = null;
                            if( right.length() == 1 && MyfirstSet.containsKey(right.charAt(0))) {
                                setF = MyfirstSet.get(right.charAt(0));
                            }
                            else{
                                if(!MyfirstSetX.containsKey(right)){
                                    HashSet<Character> set = new HashSet<Character>();
                                    MyfirstSetX.put(right, set);
                                }
                                setF = MyfirstSetX.get(right);
                            }
                            HashSet<Character> setX = MyfollowSet.containsKey(tn) ? MyfollowSet.get(tn) : new HashSet<Character>();
                            for (Character cha : setF) {
                                if (cha != '&') {
                                    setX.add(cha);
                                }
                            }
                            MyfollowSet.put(tn, setX);
    
                            // 若first(&)包含&   followA 加入 followB
                            if(setF.contains('&')){
                                if(tn != ch){
                                    HashSet<Character> setB = MyfollowSet.containsKey(tn) ? MyfollowSet.get(tn) : new HashSet<Character>();
                                    for (Character cha : setA) {
                                        setB.add(cha);
                                    }
                                    MyfollowSet.put(tn, setB);
                                }
                            }
                        }
                        //若&不存在   followA 加入 followB
                        else{
                            // A和B相同不添加
                            if(tn != ch){
                                HashSet<Character> setB = MyfollowSet.containsKey(tn) ? MyfollowSet.get(tn) : new HashSet<Character>();
                                for (Character cha : setA)
                                    setB.add(cha);
                                MyfollowSet.put(tn, setB);
                            }
                        }
                        i--;
                    }
                    //如果是终结符往前扫描  如 A->aaaBCDaaaa  此时&为 CDaaaa
                    else i--;
                }
            }
        }
    
        @Override
        public void createTable() {//构造预测分析表的格式
            //终结符数组
            Object[] VtArray = VtSet.toArray();
            //非终结符数组
            Object[] VnArray = VnSet.toArray();
            // 预测分析表初始化
            table = new String[VnArray.length + 1][VtArray.length + 1];
            table[0][0] = "Vn/Vt";
            //初始化首行首列
            for (int i = 0; i < VtArray.length; i++)
                table[0][i + 1] = (VtArray[i].toString().charAt(0) == '&') ? "$" : VtArray[i].toString();
            for (int i = 0; i < VnArray.length; i++)
                table[i + 1][0] = VnArray[i] + "";
            //全部置error
            for (int i = 0; i < VnArray.length; i++)
                for (int j = 0; j < VtArray.length; j++)
                    table[i + 1][j + 1] = "error";
    
            //插入生成式
            for (char A : VnSet) {
                ArrayList<String> l = outputSet.get(A);
                for(String s : l){
                    HashSet<Character> set = MyfirstSetX.get(s);
                    for (char a : set)
                        insert(A, a, s);
                    if(set.contains('&'))  {//如果包含&
                        HashSet<Character> setFollow = MyfollowSet.get(A);
                        if(setFollow.contains('$'))//判断follow集中是否包含$
                            insert(A, '$', s);
                        for (char b : setFollow)
                            insert(A, b, s);
                    }
                }
            }
        }
    
        @Override
        public void analyzeLL() {
            System.out.println("-------------------1.LL分析过程-------------------");
            System.out.println("|               分析栈        输入串     动作|  ");
            MyAnaStatck.push('$');
            MyAnaStatck.push('S');
            displayLL();//调用分析过程方法
            char X = MyAnaStatck.peek();
            while (X != '$') {
                char a = strInput.charAt(Index);
                if (X == a) {
                    MyAction = "match " + MyAnaStatck.peek();
                    MyAnaStatck.pop();
                    Index++;
                } else if (VtSet.contains(X))
                    return;
                else if (find(X, a).equals("error"))
                    return;
                else if (find(X, a).equals("&")) {
                    MyAnaStatck.pop();
                    MyAction = X + "->&";
                } else {
                    String str = find(X, a);
                    if (str != "") {
                        MyAction = X + "->" + str;
                        MyAnaStatck.pop();
                        int len = str.length();
                        for (int i = len - 1; i >= 0; i--)
                            MyAnaStatck.push(str.charAt(i));
                    } else {
                        System.out.println("error at '" + strInput.charAt(Index) + " in " + Index);
                        return;
                    }
                }
                X = MyAnaStatck.peek();
                displayLL();
            }
            System.out.println("LL(1)文法分析成功!");
            System.out.println("-------------------LL分析过程-------------------");
        }
    
        @Override
        public String find(char X, char a) {
            for (int i = 0; i < VnSet.size() + 1; i++) {
                if (table[i][0].charAt(0) == X)
                    for (int j = 0; j < VtSet.size() + 1; j++) {
                        if (table[0][j].charAt(0) == a)
                            return table[i][j];
                    }
            }
            return "";
        }
    
        @Override
        public void insert(char X, char a, String s) {//插入
            if(a == '&')
                a = '$';
            for (int i = 0; i < VnSet.size() + 1; i++) {
                if (table[i][0].charAt(0) == X)
                    for (int j = 0; j < VtSet.size() + 1; j++) {
                        if (table[0][j].charAt(0) == a){
                            table[i][j] = s;
                            return;
                        }
                    }
            }
        }
    
        @Override
        public void displayLL() {// 对输入串(a,a)$ 输出 LL(1)分析过程
            Stack<Character> s = MyAnaStatck;
            System.out.printf("%23s", s );//输出第一列:分析栈
            System.out.printf("%13s", strInput.substring(Index));//输出第二列:输入串
            System.out.printf("%10s", MyAction);//输出第三列:动作
            System.out.println();
        }
    
        @Override
        public void ouput() {
            // 输出终结符的first集
            System.out.println("-------------------2.first集-------------------");
            for (Character c : VnSet) {
                HashSet<Character> set = MyfirstSet.get(c);
                System.out.printf("%10s",c + "  ->   ");
                for (Character cha : set)
                    System.out.print(cha+" ");
                System.out.println();
            }
            System.out.println("-------------------first集-------------------");
            // 输出任意符号串的first集
            System.out.println("-------------------firstX集-------------------");
            Set<String> setStr =  MyfirstSetX.keySet();
            for (String s : setStr) {
                HashSet<Character> set = MyfirstSetX.get(s);
                System.out.printf("%10s",s + "  ->   ");
                for (Character cha : set)
                    System.out.print(cha+" ");
                System.out.println();
            }
            System.out.println("-------------------firstX集-------------------");
            // 输出follow集
            System.out.println("-------------------3.follow集-------------------");
    
            for (Character c : VnSet) {
                HashSet<Character> set = MyfollowSet.get(c);
                System.out.print("Follow " + c + " : ");
                for (Character cha : set)
                    System.out.print(cha+" ");
                System.out.println();
            }
            System.out.println("-------------------follow集-------------------");
            //构造LL1文法预测分析表
            System.out.println("-------------------4.LL1预测分析表-------------------");
    
            for (int i = 0; i < VnSet.size() + 1; i++) {
                for (int j = 0; j < VtSet.size() + 1; j++) {
                    System.out.printf("%8s", table[i][j] + " ");
                }
                System.out.println();
            }
            System.out.println("-------------------LL1预测分析表-------------------");
        }
    }
    

    四、结果分析

    1、输入正确的源程序截图:
    将符号ε替换为&
    在这里插入图片描述

    输出结果截图:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    2、输入错误的源程序截图:
    输入错误文法
    在这里插入图片描述
    输出结果截图:
    在这里插入图片描述
    3、总结(自己的心得体会、你编写的语法分析程序的优缺点)
    S->a|^|(T)
    T->SU
    U->,SU|ε

    • 优点:文法分析过程比较详细,任务整个完成过程是充实的,这个实验报告相当于对编译原理理论课的一次实践尝试,能收获很多课堂上面学不到的知识,同时也能巩固老师所教授的知识。

    • 缺点:在写程序的时候,卡在了空串那个点。最开始尝试直接在程序中定义文法时,ε能在程序中分析成功。后来在用读入文件的方式定义文法时,控制台出现乱码,这个点解决起来花了一点时间,最后决定将符号ε替换为&,程序才能运行成功。

    展开全文
  • 编译原理——词法分析实验

    千次阅读 2019-05-21 11:56:19
    对于如下文法所定义的语言子集,试编写并上机调试一个词法分析程序: <程序>→PROGRAM <标识符>;<分程序>. <分程序>→<变量说明>BEGIN<语句表>END <变量说明>→VAR<...
    • 实验目的

    1. 掌握词法分析器的功能。
    2. 掌握词法分析器的实现。
    • 实验内容及要求

    对于如下文法所定义的语言子集,试编写并上机调试一个词法分析程序:

    <程序>→PROGRAM <标识符>;<分程序>.

    <分程序>→<变量说明>BEGIN<语句表>END

    <变量说明>→VAR<变量表>:<类型>;| <空>

    <变量表>→<变量表>,<变量> | <变量>

    <类型>→INTEGER

    <语句表>→<语句表>;<语句> | <语句>

    <语句>→<赋值语句> | <条件语句> | <WHILE语句> | <复合语句> | <过程定义>

    <赋值语句>→<变量>:=<算术表达式>

    <条件语句>→IF<关系表达式>THEN<语句>ELSE<语句>

    <WHILE语句>→WHILE<关系表达式>DO<语句>

    <复合语句>→BEGIN<语句表>END

    <过程定义>→PROCEDURE<标识符><参数表>;

    BEGIN<语句表>END

    <参数表>→(<标识符表>)| <空>

    <标识符表>→<标识符表>,<标识符> | <标识符>

    <算术表达式>→<算术表达式>+<项> | <项>

    <项>→<项>*<初等量> | <初等量>

    <初等量>→(<算术表达式>)| <变量> | <无符号数>

    <关系表达式>→<算术表达式><关系符><算术表达式>

    <变量>→<标识符>

    <标识符>→<标识符><字母> | <标识符><数学> | <字母>

    <无符号数>→<无符号数><数字> | <数字>

    <关系符>→= | < | <= | > | >= | <>

    <字母>→A | B | C | ··· | X | Y | Z

    <数字>→0 | 1 | 2 | ··· | 8 | 9

    <空>→

    要求和提示:

    (1)单词的分类。

    可将所有标识符归为一类;将常数归为另一类;保留字和分隔符则采取一词 一类。

    (2)符号表的建立。

    可事先建立一保留字表,以备在识别保留字时进行查询。变量名表及常数表 则在词法分析过程中建立。

    (3)单词串的输出形式。

    所输出的每一单词,均按形如(CLASS,VALUE)的二元式编码。对于变量标 识符和常数,CLASS字段为相应的类别码,VALUE字段则是该标识符、常数 在其符号表中登记项的序号(要求在变量名表登记项中存放该标识符的字符 串,其最大长度为四个字符;常数表登记项中则存放该整数的二进制形式)。 对于保留字和分隔号,由于采用一词一类的编码方式,所以仅需在二元式的 CLASS字段上放置相应的单词的类别码,VALUE字段则为“空”。不过,为便 于查看由词法分析程序所输出的单词串,也可以在CLASS字段上直接放置单 词符号串本身。

    • 单词分类表

    以下为单词分类表(单词符号,种别编码):

    单词符号

    种别编码

    单词符号

    种别编码

    auto

    1

    void

    30

    break

    2

    volatile

    31

    case

    3

    while

    32

    char

    4

    标识符

    33

    const

    5

    常型整量

    34

    continue

    6

    +

    35

    default

    7

    -

    36

    do

    8

    *

    37

    double

    9

    /

    38

    else

    10

    <

    39

    enum

    11

    <=

    40

    extern

    12

    >

    41

    float

    13

    >=

    42

    for

    14

    =

    43

    goto

    15

    ==

    44

    if

    16

    <>

    45

    int

    17

    ;

    46

    long

    18

    (

    47

    register

    19

    )

    48

    return

    20

    ^

    49

    short

    21

    ,

    50

    signed

    22

    #

    51

    sizeof

    23

    %

    52

    static

    24

    [

    53

    struct

    25

    ]

    54

    switch

    26

    {

    55

    typedef

    27

    }

    56

    union

    28

    .

    57

    unsigned

    29

    //

    58

    • 单词状态图

    • 算法描述

    1.首先,我将单词类别总分为六大类:

        1:标识符

        2:数字

        3:算数运算符 + - * \

        4:关系运算符 <、<=、>、>=、<>、=、==

        5:保留字(32)

              auto      break    case    char   const      continue

              default    do      double   else   enum      extern

              float      for      goto    if      int        long

              register    return   short    signed  sizeof     static

              struct      switch  typedef  union   unsigned  void

               volatile    while

        6:界符 ;、(、)、^、,、#、%、[、]、{、}、.、\\

    2.每种单词类别的识别及判断方法如下:

    首先从文件中读一个字符,赋值给ch,

        如果ch为空格,则文件扫描列序号加一;

        如果ch为回车,则文件扫描行序号加一;

    其它情况如下:

    (1)如果ch为字母或下划线,继续扫描,直到ch不是数字、字母或下划 线,则开始判断单词类型:

              查找关键字表,若找到匹配项,则为关键字;

              否则为标识符,查找标识符表,若没有找到匹配项,则添加到标识符表中。(动态生成标识符表)

              如果ch为数字,继续扫描,直到ch不是数字,则开始判断单词类型: 若数字在合法范围内,则为数字,查找标识符表,若没有找到             匹配项,则添加到数字表中;(动态生成数字表)

               否则为非法单词。

    (2)如果ch是加减乘,一定是算数运算符。

    (3)如果ch为;、(、)、^、,、#、%、[、]、{、}、.,则一定是界符。

    (4)如果ch为<,则继续扫描下一个:

              若下一个为=,则为<=;

               若下一个为>,则为<>;

               否则,为<。

    (5)如果ch为>,则继续扫描下一个:

              若下一个为=,则为>=;

              否则,为>。

    (6)如果ch为/,则继续扫描下一个:

              若下一个为/,则为注释,这一行剩下的全被注释了;

              否则,则为/。

    3.出错处理:

    我使用了两个全局变量:line,col,分别用于定位文件中扫描的位置信息,当发现当前字符为非法字符时,输出报错信息,并输出非法字符在文件中的所在位置信息。

    4.输出显示:

    将所输出的每一单词,均按形如(CLASS,VALUE)的二元式编码。对于变量标识符和常数,CLASS字段为相应的类别码,VALUE字段则是该标识符、常数在其符号表中登记项的序号。对于保留字和分隔号,由于采用一词一类的编码方式,为便于查看由词法分析程序所输出的单词串,所以在CLASS字段上直接放置单词符号串本身,VALUE字段则为“空”。使用分支结构,根据判断结果,从而进行相应输出显示。

    • 程序结构

    1.变量常量定义:

    对程序所需常量以及全局变量进行定义,其中包含:

    (1)全局变量:

    int seekresult:fseek的时候用来接着的;

    string word="":字符串,当前词;

    char ch:每次读进来的一个字符;

    int num=0:每个单词中当前字符的位置;

    int line=1:行数;

    int col=1:列数;

    bool flag:文件是否结束扫描;

    int type;:单词的类型;

    char IDentifierTable[1000][40]:标识符表;

    char DigitBTable[1000][40]常数表等。

    (2)常量:

    static char ReserveWord[32][20]:保留字表;

    static char SuanshuOperator[4][4]:算术运算符表;

    static char GuanxiOperator[7][4]:逻辑运算符表;

    static char Jiefu[36][4]:界符表。

    2.主要函数:

    (1)bool Isletter(char x)函数:判断字符x是否为字母;

    (2)bool IsDigit(char x)函数:判断字符x是否为数字;

    (3)bool IsJiefu(char x)函数:判断字符x是否为界符;

    (4)bool IsSuanshuyunsuanfu(char x) 函数:判断字符x是否为算数运算符;

    (5)bool IsGuanxiyunsuanfu(char x)函数:判断字符x是否为关系运算符;

    (6)int Scanner(FILE *fp)函数:其主要功能为从文件里读一个单词,调用基础函数进行单词类别,。

    (7)int main()函数:程序入口,进行文件扫描,并调用Scanner(FILE *fp)函数对单词进行判断,输出分析结果。

    • 运行结果

    1.待分析文件code.txt:

    2.运行结果:

                 

    3.文件目录:

    4.常数表:

    5.标识符表:

     

    • 调试情况

    在此次实验中,遇到的问题还是比较多的,主要分为以下几种:

    1.读文件和写文件操作:

    由于待分析内容存储在文本文件中,所以文件的读取是必不可少的操作;而单词分析时需要动态生成标识符表和常数表,故需要追写文件。一开始由于语言功底不太扎实,实现的不太顺利,但是在上网查找了解决方案以后,问题就迎刃而解了。

    2.各种单词类别的识别和判断以及出错处理:

    这是词法分析器的核心也是难点,这部分必须逻辑十分清晰才可以实现,一开始虽然听懂了课堂上的内容,但是理解的还是不够深刻,感觉自己已经将单词类别进行了合理的划分,但是具体实现细节上还是遇到了不少的困难。比如,在一些相似单词的识别上面困惑了一段时间,想到了老师上课所说的“超前搜索”算法,所以我进行了实现,但是发现位置定位是一个需要特别关注的问题,我的解决方案就是:添加两个全局位置变量以及一些局部位置变量,将文件中现在正在扫描的位置以及这个单词第一个字符的位置信息记录下来,然后捋清他们之间的关系以及使用目的,则问题也就解决了,并且也使得报错信息可以包含非法字符在文件中的位置所在。

    3.标识符表和常数表的动态生成:

    关于这个问题的解决,我将它放在了识别的过程当中,就可以做到动态生成,并且添加了文件追写,则可以在文件中查看生成的表信息了。

    4.输出显示:

    这个问题一开始实现的有些困难,当我发现它的重心在于认清每个单词的分类情况,并通过识别结果就可以很好的实现了。

    • 测试文件 code.txt

    int main(void) {
      int min=2, mid=3, max=1, t;
      if (min > mid) {
        t = min;
        min = mid;
        mid = t;
      }
      if (min > max) {
        t = min;
        min = max;
        max = t;
      }
      if (mid > max) {
        t = mid;
        mid = max;
        max = t;
      }
    }
    • 源代码

    #include<iostream>
    #include<fstream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<cstdlib>
    
    using namespace std;
    
    /*
    1:标识符
    2:数字 
    3:算数运算符 + - * 
    4:关系运算符 <=、  >=、  <>、  == =、 <、>
    5:保留字(32)
    auto       break    case     char        const      continue
    default    do       double   else        enum       extern
    float      for      goto     if          int        long
    register   return   short    signed      sizeof     static
    struct     switch   typedef  union       unsigned   void
    volatile    while
    6:界符 
    */
    
    int seekresult;		//fseek的时候用来接着的 
    string word="";		//字符串,当前词 
    char ch;			//每次读进来的一个字符
    int num=0;			//每个单词中当前字符的位置
    int line=1;			//行数
    int col=1;			//列数
    bool flag;			//文件是否结束扫描 
    int type;			//单词的类型
    
    //保留字表
    static char ReserveWord[32][20] = {
        "auto", "break", "case", "char", "const", "continue",
        "default", "do", "double", "else", "enum", "extern",
        "float", "for", "goto", "if", "int", "long",
        "register", "return", "short", "signed", "sizeof", "static",
        "struct", "switch", "typedef", "union", "unsigned", "void",
        "volatile", "while"
    };
    
    //算术运算符表
    static char SuanshuOperator[4][4] = {
        "+", "-", "*", "/"
    };
    //逻辑运算符表 
    static char GuanxiOperator[7][4] = {
        "<", "<=", ">", ">=", "=", "==","<>"
    };
    //界符表(12)
    static char Jiefu[36][4] = {
    	";", "(", ")", "^", ",", "#","%", "[", "]", "{", "}","."
    };
    
    //标识符表
    //string IDentifierTable[1000] = { "" };
    char IDentifierTable[1000][40] = {};
    
    //常数表 
    //int DigitBTable[1000][50] = {};
    char DigitBTable[1000][40] = {};
    
    int Inum=0;
    
    int Dnum=0;
    
    
    //判断是否是:字母
    bool Isletter(char x)
    {
    	if((x>='a'&&x<='z')||(x>='A'&&x<='Z'))
    		return true;
    	else return false;
    }
    
    //判断是否是:数字 
    bool IsDigit(char x)
    {
    	if(x>='0'&&x<='9')
    		return true;
    	else
    		return false;
    }
    
    //判断是否是:界符 
    bool IsJiefu(char x) 
    {
    	int i=0;
    	int temp=0;
    	for(i=0;i<14;i++)
    	{
    		if( x == Jiefu[i][0] )
    		{
    			temp=1;
    			break;
    		 } 
    	}
    	if( temp == 1 )
    		return true;
    	else
    		return false;
    }
    
    //判断是否是 算数运算符:加减乘
    bool IsSuanshuyunsuanfu(char x)
    {
    	if(x=='+'||x=='-'||x=='*')
    		return true;
    	else return false;
    }
    
    //判断是否是 关系运算符:等于(赋值),大于小于(大于等于,小于等于,大于小于) 
    bool IsGuanxiyunsuanfu(char x)
    {
    	if(x=='='||x=='<'||x=='>')
    		return true;
    	else
    		return false;
    } 
    
    //从文件里读一个单词 
    int Scanner(FILE *fp)
    {
    	//先读一个字符,赋值给ch 
        ch=fgetc(fp);
        
        if(feof(fp)){
            flag=0;
    		return 0;
        }
        else if(ch==' ')
        {
            col++;
            return 0;
        }
        else if(ch=='\n')
        {
            line++;
            col=1;
            return 0;
        }
        //如果是字母开头或 '_' 看关键字还是标识符 
        else if( Isletter(ch) || ch=='_' )
        {
            word+=ch;
    		col++;
            while( (ch=fgetc(fp)) && ( Isletter(ch) || IsDigit(ch) || ch=='_'))
            {
                word+=ch;
    			col++;
            }
    		//文件读完,返回true
            if(feof(fp)){
                    flag=0;
    				return 1;
            }
            //检验是否是保留字 
            for(int i=1;i<=32;i++){
                if( word == ReserveWord[i] ){
                	//SEEK_CUR当前位置,fseek函数作用:文件位置指针从当前位置位移一个位置 
                    seekresult=fseek(fp,-1,SEEK_CUR);
                  	//5+i-1:保留字 
    				return 5+i-1;
                }
            }
            for(int Ii=0;Ii<Inum;Ii++)
            {
            	if(Inum!=0 && strcmp(IDentifierTable[Ii],word.c_str())==0)
            	{
            		seekresult=fseek(fp,-1,SEEK_CUR);	
            		//1:标识符 
            		//return 1;
            		return 1000+Ii+1;
    			}
    		}
            strcpy(IDentifierTable[Inum],word.c_str());
        	Inum=Inum+1;
    		//写追加 
    		ofstream Arithmetic_operator;
    		Arithmetic_operator.open("IDentifierTable.txt",ios::app);
    		Arithmetic_operator<<word<<" "<<endl;
        	Arithmetic_operator.close();
        	
    		seekresult=fseek(fp,-1,SEEK_CUR);	
            //1:标识符 
            //return 1;
            return 1000+Inum;
        }
     
        //开始是加减乘,一定是算数运算符3 
        else if(IsSuanshuyunsuanfu(ch))
        {
            word+=ch;
    		col++;
    		//3:算数运算符 
            return 3;
        }
     
        //开始是数字就一定是数字2 
        else if(IsDigit(ch))
        {
            word+=ch;
    		col++;
            while((ch=fgetc(fp)) && IsDigit(ch))
            {
                word+=ch;
    			col++;
            }
            int Di=0;
            for(Di=0;Di<Inum;Di++)
            {
            	if(Dnum!=0 && strcmp(DigitBTable[Di],word.c_str())==0)
            	{
            		seekresult=fseek(fp,-1,SEEK_CUR);	
            		//2:数字 
            		//return 2;
            		return 2000+Di+1;
    			}
    		}
            strcpy(DigitBTable[Dnum],word.c_str());
        	Dnum=Dnum+1;
    		//写追加 
    		ofstream Arithmetic_operator;
    		Arithmetic_operator.open("DigitBTabl.txt",ios::app);
    		Arithmetic_operator<<word<<" "<<endl;
        	Arithmetic_operator.close();
       	
    //        if(feof(fp)){
    //                flag=0;
    //				return 2;
    //        }
    
            seekresult=fseek(fp,-1,SEEK_CUR);
            //2:数字 
            return 2000+Dnum;
        }
     
        //检验界符6 
        else if(IsJiefu(ch))
        {
        	int Ji;
    		for(Ji=0;Ji<12;Ji++)
    		{
    			if( ch == Jiefu[Ji][0] )
    			{
    				break;
    			} 
    		}
            word+=ch;col++;
            //6-1+32+i:界符 
            return (6-1+32+Ji);
        }
     
        //检验关系运算符4 :<=、>=、<>、==、 < 、>
        else if( IsGuanxiyunsuanfu(ch) )
        {
            col++;
            word+=ch;
    		//检验  <> <=
            if(ch=='<')   
            {
                ch=fgetc(fp);
                if(ch=='>' || ch=='=')
                {
                    word+=ch;
                    col++; 
                    return 4;
                }
            }
            //检验  >= ==
            else{
                ch=fgetc(fp);
                if(ch=='=')
                {
                    word+=ch;
                    col++;
                    return 4;
                }
            }
            if(feof(fp)){
                    flag=0;
            }
            seekresult=fseek(fp,-1,SEEK_CUR);
            //3:算数运算符 
            return 3;
        }
     
        //首字符是 / 有可能是除号 也有可能是注释
        else if(ch=='/')
        {
            col++;word+=ch;
            ch=fgetc(fp);
            //这种情况是除号
            if(ch!='*' && ch !='/')
            {
                seekresult=fseek(fp,-1,SEEK_CUR);
                //3:算数运算符 
                return 3;
            }
            //注释符//:这一行剩下的全被注释了
            if(ch=='/')
            {
                word.clear();
                while((ch=fgetc(fp)) && ch!='\n' && !feof(fp) )
                {}
                if(feof(fp)){
                    flag=0;
    				return 0;
                }
                else{
                   seekresult=fseek(fp,-1,SEEK_CUR);
                }
                line++;col=1;
                return 0;
            }
            if(ch=='*')
            {
                bool flag5=1;
                while(flag5)
                {
                    word.clear();
                    ch=fgetc(fp);
                    col++;
                    if(ch=='\n')
    				{
    					line++;
    					col=1;
    				}
                    if(ch!='*')
    					continue;
                    else 
    				{
                        ch=fgetc(fp);
                        col++;if(ch=='\n'){line++;col=1;}
                        if(ch=='/'){
                            flag5=0;
                        }
                        else continue;
                    }
                    if(feof(fp))
    				{
    					flag=0;
    					return 0;
    				}
                }
            }
        }
        else {
            word+=ch;
            col++;
            return -1;
        }
    }
     
    int main()
    {
    	FILE *fp;
        
    	cout<<"open "<<"code.txt"<<endl;
        system("pause");
     
        flag=1;
        
    	//打开源代码文件 
    	
    	//未打开 
        if((fp=fopen("code.txt","r"))==NULL)
        {
            cout<<"Sorry,can't open this file."<<endl;
            flag=0;
        }
        //已打开 
        while(flag==1)
        {
    		//反复调用扫描函数提取单词
            type=Scanner(fp);	
     		
    		//1:标识符
            if(type>1000&&type<2000)
            {
                //cout<<"type:1 identifier      "<<"line "<<line<<" col "<<col-word.length()<<"  "<<word<<endl;
                cout<<"("<<word<<","<<type-1000<<")"<<endl; 
    			if(word.length()>20)
                	cout<<"ERROR Identifier length cannot exceed 20 characters"<<endl;
                word.clear();
            }
    		//2:数字   
            else if(type>2000)
            {
                //cout<<"type:2 positive number "<<"line "<<line<<" col "<<col-word.length()<<"  "<<word<<endl;
                cout<<"("<<word<<","<<(type-2000)<<")"<<endl;
    			if(word[0]=='0')
                	cout<<"ERROR: The first digit cannot be 0!"<<endl;
                word.clear();
            }
    		//3:算数运算符 + - * / 
            else if(type==3)
            {
                //cout<<"type:3 unary_operator  "<<"line "<<line<<" col "<<col-1<<"  "<<word<<endl;
                cout<<"("<<word<<","<<"3"<<")"<<endl;
                word.clear();
            }
            
            //4:关系运算符 <、<=、>、>=、= 、<> 
            else if(type==4)
            {
                //cout<<"type:4 double_operator "<<"line "<<line<<" col "<<col-2<<"  "<<word<<endl;
                cout<<"("<<word<<","<<"4"<<")"<<endl;
    			word.clear();
            }
            //6-1+32 - 6-1+32+11:界符
            else if(type>=37)
            {
                //cout<<"type:5 Separator       "<<"line "<<line<<" col "<<col-1<<"  "<<word<<endl;
            	cout<<"("<<word<<","<<"_"<<")"<<endl;
    			//cout<<"("<<type<<","<<"_"<<")"<<endl;  
    			word.clear();
            }
           //5 - 5-1+32:保留字 
            else if( type>=5 && type<=36)
            {
                //cout<<"type:6 reserved word   "<<"line "<<line<<" col "<<col-word.length()<<"  "<<word<<endl;
                cout<<"("<<word<<","<<"_"<<")"<<endl;
    			//cout<<"("<<type<<","<<"_"<<")"<<endl;  
    			word.clear();
            }
            //非法字符
            else if(type==-1)
            {
               cout<<"Illegal character   "<<"line "<<line<<" col "<<col-1<<"  "<<word<<endl;
               word.clear();
            }
        }
            int a=fclose(fp);
            cout<<"Do you want to close?(Y or N)"<<endl;
            char end;
            while(cin>>end && end!='Y'){
                cout<<"Do you want to close?(Y or N)"<<endl;
            }
        return 0;
    }

     

    展开全文
  • 编译原理实验:词法分析

    万次阅读 多人点赞 2018-09-29 21:17:16
    编译原理实验:词法分析1. 实验题目:词法分析实验目的实验内容实验要求输入输出2. 设计思想3.算法流程4. 源程序5. 调试数据 1. 实验题目:词法分析 实验目的 根据PL/0语言的文法规范,编写PL/0语言的词法分析...

    1. 实验题目:词法分析

    实验目的

    1. 根据PL/0语言的文法规范,编写PL/0语言的词法分析程序;或者调研词法分析程序的自动生成工具LEX或FLEX,设计并实现一个能够输出单词序列的词法分析器。
    2. 通过设计调试词法分析程序,实现从源程序中分出各种单词的方法;加深对课堂教学的理解;提高词法分析方法的实践能力。
    3. 掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的法。
    4. 掌握词法分析的实现方法。上机调试编出的词法分析程序。

    实验内容

     已给PL/0语言文法,输出单词符号(关键字、专用符号以及其它标记)。

    实验要求

    1. 把词法分析器设计成一个独立一遍的过程。
    2. 词法分析器的输出形式采用二元式序列,即:(单词种类,单词的值)

    输入输出

    输入:
      const a=10;
      var b,c;
      begin
      read(b);
      c:=a+b;
      write( c);
      end.
    输出:
      (constsym, const)
      (ident , a)
      (eql, =)
      (number, 10)
      (semicolon, ; )
      (varsym, var)
      (ident,b)
      (comma, ,)
      (ident, c)
      (semicolon, ; )
      (beginsym, begin)
      (readsym, read )
      (lparen,( )
      (ident, b)
      (rparen, ))
      (semicolon, ; )
      (ident, c)
      (becomes, := )
      (ident, a)
      (plus, +)
      (ident,b )
      (semicolon, ; )
      (writesym,write)
      (lparen, ( )
      (ident, c)
      (rparen,) )
      (endsym, end )
      (period, .)

    2. 设计思想

    基本字:

    单词(编码) 正规式r
    begin(beginsym) begin
    call(callsym) call
    const(constsym) const
    do(dosys) do
    end(endsym) end
    if(ifsym) if
    odd(oddsym) odd
    procedure(proceduresym) procedure
    read(readsym) read
    var(varsym) var
    while(whilesym) while
    write(writesym) write
    then(thensym) then

    标识符:

    单词(编码) 正规式r
    <标识符>(ident) (字母)(字母 |数字)*

    常数:

    单词(编码) 正规式r
    <常数>(ident) (数字)(数字)*

    运算符:

    单词(编码) 正规式r
    +(plus) +
    -(minus) -
    *(times) *
    /(slash) /
    =(eql) =
    <>(neq) <>
    <(lss) <
    <=(leq) <=
    >(gtr) >
    >=(geq) >=
    :=(becomes) :=

    界符:

    单词(编码) 正规式r
    ( (lparen) (
    ) (rparen) )
    , (comma) ,
    ; (semicolon) ;
    . (period) .

    3.算法流程

    在这里插入图片描述

    1. 词法分析程序打开源文件,读取文件内容,直至遇上文件结束符,然后读取结束。
    2. 接下来就要对源文件从头到尾进行扫描了,从头开始扫描,这个时候扫描程序首先要询问当前的字符是不是空格,若是空格,则继续扫描下一个字符,直至不是空格。然后询问这个字符是不是字母,若是则进行标识符和保留字的识别;若这个字符为数字,则进行数字的判断。否则,依次对这个字符可能的情况进行判断(界符和运算符),若将所有可能都走了一遍还是没有知道它是谁,则认定为错误符号,输出该无法识别error,程序结束。每次成功识别了一个单词后,单词都会存在word1[]数组中,然后字符指针往后移,进行下一个单词的识别。
    3. 主控程序需要负责对每次识别的种别码进行判断,对于不同的单词种别做出不同的反应,直至文件结束。
    4. 本次实验我采用了map这个STL关联容器,主要是考虑到词法分析中的数据映射的关系,因此采用这种结构。map提供一对一的数据处理能力,其中第一个可以称为关键字,每个关键字只能在map中出现一次,第二个可能称为该关键字的值。这个容器是非常方便使用的,对于查找可以直接使用迭代器进行,利用find()函数,若一直到末尾都未找到,则是不能识别或为标识符。

    4. 源程序

    #include<bits/stdc++.h>
    using namespace std;
    map<string,string> word;//应用map数据结构形成一个string->string的对应
    std::map<string,string>::iterator it;//用来遍历整个对应关系的迭代器
    void map_init(){//对应关系进行初始化
        word["begin"]="beginsym";
        word["call"]="callsym";
        word["const"]="constsym";
        word["do"]="dosym";
        word["end"]="endsym";
        word["if"]="ifsym";
        word["odd"]="oddsym";
        word["procedure"]="proceduresym";
        word["read"]="readsym";
        word["then"]="thensym";
        word["var"]="varsym";
        word["while"]="whilesym";
        word["write"]="writesym";
        word["+"]="plus";
        word["-"]="minus";
        word["*"]="times";
        word["/"]="slash";
        word["="]="eql";
        word["<>"]="neq";
        word["<"]="lss";
        word["<="]="leq";
        word[">"]="gtr";
        word[">="]="geq";
        word[":="]="becomes";
        word["("]="lparen";
        word[")"]="rparen";
        word[","]="comma";
        word[";"]="semicolon";
        word["."]="period";
    }
    int main(){
        map_init();//初始化
        char ch;
        char a;
        string word1;//string变量识别单词
        string str;//string变量进行字符识别
        ifstream infile("F:\\编译原理\\第一次实验\\analysis.txt");//文件输入流
        ofstream outfile("F:\\编译原理\\第一次实验\\result.txt");//文件输出流
        ostringstream buf;
        while(buf&&infile.get(ch)) buf.put(ch);//将文件中的字符读出来
        str= buf.str();//将得到的字符储存到string类型变量中
        int csize=str.length();
        for(int i=0;i<csize;i++){//对整个字符串进行遍历
            while(str[i]==' '||str[i]=='\n') i++;//若最开始为空格或换行符,则将指针的位置往后移
            if(isalpha(str[i])){//对标识符和基本字进行识别,调用库函数isalpha()
                word1=str[i++];
                while(isalpha(str[i])||isdigit(str[i])){
                    word1+=str[i++];
                }
                it=word.find(word1);
                if(it!=word.end()){//判断是不是基本字,若为基本字则进行输出
                    cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
                }
                else{//否则直接输出
                    cout<<"(ident"<<","<<word1<<")"<<endl;
                }
                i--;
            }
            else if(isdigit(str[i])){//判断是不是常数,调用库函数isdigit()
                word1=str[i++];
                while(isdigit(str[i])){
                    word1+=str[i++];
                }
                if(isalpha(str[i])){
                    cout<<"error!"<<endl;
                    break;
                }
                else{
                    cout<<"(number"<<","<<word1<<")"<<endl;
                }
                i--;
            }else if(str[i]=='<'){//对<,<=分别进行判断
                word1=str[i++];
                if(str[i]=='>'){
                    word1+=str[i];
                    cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
                }else if(str[i]=='='){
                    word1+=str[i];
                    cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
                }else if(str[i]!=' '||!isdigit(str[i])||!isalpha(str[i])){
                    cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
                }else{
                    cout<<"error!"<<endl;
                    break;
                }
                i--;
            }else if(str[i]=='>'){//对>,>=分别进行判断
                word1=str[i++];
                if(str[i]=='='){
                    word1+=str[i];
                    cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
                }else if(str[i]!=' '||!isdigit(str[i])||!isalpha(str[i])){
                    cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
                }else{
                    cout<<"error!"<<endl;
                    break;
                }
                i--;
            }else if(str[i]==':'){//对:=进行判断
                word1=str[i++];
                if(str[i]=='='){
                    word1+=str[i];
                    cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
                }else{
                    cout<<"error!"<<endl;
                    break;
                }
                i--;
            }else{//对其他的基本字依次进行判断
                word1=str[i];
                it=word.find(word1);
                if(it!=word.end()){
                    cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
                }else{
                    cout<<"error!"<<endl;
                    break;
                }
            }
        }
        infile.close();
        return 0;
    }
    

    5. 调试数据

    待输入的文件流:
    在这里插入图片描述
    输出数据:
    在这里插入图片描述
    在这里插入图片描述
    说明:如上实验仅符合当时实验要求的相关条件,其他的需求略微进行更改就行,思想是一样的,还是很简单的。输入输出自己按自己需求更改即可。

    展开全文
  • 编译原理词法分析(项目报告)

    千次阅读 2018-07-21 19:52:00
    理解词法分析在编译程序中的作用,加深对有穷自动机模型的理解,掌握词法分析程序的实现方法和技术,加深对编译原理的理解,掌握编译程序的实现方法和技术至关重要。 本次项目则为简单的词法分析,通过设计编制...
  • 编译原理及交叉编译

    2018-04-20 12:51:17
    转载: https://blog.csdn.net/testmyieda22/article/details/51444804编译原理及交叉编译编译原理gcc/g++在执行编译的时候,只要分四个阶段 :1、预处理阶段,完成宏定义和include文件展开等工作;不生成文件 [预...
  • 编译原理学习(一)词法分析

    千次阅读 2016-11-22 22:22:52
    理解词法分析的工作原理。 掌握利用状态转换图设计词法分析的基本方法。 实现Micro语言的词法分析程序 二. 实验内容根据给出的Micro语言的定义,设计并实现它的的词法分析,实现源程序的输入、 预处理和词法...
  • 编译原理】引论

    千次阅读 2020-02-18 20:59:54
    文章目录编译原理引论(一)认识编译程序(二)编译过程概述1、阶段划分2、编译程序的结构3、编译程序的生成 编译原理引论 (一)认识编译程序 什么是编译程序? 这要从翻译程序、解释程序以及编译程序的联系与区别...
  • C语言的编译原理及过程

    万次阅读 2016-07-13 10:08:21
    前几天有个朋友问我关于C语言的编译原理和编译的过程,当时我也没有说明白,今天特意在书上和网上查阅资料,简单的总结了一下关于C语言的编译原理及过程。  集成开发环境是用于提供程序开发环境的应用程序,一般...
  • 编译原理)java实现词法分析

    万次阅读 多人点赞 2017-10-30 13:49:04
    1、闲话最近在学编译原理,需要用语言实现一个词法分析,其实挺简单的,主要涉及一些语言字符串操作处理,如果会正则表达式的话,感觉实现这个会很简单,但是我并不会啊,然后自己用java实现了,也算是加强了对...
  • 对于编译原理的理解

    千次阅读 2018-03-15 20:42:31
    编译原理 今天组长教育了一下整个程序的编译过程,感觉自己对于这块了解还是很少,有许多知识之前知道,现在忘记了,还有很多规则只是知道,但并不知道它为什么要这样写,所以再次记录一下,有什么问题或者错误...
  • 编译原理:词法分析实验报告

    万次阅读 多人点赞 2019-04-29 15:59:37
    词法分析实验报告 文章目录词法分析实验报告一、实验目的二、实验原理三、实验要求四、...设计、编制并调试一个词法分析程序,加深对词法分析原理的理解。 二、实验原理 词法分析程序的基本任务是从字符串表...
  • Android系统编译原理

    千次阅读 2017-01-20 11:41:31
    Android系统编译原理 [1] 历史  2003年Android公司成立,系统开发  2005年Android被google收购  2007年11月5日,google公司推动成立手机开发联盟(HAL)  2008年9月Android 1.0正式发布,HTC G1使用   ...
  • 编译原理知识点

    千次阅读 多人点赞 2019-05-16 09:15:52
    1. 编译程序(编译器):先将源程序翻译成汇编语言程序或机器语言程序(称为目标程序),然后再执行它。 2. 解释程序(解释):按解释方式进行翻译的翻译程序称为解释程序。解释程序的主要优点是便于对源程序进行...
  • 编译原理分析过程

    千次阅读 2017-01-22 21:26:06
    一、编译原理概述 编译程序就是把高级语言源程序生成为汇编代码的过程,生成的汇编代码再由汇编连接等生成目标机器上的可执行代码。 一般编写高级语言编译程序采用自举形式,如,C语言编译器首先由其他语言如...
  • Linux C编译原理

    千次阅读 2018-09-28 22:11:17
    1.编译程序:把一种语言(源语言---高级语言)转换成另一种语言(目标语言---低级语言--&gt; 汇编或机器语言)。 2.词法分析:对输入的字符串进行扫描和分解,识别出一个个字符及其数据类型; 3.语法分析:对...
  • C语言编译原理介绍

    千次阅读 2014-04-02 20:46:01
    c语言编译原理图 1、预处理指令:gcc -E file.c -o hello.i # 删除所有的注释,以空格代替 # 将所有的#define删除,并且展开所有的宏定义 # 处理条件编译指令#if,#ifdef,#elif,#else,#endif  指令 用途  # ...
  • 编译原理-词法分析的原理及实现

    千次阅读 2019-12-21 22:47:31
    设计、编制并调试一个词法分析程序,分析一段程序的词法,包括:过滤无效字符、数值转换、宏展开、预包含处理等,加深对词法分析原理的理解。 2.单词分类表 单词分类表如表1所示 类别 类别码 类别 类别码 ...
  • 编译原理(一、引论)

    千次阅读 2018-03-06 18:58:21
    前言:最近学习编译原理,遂参照教材作以记录。各位读者若对本文所述有质疑,欢迎批评指正。 参考:《程序设计语言——编译原理》第3版 陈火旺 刘春林 谭庆平 赵克佳 刘越 编著 国防工业出版社 程序设计语言...
  • 编译原理--词法分析

    千次阅读 2017-11-23 22:11:55
    设计、编制并调试一个自定义语言C--的词法分析程序,加深对词法分析原理的理解。 二、 实验内容 2.1 自定义语言C--的词法系统 1)类型系统:支持int、char、void基本类型,分别用词法记号表示为关键字int、char和...
  • 编译原理实验:语义分析及中间代码生成

    万次阅读 多人点赞 2018-09-29 22:47:27
    编译原理实验报告:语义分析及中间代码生成1. 实验题目:语义分析及中间代码生成实验目的实验内容实验要求输入输出2. 设计思想3.算法流程4. 源程序5. 调试数据 1. 实验题目:语义分析及中间代码生成 实验目的 通过...
  • 编译原理------词法分析C/C++代码实现

    万次阅读 多人点赞 2019-04-17 10:08:27
    设计、编制并调试一个词法分析程序,加深对词法分析原理的理解。 二、实验内容 2.1 待分析的简单的词法 (1)关键字: begin if then while do end 所有的关键字都是小写。 (2)运算符和界符 : = + - * / &...
  • TINY编译器《编译原理

    千次阅读 2016-03-17 21:37:49
    实现TINY+编译器 ,华南理工大学,《编译原理》课程实验
  • 编译原理的地位 是软件技术的基础 是计算机专业的基础课程,是专业必修课 编译原理的作用 编译原理是介绍如何将高级语言程序变换成低级语言程序的方法。 其理论基础坚实,其形式化系统不仅用于编译程序,还大量...
  • 编译原理实验:自下而上语法分析

    千次阅读 2018-09-29 22:26:12
    编译原理实验报告:自下而上语法分析1. 实验题目:自下而上语法分析实验目的实验内容实验要求输入输出2. 设计思想3. 算法流程4. 源程序5. 调试数据 1. 实验题目:自下而上语法分析 实验目的 给出PL/0文法规范,...
  • 编译原理是计算机专业的一门重要专业课,旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。 编译原理是...
  • 学会用lex设计一个词法分析。 实验内容: 使用lex为下述文法语言写一个词法分析。 语言文法: <程序> --> PROGRAM <标识符> ; <分程序> <分程序> --> <变量说明> BEGIN <...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 82,195
精华内容 32,878
关键字:

编译原理调试器