（控制理论与控制工程专业论文）运动控制器指令编译系统的研究与实现.pdfVIP

ad i s s e r t a t i o ns u b m i t t e t h ed e g r e e r e s e a r c ha n d c o m p i l i n g m 。e c a n d i d a t e ：g u a nw e n x i a n g s u p e r v i s o r ：p r o f c h e nw e i j u n e2 0 1 0 f a c ul t yo fa u t o m a t i o n g u a n g d o n gu n i v e r s i t yo ft e c h n o l o g y g u a n g z h o u ，g u a n g d o n g ，p r c h i n a ，5 10 0 0 6 摘要 皇曼置置鼍鲁皇詈鼍皇冒i i | 1 l 曼i 暑量! ! 曼! 皇曼曼! 鼍曼詈寡鼍鲁皇皇毫曼皇皇量暑皇曼量曼鼍曼皇璺鼍暑鲁暑鼍! 曼量毫曼皇曼詈曼曼曼鼍暑曼曼詈量曼曼罡暑詈量暑曼曼鼍皇 摘要 数控技术的发展趋势就是采用运动控制器的丌放式的数控系统。主要数控技术的 发展趋势就是采用“p c + 运动控制器”的开放式数控系统。美国将其称为新一代的工 业控制器，同本称其将带来第三次工业革命，并预测其应用将和现在的p l c 一样普遍。 因此，运动控制器技术是生产数控系统的核心技术。 在运动控制器的硬件系统确定之后，运动控制器的性能在很大程度上决定于其指 令系统的特性。运动控制器指令编译系统是客户端指令系统的核心。运动控制语。i j 。编 写的程序，必须通过编译或解释来使运动控制器执行。所以运动控制语言及其编译器 或解释器直接影响到运动控制器使用的难易，运动控制器功能的强弱，以及运动拧制 器响应的速度。 数控( 简称n c ) 代码编译器的研究分为两个方面：一是用于仿真；二是用于控制。 前者的研究国内已达到很高的水平，而后者的研究多数只是在相关性文章中提到，其 专门的技术报告更是少见，似乎此方面的研究没有引起特别的关注。但在现实中，随 着丌放式数控系统硬件的同益成熟，对数控系统软件架构和数控软件部件的研究也越 来越显得重要，这是因为软件架构的合理性和可重用软件部件的性能直接影响数控系 统的功能和精度。在数控系统软件中，n c 代码的编译或解释是不可缺少的环节，相关 的软件部件的合理性和性能的优劣直接影响系统软件的性能。因此，n c 代码编译器作 为一个数控软件部件，其研究意义十分重大。 本文以g a l i l 指令系统为研究对象，在简要分析g a l i l 运动控制指令语法规则的嬉 础上，介绍了自主研发的客户端运动控制指令编译系统的基本思想和设计流程。从词 法分析、语法分析、整合处理、语义分析和后期处理诸方面详述了编译系统的实现原 理和方法，重点解决了目标文件的编码和解码问题。此指令编译系统及相关的算法均 在国产m c t 8 0 0 0 系列运动控制器上进行了验证，结果是有效和诈确的。 本课题研究方法简述如下： 一、本文研究的是如何实现四轴独立运动控制器的软件设计，由上位机编译器对 源程序进行词法、语法、语义进行分析，最终生成目标文件，然后下载到嵌入式运动 广东工业大学硕士学位论文 器( 下位机) 中由解释器解释，下位机解释器使用一个循环结构读取并解释下载到运 制器用户程序区的运动控制程序，进而实现运动控制。主要是对运动控制程序进 译( 编码) 和解释( 解码) 。 二二、本课题基于摩信科技公司的机床系统和雷泰控制自主研发的运动控制器硬件 验平台，通过搭建人机界面和本设计的软件，实现数控加工中所涉及的点对点运 插补运动等。 三、将设计好的客户端加工程序在本设计的编译器下编译，将生成的目标文件数 过m a t l a b 仿真，结果正确后再将目标文件传送到下位机解析执行，确保提取的 的正确性。 四、分析与研究仿真结果和加工执行效果，并给出结论。 奉论文内容的安排如下： 第一章讲述了运动控制器的研究状况，问题的提出以及国内外的发展，并介绍课 题研究方法以及论文的大致情况。 第+ ：节简要介绍了编译器的工作原理及各部分工作的相关知识。 第三章介绍了上下位机的功能实现，包括编译器语法检查、编码的实现( 即目标 文件乍成) 和解码的实现( 即下位机解析器的工作流程) 等。 第四章针对本设计要求设计的上位机编译器和下位机解释器，通过搭建硬件平台 和人机界面，对用户编写的客户端加工程序进行加工，结果令人满意。 关键词：指令编译系统；n c 代码编译器；运动控制器；g a l i l 指令系统 a b s t r a c t a bs t r a c t c n ct e c h n o l o g yt r e n d si st ou s em o t i o nc o n t r o l l e ro p e nc n cs y s t e m t h em a i nt r e n d o fc n ct e c h n o l o g yi st h eu s eo f ”p c + m o t i o nc o n t r o l l e r ”o p e na r c h i t e c t u r ec n cs y s t e m t h eu n i t e ds t a t e ss a i di tw a st h en e wg e n e r a t i o no fi n d u s t r i a lc o n t r o l l e r s ，a n dj a p a ns a i di t w i l lb r i n gt h et h i r di n d u s t r i a lr e v o l u t i o na n df o r e c a s tt h a ti t sa p p l i c a t i o nw i l lb ea sc o m m o n a sp l c t h e r e f o r e ，t h em o t i o nc o n t r o l l e rt e c h n o l o g yi st h ec o r et e c h n o l o g yo fp r o d u c t i o no f n cs y s t e m w h e nt h eh a r d w a r es y s t e mo ft h em o t i o nc o n t r o l l e ri sd e t e r m i n e d ，t h ep e r f o r m a n c eo f m o t i o nc o n t r o l l e ri n s t r u c t i o ni sd e t e r m i n e db yt h e i rc h a r a c t e r i s t i c s i n l a r g ep a r t t h e i n s t r u c t i o nc o m p i l es y s t e mo fm o t i o nc o n t r o l l e ri st h ec o r eo ft h ec l i e n ti n s t r u c t i o ns y s t e m p r o g r a m sw r i t t e nb ym o t i o nc o n t r o ll a n g u a g e w i l lb ec o m p i l e do ri n t e r p r e t e db yt h e c o n t r o l l e rt om a k et h em o t i o ne x e c u t i o n t h e r e f o r e ，m o t i o nc o n t r o ll a n g u a g ea n di t s c o m p i l e ro ri n t e r p r e t e rd i r e c t l ya f f e c tt h ee a s eo fu s eo fm o t i o nc o n t r o l l e r , f u n c t i o no f t h e s t r e n g t ha n ds p e e do fr e s p o n s eo ft h em o t i o nc o n t r o l l e r n cc o d eo ft h ec o m p i l e ri sd i v i d e di n t ot w oa s p e c t s ：f i r s t ，i sf o rt h es i m u l a t i o n ；s e c o n d i su s e dt oc o n t r 0 1 t h es t u d yo ff o r m e ri no u rc o u n t r yh a sr e a c h e dah i g hl e v e l ，b u tt h el a t t e r i so n l ym e n t i o n e di nt h er e l a t e da r t i c l e ，a n dt h et e c h n i c a lr e p o r to fi t ss p e c i a li sr a r e i ts e e m s t h a tr e s e a r c hi n t h i sa r e ai sn o to fp a r t i c u l a rc o n c e r n b u ti nr e a l i t y , w i t ht h eg r o w i n g m a t u r i t yo fo p e n c n cs y s t e mh a r d w a r e ，t h es e a r c ho f t h es o f t w a r ea r c h i t e c t u r ec n cs y s t e m a n dc n cs o f t w a r ew i l lb em o r ea n dm o r ei m p o r t a n t ，b e c a u s et h er e a s o n a b l e n e s so ft h e s o f t w a r ea r c h i t e c t u r ea n dt h ep e r f o r m a n c eo fr e u s a b l es o f t w a r ec o m p o n e n t sd i r e c t l ya f f e c t t h ef u n c t i o n sa n dp r e c i s i o no ft h ec n cs y s t e m i nt h en u m e r i c a lc o n t r o ls y s t e ms o f t w a r e ， c o m p i l i n g o ri n t e r p r e t i n gi st h ee s s e n t i a ll i n ko fn cc o d e ，a n dp e r f o r m a n c ea n dt h e r a t i o n a l i t yo ft h er e l a t e ds o f t w a r ec o m p o n e n t sd i r e c t l yi m p a c tt h ep e r f o r m a n c eo fs y s t e m s o f t w a r e t h e r e f o r e ，n cc o d ec o m p i l e r , a sa s o f t w a r ec o m p o n e n t ，w h o s er e s e a r c hi so fg r e a t s i g n i f i c a n c e t h r o u g ht h ed e s i g no fm a n - m a c h i n ei n t e r f a c es o f t w a r e t h i r d l y , c o m p i l i n gt h ec l i e n tp r o c e s s i n gp r o g r a mb yt h ec o m p i l e r , a n ds i m u l a t i n gw i t h t h eg e n e r a t e dt a r g e tf il ed a t at h r o u g ht h em a t l a bs i m u l a t i o n w h e nt h er e s u l t si sr i g h t a f t e rc h e c k i n g ，t r a n s f e r st h et a r g e tf i l et ol o w e rm a c h i n e ，w h i c he n s u r e st h ec o r r e c t n e s so f t h ee x t r a c t e dd a t a f o u r t h ，a n a l y s i s i n ga n dp r o c e s s i n go fs i m u l a t i o nr e s u l t sa n dt h ep e r f o r m a n c e ，a n dt h e n m a k e sc o n c l u s i o n s t h ea r r a n g e m e n to ft h et h e s i si sa sf o l l o w s c h a p t e r 1d e s c r i b e st h es i t u a t i o no ft h em o t i o nc o n t r o l l e r , r a i s e st h ed e v e l o p m e n t q u e s t i o na th o m ea n da b r o a d ，a n dd e s c r i b e st h er e s e a r c hm e t h o d sa n ds t r u c t u r eo f t h ep a p e r c h a p t e r2b r i e f l yd e s c r i b e st h ew o r k i n gp r i n c i p l eo ft h ec o m p i l e ra n dt h e r e l e v a n t i v c h a p t e r4d e s i g n sr e q u i r e m e n t so ft h i sc h a p t e rd e s i g n e d f o rp cc o m p i l e ra n ds l a v e i n t e r p r e t e r , u s e r - w r i t t e np r o c e d u r e sf o rp r o c e s s i n gc l i e n t s i d ep r o c e s s i n g k e y w o r d s ：i n s t r u c t i o nc o m p i l i n gs y s t e m ；n cc o d ec o m p i l e r ；m o t i o nc o n t r o l l e r ；g a l i l i n s t r u c t i o ns y s t e m v 嚣“ 目录v i c o n t e n t s v i i i 第一章绪论l 1 1 研究背景1 1 2 国内外研究状况2 1 3 本文研究内容4 第二章编译器简介5 2 1 编泽器历史5 2 2 编译器工作原理6 2 3 编译器的相关知识7 2 3 1 词法分析( 扫描程序) 8 2 3 2 语法分析8 2 3 3 语义分析8 2 3 4 代码生成8 2 4 编译器相关术语9 2 4 1 记号9 2 4 2 语法树9 2 4 3 符号表9 2 4 4 常数表9 2 4 5 中i 日j 代码1 0 2 4 6 临时文件1 0 2 5 小结10 第三章编译器的算法与实现l l 3 1 编码算法与实现l l v i 目录 3 1 1g a l i l 语法规则1 1 3 1 2 编译器语法检查1 2 3 1 2 1 词法分析15 3 1 2 2 语法分析2 l 3 1 2 3 整合处理3 0 3 1 2 4 语义分析3 3 3 1 2 5 后期处理3 7 3 1 2 6 生成中间文件3 9 3 1 3 编码算法：目标文件生成4 0 3 1 3 1 整型数据包i d p 的格式定义4 0 3 1 3 2g a l i l 各语句编码格式4 1 3 1 4 实例4 6 3 2 解码算法与实现4 8 3 2 1 下位机的工作原理4 8 3 2 2 解析器的工作流程4 9 第四章实验结果与分析5 6 4 1 实验系统简介5 6 4 1 1 应用方案5 6 4 1 2 硬件平台搭建5 6 4 1 3 人机界面5 9 4 2 实验过程、结果与分析6 0 4 3 小结6 8 结论与展望6 9 参考文献7 l 攻读学位期间发表的论文7 4 独创性声明7 5 致谢7 6 附录7 7 附录l 链表及树实现代码7 7 v i l 2 3 3s e m a n t i ca n a l y s i s 8 2 3 4c o d eg e n e r a t i n g 8 2 4r e l a t e dt e r mo fc o m p i l e r 9 2 4 1t o k e n ( t o k e n ) 9 2 4 2s y n t a xt r e e 9 2 4 3s y m b o lt a b l e 9 2 4 4l i t e r a lt a b l e 9 2 4 5i n t e r m e d i a t ec o d e ) 10 2 4 6t e m p o r a r yf i l e l0 2 5s u m m a r y 1 0 c h a p t e r 3a l g o r i t h ma n di m p l e m e n t a t i o no fc o m p i l e r i i 3 1c o d i n ga l g o r i t h ma n di m p l e m e n t a t i o n 11 v i i i c o n i b n i s 3 1 1g r a m m a rr u l e so f g a l i l 11 3 1 2s y n t a xc h e c k i n go fc o m p i l e r 1 2 3 1 2 1l e x i c a l a n a l y s i s 1 5 3 1 2 2g r a m m a ra n a l y s i s 2 1 3 1 2 3i n t e g r a t i o np r o c e s s i n g 3 0 3 1 2 4s e m a n t i ca n a l y s i s 3 3 3 1 2 5p o s t p r o c e s s i n g 3 7 3 1 2 6i n t e r f i l eg e n e r a t i n g 3 9 3 1 3c o d i n ga l g o r i t h m ：t a r g e t f i l eg e n e r a t i n g 4 0 3 1 3 1f o r m a td e f i n i t i o no f i n t e g e rd a t ap a c k e t 4 0 3 1 3 2c o d i n gf o r m a to fg a l i l ss t a t e m e n t s 4 1 3 1 4e x a m p l e 4 6 3 2d e c o d i n ga l g o r i t h ma n di m p l e m e n t a t i o n 4 8 3 2 1w o r k i n gp r i n c i p l eo fh y p o g y n o u sm a c h i n e 4 8 3 2 2w o r k i n gf l o wo fi n t e r p r e t e r 4 9 c h a p t e r 4e x p e r i m e n t a lr e s u l t sa n da n a l y s i s 5 6 4 1i n t r o d u c t i o no fe x p e r i m e n t a ls y s t e m 5 6 4 1 1a p p l i c a t i o ns c h e m e 5 6 4 1 2h a r d w a r ep l a t f o r mb u i l d i n g 5 6 4 1 3m a n m a c h i n ei n t e r f a c e 5 9 4 2e x p e r i m e n t a lp r e c e s s ，r e s u l ta n da n a l y s i s 6 0 4 3s u m m a r y 6 8 c o n c l u s i o na n dp r o s p e c t 6 9 r e f e r e n c e s 7 1 p a p e r sp u b l i s h e dd u r i n gs t u d yp e r i o d 7 4 s t a t e m e n t 7 5 a c k n o w l e d g e m e n t s 7 6 a p p e n d i x 7 7 a p p e n d i x1c o d e so fl i n k e d l i s ta n dt r e e 7 7 l 第一章绪论 1 1 研究背景 第一章绪论 随着自动化技术的进一步发展，运动控制器( 步进、交流、直流) 的应j j 已走出 机械加工行业，越来越多地应用于其它工业自动化设备控制，如电子机械、木工机械、 纺织机械、印刷机械等诸多行业。主要数控技术的发展趋势就是采用“p c + 运动控制 器”的开放式数控系统。美国将其称为新一代的工业控制器，同本称其将带来第三次 工业革命，并预测其应用将和现在的p l c 一样普遍。 一个典型的运动控制系统主要由运动部件、传动机构、执行机构驱动器和运动挖 制器构成，整个系统的运动指令由运动控制器给出，因此运动控制器是整个运动控制 系统的灵魂 4 - 5 1 。采用运动控制器的数控系统将成为新一代数控技术发腱潮流，运动控 制器将成为未来数控系统的核，l = , 1 6 1 。 运动控制语言是人的控制意图和控制器交流的主要方式i ，l 。在运动控制器的硬件系 统确定之后，运动控制器的性能在很大程度上决定于其指令系统的特性 s i 。从数控系统 结构分析，工业控制计算机i p c 内部嵌入通用运动控制器( 卡) m c 是一种嵌入式上下位 机结构的丌放式数控系统，上位机用于加工任务的调度管理，下位机运行控制程序， 下位机如何根据n c 代码的意义进行控制? 这就需要一个解决方案，其中的藿要环节 就是n c 代码的编译或解释1 9 i 。 运动控制器指令编译系统是客户端指令系统的核心。运动控制语毒。编写的程序， 必须通过编译或解释来使运动控制器执行 z o l 。所以运动控制语言及其编译器或解释器 直接影响到运动控制器使用的难易，运动控制器功能的强弱，以及运动控制器响应的 速度i nn l 。运动控制器指令编译系统( 以下简称n c 编译器) 的主要功能是将用文本格 式( 通常是a s c i i 码) 表示的零件加工程序，以程序段为单位转换为后续程序所需要 的数据结构或格式( 如刀补处理程序等) 。n c 编译器是数控系统软件的核心部分，它 的功能强弱直接影响数控系统的性能 6 , t 2 - t ，i 。 n c 代码解释器可嵌入或不嵌入控制程序中，嵌入方式占用了较多的卜位机的内存 和资源，不利于多轴实时控制和采用高级算法进行高精度控制。同时使下位机软件的 广东工业大学硕士学位论文 构变得复杂 1 4 l 。此外，对于大型n c 程序，需要分批下传给下位机。且n c 程 程序，解释模式在处理子程序调用跳转和返回方面、在如何保证控制实时性 了非常大的困难：不嵌入方式是上位机解释一个n c 命令，就要下发一次解 增加了上下位机通信控制的频度，占用了一部分下位机的c p u 资源。也没有 予程序的调用与返回的难题j 。为了克服上述的缺陷十分需要在软件上探索 路和方法，研究、设计和丌发n c 代码编译器是达到实现控制目的和解决问 途径。 ( 简称n c ) 代码编译器的研究分为两个方面：一是用于仿真：二是用于控制陋7 l 。 究国内已达到很高的水平，如哈工大、上海交大、华中理工等相继实现了具 有高水平的仿真型n c 代码编译器，而后者的研究多数只是在相关性文章中提到，其 专门的技术报告更是少见，似乎此方面的研究没有引起特别的关注。但在现实中，随 着开放式数控系统硬件的同益成熟，对数控系统软件架构和数控软件部件的研究也越 来越显得重要，这是因为软件架构的合理性和可重用软件部件的性能直接影响数控系 统的功能和精度。在数控系统软件中，n c 代码的编译或解释是不可缺少的环节，相关 的软件部件的合理性和性能的优劣直接影响系统软件的性能引。因此，n c 代码编译 器作为一个数控软件部件，其研究意义十分重大。 1 2 国内外研究状况 最早采用的n c 代码错误检查方法为人工检查法，即通过检查者阅读加工程序、 或借助坐标纸及其它一些绘图工具来检查加工时的刀具轨迹，从而发现其中的错误， 其优点足比较方便、灵活，但不适用于大而复杂的程序，且易再次出现错误，目前已 经不适应现实需要。为提高n c 代码编译效率，采用高级语言式编译技术开发n c 编泽 系统是未来n c 系统编译技术发展方向1 1 9 l 。国内外对此都作了许多研究工作。 同本a i k o k ua l p h a 公司的s u p e rv e r i f y 是个很好的n c 代码编译和检验( 仿真) 软 件，它不仅能验证n c 程序的正确性，并可进行代码优化，缩短加工时间。其适用范 围广，包括车削、铣削、车铣等从两轴到i 轴连动的多种加工方式，集成了大多数知 名的n c 控制系统，并支持多种包含宏子程序等功能在内的n c 代码格式1 2 0 l 。 美闲s i n u ss y s t e m sc o r p 在c n c 仿真校验技术上成果卓著，它开发的v i r t u a l c o n t r o i l e r 是一个功能强大的通用后处理器，可模拟c n c 加工周期。将特定n c 机床的 2 第一章绪论 g 代码、m 代码等指令翻译成通用的a p t 。c l 文件或其它用户需要的数据格式，进行 n c 代码检验以及优化，并可进行3 5 轴铣削、2 4 轴车削、车铣和线切割加t 仿真。 在仿真过程中，可精确解释和描述n c 代码的每个命令及功能，准确再现加工过程。 v i r t u a lc o n t r o l l e r 内置有1 0 0 多个c n c 控制系统，用户可根据预先配置的n c 控制系统 来进行n c 代码检验、仿真或转化，还可根据自身需要对其进行定制。1 9 7 4 年成立的 美国n c c s ( n u m e r i c a lc o n t r o lc o m p u t e rs e i e n e e s ) 公司最初只是一个n c 服务机构，现 已发展成为美国西海岸最大的n c 服务中心，其服务范围也扩展到多轴n c 加工、几何 建模、后处理、n c 代码检验和机床仿真等诸多方面。其丌发的多轴加工软件p o s t w o r k s 是一个通用后处理软件，其范围可覆盖从二轴到十轴的车、铣、车铣、线切害0 、激光 等加工，它可对n c 代码进行词法、语法检查，进行加工过程全景仿真，并支持不同 格式n c 代码之间的转换1 2 1 | 。 国内在此研究领域也作了很多尝试，我国己有几家高等院校实现了针对单一n c 系统的代码编译器，目前应用情况良好1 2 2 1 。清华大学国家c i m s 工程中心丌发了n c 代黟 码翻译器，该翻译器的主要工作概括起来有两个：检错和翻译。检错，即按照该数控 系统的编程规定和有关数控力n - v _ 的常识，对n c 代码进行词法分析、语法分析、语义辔 分析，从而检查出该n c 代码的词法错误、语法错误、逻辑错误( 其t l 包括数捌1 i 合理， 加工状态不合理等) 。经过检错阶段，若n c 代码未被查出错误，则进入翻译阶段，即 从n c 代码中提取控制机床部件运动的有关命令动作和状态信息，将运动的数据按照 ” 位移和速度的变化划分成一系列时间片段，计算出各时间片段机床各搬标的位移1 2 2 1 。 华中理工大学数控技术研究所提出了n c 程序的“资源重叠流水处理”解释方法， 该方法具有节约系统资源，便于并行处理的特点，并能充分利用和发挥w i n d o w s 平台 “弱实时性和多任务”的优势。另外华中理工大学丌发的n c 程序检验仿真系统 n c c p v s s ，能实现对n c 程序编制过程中出现的错误进行离线检验，可提高n c 设备 的调试手段和效率1 2 3 1 。 2 0 0 2 年，大连铁道学院的张生芳等人应用正规文法和l a i 。r ( 1 ) 方法对n c 程序进 行词法、语法分析，开发出了一个具有通用意义的n c 代码编译系统。这种编译器基 于j b 3 2 0 8 8 3 和j b 3 8 3 2 8 5 ，建立了不同n c 系统相同功能指令i u j 的相互关联，实现了 n c 系统间的代码相互转换，利用专用编译工具l e x & y a c c 开发出n c 代码编译模块， 保证了词法、语法分析的全面性和准确性，具有较高的可靠性及实用性1 2 4 1 。 仪器的虚拟制造系统 件的编码和解码设计 由上位机编译器对源 间代码，然后下载到 嵌入式运动控制器( f 位机) 中出解释器解释，下位机解释器使用一个循环结构读取并解 释下载到运动控制器用户程序区的运动控制程序，进而实现运动控制。主要是对运动 控制科序进 f 编泽( 编码) 和解释( 解码) 。 2 、本课题基于摩信科技公司的机床系统和雷泰控制自主研发的运动控制器硬件为 实验平台，通过搭建人机界面和本设计的软件，实现数控) j u t _ 中所涉及的点对点运动 和插补运动等。 3 、将设计好的客户端i j n t 程序在本设计的编译器下编译，将生成的目标文件数据 通过m a t l a b 仿真，结果f 确后再将目标文件传送到下位机解析执行，确保提取的数 据的i r 确性。 4 、分析与研究仿真结果和；o n t _ 执行效果，并给出结论。 4 第二章编译器简介 2 1 编译器历史 第二章编译器简介 上世纪5 0 年代，i b m 的j o h nb a c k u s 带领个研究小组对f o r t r a n 语言及其编 译器进行开发。但由于当时人们对编译理论了解不多，丌发工作变得既复杂又艰j 苦。 与此同时，n o a mc h o m s k y 开始了他对自然语言结构的研究。他的发现最终使得编译器 的结构异常简单，甚至还带有一些自动化。c h o m s k y 的研究导致了撤掘语啬文法的难 易程度以及识别它们所需要的算法来对语言分类。正如现在所称的c h o m s k y 架构 ( c h o m s k yh i e r a r c h y ) ，它包括了文法的四个层次：o 型文法、1 型文法、2 型文法和3 型文法，且每一个都是其前者的特殊情况。2 型文法( 或上下文无关文法) 被证明足程 序设计语言中最有用的，而且今天它已代表着程序设计语言结构的标准方式。分析问 题( p a r s i n gp r o b l e m ，用于上下文无关文法识别的有效算法) 的研究是在6 0 年代和7 0 年代，它相当完善的解决了这个问题。现在它已是编译原理中的个标准部分m i 。 有限状态自动机( f i n i t ea u t o m a t o n ) 和正则表达式( r e g u l a re x p r e s s i o n ) 同上下 文无关文法紧密相关，它们与c h o m s k y 的3 型文法相对应。对它们的研究与c h o m s k y 的研究几乎同时开始，并且引出了表示程序设计语言的单词的符号方式l - s 1 。 人们接着又深化了生成有效目标代码的方法，这就是最初的编译器，它们被。直 使用至今。人们通常将其称为优化技术( o p t i m i z a t i o nt e c h n i q u e ) ，但【大】其从未真诉地 得到过被优化了的目标代码而仅仅改进了它的有效性，因此实际上应称作代码改进技 术( c o d ei m p r o v e m e n tt e c h n i q u e ) i z 6 1 。 当分析问题变得好懂起来时，人们就在丌发程序上花费了很人的功火来研究这一 部分的编译器自动构造。这些程序最初被称为编译器的编译器( c o m p i l e r c o m p i l e r ) ， 但更确切地应称为分析程序生成器( p a r s e rg e n e r a t o r ) ，这是因为它们仅仅能够自动处 理编译的部分。这些程序中最著名的是y a c c ( y e t a n o t h e rc o m p i l e r c o m p i l e r ) ，它是 由s t e v ej o h n s o n 在1 9 7 5 年为u n i x 系统编写的。类似的，有限状态自动机的研究也发 展了一种称为扫描程序生成器( s c a n n e rg e n e r a t o r ) 的工具，l e x ( 与y a c c 同时，由 m i k el e s k 为u n i x 系统丌发) 是这其中的佼佼者1 2 7 1 。 广东工业大学硕士学位论文 在7 0 年代后期和8 0 年代早期，大量的项目都贯注于编译器其它部分的生成自动 这其中就包括了代码生成。这些尝试并未取得多少成功，这大概是因为操作太复 人们又对其不甚了解1 2 s 。 编译器设计最近的发展包括：首先，编译器包括了更加复杂算法的应用程序它用 断或简化程序中的信息；这又与更为复杂的程序设计语言的发展结合在一起。其 型的有用于函数语言编译的h i n d l e y m i l n e r 类型检查的统一算法。其次，编译器已 越成为基于窗口的交互开发环境( i n t e r a c t i v ed e v e l o p m e n te n v i r o n m e n t ，i d e ) 的 分，它包括了编辑器、连接程序、调试程序以及项目管理程序。这样的i d e 标准 有多少，但是对标准的窗口环境进行开发已成为方向。另一方面，尽管近年来在 原理领域进行了大量的研究，但是基本的编译器设计原理在近2 0 年中都没有多大 的改变，它现在j 下迅速地成为计算机科学课程中的中心环节【2 9 1 。 在九十年代，作为g n u 项目或其它丌放源代码项目的一部分，许多免费编译器和 编译器丌发工具被丌发出来。这些工具可用来编译所有的计算机程序语言。它们中的 一些项目被认为是高质量的，而且对现代编译理论感性趣的人可以很容易的得到它们 的免费源代码。大约在1 9 9 9 年，s g i 公布了他们的一个工业化的并行化优化编译器 p r 0 6 4 的源代码，后被全世界多个编译器研究小组用来做研究平台，并命名为o p e n 6 4 。 o p e n 6 4 的设计结构好，分析优化全面，是编译器高级研究的理想平台。编译器是一种 特殊的程序，它可以把以特定编程语言写成的程序变为机器可以运行的机器码。我们 把一个程序写好，这时我们利用的环境是文本编辑器。这时我程序把程序称为源程序。 在