（机械制造及其自动化专业论文）基于dl模型的nc铣削加工仿真系统的研究.pdf

， c 一 j 。! h y ： 。jq 辱 m a j o r ：m e c h a n i c a lm a n u f a c t u r ea n da u t o m a t i o n c a n d i d a t e ：腑ic h e n s u p e r v i s o r ：a s s o c i a t ep r o f c h u a n m i nz h u m a r c h ，2 0 0 7 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：1 障伸 叫年) 月矽e t 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 年 月日年月日 签名：潍伟 炒7 年多月矽e l 摘要 摘要 本文从计算机图形显示原理出发，设计并完成了用以检查n c 代码准确性的 仿真加工系统，该系统动态地仿真铣削加工过程，可以代替传统的试切手段， 其主要内容包括： 1 n c 代码解释。在解释器的语法分析程序制作上采用了y a c c 工具，本 系统的n c 代码解释器编辑、调试n c 代码，并将代码信息转换成仿真数据。 2 基于d e x e l 模型的仿真加工。本文采用最常用的边界表示法( 三角面表 示法) 对仿真对象刀具与毛坯进行几何描述；在几何描述基础上，生成仿真对 象的d e x e l 结构；基于著名的b r e s e n h a m 直线扫描算法将刀路轨迹离散成一系列 刀位点，在每个刀位点进行刀具与毛坯d e x e l 结构之间的布尔运算；利用r g b 颜色模型进行色调图显示，用于检验严重的加工程序错误。 3 实例验证。以相同n c 代码作为仿真加工实例，通过比较本系统与 s o l i d c a m 软件仿真模块的加工结果，有力地说明本仿真系统在加工效率，d e x e l 离散精度和仿真效果三者之间找到了最佳切入点。 关键词：d e x e l ，铣削加工，加工仿真，离散 ， _ a b s l a c t a b s t r a c t b a s e do nc o m p u t e rg r a p h i c sp r i n c i p l e ，t h i sd i s s e r t a t i o nc o m e u pw i t ha m a c h i n i n gs i m u l a t i o ns y s t e mt ov e r i f yn cc o d e t h es y s t e mc a l ld i s p l a yn cm i l l i n g i nr e a lt i m ea n ds oi tc a nt a k ep l a c eo ft r i a lc u t t h ed i s s e r t a t i o nm a i n l yi n c l u d e sa s f o l l o w ： 1 n cc o d ei n t e r p r e t a t i o n t h ew a yo fu s i n gy a c ct o o lt od e v e l o ps y n t a xp a r s e r o fi n t e r p r e t e rm a k e ss y s t e md e v e l o p m e n te a s i e r t h ei n t e r p r e t e ri sc a p a b l eo fe d i t ， d e b u g g i n ga n da l s oc o n v e r t i n gn c c o d ed a t ai n t os i m u l a t i o no n e s 2 d e x e lm o d e lb a s e dm a c h i n i n gs i m u l a t i o n f i r s t l y , g i v eg e o m e t r yd e s c r i p t i o n o ft o o la n dw o r k p i e c eb yt h em o s tc o m m o nb r e pm e t h o d - - m t r i g o n - s u r f a c e r e p r e s e n t a t i o n s e c o n d l y , c r e a t ed e x e ls t r u c t u r eo ft o o la n dw o r k p i e c eb a s e do nt h e i r g e o m e t r yd e s c r i p t i o n t h i r d l y , c o n v e r tc u tt r a c ki n t oi n d e p e n d e n tc u tl o c a t i o n s ( c l ) ，i n w h i c hb o o l e a nm i n u so p e r a t i o nc a r r i e so u tb e t w e e nd e x e ls t r u c t u r eo ft o o la n d w o r k p i e c e f i n a l l y , d i s p l a yt h es i m u l a t i n go b j e c t i o na n dm i l l i n gs u r f a c e su s i n gr g b c o l o rm o d e l 3 i n s t a n c e a f t e rac o m p a r i s o no fs i m u l t i o nr e s u l t sb e t w e e nc u r r e n ts y s t e ma n d s i m u l a t i o nm o d u l eo fs o l i d c a mt h r o u g hs a m ei n s t a n c e , i ti sc o n c l u d e dt h a t m a c h i n i n ge f f i c i e n c y , d i s p e r s i o nd i g r e ea n de f f e c tk e e pi nab e s tb a l a n c e k e yw o r d s ：d e x e l ，m i l l i n g ，m a c h i n i n gs i m u l a t i o n , d i s c r e t e i i 2 2 词法分析程序的手工编制7 2 2 1n c 程序简介7 2 2 2 词法分析的实现8 2 3 用y a c c 工具构造语法分析器1 0 2 3 1n c 代码的e b n f 表示1 0 2 3 2 语法分析程序的实现1 2 2 4 错误检查1 7 2 5 本章小结1 8 第3 章利用d e x e l 方法实现仿真加工2 0 3 1 概述2 0 3 1 1n c 铣削加工仿真存在的问题2 0 3 1 2 解决办法2 0 3 1 3 仿真加工图形生成的步骤2 1 3 2 仿真对象的实体造型及其坐标变换2 1 3 2 1 三维实体造型概述2 1 3 2 2 毛坯和刀具的实体造型2 3 3 2 3 坐标变换3 0 3 3 仿真对象的d e x e l 结构生成3 2 3 3 1d e p t h b u f f e r 算法3 2 i l l 4 1 1n c 代码解释模块4 8 4 1 2 参数准备模块4 9 4 1 3 仿真加工模块4 9 4 2 仿真加工实例5 1 4 2 1 直线加工法实例5 2 4 2 2 螺旋加工法实例5 3 4 2 3 从加工实例得到的结论5 5 4 3 本章小结5 5 第5 章结论与展望5 6 5 1 研究内容总结5 6 5 2 展望5 6 致谢5 8 参考文献5 9 个人简历在读期间发表的学术论文与研究成果6 1 i v 第1 章绪论 1 1c a d c 朋概述 第1 章绪论 计算机辅助设计与制造( c a d c a m ) 是近年来工程领域中发展最迅速最引 人注目的高技术之一。随着计算机软、硬件技术和其它科学技术的进步与发展， c a d c a m 技术日趋完善，今天的c a d c a m 已经广泛应用于数值计算、工程绘 图、工程信息管理、生产控制等设计生产的全过程中。c a d c a m 技术的发展 与应用水平已成为衡量一个国家科学技术现代化和工业现代化的重要标志之一， 在一定程度上能反映出一个国家的综合实力【l 们。 c a d 是“c o m p u t e ra i d e dd e s i g n ”的首写字母的缩写，其中文名为“计算机 辅助设计9 9 0 c a d 技术思想起源于2 0 世纪5 0 年代末，麻省理工学院的s m h e rl a n d 博士的研究工作。4 0 年来，c a d 技术已发展成为以“计算机技术”和“计算机图形 学”为技术基础，并融合各工程学科知识( 即各应用领域中的设计理论与方法) 的一种高新技术。总结c a d 技术的发展历史，各阶段的主要技术特点为： 2 0 世纪6 0 年代二维、三维线框造型； 2 0 世纪7 0 年代自由曲面造型； 2 0 世纪八十年代中期至今一基于约束的实体造型。 三维计算机图形技术的发展，推动着计算机辅助设计技术向高技术领域推 进，逐渐向三维c a d 技术过渡和发展。三维的优势使得广大科研人员和软件开 发者对其宠爱有加，尤其是d a s s a u l ts y s t e m s 公司的c a t i a ，e d s 公司的 u g ，p t c 公司的p r o e 等主流c a d 软件深入研发，三维c a d 软件席卷c a d 市场。国内的高校和科研院所在c a d 支撑和应用软件的开发上担任极其重要的 角色：在优化设计方面，有华中科技大学的优化程序库o p b ；在二维交互式绘 图方面，有清华和华中科技大学共同研制的g h m d s ，可以和a u t o c a d 的1 2 版基本兼容；在二次开发平台上北航的c a x a 三维造型软件基于e d s 公司的 p a r a s o l i d ，南航的s u p e r m a n c a d c a m 2 0 0 0 基于d s 下属的s p a t i a l 公司的a c i s 开发，并逐渐形成了自己的开发平台。 随着c a d 技术不断研究、开发与广泛应用，对c a d 技术提出越来越高的 要求，c a d 从其自身技术的发展来看，将朝着以下几个方向发展：集成化、面 向先进制造技术的c a d 技术、智能化、并行工程、网络化。 c o m p m e ra i d e dm a n u f a c t u r i n g ，简称c a m ，即计算机辅助制造，可定义为 能通过直接或间接地与工厂资源接口的计算机来完成制造系统的计划、操作工序 第1 章绪论 控制和管理工作的计算机系统，以数控加工( 自动) 编程为主。c a m 是计算机 几何图形( c a g d ，c o m p u t e r - a i d e dg e o m e t r yd e s i g n ) 和机械加工工艺相结合产 生的现代机械自动化加工技术。2 0 世纪5 0 年代，麻省理工学院设计了一种专门 用于机械零件数控加工程序编制的语言，称为a p t ( a u t o m a t i c a l l yp r o g r a m m e d t 0 0 1 ) 数控程序语言，解决数控程序的编制问题，从而揭开了基于计算机的数控 编程技术的研究。另外，c a d 几何建模技术的发展促进了c a m 技术的发展， c a m 从最初的基于线架，经基于曲面c a m ，到今天的基于实体和基于参数化特 征的c a m 。在国外，有p r o e 、u g 、c a t i a 、c i m a t r o n 、d e l c a m 等软件； 国内在技术上也取得了重大突破，逐渐形成了适合我国生产需要和生产模式的 c a m 软件和模块，如北航的c a x a 的三维数控加工自动编程，南航基于a c i s 平台开发的s u p e r m a n 2 0 0 0 c a d c a m 的铣削自动编程模块。c a m 技术总的发展 情况滞后于c a d 技术，但已受到研发者的重视，加之数控加工对c a m 提出的 新的功能要求，c a m 领域将会获得更大的发展1 。 1 2n c 加工仿真技术概述 数控加工仿真是c a d c a m 技术的底层关键技术，也是数控技术、仿真技 术与虚拟现实技术等先进技术的交叉应用学科之一。数控加工仿真是利用计算机 来模拟实际的a n - r _ 过程，验证n c 程序和刀路文件的可靠性，能减少试切，进而 解决试切验证占用机床的问题，提高了生产率。 1 2 1n c 仿真技术 从仿真环境的对象特征及其目的来看，n c 仿真分为几何仿真和物理仿真。 几何仿真不考虑切削参数、切削力及其他物理因素的影响，只仿真刀具工件几 何体的运动。切削过程的力学仿真属于物理仿真的一种。切削力是计算切削功率、 选择刀具、设计夹具和制定工艺等环节中不可少的数据，对确定合理的金属切削 用量，优化刀具的几何参数，都具有非常重要的意义；它直接影响着切削热的产 生。并进一步影响着刀具磨损、刀具耐用度和已加工表面质量。将工件的受力分 析实时应用在虚拟加工过程当中，不仅能模拟演示由于工件、刀具等的参数改变 所带来的受力改变，还能进行及时调整，帮助选择最合适的加工参数。 1 2 2n oj j u r 几何仿真的研究现状 几何仿真方法随着实体建模技术的发展而发展，根据建模技术的不同，可将 2 第1 章绪论 n c 几何仿真技术归纳为四类方法：实体建模法、z b u f f e r 方法、离散矢量法和 空间离散法等3 1 。 1 2 2 1 国外的研究现状 实体建模系统使同时进行刀路仿真和验证变得可能，可是计算量太大。c s g ( c o n s t r u c t i v es o l i dg e o m e t r y ) 的仿真系统开支正比例于刀具路径的四次方，即 其复杂度为o ( n 4 ) p 1 。一般的曲面加工程序有近1 0 ，0 0 0 个刀具路径。当前 的实体建模研究集中在用b r e p ( b o u n d a r yr e p r e s n t a t i o n ) 来优化刀具扫描体的 计算。基于b r e p 模型的仿真系统开支由减去扫描体生成的新表面决定的，其复 杂度在o ( n ) 和o ( n ) 之间。 z b u f f e r 方法使实体建模法中的直接布尔运算化简为关于光线的一维布尔运 算，复杂度为o ( n ) p 1 ，显著提高了仿真验证的效率。很多公司开发了基于z - b u 脑 方法的产品。采用z - b u f f e r 数据结构的像素光线表达法受z b u f f e r 数据机构和像 素物理特性的影响，检验精度受限于光线方向而且难以实现五轴数控加工的验 证。 w a n gw p 和w a n gk k p l 提出一种基于图像空间的z b u f f e r 方法，这种方法 和计算机图形学中用于隐藏面消除的z b u f f e r 算法相似。首先从屏幕上的每个像 素引出系列平行法线矢量，然后利用扫描线算法在这些矢量和刀具扫描体之间 进行求交运算。这种方法对每个像素要存储工件进出点的z 向深度。工件和刀具 扫描体每执行一次布尔运算，工件的z - b u f f e r 就进行一次比较、更新操作。w a n g 和其它几位研究者还使用了一种称为扩展z - b u f f e r 的方法，适用于五轴加工仿 真。 c h a p p e l 提出标准矢量法，即所谓的“点矢”( p o i n t v e c t o r ) 技术。在工件 表面选择一些点集合以近似代替工件实体，通过这些点计算出法向矢量，接着， 把法矢延伸直到与刀具扫描体相交，实现工件表面法矢与刀具扫描体在一系列位 置上求交。由于避免了仿真中间步骤而提高了效率，但它没有克服计算效率和实 用性问题，这种方法没有得到推广。 j e r a r d 和o l i v e r p l 分别提出了用于复杂曲面n c 验证的离散矢量法。他们都 沿用了c h a p p e l 的方法，设计曲面是由离散点集近似表达的，并且每个离散点对 应相应的矢量。o l i v e r 离散法是基于图象的像素级离散，该方法与z - b u f f e r 像素 表现光线表达法相比，在检验精度上有了较大的提高。j e r a r d 实现了基于物体的 离散，不受屏幕像素的影响，采用z b u f f e r 算法将网格，各矢量彼此平行，检验精 度没有得到很大改善，j e r 甜d 经过改进采用曲面法矢量与离散点相对应后，才真 正满足了复杂曲n c 验证对精度的要求。 v a nh o o k p l 提出了一种扩展z b u f f e r 算法，即基于d e x e l 模型的离散法。和 第1 章绪论 w a n g 的方法不同的是他不采用扫描体包络面相交的扫描线，而是采用预先计算 好的工件像素图象。沿着刀具路径执行毛坯和刀具之间的布尔运算。这种图象空 间分割法实现了实时性加工仿真，但它仅局限于三轴加工仿真。 表1 1 5 1 给出了当前的几何加工仿真算法和方法。 表1 1n c 刀路验证算法的比较 t a b l e1 1c o m p a r i s o no f a l g o r i t h m sf o rn ct o o lp a t hv e r i f i c a t i o n a l g o r i t h mw o r k p i e c e t o o l s w e p t c u to v e r c u tv i e w c o m p u t i m o d e lb l a n km o d e lv o l u m e w o r k p i e c e u n d e r c u t d e p e n - l a g m o d e lm o d e le n d r sd e n tt i m e s o l i d c s g b r e p c s g c s ( 、 c s g b r e p y e sn 0 v e r y m o d e l i n g b - r e pb - r e p s 1 0 w c s g b r e p z - b u f f e rz - b u f f e ro fz - b u f f e r s w e p ti m a g e y e sy e sf a s t b l a n ko f t o o lv o l u m ef r a m e z - b u f f e rb u f f e r s u r f a c es u r f a c e3 d3 d c u t y e s y e ss l o w n o r m a l sn o r m a l s p o l y g o np o l y g o n - s u r f a c e - n s n s d e x e l d e p t hd e p t hd 印mi m a g e y e sy e ss l o w e l e m e n te l e ：m e n t e l e m e n tf r a m e b u f f e r 1 2 2 2 国内的研究现状 哈尔滨工业大学f m s 研究中心研制的并通过专家鉴定的数控加工过程三维 动态图形仿真n c m p s ，该软件直接读取刀位信息，模拟加工中- t l , n i 零件全过 程，可进行碰撞检验。清华大学和华中科技大学合作研制的加工过程仿真器 h m p s ，以s i m n m e n s8 5 0 m 为对象进行仿真，仿真过程由n c 代码驱动，采用 交互式实时控制和管理。清华的韩u 进行了虚拟加工环境的开发，开发出了虚 拟机床的v r 加工环境。华中科技大学提出了基于八叉树模型的刀具扫描体方法 进行干涉与碰撞检验。西北工业大学p h l 做了很多基于空间离散法的n c 加工仿 真的研究。范纠在y u n c h i n gh u a n g u 叫的基础上实现换视向时重构d e x e l 模型的 方法。方川实现先换视向再离散模型的方法。虽然在n c 图形验证技术领域取 得了许多成就，但这丝毫没有减缓我们所面临的压力，我国目前的数控加工验证 局限于几何验证的范畴。国内对数控加工过程仿真尚处于跟踪、消化阶段，还没 有完善的适合生产使用的商品化实体仿真软件，原因在于实体仿真建模技术一定 程度上受到国内c a d 核心层技术发展的限制。 4 第1 章绪论 1 3 本文研究范围及具体工作 本文从计算机图形学基本原理出发，利用d e x e l 模型实现n c 铣削加工仿真， 用于检验n c 代码的准确性。研究内容主要是n c 代码解释和加工仿真。具体工 作安排如下： 第2 章研究了基于y a c c 工具的n c 代码解释器的实现。首先，设计了解释 器的整体结构。其次，分析了n c 代码的基本特点，通过对n c 代码的识别，实 现了词法分析。接着，给出了n c 代码的e b n f 形式，作为y a c c 工具p a r s e r g e n e r a t o r 的源文件，在p a r s e rg e n e r a t o r 集成开发环境下生成语法分析程序。最 后，研究了n c 解释器的错误处理机制，为仿真加工创造了条件。 第3 章研究了基于d e x e l 方法的加工仿真的实现。本章是全文的重点，从计 算机图形生成过程全面阐述了d e x e l 方法的实现。首先，对仿真对象刀具和毛坯 进行实体造型，给出了仿真对象的b r c p 模型表示。其次，在b r c p 模型基础上， 生成仿真对象的d e x e l 结构，实现了对象在物体空间的离散等价体，从而使得实 体间复杂的布尔求减运算化简为d e x e l 结构之间的一维的布尔运算。接着，笔者 基于著名的b r e s c n h a m 直线扫描算法实现刀具铣削轨迹的离散，在每个刀位点执 行刀具和毛坯的布尔减运算。最后，对仿真对象及铣削表面进行色调显示，利用 r g b 颜色模型以不同的颜色显示毛坯、刀具及铣削表面，忽略光照模型，根据 视线与显示表面法矢的夹角大小进行灰度值不同的显示，夹角越小，亮度越大， 夹角越大，亮度越小。 第4 章研究了仿真系统的实现。主要内容有模块设计，界面设计和仿真加工 实例。通过相同的加工实例，比较本系统与商业化软件s o l i d c a m 的加工结果， 分析了仿真系统设计需要坚守的准则：系统的设计需要充分考虑时间、空间和效 率三者之间的辩证关系。 5 第2 章基于y a c c 的n c 代码解释器的实现 第2 章基于y a c c 工具的n c 代码解释器的实现 n c 代码解释指对n c 代码进行词法分析、语法分析，查出其中存在的错误， 最后将n c 代码转换成所需的仿真数据。 n c 代码解释器的译码方式主要有两种：一种为“编译”方式，另一种为“解释” 方式u 瓦拶。编译方式一次性把n c 代码翻译为机器指令，速度快，但是结构复杂， 实现难度较大。解释方式将n c 代码整理成一定形式，由主程序一次一次取出， 进行分析判断，交由相应子程序执行，其优点是占内存少，易实现，交互性强， 但是速度相对慢。虽然对于系统开发来说，速度越快越好，但是译码模块并不是 验证系统的主要实时性任务。所以本系统中，采用了易于实现的解释方式来翻译 n c 程序。 目前n c 代码解释过程一般借助高级语言( c ，f o r t r a n 等) 来完成，程序员 工作量很大，本系统在实现难度大的语法分析器上，采用了编译工具y a c c ，实 现了手工编写词法分析程序与工具自动构造语法分析程序的结合。 2 1 解释器的架构 n c 程序的文法结构比较简单，词法分析器做起来难度不大，采用手工编程 的方法来实现。而作为解释器核心的语法分析器，采用语法生成工具y y a c ( y e t a n o t h e rc o m p i l e rc o m p i l e r ) 来构造。 解释器的工作流程图如图2 1 所示，主要由三个模块组成，词法分析、语法 分析和错误检验。流程图中出现的y y l e x 函数是出于语法自动构造工具的需要， 工具y a c c 的主体函数y ) ，p a r s e 通过不断读取词法分析的输出作为输入流，默认 情况下，y y a r s e 把y y l e x 作为词法分析的输出，而本系统的词法分析是手工编程 实现的，没有自动产生y y l e x 函数，因此，需要写个y y l e x 函数作为接口函数， 供) ，) ，p a i s e 函数调用。 1 词法分析其功能是将n c 程序源代码转换成程序字，就是不断对源代码 做识别，将识别出来的标识( t o k e n ) ，亦可称作程序字，放到自定义的链表上， 此链表作为语法分析器构造和n c 代码向仿真参数数据转换的输入流。 2 语法分析语法分析是解释器的核心部分，其功能是判断由词法分析给出 的单词序列是否符合n c 程序的文法规则。语法分析比较复杂，手工编程的话难 度较大。本系统利用编译工具y a c c 自动构造了一个l r 语法分析器。主要就是 根据n c 程序的文法特点，定义转换规则，作为y a c c 的源程序，然后由y y a c 6 第2 章基于y a c c 的n c 代码解释器的实现 图2 1n c 代码解释实现流程 f i 9 2 1f l o wc h a r to f n cc o d ei n t e r p r e t i n gr e a l i z a t i o n 生成符合c 语言特点的语法分析程序。 3 错误检验错误检验包括词法错误和语法错误等，本系统的错误检验功能 可以定位错误位置和出错原因。 2 2 词法分析程序的手工编制 2 2 1 n c 程序简介 n c 程序由若干块组成，块由若干指令字组成。字是由一个地址字符和一个 表示数值的数字或数字序列组成的，如图2 2 所示。 母，用于表示坐标轴( x ， 了常用地址符的功能。 第2 章基于y a c c 的n c 代码解释器的实现 图2 2 n c 代码的块结构 f i 醇2s t r u c t u r eo f n cc o d eb l o c k 表2 1 常用字母代码的含义 t a b l e 2 1m e a n i n go fc o m m o n a l p h ac o d e 功能代码备注 程序号 o程序号 子块号 n子块号 准备功能 g定义活动方式 坐标地址 x 、y 、z 轴向运动指令 进给速度 f 定义进给速度 主轴速度 s 定义主轴转速 刀具功能 t 定义刀具号 辅助功能m机床的辅助动作 偏置号h 、d偏置号 子程序调用次数p子程序调用次数 子程序调用 l子程序调用 参数p 、q 、r 固定循环次数 暂停 p 、x 暂停时间 2 2 2 词法分析的实现 矿 词法分析程序完成的是解释器第一阶段的工作。其主要任务是对n c 源程， 进行识别，把识别出来的标识符号放到自定义链表上，作为构造语法分析及卜 8 第2 章基于y a c c 的n c 代码解释器的实现 代码向仿真数据转换的输入流。简言之，词法分析程序的功能是读入数控代码， 输出标识符号。 针对n c 程序的特点，作为识别目标的标识采用三元式表示，( 标识种别， 标识名称，标识自身的值( 实部，虚部) ) 。在系统开发中，是这样定义的： c l a s e ec t o k e n 标识类 以下是标识类的私有变量部分 i n tt o k e n t y p e ；标识类别 c s t r i n gt o k e n n a m e ；标识名称 u n i o n i n tt o k e n i n t ；标识值的实部 d o u b l et o k e n r e a l ； 虚部 ： 另外，定义n c 程序的字符集，用于判断读取的字符是否属于解释器该识别 的范畴，是的话，做相应的归类处理，将所读取的字符信息赋值给标识类对象， 最后，将被赋值对象作为一个结点插入链表。词法分析的实现如图2 3 所示。 图2 3 词法分析实现过程 f i 9 2 3f l o wc h a r to f n cc o d ei n t e r p r e t i n gr e a l i z a t i o n 9 第2 章基于y a c c 的n c 代码解释器的实现 2 3 用y a c c 工具构造语法分析器 n c 代码的语法分析是解释程序的核心部分，其功能是识别由词法分析给出 的标识符号序列是否是n c 代码文法的正确程序。本节介绍语法分析器的自动构 造。 2 3 1n c 代码的e b n f 表示 2 3 1 1 文法的概念驯 文法g 定义为四元组( v ，v r ，p ，s ) 。 其中v 为非终结符( 或语法实体，变量) 集；v r 为终结符集；p 为产生式( 也 称规则) 的集合；v 、v r 和p 是非空有穷集。s 称为开始符号，它是一个非终 结符，至少要在一条规则中作为左部出现。 v n v r = 西 通常用v 表示v uv r ，v 称为文法g 的字母表。 很多时候，不用将文法g 用四元组显式地表示出来，而只写出其产生式。 一般约定，第一条产生式的左部是开始符号；用尖括号括起来的为非终结符，不 用尖括号括起来的是终结符。终结符即构成语言文法的单词，是语法成分的最小 单元，而非终结符则是一个语法成分，书写语言程序中并不出现。 乔姆斯基( c h o m s k y ) 于1 9 5 6 年建立了形式语言的描述理论，把文法分成 四种类型，即0 型、l 型、2 型和3 型。它们之间的差别在于对产生式有不同限 制。 0 型文法设g - ( v ，v r ，p ，s ) ，如果每个产生式妒口是这样一种结构： 0 f u v r ) 且至少含有一个非终结符，而p ( v u v r ) 。 1 型文法设g = ，v r ，p ，s ) ，如果p 中的每个产生式护p 均满足例h ， 仅仅s 一占除外。 2 型文法设皑v ，v r ，p ，s ) ，如果每个产生式伊p 是这样一种结构： a 是一个非终结符，而口( v u v r ) 。则此文法称为2 型的或上下文无关 ( c o n t e x t - f r e e ) 的。 3 型文法设皑v ，v r ，p ，s ) ，如果每个产生式一口都是舾o b 或舾鸽 其中a 和b 都是非终结符，0 c 是终结符。 四个文法类的定义逐渐增加限制的，每种正规文法都上下文无关，每种上下 文无关文法都是上下文有关的，而每一种上下文有关文法都是0 型文法。称0 1 0 第2 章基于y a c c 的n c 代码解释器的实现 型文法产生的语言为o 型语言，上下文有关文法、上下文无关文法和正规文法产 生的语言分别称为上下文有关语言、上下文无关语言和正规语言。n c 代码是典 型的上下文无关文法，即语法单位可完全独立于其可能出现的环境2 5 1 。 2 3 1 2n c 代码的e b n f 表示 形式语言的理论已证明，给定一个文法，就能从结构上唯一确定其语言弘。 因此，给出n c 代码的文法表示是很有意义的( 文法表示是语法分析器自动 构造的必要前提) 。同其它高级程序设计语言一样，n c 程序能用3 型文法( 正 规文法) 描速。下面给出n c 程序的扩充巴科斯瑙尔范式( e b n f ) 表示形式。 e b n f 表示的符号说明。 表示语法构造成分，或称语法单位，为非终结符。 ：= 该符号的左部由右部定义，可读作“定义为”。 i 表示或，为左部可由多个右部定义。 ) 表示花括号内的语法成分可以重复。在不加上下界时可重复0 到任意 次数。 】可选项 ( ) 表示括号内的成分优先 上述符号称“元符号”，定义用到上述符号作为文法符号时需引号”括起。 n c 代码的e b n f 表示为： ：= 【 】 i ：= 【m ：- - - - 【m ：= 】 ：= ) 、i l ：= ：= 【 ) ：=： 】 ：= 【 、i l ：= p r o gl ：= m 1 7 h a ：= l ：= n ：= ( l 一) i i 一) ：= ( x i y i z i a i b i c i u i v i w i r i i i j i k ) ：= i i i i i i i i ：g ：- f ：= s ：= - t ：= ( h i d ) ：= ( p i d ) 】 ：_ p ：= 文本 ：- = 0 1 11 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 3 2 语法分析程序的实现 2 3 2 1 语法分析方法概述例 目前，语法分析的常用方法有自顶向下分析( t o p d o w np a r s e r ) 和自底向上 分析( b o r o m u pp a r s e r ) 两大类。自顶向下分析包括确定分析和不确定分析，自 底向上分析包括算符优先分析和l r 分析。这些分析方法各有千秋，除了自顶向 下的不确定分析外，都是当今解释程序构造的实用方法。 1 自顶向下分析法也称面向目标的分析方法，即从文法的开始符号出发企 图推导出与输入单词串完全相匹配的句子，若输入串是给定文法的句子，则必能 推出，反之则出错。 确定的自项向下分析首先从文法开始符号出发，根据当前输入单词唯一地确 定选用哪个产生式替换相应非终结符往下推导，或构造一棵相应的语法树。它又 可分为递归子程序法和预测分析法两种。应用确定的自顶向下分析的文法必须是 l l ( 1 ) 文法，其中第一个l 表明白顶向下分析是从左向右扫描输入串，第二个 l 表示分析过程将从最左推导，1 表示只需向右看一个符号便可决定如何推导即 选择哪个产生式( 规则) 进行推导。类似也可以有l l ( k ) 文法，即需向前查看k 个符号才可确定选用哪个产生式。通常k = i ，个别情况k = 2 。 确定的自顶向下语法分析虽然对文法有一定限制，但由于实现方法简单，直 观，便于手工构造或自动生成语法分析器，因而仍是目前常用的语法分析方法之 一。 不确定的自顶向下分析在文法不满足l l ( 1 ) 时，可用此种方法，它也称为 带回溯的自顶向下分析法。在文法中当一个非终结符的产生式有多个候选时，而 当前输入单词无法唯一确定应选用的产生式，就会引起回溯。 1 2 第2 章基于y a c c 的n c 代码解释器的实现 此方法是一个试探过程，当分析不成功时则推翻分析退回到适当位置再重新 试探其余候选可能，直到把所有可能的推导序列都试完仍不成功才能确认输入串 不是该文法的句子而报错。它实际上是一种穷举的试探方法，因此效率低，代价 高，极少使用。 2 自底向上分析法又称移进一归约分析法( s h i f t r e d u c ep a r s e ) ，即对输入 符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分 析，一旦栈顶符号串形成某个句型的句柄时，就用该产生式的左部非终结符代替 相应右部文法符号串，这称为一步归约。重复这一过程直到栈中只剩下文法开始 符号时则分析成功，即确定输入串是该文法的句子。其关键问题在于分析过程中 如何确定句柄。 优先分析法可分为简单优先分析法和算符优先分析法两种。简单优先分析法 的基本思想是对文法按一定原则求出该文法所有符号即终结符和非终结符之间 的优先关系，按照这种关系确定归约过程中的句柄，其归约过程实际上是一种规 范归约。这种方法准确、规范，但分析效率较低，实际使用价值不大。算符优先 分析的基本思想是只规定算符之间的优先关系，即只考虑终结符之间的优先关 系，在归约过程中只要找到句柄就归约，并不考虑归约到的非终结符名，因而不 是规范规约。这种方法虽然有不规范问题，但分析速度快，特别适用于表达式分 析，实际应用中常采取一些措施克服其缺点。l r 分析法根据当前栈中的符号串 ( 通常以状态表示) 和向右顺序查看输入串的k 个( k o ) 符号就可唯一确定 分析器的动作是移进还是归约及利用哪个产生式归约，因而能唯一确定句柄。此 方法的归约过程是规范推导的逆过程，因此也是一种规范归约过程。l r ( k ) 分 析方法是1 9 6 5 年k n u t h 先生提出的，括号中的k 表示向右查看输入串符号的个 数。这种方法对于大多数用无二义性上下文无关文法描述的语言都可进行识别， 而且还具有分析速度快，准确、即时确定出错位置等优点。但用此方法来构造一 个实用语言文法分析器的工作量相当大，k 越大构造越复杂，实现越困难。因此， 目前真下实用的解释程序，所采用的l r 分析器都是借助于美国b e l l 实验室推出 的y a c c 来实现的。 2 3 2 2y a c c 语言和集成开发工具p a r s e rg e n e r a t o r 1 y a c c 语言 y a c c ( y e ta n o t h e rc o m p i l e r - c o m p i l e r ) 是19 7 8 由s t e p h e nc j o h n s o n 等在 美国贝尔实验室研制出来的一个基于i ，a i ，r ( 1 ) 类文法的语法分析程序的自动 构造工具。与高级语言相比，用y a c c 构建语法分析器在效率和效果方面都有 很大改善。y a c c 不是独立的语言，只是其宿主语言( 如c 、j a v a ) 的扩充， 本身并没有描述动作设计新的语言，而是借助其宿主语言来描述动作“。y a c c 第2 章基于y a c c 的n c 代码解释器的实现 接受用e b n f 描述的上下文无关语言的语法规则，且语法满足i a i r ( 1 ) 文法 的要求，y a c c 将其源程序及动作翻译成语法分析程序哪a r s e 2 4 1 ，示意图 如图2 4 。 y a c c 厂1 百石r 编译工具r 函磊i i l 源程序li n 狮e t a b h l _ - - _ _ _ _ _ - _ _ _ _ _ - - _ - - _ _ _ - - _ - _ - _ i _ - _ - _ _ _ - - |l 图2 4 语法分析程序的生成 y a c c 的工作需要人工编写语义处理程序作为前提，在y a c c 的源程序中， 容许在e b n f ( 扩展的巴科斯瑙尔范式) 描述的每条转换规则后增加该规则被 识别出来时需要完成的动作( 在本文中是一段c 程序) ，表明此规则规约时所作 的动作。 y y a c 源程序由说明部分、转换规则和程序段三部分组成，如下： 说明部分 转换规则 程序段部分 说明部分有两个可选择的部分。用“ ”和“) ”括起来的部分说明语义动作 中使用的数据类型、全局变量、包含头文件等。另一部分以”开头的，以关键 字 t o k e n 定义终结符。 转换规则部分把多个候选的产生式如s 呻p 。ip 2i ip 。表示成以下形式： s ：p l a c t i o n1 ip 2 a c t i o n 2 ) l p 。 a c t i o n n ) 程序段部分由完成a c t i o n 的一些函数组成。 以上三部分仅转换部分是必需的。 2 集成开发工具p a r s e rg e n e r a t o r 将y a c c 源程序转换成语法分析器需要相应的开发环境。常用的有u