（控制理论与控制工程专业论文）编译技术的工程应用研究.pdf

北京化工大学学位论文用纸 编译技术的工程应用研究 摘要 编译理论和技术是计算机领域中的核心理论与技术之一。在编译 器设计中，涉及到多项相关理论和技术，如形式化语言、自动机理论、 形式化语义理论、词法分析技术、语法分析技术、词法分析器和语法 分析器自动生成技术、语法制导翻译、中间代码、代码优化技术、数 据流分析等。这些理论和技术同样可以运用在工程应用系统的设计中， 解决许多信息分析和处理方面的问题，提高工程应用系统的适应能力 和可扩展能力。 本文首先讨论了基本编译技术在工程应用系统设计中的应用框 架，提出了应用系统内置词法分析器和语法分析器的工作模式，讨论 了利用编译技术进行信息分析时不同层次的语义处理实现方案、在工 程应用系统设计中的几种内置脚本引擎的实现方案，提出了可用户化 定制的工程应用系统设计模式。进一步研究了以编译技术为基础的逆 向建模技术和语句序列化代码分析技术及其应用。 在工程应用系统的设计中，不仅可以利用正则表达式分析技术实 现对复杂结构信息的检索，还可以运用词法分析技术对复杂结构信息 北京化工大学学位论文用纸 进行整理和分类，使信息的结构更为规范化，更便于分析和处理。在 词法分析的基础上，进一步运用语法分析技术则可以对复杂结构的信 息进行高效和准确的识别和分析。 在信息结构不确定的工程应用领域中，利用词法分析器和语法分 析器的自动生成技术，将词法和语法分析器嵌入在应用系统中，用词 法规则和语法规则对信息结构进行描述，并作为工程应用系统的输入， 由内置词法和语法分析器自动生成分析驱动表，即可以所描述结构的 信息进行高效、准确的分类、识别和分析。 在词法规则和语法规则的指导下，对信息进行分类、识别和分析， 分析结果通常需要反映为特定的语义行为。将语义行为的描述独立于 工程应用系统的设计，可以使系统具有更高的灵活性和可用户化能力。 根据对语义行为控制能力强弱的要求，可以采取预定义语义行为描述、 可编程语义行为描述、对象支持可编程语义行为描述等几种语义行为 描述策略。控制能力越强，语义行为的描述就越复杂，语义行为描述 的处理也就会越复杂。 脚本语言可以作为语义行为描述的一种有效手段。内置脚本引擎 的设计和使用可以给工程应用系统提供强大的用户控制能力，终端用 户可以以行为脚本的形式向应用系统提交对用户化行为的描述，行为 脚本在脚本调度机制和内置脚本引擎的支持下被调度和执行，从而可 以使应用系统具有更好的用户适应性和更高的用户化程度。本文选择c 北京化工大学学位论文用纸 个角度为研究人员和设计人员更形象地展示代码的结构和流程，帮助 研究人员和设计人员更全面、更准确地理解代码、发现问题，甚至可 以帮助设计人员寻找系统的优化方案。 在工程应用系统的设计中，对于代码内存在的隐蔽性错误，以手 工方式进行检测不仅工作量大，而且难以保证全面性和准确性。在代 码语法分析的基础上，进步对代码进行语句序列化，即可以通过语 句序列遍历分析代码在运行时的各种可能状态，并根据预定规则和用 户规则对代码的逻辑进行检测，帮助设计人员发现代码中隐藏的可能 逻辑错误。 关键词：编译技术，脚本引擎，用户定制，逆向建模 北京化工大学学位论文用纸 e x p r e s s i o na n a l i s y st e c l l i l o l o g y c o u l d b eu s e dt or e t r i e v a l c o m p l e x i n f o m a t i o n ， b u ta l s ol e x i c a la n a l y s i s t e c h n o l o g y c o u l d b e u s e dt o r e g u l a t ea n dc l a s s i 母i n f o r m a t i o n s ，t 0m a k et l l es 协j c t u r eo fi n f o m a t i o n m o r en o m l a l i z a t i o n ，e a s i l yt oa n a l i s y sa n dh a i l d l e b a s e do nl e x i c a l a n a l y s i s ，s y n t a ) ( a n a l y s i st e c h n o l o g yc o u l dm a k ef u r t h e re 行0 r t st od i s c e m a n da i l a l y s i si n f b 珊a t i o nw i t hc o m p l e xs t m c t u r em o r ee m c i e n t l ya n d m o r ee x a c t ly i nt h e e n g i n e 耐n g印p l i c a t i o n f i e l dw u n c e r t a j ni n f o 】瑚a t i o n s t m c t u r e ， b a s e do nl e x i c a l a i l a l y z e ra n ds y m a xa n a l y z e rg e n e r a t o r t e c h n o l o g y ，m ei n f o r m a t i o ns t m c t u r ec o u l db ed e s c r i p t e dw i t hl e x i c a l r u l e sa n ds y n t a ) ( r u l e s ，a n db et r e a t e da st l l e i n p u t o fe n g i n e e r i n g a p p l i c a t i o ns y s t e m ，s ot h ea n a l y s i sd r i v e r 诅b l ec o u l db eg e n e r a t e di n s i d e t l l es y s t e ma u t o m a t i c l y ，a n db eu s e dt od i r e c ts y s t e mt oc l a s s i f y ，d i s c e m a n da i l a l y s i sa l lk i n d so fi n f o m a t mw i md i 髓r e n ts t r i l c t l m se f f i c i e n t l y a n de x a c t l y t h er e s u l to fc l a s s i 匆i n g ，d i s c e m i n ga i l da 1 1 a l y s i s i n gt oi n f o n n a t i o n s d i r e c t e db yt h el e x i c a lr u l e sa n ds y n t a xm l e sa l w a y sn e e dt ob er e n e c t e d t os o m es p e c i a ls e m a n t i cb e h a v i o r s t h ei n d e p e n d e n t l 甜d e s c r i p t i o no f s e m a l l t i cb e h a v i o ri nd e s i g i lo fe n g i n e e r i n g 印p l i c a t i o ns y s t e mc o u l d m a k et h e s y s t e m m o r en e x i b l ya n du s e m b l y _ a c c o r d i n g t ot h e r e q u i r e m e n to ft h ec o n t r o l l a b i l i t yo fs e m a n t i cb e h a v i o r s ，t h ed e s i g no f t h e印p l i c a t i o n s y s t e mc o u l dc h o o s ep r e d e f i n e ds e m a n t i cb e h a v i o r d e s c r i p t i o n ，p r o g r a m m a b l e s e m a i l t i cb e h a v i o r d e s c r i p t i o n ， 0 r p r o g r 啪m a b l e s e m a n t 主cb e h a v i o rd e s c r i p 廿o n s u p p o n i 甜w i t l lo b j e c t m o r ep o w e r 如l 也ec o n t r o l l a b i l i t yo fd e s c r i p t i o no fs e m a n t i co f b e h a v i o r i s ，t h ed e s c r i p t i o no fs e m a n t i c b e h a v i o ri sm o r ec o m p l e x ，a n dt h e 北京化工大学学位论文用纸 h a i l d l i n gt om ed e s c r i 皿o no fs e m a n t i cb e h a v i o ri sm o r ec o m p l e xa l s o s c r i p tj a n g u a g ei sa ne f f i c i e n ta p p r o a c ho ft h ed e s c r i p t i o no fs e m a n t i c b e h a v i o r d e s i g n i n ga n du s i n go fe m b e d d e ds c r i p te n g i n ec o u l dp r o v i d e p o w e r m lu s e rc o n t r o l l a b i l i t yt oe n g i n e e r i n g 印p l i c a t i o ns y s t e m u s e r c o u l ds u b m i tt 1 1 e d e s c d p t i o n o f r e p o n s e b e h a v i o rt o s y s t e m w i m b e h a v i o rs c r i p t t h es c r i p tw i l lb ed i s p a t c h e db ys c r i p td i s p a t c hs y s t e m ， a n de x e c u t eu n d e rt h es u p p o r to fe m b e d d e ds c r i p te n 百n e w i t hu s i n go f b e h a v i o rs c “p t ，a p p l i c a t i o ns y s t e mc o u l db em o r ea d a p t a b l y t h ed e s i 印 o fe m b e d d e ds c r i p te n g i n er e f e r st om e 叩e ns o u r c ec o m p i l e rg c c ， c h o o s i n gcl a n g u a g ea sm el a n g u a g eb 鹊e ，a n dc h 0 0 s i n gg c c 一仃e e ，i 吼 a n ds c i la se x p l a i n i n gl a y e rs e p 啪t e l y i nm ed e s i g i lo fm ep r o c e s si n d u s 订y 印p l i c a t l o ns y s t e m ，m e 咖c t u r e n l l e so fd a t a 疔锄ec o l l e c t e d 爵o md i 虢r e n ts o u r c ec o u l db ed e s c r i p t e d 证 f o m a l l a l l g u a g e ，a j l db ei n l ) u t e di n t 0d a t a 丘a m ep r o c e s ss y s t e ma s c o n f i g u r a t i o ni n f - 0 h n a t i o n t h i s 坝嗲w i l lm a k e l ep r o c e s so fd a 诅触m e a n a l y s i sa n dh a n d l ed e p e n d e m e df i r o mt l l ed e t a i ld a t af r o mf o m l a t ，s o r e b u i l d i n go ft h ea p p l i c a t i o ns y s t e mc o u l db ea v o i d e dw h e n 也ed a t a f - 肿lf o m l a ti sc h a n g e d c u s t o ma c t i o ni nd e s i g no fp r o c e s si n d u s t 叫m o n i t i n gs y s t e mi s 啪o m e rt y p i c a lc a s eo fc o m p r e h e n s i v ea p p l y i n go fc o m p i l et e c h n o l o g y i nd e s i g no fp r o c e s si n d l l s t r ym o n i t i n gs y s t e m ，d i f f b f e n tu s e r 3c o u l dh a v e d i 矗奄r c n tr e q u i m e m st ot h ew a yo fd a t ap m c e s s ，r e p o n s eb e h a v i o r w i t l e m b e d d i n go fe m b e d d e ds c r i p te n g i n ea n dc u s t o ma c t i o nm e c h a i l i s m ， u s e r ss p e c i a lr e q u i m e n t sc o u l db es e p 揪df r o mt h ei m p l e m e n to fm e 如n c t i o nd e t a i lo f a p p l i c a t i o ns y s t e m ，s ot h ed e s i g no fa p p l i c a t i o ns y s t e m c o u l df o c u si nb u s i n e s sl o g i ca n dm n c t i o n t h ec u s t o ma c t i o ni n t e m c e 北京化工大学学位论文用纸 c o u l db ep r o v i d e dt ou s e rt h r o u g ht h ew a yo fe v e n tr 印o n s e i nt h e p r o c e s so fs y s t e md i s t r i b u t i n go rs y s t e mu s i n g ，a d m i n i s 心l t o ro re n d - u s e r c o u l dd e s c r 啦c u s t o ma c t i o nw i 也b e h a v i o rs c r i p t ，a n db i n ds c r i p tt o s p e c i a lr 印o n s ee v e n t t h es c r i p tw i l lb ed i s p a t c h e db ye v e md i s p a t c h s y s t e m ，a n db ee x p l a i n e da n de x e c u t e db ye m b e d d e ds c r i p te n 西n e ，t o a c c o m p l i s hc u s t o ma c t i o no fu s e r w i t l lt l l a t ，印p l i c a t i o ns y s t e mc o u l d r e p r e s e n td i 僚r e l l tb e h a v i o ra c c o r d i n gt od i 虢r e n tr e q u i r e m e n to fu s e r n o th a et or e b u i l d a n a l y s i s i n gt oe i t h e re n g i n e e r i n ga p p l i c a t i o ns y s t e md e s i g n e db y o n e s e l o rr e f e r e n c ec o d ec o m ef - r o mo t l l e rs o u r c e ，m o d e ld o c 啪e n t sa r e i m p o r t a n ta n a l y s i st 0 0 1 s i n v e r s em o d e l i n gt e c l l l l 0 1 0 9 yb a s e do nc o m p i l e t e c l i i l o l o g yc o u l db eu s e dt oa 1 1 a l y s i ss o u r c ec o d ea n dg e n e r a t em o d e l d o c 砌e n t sw h i c ha r eu pt oin m ，s t 眦d a r da u t o m a t i c l y t h ed o c 呦e n t s c o u l ds h o wc o d e 咖c t u r ca n dp m c e s sn o wt or e s e a r c h e ra n dd e s i g i l e r m o r ev i v i d l y ，h e l pr e s e a r c h e ra i l dd e s i g n e rt ou n d e r s t a n dc o d e ，f i n do u t p f o b l e mm o r ec o m p l e t e l ya l l de x a c t l y ，e v e nt oh e l p d e s i g n e rf i n do u tm e o p t i m i z a t i o ns c h e m e m a i l u a lc h e c k i n gt oe r r o r sh i d d e ni nc o d e si sn o to n l yb u r d e n s o m e ， b u t “s ou n _ a l l r o u n da n du n c e m t a i n b a s e d0 na l l a l y s i st oc o d es y m a x ， c o d ec o u l db e 血n t l e rs e r i a l i z e di n t os t a t e m e m s t h r o u g h 髓a l y s i s i n gt 0 s t a t e m e n ts e r i a l s a u t o m a t i c l y r u n t i m e s t a t eo ft h ec o d ec o u l d b e c h e c k e d ，a 1 1 dm a k ef u n l l e rc h e c k i n gt oc o d el o g i ca c c o r d i n g t 0 p r e d e f i n e dr u l e sa n du s e rn l l e s 7 i h i sw i l lh e l p d e s i g n e rt o f i n do u t p o s s i b l e1 0 9 i ce r 】幻r sh i d d e ni nc o d e k e yw o i 王d s ：c o m p i l e7 1 1 e c h n o l o g y ，s c r i p te n g i n e ，u s e rc u s t o m i z e d ， i n v e r s em o d e l i n g v i i - 北京化工大学学位论文用纸 g c c o r c f a d f a n f a i 玎l r t x m d c i l m s i l s c i l v a s m w s h p v 符号说明 g n u c o m p i l e rc o l l e c t i o n 0 p e nr e s e a r c hc o m p i l e r f i n i t ca u t o m a t a d e 记蕊n i s t i cf i n i t ea 1 n o m a t a n o f l d e t e m l i n i s t i cf i n i t ea u t o m a t a r e g i s t e rt t a i l s f e rl a n g u a g e r e g i s t e rt r 肌s f e rl a l l g u a g ee x p r c s s i o n m a c h i n ed e s c r 碴t i o n c o m m o ni n t e m l e d i a t el a n g u a g e m i c r o s 0 ri m e m e d i a t el a l l g u a g e s i m p l ec o m m o ni n t e h n e d i a t el a l l g u a g e v i n u 丑l a s m 、矾n d o w ss c d p th o s t v a r i a b l e sp o s s i b l e v a l u e x i - 北京化工大学 学位论文原创性声明 y8 8 2 3 6 本人郑重声明：所呈交的学位论文，是本人在导师的 指导下，独立进行研究工作所取得的成果。除文中已经注明 引用的内容外，本论文不含任何其他个人或集体已经发表或 撰写过的作品成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 学位论文作者签名：劈曰佑 2 0 0 5 年1 1 月1 0 日 北京化工大学学位论文用纸 编译器o r c 【1 9 】。o r c 是i n t e l 以自己的处理器产品f 2 0 l 为背景，在编译器研发领域 开展的一项活动，i n t e l 还为开发商提供了高品质的编译器和性能分析工具。i m e l c + + 编译器和i n t e lf o r t m 编译器为i a 3 2 和安腾处理器系列实施了创新优化技术。 i n t e l 凭借其广泛的微处理器体系结构知识和先进的编译器方法，为关键任务和高 性能应用开发提供了具备出色应用性能的编译器。 自2 0 0 2 年发布以来，o r c 受到了大量研究机构的青睐，其下载量超过4 0 0 0 份。许多大学和学院的研究小组已将o r c 作为其编译器和计算机体系结构研究项 目的基础设施。 明尼苏达大学计算机科学与工程系的p e t l - c h u n gy e w 教授这样评价0 r c ： “o r c 为研究机构做出了重要贡献。该编译器框架使众多研究活动得以开展，从 与创新设备相关的优化和功能编译器研究到多线程和未来微处理器特性等，不胜 枚举。” 1 2 国内编译理论和技术的发展 我国在编译理论和技术上的研究和开发工作起步并不算晚。早在6 0 年代初期， 董韫美院士和杨芙清院士就分别在中科院和北大领导了研究组为国产计算机开发 面向高级语言a l g o l 和f o r t r a n 的编译系统。 在改革开放前，根据国家的需要，中科院、国防科大、江南计算所、北大等 单位一直在研制国产计算机，包括大型机和高性能计算机( 如向量机、并行机) ， 相应的也在研制高级语言编译器。中科院计算所以董韫美院士领导的研究组先后 开发了1 1 9 机、1 0 9 机的类a l g o l 语言编译器b c y 。国防科大也开发了向量编 译器和向量识别器。 7 0 年代，中科院计算所张兆庆教授研究组( 后称a c t g r o u p ) 开始在国产机 上研制f o r t r a n 语言编译器，先后参与了众多的院级和国家级科研攻关项目， 主持开发了0 1 3 ，7 5 7 ，k j 8 9 2 0 等国产大型机系统中的f o r l i 乙n 语言编译器，所 研制的编译器支持了数百万行应用软件的运行。 北京化工大学学位论文用纸 9 0 年代以来，a c t 0 r o u p 承担了多项科学院重大项目、国家攻关项目、8 6 3 项 目，以及多项国际合作项目，先后开发了共享内存多处理机的并行识别器、分布 式内存多处理机的并行识别器、s i m d 芯片和v l i w 芯片的并行优化c 编译器， 还推出了集成化、可视化的并行编程环境。a c t ( 两邶在先进编译技术和并行编程 环境方面的研究工作获得国内外专家高度评价，国际著名学者评价此研究组居编 译领域的世界先进行列，其研究成果正逐步推向国内外市场。 另一方面，自9 0 年代以来，国内主要以研制并行机为主相应的并行编译器 研制也在国内开展起来。代表性的成果有：上海复旦大学朱传琪教授研究组研制 的面向共享存储并行机的并行优化编译器a f t ，被评为达到世界领先水平。清华 大学汤志忠教授研究组在软流水优化技术上也做了很多优秀的研究工作。清华大 学郑纬民教授研究组开发了交互式并行化系统t i p s e x p l o r c r ，北京大学许卓群教 授、李晓明教授研究组在h p f ( h i 曲p e r f o r m a n c ef o r t r a n ) 编译器方面做了多年工 作，取得了很好的研究成果。此外，国防科大、江南计算所等单位也都有从事并 行编译技术研究。随着芯片研制，国内还有若干单位也在开展基于g c c 生成面向 特定芯片的编译器工作。 2 0 0 3 年4 月，在德国柏林举行的i n t e l 信息技术峰会上，i n t e l 公司与中国科学 院( c a s ) 计算所联合发布了针对i n t e l 安腾 处理器系列的开放研究编译器 ( o r c ) 2 0 版本。此套支持l i n u x 的开放源代码编译器工具专门面向进行高级编译 器和微体系结构研发的研究人员，在以前版本的基础上增添了多种新特性。 此编译器的新特性有助于编译器研究人员了解如何为安腾体系结构实施内存 分层优化、c + + 编程特性、以及全部函数的优化等。o r c2 o 包括性能分析工具， 能够帮助研究人员了解程序热点和瓶颈。 0 r c2 0 使用模块化编译器组件，支持每个“模块”完成具体的优化任务。这 就使研究人员能够快速测试基本编译器框架中的不同技术。编译器框架也带有基 础性的工具，如程序性能分析( p r o n l i n 曲和域生成( f e 舀o nf o n n a t i o n ) 等。 i n t c l 高级院士兼i n t e l 企业平台部i n t e l 微处理器研究实验室主任j i l s t i nr a t n l e r 北京化工大学学位论文用纸 说：“i n t e l 与中国科学院的合作取得了可喜的成果。2 0 升级至开放研究编译嚣将 会加速安腾微处理器的研究，提供灵活可扩展的平台来探索新的代码生成和优化 技术。” 中国科学院计算所所长李国杰指出：“编译器框架的先进特性为安腾处理器系 列体系结构提供了出色的功能。该世界一流的框架使o r c 成为尖端研究工具，并 引领着中国和全球研究机构的编译器和处理技术创新。” 我国在编译器研究领域所取得的卓越成就表明，我国在编译器领域的研究水 平基本与国际同领域的研究水平同步。 1 3 编译技术的工程应用 建立在形式化方法、自动机理论和形式化语义理论基础上的编译技术包含多 个组成部分，如正则表达式分析、词法分析、语法分析、语法制导分析、词法分 析器和语法分析器自动生成、语义分析2 m 3 1 和处理【2 4 2 孔、中间代码的生成和运用 1 2 6 1 、交叉编译、空间分配与管圳2 7 3 “、代码优化1 3 2 删与生成【4 1 4 3 1 、链接与加载1 蜘 等等。编译技术的本质是信息的形式化表达和基于形式化的信息分析和处理，因 此编译技术也是信息分析和处理的利器，在编译过程各个阶段所使用的各种思想、 理论和技术，同样可以运用在工程应用系统设计的适当场合中。 形式化方法分为形式化描述和基于形式化描述的形式化开发，由于形式化方 法是建立在严格的语法语义基础上的，因此形式化方法具有比非形式化方法更好 的一致性、确定性和完整性。 d o n a l de m m 在1 9 7 7 年5 月开始设计的t c x 科技排版系统、王选教授主持 设计和开发的方正排版系统都是形式化方法的经典应用实例。 形式化方法还在数字电路设计和验证、通信协议设计和验证、需求分析描述、 系统正确性验证f 4 5 、可靠性验证【4 纠9 1 、测试用例设计50 1 、运行时态分析【5 1 ，5 2 1 、 数据流分析1 5 3 聊1 等许多方面的应用中都取得了显著的成绩。 虽然到目前为止，形式化方法在实际应用中还不得不面对一些尚未克服的困 北京化工大学学位论文用纸 难，例如，逻辑系统的不完备性( i n c o m p l e t e n e s s ) 、逻辑系统的不可判定性 ( u n d e c i d a b i l i t y ) 、自动推理的难处理性( i n 仃a c t a b i l i t y ) ，但是形式化方法在实际应用 当中还是可以发挥许多重要的作用。 虽然一些已经取得成功的应用实例表明，有理由相信编译理论和技术在工程 应用系统的设计中也应该有广阔的应用空间，但由于编译技术本身的理论复杂性 和结构复杂性，对于一般工程应用系统的设计人员来说，编译技术在工程应用系 统设计上的实施具有较高的难度，尤其目前在国内工程应用系统的设计中，编译 技术的应用大多还只停留在一个较浅的层次上。 对编译技术在工程应用系统设计上的应用领域、实施方案进行研究，不仅可 以拓展编译技术的应用范围，为工程应用系统设计人员提供参考实施方案，而且 为工程应用系统的设计探索了新的结构模式。 1 4 本文的工作及论文结构 本文对编译技术在工程应用系统设计中的应用领域、实施方案进行了研究， 并结合应用实例进行了讨论。 在第一章绪论中，介绍了编译理论和技术在国内和国外的发展状况、编译技 术在工程应用系统设计上的应用情况，提出了本课题的研究意义。 在第二章中，研究了正则表达式分析技术、词法分析技术在工程应用系统设 计中的应用领域和实施方案，提出了工程应用系统内置词法分析器的实现方案和 接口设计方案。 在第三章中，研究了语法分析技术在工程应用系统设计中的应用领域和实施 方案，提出了基于l r ( 1 ) 分析的工程应用系统内置语法分析器的实现方案和接口设 计方案。 在第四章中，研究了语义处理技术在工程应用系统设计中的应用领域，提出 了三种适应不同需求的语义行为描述策略，并研究了相应的实施方案。 在第五章中，分析了g c c 编译器的内部结构，研究了工程应用系统内置脚本 北京化工大学学位论文用纸 引擎的实现结构，研究并对比了以o c c 编译器为基础，构造内嚣脚本引擎的几种 不同实施方案。 在第六章中，以过程工业应用系统中的数据帧处理问题和过程工业监测系统 中的用户行为定制问题为对象，研究了应用形式化方法构造通用型数据帧分析和 处理系统的解决方案，和以内置脚本引擎技术实现用户行为定制的解决方案，提 出了用户定制技术的观点。 在第七章中，研究了以语义分析为基础的逆向建模技术及其实施方案，并对 逆向建模技术的应用进行了讨论。 在第八章中，研究了以语句序列化为基础的代码运行态分析技术，讨论了运 行态分析技术在代码分析和测试中的作用。 在最后一章中，对全文的研究内容进行了总结，并对本课题的后续研究工作 进行了展望。 北京化工大学学位论文用纸 第二章词法分析技术的工程应用 2 1 词法分析技术 词法分析过程是编译过程的第一个阶段，其基本目的是将字符流转换为词法 符号流。词法分析器是建立在有限自动机的基础上的，根据词法规则的描述，可 以通过手工或自动的方式生成相应的分析驱动表和有限自动机，有限自动机在分 析驱动表的驱动下对输入字符流进行分词处理。 词法分析技术在编译领域之外还可以应用予复杂结构信息的检索和分类，其 中最典型的应用实例就是利用正则表达式描述匹配模式并进行复杂信息检索，这 已成为复杂信息检索中的一项基本手段。 另外，在工程上还经常需要对以字符流或字节流方式传递的信息流进行识别、 分类和处理，利用词法分析技术可以对信息漉进行预分词处理，使信息流的逻辑 结构更为清晰，以便于更进一步的分析和处理。 在构造编译器的词法分析器时，虽然可以通过手工的方法根据词法规则描述 生成词法分析器的状态转换表，但当词法规则数量较大时，手工的计算工作量可 能会很大，因此通常会采用词法分析器自动生成的方法，如利用g n u 的l i 或 类似工具来生成词法分析器的实现代码。 对词法规则进行描述的基本语法是正则表达式。正则表达式是描述字符串匹 配模式的一种方式，其历史可以一直上溯至对人类神经系统如何工作所做的早期 研究。最初，两个神经生理学家w a r r e nm c c u i l o c h 和w a l t e rp i n s 研究出了一种数 学方式来描述人类的神经网络。1 9 5 6 年，数学家s t e p h e n e e n e 在m c c u l l o c h 和 p i t t s 早期工作的基础上，发表了一篇标题为“神经网事件的表示法”的论文，引 入了正则表达式的概念。正则表达式就是用来描述被称为“正则集的代数”的表 达式，因此采用“正则表达式”这个术语。 随后，u n i x 的主要发明人k e nt h o m p s o n 发现可以将这一工作应用于自己的 北京化工大学学位论文用纸 计算搜索算法的一些早期研究中。正则表达式的第一个实用应用程序就是u m x 中的q e d 编辑器。 从那时起，正则表达式逐渐被应用到信息技术领域中，经过几个时期的发展， 现在的正则表达式标准已经被i s o ( 国际标准组织) 批准和被o p e ng r 0 1 l p 组织认 定。 现在，正则表达式不仅是编译技术中词法规则表述的基本手段，而且已经成 为基于文本的编辑器和搜索工具中一个重要的模式表示方式。 随着对正则表达式应用需求的增加，在一些开发系统中已经内置了对正则表 达式的支持。例如，在m i c m s o f t 的n e t f 豫m e w o r k 中，就提供了基于正则表达式 的模式匹配功能，而j a v a 语言也在其1 4 版本以后增加了一个软件包j a v a _ u t i l r e g e x ， 提供对正则表达式的支持。 在工程应用系统的设计中，也可以利用正则表达式分析技术做为复杂信息检 索的一种手段。从应用角度来说，这一功能甚至可以直接从开发环境中获得，而 不须自行再去实现。 除了直接使用正则表达式分析技术外，在工程应用系统的设计中，当信息结 构的规则确定时，可以采用与词法分析器手工设计相同的方法，构造信息结构的 状态转换表，生成信息预分词的功能模块。对复杂结构信息进行整理和分类。 在工程应用系统的设计中，当信息结构的规则不确定时，为了适应可能遇到 的各种不同结构的输入信息，可以采取在运行时刻提供词法规则的策略，而不是 在设计阶段就确定要处理的词法规则。因此，在工程应用系统的设计中可以借鉴 词法分析器的自动生成技术对动态输入的词法规则进行处理，在运行时刻生成分 词驱动表。与编译器设计不同的是，在工程应用系统的设计中，词法分析驱动表 的自动生成过程是与词法分析过程一起做为工程应用系统的组成部分整合在应用 系统内部的，而且通过自动生成过程所生成的不是源代码，而是可供分词部分引 用的分析驱动表。 北京化工大学学位论文用纸 2 2 正则表达式的分析算法 虽然正则表达式的分析功能通常可以直接从开发环境中获得，但由于正则表 达式的分析技术是词法分析技术的核心，因此本文对正则表达式的分析技术及其 实现也进行了探讨。 词法分析技术是建立在有限自动机原理上的。在词法分析能够进行之前，首 先需要通过对词法规则的分析，建立有限自动机分析驱动表分析驱动表实际 上描述了一个以状态为行，以输入符号为列的状态转换矩阵。 词法分析过程就是在分析驱动表的驱动下，对输入字符流进行分词处理的过 程。随着字符流的读入，分析状态也在分析驱动表的驱动表推演，每当分析状态 推演到一个归约状态时，即得到一个分词项目。 正则表达式是词法规则描述的基础，因此根据正则表达式生成有限自动机分 析驱动表是词法分析技术的核心。 在对单一正则表达式进行处理时，丁f 则表达式的基本字元是基本字符、转义 字符和正则运算符( 正则表达式中的转义字符和运算符参见附录) ，每个基本字符 和转义字符将被视为一个可输入德号，对应于驱动表中的一列。 根据正则表达式生成有限自动机分析驱动表的算法步骤如下： 算法输入：正戳表达式串 算法输出：分析正鼬表达式分析驱动表 e i ：扫描正爨u 表达式以递归下降法生成规辩语法树； e 2 ：螽守遍历规购语法捌生成n f a ； e 3 ：角子集法将n f a 转换为d f a ； e 4 ：约简d f a ： e 5 ：将d 融转换为分析驱动表： 由于正则表达式的运算符并不复杂，可以用递归下降法逐步生成规则对应的 语法树，每个非叶结点对应一步正则运算，叶结点对应一个可输入符号。 例如：由正则表达式( l e t t e r ，u n d e r l i n e ) ( l e t t e r ，u n d e r l i n e ，d i g i t ) 4 生成的规则语 0 北京化工大学学位论文用纸 法树如图2 1 所示 图2 1正则表达式规则语法树示例 对规则语法树做后序遍历，依次对每个正则运算生成对应的n f a 转换图， 即可以生成整个语法树对应的n f a 转换图。 n f a 转换图是以状态为结点，状态转抉关系为弧的有向图，在每个转换关系 都附着着对应的输入符号或空符号e 。约定转换图有唯一的起点和终点，即转换 图有唯一的起始态和终止态。对几种基本正则运算，分别定义n f a 转换图生成规 则如下： 叶结点a 对应的n f a 转换图： a 川 图2 2 正则表达式规则语法树叶结点对应的n f a 转换图 连接关系a b 对应的n f a 转换图： 叫墨至难j 图2 3 连接关系a b 对应的n f a 转换图 选择关系a ，b 对应的n f a 转换图： 北京化工大学学位论文用纸 转换弧集合为f ，终止状态结点集合为z ，d f a 中的每一个状态结点对应于n f a 中的一个状态结点子集，子集法的算法步骤如下： 算法翰a ；n f a s ? es z ) 算法输出：d f a ( s ：f 1 ，s o ? z ) e l ：韧热争纯s 1 = s e s 0 1 = c l o s u r e s o ) ： e 2 ：遍历s 一中的鼹有状态结点s l j = s t l ? s 晓? j 。? s 稿，对瑷有的输入符sa 计算 t = 一c l o s u r e ( f ( f s l | s 盘。，? s t 0 a ) ) ，若得勤的t 不存在于s 中。鄹将t 掘入翔s 。 中。并在f j 中掘a 鼹( s l ? d 令f ( s l ，t ) = n ； e 3 ：遍历完毕螽k t 中所有含有z 的状态结点即构成z ， 由n f a 生成的d f a 的状态结点还可以进一步约简，通过对状态的等价性分析， 可以将状态数最小化，得到一个规模更小的d f a 。 设得到的d f a 的状态结点集合为k ，转换关系弧集合为f ，终止状态结点集 合为z ，约简算法步骤如下： 算法输入：d f a ( k es z ) 算法输出：约简d f a ( k 1 。es o j z ：) e l ：初始彳艺划分集合p = f z 艮z ： e 2 ：遍历集合p 中的每一个数态子集p i 用每一个输入符号a 对状态集台p l 进行划分 p np 2 j p 3 j ，。p p 其中p 争是f ( p ha ) 的一个子集，且p 包含在p 钓某个子集p k 中t e 3 ：重复e 2 直翻p 不再增长澍p 中的每一个子集p t 。任取p l 中的某个状 态结点予以保留记八k j 鼢赊p ? 中的其他状态结点并将被魏除结点魄相关弧全 部转翻保肇结点上记入f ： 对约