（计算机软件与理论专业论文）编译原理辅助教学软件系统.pdf

东北大学硕士学位论文摘要 编译原理辅助教学软件系统 摘要 编译原理是现代计算机系统的重要组成部分。在计算机科学的课程中，编译原理占有非 常重要的位置。它是每个计算机专业的学生必修的一门课程。但是，编译原理较其它计算机 专业课程而言，显得过于枯燥、抽象和难于理解。所以，本课题研究的目的就在于希望利用 目前先进的可视化系统集成开发环境，开发出一套编译矩理课程辅助教学软件系统，并将该 系统运用到教学实践中去。其意义在于使学生对编译原理这门课程的内容有一个更加直观的 认识，加深学生对编译原理这门课程的理解，唤起学生的学习兴趣，从而提高教学质量。这 也是适应二。卜一世纪教学改革的需要。而且此次开发用到的技术和概念也可以应用到一般软 件设计与开发中去。 本系统是在v i s u a lc + + 6 0 环境下开发的编译原理辅助教学软件系统。它主要分为两大部 分，第一部分是编译原理教学的课程演示系统。主要实现了文法基础知识演示、自动机状态 图表示、自动机的确定化和最小化、自顶向下语法分析u 。1 分析方法、自底向上语法分析简 单优先分析方法、算符优先分析方法、l r 0 分析方法、s l r l 分析方法、l r l 分析方法。实现 了自动构造l r 0 、s l r i 、l r l 分析表。第二部分为编译器系统结构。主要实现对给定的类p a s c a l 源程序进行编译，并显示词法分析结果、符号表、中间代码生成结果等信息。 本系统中的各个部分都经过人量的实例反复测试，实验表明，各部分正确无误，效果良 好。 关键字：编译原理，语法分析，符号表，语义分析中问代码 l i 东北大学硕士学位论文摘要 a b s t r a c t t h ec o m p i l e rc o n s t r u c t i o ni st h es i g n i f i c a n tc o m p o n e n to fc o n t e m p o r a r yc o m p u t e r s y s t e mt h ev e r ys i g n i f i c a n tp l a c ei sp r o s s e s s e dt dt h ec o m p i l e rp r i n c i p l e si nt h e c o m p u t e rs c i e n t i f i cc u r r i c u l u m s ，a n di ti st h ec o m p u l s o r yc u r r i c u l u mf o re v e r ys t u d e n t o fc o m p u t e rs p e c i a l i z e ds u b j e c ty e t ，c o m p i l e rp r i n c i p l e ss e e m sm o r eu n i n t e r e s t i n g , a b s t r a c ta n dd i f f i c u l tt ou n d e r s t a n dt h a nt h eo t h e rc o m p u t e rc u r r i c u l u m s t h e r e o ft h e a i mo ft h i sd i s c u s s i o ni sd e v e l o p i n gt h ea s s i s t a n ti n s t r u c t i o ns o f t w a r es y s t e mo f c o m p i l e rp r i n c i p l e sb yu s i n gt h ea d v a n c e dv i s u a ls y s t e mi n t e g r a t i o nd e v e l o p m e n t e n v i r o n m e n t ，m o r e o v e ru t i l i z i n gt h es o f t w a r et ot h ee d u c a t i o np r o c e s s s u c hs e n s el i e s i nt h a ti tc a np a u s es t u d e m sp o s s e s s i n gt h em o r ea u d i o _ v i s u a ll e a r n i n go f t h ec o m p i l e r p r i n c i p l e s ，u n d e r s t a n d i n gt h i sc u r r i c u l u md e e p l y , a n di ta l s os t i m u l a t et h ei n t e r e s to f s t u d e n t s t h e r e b yi tc a l li m p r o v et h ee d u c a t i o nq u a l i t y t h i si st h ed e m a n do fa d a p t i n g t o2 1 c e n t u r yr e f o r m si ne d u c a t i o n a d d i t i o n a l l y , s o m ec o n c e p t i o n sa n dt e c h n o l o g i e s t h a ta r eu s e di nt h i sd i s c u s s i o no a nb eu t i l i z e dt od e s i g na n dd e v e l o ps o m eo t h e r s o f t w a r e t h i s s y s t e mi s a na s s i s t a n ti n s t r u c t i o ns y s t e mo fc o m p i l e rp r i n c i p l e s i ti s d e v e l o p e du n d e rv i s u a lc + + 60c i r c u m s t a n c e s i tc o n t a i n st w os e c t i o n s t h ef i r s t s e c t i o ni st h ec o m p i l e rp r i n c i p l e st e a c h i n gd e m os y s t e m t h em a i nb o d yi sf o u n d t i o no f g r a m m a r s ，t h et r a n s i t i o ng r a p ho f f i n i t ea u t o m a t i o n , c o n v e r s i o no f an f at ot h ed f a , m l n l m l z m gt h ed f a , t h el l lp a r s i n ga l g o r i t h mo fu p _ d o w np a r s i n ga n do t h e r s a l g o r i t h mo fb o t t o m _ u pp a r s i n g i tr e a l i z eb u i l d i n gl r 0 ，s l r la n dl r lp a r s i n gt a b l e a u t o m a t i c a l l y t h es e c o n ds e c t i o ni st h es y s t e ms t r u c t u r eo fac o m p l i e r i tc a l lc o m p i l e t h es o u r c ep r o g r a ms i m i l a rt op a s c a l ，a n ds h o wt h er e s u l to fs y n t a xa n a l y s i s ，s y m b o l t a b l ea n di n t e r m e 赫ec o d ei n f o r m a t i o n , a n ds oo n a l lt h ep a r t so f t h i ss y s t e mh a v eb e e nt e s t e dr e p e a t e d l yb yl a r g eq u a n t i t ye x a m p l e s i th a sb e e nt e s t i f i e dt h a ta l lt h ep a r t so ft h i ss y s t e ma r ec o r r e c ta n de f f e c t i o v eb y e x p e r i m e n t a t i o n k e y w o r d ：c o m p i l e rp r i n c i p l e s ，g r a m m a r sp a r s e ，s y m b o lt a b l e ，s e m a n t i ca n a l y s i s ， i n t e r m e d i a t ec o d e i r 声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或 撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 本人签名：南致 日期：五邪华，、8 东北太学硕士学位论文第一章绪论 1 1 引言 第一章绪论 “编译原理”是计算机专业特别是计算机软件专业的一门重要专业课。设置奉课程的目 的在于系统地向学生讲述编译系统的结构、工作流程及编译程序备组成部分的设计原理和实 现技术，使学生通过学习本课程，既掌握编译理论和技术方面的基本知识，也具有对编译器 的分析、设计、实现等方面的初步能力。 编译器的编写涉及到程序设计语言、计算机体系结构、语言理论、算法和软件工程等学 科。编译原理是计算机专业中最难的课程之一。在理论上它要求学生掌握冉关形式语言和自 动机的抽象概念，在技术上要求学生能够熟练地利用各种数据结构进行编程。编译原理教学要 求学生对形式语言和其内部结构有一个较深刻的认识。为此，我选择了“编译原理辅助教学 软件系统”做为研究课题希望借此帮助广大学生更好地学习这门课程。 1 2 本课题研究的目的和意义 随着计算机科学技术以及多媒体技术的迅猛发展计算机辅助教学作为一种新颖的教学 方式，逐步进入我国教育领域的各类学校的各个学科，引起教学模式、教学方法以及教学思 想的重大变化。在高等院校中许多课程理论性较强，且不容易形象地把教学内容表示出来， 编译原理就是典型的这类课程。编译原理是计算机学科中一门重要的课程。编译程序是一个 大的复杂的系统软件，其内容抽象，学生理解上存在一定的困难 虽然目前在编译理论与方法上的研究及成果已有很多，而且在编译程序设计这个领域里 已实现了词法分析研究器和语法分桥器的自动生成工具，如l e x 、y a c c 等。但在编译原理 教学过程中，现在还没有一套完整的编译过程演示系统软件。常见的软件一般都针对编译过 程的某部分或某一方法。还有一些在d o s 下开发的演示软件，受开发工具的限制，图形界 面不够清晰，操作复杂，所以本次研究就是希望棚目前先进的可视化系统集成开发环境， 开发出一套界面简洁，操作筒警的图形化演示系统。 、 本次研究的一个重要目舳就是调动学生对这门课学习的必趣，并探讨编译原理的实验教 学的方向。编译原理这门课程过去在教学中进行讲解时，主要依靠手工的板书来书写各种分 析技术的中间结果。即使改变为多媒体教学，也存在无法对讲解的实例进行修改的弱点。这 次设计的辅助教学系统就是要用一种交互式的方式，随时分析同学们设计的文法，或是解答 课后练习，以提高学生的兴趣，二减少教帅的工作量t 一 编译原理的教学一般都是从文法和语言的基础知识开始，沿着词法分析、语法分析、语 义分析、语法导翻译、中间代码生成及符号表维织序列进行。这种教学方式本着南浅入深， 可以逐渐带动学生进行深入学习。但是，这样一来，学生在学习过程中，可能直至中间代码 东北大学硕士学位论文第一章绪论 生成以后才能得到编译器的一个完整的概念。而这时一半的课时已过，对编译器进行深入的 探讨也成了泡影。在编译原理的教学开始如粜直接讲解编译器的全部技术。学生又无法完全 理解。这次丌发的“编译原理辅助教学软件系统”实观了编译器分析过程的总体演示。如果 在讲课开始就为学生演示这部分内容，他们就对编译器有一个完整的印象，有助于更深入 地学习。 设计这个系统并不是单纯重复前入的工作。同类软件目前只看到清华大学计算机系为c a i 教学软件大赛设计的编译原理辅助教学软件p 和吉林大学计算机科学与技术学院编译原理 多媒体c a i 课件p 例c a i ( p r i n c i p l eo rc o m p i l em u l t i m e d i ac a i ) 1 0 ) o 前者是在s 环境下开 发的，界面受到操作系统的限制明显不如本系统。本系统不仅可以处理拥有循环、条件、赋 值语句的程序，而且在输出界面上尽量显示所有中问结果：在用于教学演示目的后，还实现 了编译器的前端。 本课题的总体设计完全依据编译原理的教学内容，即上下文无关文法基础及词法分析、 语法分析技术研究、语法制导的语义翻泽、代码优化及目标代码生成。该系统分为教学演示 和编译器开发两部分。前者做为一个解题系统，涵盖了文法基础、词法分析及语法分析的内 容。后者则真止实现一个编译器。限于时间关系，此次开发并没有完全涵盖编译器的全部内 容。剩余部分将做为后期开发的内容。 1 。3 编译系统及编译过程概述 编译系统是现代计算机系统的重要组成部分。从功能上看，一个编译程序就是一个语言 翻译程序。它把一种语言( 源语言) 书写的程序翻译成另一种语言( 目标语畜) 的等价程序。 一个编译程序的重要性体现在它使得多数计算机用户不必考虑与机器有关的繁琐细节，使程 序员与程序设计者独立于机器 2 1 。在编译技术的出现后，人们才设计了高级语言，这些语言 摆脱了机器语言繁琐的细节，更接近于人的自然语言，并迅速流行开来。 1 3 1 编译程序的阶段 薯拇桂序 图11 编译器的阶段 f i g1 1t h ep h a g e so f ac o m p i l e r 2 编译器前端 编译器后端 东北大学硕士学位论文第一章绪论 编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体过程。从概念_ ：讲， 一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转换 成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的，图ll 所示的是一 种典型的划分方法。这种划分将编译过程划分成词法分析、语法分折、语义分析、中闻代码 生成、代码优化和目标代码生成六个阶段【1 】。另外两个与这六个阶段都有关系的重要工作是 符号表管理和出错处理。 1 3 2 编译程序的分组与分遍 编译程序的阶段又被分为前端( f r o n te n d ) 和后端( b a c ke n d ) h j 。前端通常是指那些依 赖于源语言，而与目标机无关的部分。这砦阶段包括词法分析、语法分析、语义分析和中问 代码生成。某些优化工作也可以在前端完成。当然，前端也包括与前端每个阶段有关的出错 处理和符号表管理工作。后端工作足指那些依赖于目标机而一般不依赖源语言只与中问代 码有关的阶段。即目标代码生成和相关的m 错处理及符号表操作。 可以设想，不同语言编译的前端生成同一种中间语言，再使用一个共同的后端，则可以 为同一机器生成几个语言的编译程序。 一个编译过程可出一翅、两遍或多遍完成。所谓“遍”，是指对源程序或其等价的中间 语言程序从头到尾扫视并完成规定任务的过程l j 】。对于有优化处理的编译过程一般会由两遍 完成。 1 4 本系统的设计思想 基于辅助教学的目的，本软件的功能不仅在于最终得到一个分析结果，更重要的是所有 中间分析步骤的输出显示，即要具有动态跟踪显示的作用。 1 4 1 中闻步骤的存贮 本软件为各种分析方法设计了大量的结构数组用于保存分析过程。在输出时不仅要 输出分析结果，更主要的足输出了c p 闻分析步骤，方便观看分析结果，以使学生对编译过程 有一个直观的认识，d i l n 对各种分析方法的了解，激发学生的学习兴趣。例如，实际上，一 个编译器在语法分析中并不真正地实现并存贮4 棵语法树，只是一步一步地按语法分析的要 求，得出一个结沧。这里，为了保存中间分析步骤，专门设计了一个数组，用于保存各个分 析步骤中的当前读入符号、剩余符号串、符号栈的内容及栈动作。另外，还设汁了一个树数 组，存放所有分析过的文法符号，并标记彼此问的父子关系，用于在屏幕上画出语法树。在 算符优先分析中，实际的f i r s t v t 矩阵实际只要求填写真假标记，实现时则用填写次序来代 替原标记。 东北太学硕士学位论文第一章绪论 1 4 2 程序清晰可读，方便以看扩充 在软件设计巾，叶1 间分析步骤的输出一般有两种方式，一种是在分析过程巾实时输出， 这种方式不存贮中间运算结果。第二种方式是在分析过程中存贮所有的中间结果，在分析结 束后，再按要求进行输出。在本系统设计中采用的就是第二种方法。 在实际输出时，木系统将所有的分析结果均存贮到数组中，在实际分析结束后，一步一 步地将中间结果显币的屏幕上。这样可以将分析过程与结果显不隔离，使程序更加清晰可读， 也方便以后的扩展。本系统设计过程中，考虑到实际教学的应用，所有屏幕输出基本上按照 教师的板书习惯设训，尤其是在语法分析过程中，考虑到教学中必定要用到前后分析步骤对 比，所以并没有刻意追求单步分析，只是列表表现中间分析步骤。这一点与教师的板书形式 是一模样的。这种先存贮中间结果后进行输出的设计方式，最大好处就在于以后想将输出 界面转化为单步输出时，只要增加相应的消息响应就可以了。 1 5 本系统的主要内容 1 5 1 整体设计 图12 编译原理课稃教学演示系统结构圈 f i g1 2t h es t r u c t u r ec h a r to f c o m p l i e rp r i n c i p l e st e a c h i n gd e m os y s t e m 4 东北走学硕士学位论文 第一章绪论 本系统分析为两部分，第一部分为编译原理课程的教学演示系统。它主要涵盖了文法基 础词法分析与语法分析部分。第二部分是实现一个编译器。因为语义分析及至中问代码生 成不再是个孤立的步骤，它是整个穿插在语法分析中间实现的，并且依据不同的程序语言 设计文法会采用不同的分析方法。单独创建一个语义分析和中问代码生成的演示系统将割裂 这种关系。鉴于第一部分已经对现阶段常用的语法分析方法进行了演示和实现，所以第一部 分，设计实现了一个编译器，并将前一部分的工作整合起来，以便形象化地演示。 其中编译原理课程教学演示系统的系统结构如图12 所示。 编译器设汁的系统结构如图l3 所示。 1 5 2 系统的类设计 图1 3 编译器系统结构圈 f i g1 3t h es y s t e ms t 兀l c t u r ec h a r to f t h e c o m p l i e r 图1 4 编译原理教学演示系统的类关系图 f i g 14t h ec l a s sr e l a t i o no f c o m p i l e rp r i n c i p l e st e a c h i n gd e m os y s t e m 在系统设计中，考虑到一个文法首先拥有自己的属性，即文法四元组，另外它拥有自已 的动作，即可以测试一个符号串是否是自已文法的合法句子。这样一个属性( 数据) 与动作 东北大学硕士学位论文第一章绪论 ( 函数) 紧密相关的个体完全符合面向对象设计的要求，为此，此次系统设计是面向对象的 编程的单位是类。 在编译原理课程教学演示系统中类的关系如图1 4 所示。 编译器类关系如图15 所示。 图i 5 编译器的类关系图 f i g1 5t h ec l a s sr e l a t i o no f c o m p i l e r 以类为甲位进行编程不仅将数据及其操作封装起来，而且是软件复用的一个有效途径。 在教学演小系统中，c m y c a a m m a r s 类、c l r o c r r a m m a r s 类、c s l r l g r a m m a r s 类问的继承关 系就充分体现了这种好处。不仅节约了设计时间，也体现了对象彼此问的关系。例如一开始 曾设想c l r l g r a m m a r s 类也做为c l r o c r r a m m a r s 类的子类，但在设计中，发现它们之间的关 系与c s l r l g r a m m a r s 与c l r o g r a m m a r s 类的关系不同，所以赢接将c l r l g r a m m a m 做为文 法基类的子类。 1 5 3 系统的输出设计 上面已经说过，在辅助教学系统的设计中，最重要的是结果的输出设计。在本系统中， 根据不同的教学内容i t 嫒计了不同的屏幕输出形式。 ( 1 ) 文法基础知识的输出 文法基础知识方面由于算法相对简单，：易于理解，因此，输出孵只是将原始文法与变换 后的文法对照输出。 ( 2 ) 自动机知识部分 自动机知识难于讲解的地方在于自动机的转化过程。在输出时，我对所有中问变换的结 果均按生成的顺序进行输出，而不是考虑美观的方式进行j # 序输出。 自动机的图形输出中，所有状态直线排列，这样可以占用较小的空间，转换标记则按高 度进行、馊计，以防止弧线交叉的过于复杂。 ( 3 ) 诃法分析部分 词法分析的重点在于程序语句的分割与分类，在屏幕的输出要将所有查找或填写的表格 列出来。 ( 4 ) 语法分析部分 东北大学硕士学位论文 第一章绪论 无论自项向下还是自底向上的语法分析中均要用到分析表和分析控制程序，在课堂讲解 中，最容易混淆也是最费时间的也是这两部分。本系统语法分析屏幕输出的基本格式如下： 图l6 语法分析的屏幕输出格式 f i g 1 6t h eo u t p u t i n gf o r mo f g r a m m a r sp m i n g ( 5 ) 符号表部分 符号表部分讲解的难点不在于它的构造算法，而在于它的复杂和庞大，在于对它存取访 问的频繁度。即使构造一个简单的符号表也有着复杂的指向和对应关系。冈此在屏幕卜要输 出一个符号表的各个部分，让学生有一个直观的了解。 ( 6 ) 语义分析及中间代码生成 前面已经讲过，语义分析及至中间代码生成不是一个孤立的步骤，它是整个贯穿在语法 分析中闯。所以这部分的演示是在编译器分析追踪中完成的。在屏幕上的输出格式如下： 图l ，7 编译器的屏幕输出格式 f 远1 _ 7t h eo u t p u f i n gf o r mo f t h ec o m p i l e r 东北大学硕士学位论文 第一章绪论 1 5 4 软件配置 本系统开发环境为：w i n d o w s9 8 操作系统下的面向对象的可视化开发系统v c + + 6 0 。 东北大学硕士学位论文第二章编译原理基础知识 第二章编译原理基础知识 2 。1 产生式文法的化简和改造 编译过程是一个非常复杂的信息加工过程。我们在这个过程中首先遇到的就是如何确切 地描述和定义种程序语言，其次是如何识别和分析这种语言。 在2 0 世纪5 0 年代，n c h o m s k y 首先对语言的描述问题进行探讨“。他提出种用来描述 语言的数学系统，并以此定义了四类性质不同的文法和语言。人们把用一组数学符号和规则 来描述的语言方式称为形式描述，把所用的数学符号和规则称为形式语言。这里所说的“形 式”是指仅考虑数学符号闻的推演，而不涉及符号的具体含义。 2 1 1 文法的有关概念 定义1 ： 一个用来描述语言语法结构的文法g 【4 可形式地定义如下： 一个文法g s l g 粼如( ，p ，s ) 的四元式。其中，p 均为非空 的有限集，分别称为非终结符集、终结符集和产生式集。具体来说： ，一系列需要定义的语法范畴， ，若干基本符号，不需要进一步定义， p ，用“ ”连接起来的有序对( a ，口) 的集合，称为规则，也叫产生式。其中a 是一个 非终结符，g 是一个由终结符或非终结符组成的符号串，即口帆u ) 。 s ，是文法的开始符号。s 此外，我们还将出现在产生式左、右侧的全部符号的集台称为词汇表，记为v 。显然： v = u ；n = 庐。 更确切地说，上面给出的是上下文无关文法的定义。这是因为由符号串口去替换a 时， 并不考虑a 所处的环境，即与a 的上下文无关。除非另做说明，我们以后所说的文法均指上 下文无关文法。 定义2 ： 设g 【s 】是一个文法，我们把能由文法的开始符号s 推导出的符号串口称为g 的一个句型。 当口仅由终结符号组成时，称之为g 的一个句子。 东北大学硕士学位论文第二章编译原理基础知识 定义3 ： 设g f s 】是一个文法，我们把g 所产生的全部句子所组成的集合称为g 产生的语言。记为 l ( g ) 。 定义4 ： 设g i ，g 2 是两个文法，若l ( g 1 ) = l ( g 2 ) ，就称g l ，g 2 两个文法等价。 2 i 2 文法类的设计 v c + + 使用类来定义存放拥有数据和行为的实体。这里，设置一个c m y g r a m m a r s 类，其 实例存放文法的四元式。 c m y c j r a m m a r s 类的数据成员定义如下： c l a s sc m y ( 逾m p u b l i c ： v o i ds o t g r a m m a r s ( c e x p r e a c c o p t p a r a d l g + ) ；，设置一个方法实例 安全的动态数组，存放表达式数组，用a l p h a a n d c o n e n t 结构的 f f c h a r 部分存放产生式的左部，用c s w m g 部分存放产生式的右部。 n m a r k 部分存放产生式的处理标志，是否被分分割，或是否有用 c a r r a y a r e g u l a r e x p r e s s i o n ； c s a i n gs v n c o l l e e t ； c s 矗n gs v t c o l l e c t ；，字符串，存放终结符集及非终结符集 t c h a r c b e g i n a l p h a ； 文法的开始符号，属于s v n c o l l e e t 集合 c s 雠n gs n u l l v n c o l l e e t ；g 含所有可以+ 推导出n u l l 的非终结符 b o o lb n u l l l a n g u a g e ； 文法定义的语言是否含有空符号串e 的标记 ，存放可推出单产生式的非终结符。它的a l p h a 分量存放非终结符 它的c s t r i n g 分量存放该非终结符+ 推导出的其它非终结符。 c a n a y e s ；s 一 a b ；a - a a b ；b - b b ；a - n ；b 一 n 运行结果为： 图2 4 删除空产生式的演示结果 f i g 2 4t h ed e m or e s u l to f d e l e t i n g8 一r e g u l a re x p r e s s i o n 2 1 6 单产生式的消除 2 1 6 1 单产生式的定义 我们把右部仅含有一个非终结符的产生式，即形如a b ，( a ，b ) 的产生式称为 东北天擘硕士学位论文第二章编译原理基础知识 单产生式。如果个文法含有过多的单产生式，将会增加编译程序在工作中所需要的时间和 存储空间。 本节中所使用的算法，要求所给文法已消除e 产生式。 2 1 6 2 消除单产生式的算法f 2 1 ( 1 ) 对每一个非终结符a l 作它的单产式可以推导出的f 终结符的集合w i ( 2 ) 构造产生式集 p i = u 口f 寸盘| b - - ) - 口，b 聊，口匹 j = l ( 3 ) 所得的新文法g 1 - ( ，p i ，s ) 所定义的语言是与原文法g 等价的。若g i 中 含有无用符号或无用产生式，可用相应的算法消除。 2 i 6 3 删除单产生式的算法的实现 该功能通过主菜单“文法分析”的“消除单产生式”菜单项实现的。 首先弹出对话框接收文法参数。 这里设文法示例为：非终结符s ，a ，b ；终结符如；开始文法符号s 产生式集为：s - a b ；s 一 a ；s - b ；a 一 a a b ；a 一 a b 零一 b b | b - b ， 运行结果为： 倒25 删除争产生式明 黄不结果 f i g25 t h ed e m or e s u l to f d e l e t i n gs i m p l er e g u l a re x p r e s s i o n 1 6 东北大学硕士学位论文 第二章编译原理基础知识 2 2 自动机演示及确定化 2 , 2 1 自动机的基本概念 有限自动机( f i n i t ea u t o m a t a ) 是语言的一种识别工具，它能准确地识别正规文法所定义 的语言和正规式所表示的集合。它读入一个串x ，如果x 是语言中的句子，则接收，否则， 不予接收。引入有限自动机理论，是为词法分析自动构造找到的特殊方法和工具。 一个有限自动机m 是一个五元组的数学模型： m = ( s ，6 ，s o ，f ) 其中：s 是状态的有限集合，集合中的每个元素是自动机的一个状态； 字母表，即输入符集； 8 变换函数；形式为艿 j ，a ) = s ，其中s ，一e s ，a ，6 表示从s 状态接收字 母a 到达s 状态； s o 初始状态；s 。s 确定的有限状态自动机的初始状态是唯一的； f 结束状态集合：f c _ s ，f 可以不唯一； 有限自动机分为两类，确定的有限自动机( d e t c x m i n i s 6 c f i n i t e a u t o m a t a ，d f a ) 和非确定 的有限自动机( n o n d e t e r m i n i s t i cf i n i t ea u t o m a t a ，n f a ) 。所谓d f a 是指，在当前状态下输入 一个符号，有穷自动机转换到唯一的下一个状态( 后继状态) ，d f a 只有一个初始状态。而 n f a 在当前状态下输入一个符号可能有不少于两种可选择的后继状态，n f a 的开始状态不唯 一，是一个集合，即n f a 开始状态不唯一，变换函数不单值。值得注意的是，n f a 可以带 有e ( 空) 边。n f a 较易实现，但分析时会有回溯，因此要把它转化为d f a 。 有限自动机可以用有向图表示，称为“状态转换图法”。一个状态转换图是由一组矢线连 接的有限个结点组成的有向图。每个结点代表一个状态，带有字符的有向边表示转换函数， 表示起始状态接收一个字符转换后继状态。有限自动机还可以用“转换矩阵法”表示。表的 行表示状态，列表示输入字符，表元素表示相应状态行对应输入字符列下的新状态。即n 行m 列为占0 ，聊) 的值。自动机的状态转换图表示法表现清晰，易于理解。转换矩阵表示法适于 计算机实现。 2 2 1 1 一个自动机的示例 示例1 ：有自动机m 定义如下：m = “o ，1 ，2 ，3 ) ， a ，b ，8 ， o ， 3 ) 其中转换函数定义为：6 ( o ，a ) = l ；8 ( o ，6 ) - - 2 ；6 ( 1 b ) = 2 ；6 ( 2 ，a ) = 1 ；6 ( 2 ，b ) = 3 ；6 ( 3 ，a ) i _ 3 8 ( 3 ，b ) - 3 ；则m 的转换图表示如下：( 起始状态用红色表示，结束状态为蓝色表示) 1 7 东北大学硕士学位论文第二章编译原理基础知识 图26 自动机的状态转换圈 f i g2 6t h es t a t et r a n s i t i o n c h a r to f f i n i t ea u t o m a t o n 状态转换表表示如下 表21 状态转换表 t a b l e2lt h et r a n s i t i o nt a b l eo f f i n i t ea u t o m a t o ns t a t e 字符 糍恭 ab 012 1 3 2 21 3 333 2 2 1 2 表示自动机的类的定义 系统设置一个c f i n i t e a u f o 类，来存放自动机的五元组并实现与自动机有关的操作。 c f i n i t e a u t o 类的具体定义如下： c l a s sc f i n i t e a u t o p u b l i c ： v o i ds e t f a ( c f a a e c e p t p a r a d l g + p m y f a d l g ) ；用对话框的值初始化f a a l p h a a n d c o n t e n tma l p h a c o n t e n t f a m a x n u m ；n 接收字母表中各元素 i n tm 接收字母表元素的个数_ n a i p h a n u m ； s t a t e p o i n t mf a s t a t e f a m a x n u m ；接收自动机状态点的名字及是否是起始点 i n tmn s t a t e n u m ； n 状态集台元素的个数 n 自动机映射矩阵，行为状态元素，列为字母表元素，项为状态元素。 表示行状态接收列元素后，转为项元素。 t c h a rme f a s q u a r e f a m a x n u m f a m a x n u m f a m a x n u m ； 存放n f a 向d f a 转换后新生成的状态集合 c s t r i n g a r r a ys t e m p s t r i n g a r r a y ； 东北大学硕士学位论文 第二章编译原理基础知识 存放n f a 向d f a 转换后的矩阵，元素为串类型 c s t m a ga s t r i n g o r d e r r 心d a x n u m f a m a x y u m ； ，最小化d f a 时用，待处理的状态集合( 串) ，如果要分开，就在标志位上记做l s 缸n g w i i l l m a f ka s t a t o s e t f o r t r e a t e f a m a x n u m ； 2 2 2 自动机的匝形娃i 莨 2 2 2 1 自动机图形化表示的有关函数设计 自动机的图形化表示即是由给定的自动机五元组数学模型，输出它的状态转换图。 c f i n i t e a u t o 类的成员函数d r a w f a o 负责画出自己。函数原型为： d r a w ! a ( c d c * p d c i n t n w i d t h , i n t n n e i g h t ) ；n 传递设备描述表的指针，用于绘图 该函数首先利用传入的设备描述表指针，获取当前字体的长宽信息，并依据字体的信息 在相关位置输出状态名称( 起始状态用红色表示，结束状态为蓝色表示，其它状态为黑色) 。 之后，依据状态名称的位置，设置外接矩形并画圆。 c r e e tr e e t l ( ( 1 0 0 + i + 5 * n c h a r h e i g h t ) ，( i 埘e i 业以- 2 + n c h a r h e i g h t ) ， ( 2 5 + n c h a r h e i g h t + 1 0 0 4 i ) ，( n h e i g h t 2 + 2 2 + n c h a r h e i g h t ) ) ； 捧蜒- e i 舻e ( m 1 ) ； 循环所有状态，查询是否有指向自身的弧，若有则利用c i r c l e w i t h a r r o w 函数负责画圆。 对于指向其它状态的弧，和用a r e w i t h a r r o w 函数画弧。 以上两个函数参数分别有：p v c 设备描述表指针，f e e t 状态的外接矩形c t e m p c h a r 接 收的字符n t o m p l a y e c 要画弧线的层数p o i n t lp o i n t 2 弧的起始点和目标点， n t e m p s e l f l , a y e r n t e m p g e p e a t 若是第一个接收的字符要显示带箭头的弧线，否则仅显示或符号“l ”和接收的 字母。 这里，弧线均为逆时针方向，依据起始点和终止点的位置判断弧线画在上半圆还是下半 圆。为了防止弧线互相交叉的过于严重，依据起始点接收字符的数量，设置层次数，分散弧 线。输出接收的字符时，判断了是上方弧线还是下方弧线，以保证字符写在弧线的外侧。 2 2 2 2 自动机图形化的功能实现 该功能通过主菜单“自动机示例“的“画自动机”实现。 首先弹出对话框接收自动机参数。要求状态名称、接收的字符均用“，”分隔。转换函数 的形式为；( 起始状态接收的字符) = 后继状态；这里特别要求用字符“n ”表示e ( 空) 。但 除了带e ( 空) 边的n f a 向d f a 转换中，n 的特殊含义起作用外，其它部分均不特别考虑n 的特殊含义， 示例2 ： 自动机的状态集合为： 0 ，1 ； 起始状态集合为： o ； 终止状态集合为： 1 ) 。 1 9 东北大学硕士学位论文第二章编译原理基础知识 字母表为： o ，1 ， 转换函数为： 6 ( 0 ，0 ) = 0 ； 6 ( 0 ，1 户1 ； 6 ( 1 ，o ) = 1 ； 6 ( 1 ，1 户o ： 示例自动机的图形化表示如图 图27自动机的图形化表示 f i g2 7 t h eg r a p h i ce x p r e s s i o no f f a 2 。2 3 非确定自动机的确定化 非确定自动机的确定化就是将其转化为d f a 。 2 2 3 1 非确定自动机确定化的基本原理回 n f a 与d f a 均是有限自动机，它们的区别在于：n f a 可有多个初始状态，d f a 只有唯一 的初始状态；n f a 状态的转换函数不单值，它接收一个字符可有多个后继状态，d f a 状态接 收一个字符后只有唯一的后继状态；n f a 可能有e ( 空) 转换存在。显然在非确定的有限自 动机中，由于某些状态的转移需要从多个可能的后继状态中进行选择，故一个n f a 对符号串 的识别就必然是一个试探的过程。这种不确定性给识别过程带来的回溯反复，无疑会影响到 f a 的工作效率。我们可以证明，对应一个n f am ，“。定存在一个d f am ，使得非确定机 东北大学硕士学位论史第二章编译原理基础知识 m 所确定的语言等价于确定机m 确定的语言；即：l ( m ) 乩( m ) 川。同榉，我们也可 以证明，i 蚓蕊麓嬲凝濑辫镶舞臻鼹魍裹暾礴黎纛貉蹶黼翳蘸满霸漂势寝潦蒋疆匿i 鹫擀具有 ( 卒) 动作的n f a m 也一定存在一个n f am ，使l ( m ) _ l ( m ) 。 2 2 3 2 不带( 空) 边的n f a 向d f a 转化的算法 ( 1 ) 构造d f a 变换矩阵框架表。 屎n p a 删獬人予付莱二 状态行状态行的第一行为n f a 的起始状态 该集合作为转换后d f a 的起始状态 集合 ( 2 ) 填写表项。根据n f a 的转换函数填写表项，表项往往是个状态集合。 ( 3 ) 扩充d f a 变换矩阵表状态行的内容。把表项中所有还未做为状态行的状态集合做为 新的状态行。 ( 4 ) ：重复( 2 ) 、( 3 ) 直至没有新的状态集合出现。 摄后得到一个等价的d f a 状态转换表。这个等价的d f a 开始状态为变换矩阵框架表的第 一行。结束状态可能不唯一，所有包含原n f a 结束状态的行均为等价d f a 的结束状态。 2 233 不带e ( 空) 边的n f a 向d f a 转化的功能实现 该功能通过主菜单“自动机示例”的“n f a - ) d f a ”实现。 首先弹出对话框接收n f a 参数。 本程序通过主菜单“查看”的“s p l i t ”菜单项实现分割窗口的功能，这样就可以拆分窗 口，以便于e 下方的图形对映显示，方便教学。 在屏幕上方显示的是原n f a 的状态转换图，接着显示的是转换后的d f a 的状态转换图， 出于教学目的，在屏幕的下方要显示由n f a 构造的d f a 变换矩阵袁。 d f a 的变换矩阵表的“中间串”由原n f a 的状态组成。“新状态”是对这些状态集合的 换名。左边字母表下为状态集合接收某个字母后转换后的状态集台。右方的字母表下为换名 后的变换矩阼表。 示例3 自动机的状态集合为： 1 , 2 ，3 ；起始状态集合为： 1 ，3 ；终止状态集台为： 2 。 字母表为： 曲) 转换函数为： 6 ( 1 ，a ) = l ；6 ( 1 ，a ) = 2 ；6 ( 1 , b ) = 3 ；6 ( 2 b ) = 2 ；6 ( 3