（电路与系统专业论文）vhdl编译器设计技术研究.pdf

四川大学硕士学位论文 v h d l 编译器设计技术研究 电路与系统专业 研究生齐星刚指导教师赵刚 随着近年来超大规模集成电路的迅速发展，对设计者提出了更高的挑战。 采用硬件描述语言与高层次综合进行芯片设计已势在必行。高层次综合也叫行 为级综合，其基本任务是完成数字系统行为描述到寄存器传输级( r t l ) 描述 的转换。高层次综合技术可以使得设计者可以在更高的层次进行设计，自顶而 下地跨越各个层次完成整个设计，从而有效地提高数字设计能力，缩短设计周 期。高层次综合工具的研究也倍受关注，最著名的就是s y n o p s y s 公司的行为综 合工具b c 。 本文是关于m e e1 0 7 6 子集的v h d l 语言编译系统的设计与技术研究。 v h d l 编译系统是v h d l 高层次综合系统的前端，它接受v h d l 语言源 描述，并生成一种中间格式以供后面的综合或模拟系统使用。本系统在w i n d o w s 环境下开发，使用p a r s e rg e n e r a t o r2 0 中的a l e x 、a y a c c 以及c 语言来完成 词法分析模块、语法分析模块的自动生成，这样的优点是加快了开发速度，同 时也便于系统的维护和移植。 本文提取了一个用于本编译系统的可综合v h d l 语言子集，吸收了行为 描述中基本和常用的语句结构，而去除了一些鲜能用到的语法，这样缩小了编 译系统的体积和并提高了编译效率。在深入研究词法规则的基础上，本文提出 v h d l 语言词法元素的分类表示方法；同时采用了一系列的预处理和减小单词 型样规模等技术有效地降低了词法分析器的规模，提高了编译速度；在词法分析 器的实现中，完成了对语法结构的翻译，特别地，对表达式的翻译问题和带见 的一些歧义语法进行了深入的研究，并提出了解决方案；使用哈希技术对符号表 进行统一管理，并通过建立一个动态堆栈来维护层次信息；最后，本文通过遍历 。 四川大学顼士学位论文 指令表的方法，将行为信息提取出来，并转换成一种数据控制流图( c d f g ) 作为编译系统的最终输出结果；另外本编泽系统也有较好的出错处理系统。 除了对编译系统本身的介绍外，为了使大家能对编译系统在整个高层次综 合中的地位有一个清晰的了解，我们在第一章中也对高层次综合的整体流程进 行了简单介绍。 本文所实现的v h d l 语言编译系统已通过许多测试实例。对常用的算术逻 辑运算、条件分支和循环语句、进程语句、各种基本结构都很有很好的支持， 又由于本系统的专用性，具有体积小，编译速度快，生成的c d f g 信息具有信 息完整、结构清晰等优点，为后续的综合或模拟系统的开发奠定了良好的基础。 关键词：v h d l 词法分析语法分析c d f g 2 坚型查兰堡主兰竺笙兰 r e s e a r c ho fv h d l c o m p i l e r sd e s i g nt e c h n i q u e s c i r c u i t s & s y s t e m sm a j o r p o s t g r a d u m eq ix i n g g a n gs u p e r v i s o rz h a og a n g w i t ht h ed e v e l o p m e n to fv l s i ( v e r yl a r g es c a l ei n t e g r a t i o n ) ，m o r eb i g c h a l l e n g ei sf a c e df o rd e s i g n e r s i ti sn e c e s s a r yt od e s i g nc h i pw i t hh d l ( h a r d w a r e d e s c r i p t i o nl a n g u a g e ) a n dh l s ( h i g h l e v e ls y n t h e s i s ) w h i c h a l s oi sc a l l e d b e h a v i o r a ls y n t h e s i s t h em a i nt a s k i st r a n s l a t i n gt h eb e h a v i o r a ld e s c r i p t i o no fa d i g i t a ls y s t e mi n t ot h ed e s i g no fr t l ( r e g i s t e rt r a n s f e rl e v e l ) t h eh is s k i l lc a n h e l pd e s i g n e r sb e g i nf r o mh i g h e rl e v e la n dc o m p l e t et h ew h o l ed e s i g nf r o mt o pt o d o w ns p a n n i n gs o m el e v e l s i tw i l le f f e c t i v e l ye n h a n c et h ec a p a b i l i t yo fd i g i t a l c i r c u i td e s i g na n dg r e a t l ys h o r t e nt h ed e s i g nc y c l e t h er e s e a r c hf o rt o o l so fh isi s a l s ob ep a i dm u c ha t t e n t i o nt o , t h em o s tf a m o u st o o lo fb e h a v i o r a ls y n t h e s i si sb c t h i sp a p e ri sa b o u td e s i g na n dr e a e a r c ho ft h ev h d lc o m p i l i n gs y s t e mb a s e d o nt h es u b s e to fi e e e1 0 7 6 t h ev h d l c o m p i l i n gs y s t e mi st h ef r o n t e n do ft h ev h d lh i 曲。l e v e ls y n t h e s i s s y s t e m ，i ta c c e p tv h d l s o u r c ed e s c r i p t i o na n dg e n e r a t eai n t e r f a c ef o r m a tu s e db y t h el a t t e rs y n t h e s i so rs i m u l a t i o ns y s t e m s t h i ss y s t e mi sd e v e l o p e du n d e rw i n d o w s s e n v i r o n m e n t ，a n du s i n gp a r s e rg e n e r a t o r2 0a n dc t oa c c o m p l i s ht h ei m p l e m e n to f l e x i c a la n a l y z e ra n dg r a m m a ra n a l y z e r t h ea d v a n t a n g eo fi ti sa d v a n c i n gt h e d e v e l o p i n gs p e e da n dc o n v e n i e n tt om a i n t e n a n c ea n dt r a n s p l a n to f t h es y s t e m bt h ep a p e r , w ep i c ku pas u b s e to fv h d 乙a b s o r bt h eb a s i ca n dw i d e l yu s e d g r a m m a rs t r u c t w i p eo t h es t r u c tt h a ta l m o s tn o tb eu s e d t h i ss h o r t e nt h es i z eo f c o m p i l i n gs y s t e ma n di m p r o v et h ec o m p i l i n ge f f i c i e n c y b a s e do n t h er e s e a r c ho f 3 四川大学硕士学位论文 v h d ll e x i c a l r u l e s ，w ep r e s e n t t h e w a yo fc l a s s i f y i n gv h d ll e x i c a l e l e m e n t s m e a n w h i l e ，w e ：t a k es u c ht e c h n i q u e sa s r e d u c i n gt h es c a l eo fl e x i c a l e x p r e s s i o na n dp r e p r o c e s s i n g i nt h ee n d ，t h es c a l eo ft e x i c a la n a l y z e rw a sg r e a t l y d e c r e a s e da n dt h ec o m p i l i n gs p e e dw a si m p r o v e d i nt h ei m p l e m e n to fg r a m m a r a n a l y z e r , w ef i n i s ht h et r a n s l a t i n go ft h eg r a m m a rs t r u c t e s p e c i a l l y , w eh a v ead e e p s t u d yo nt h ep r o b l e mo fe x p r e s s i o nt r a n s l a t i n ga n dt h es t r u c tw h i c hh a sd i f f e r e n t m e a n i n g s w ep r s e n tt h ew a yt or e s o l v et h e s ep r o b l e m s w eb s eh a s ht e c h n o l o g yt o m a n a g et h es y m b o ll i s t ，a n dm a n a g et h ei n f o r m a t i o no fl e v e l sb ye s t a b l i s h i n ga d y n a m i cs t a c k a tl a s t ，w ee x t r a c tt h eb e h a v i o r a li n f o r m a t i o nb ys e a r c h i n gt h e s t a t e m e n t - l i s ta n dt r a n s l a t ei ti n t oc d f ga st h el a s t o u t p u t o fc o m p i l i n g s y s t e m b e s i d e st h e s e ，o u rs y s t e ma l s oh a v eg o o d e r r o rm a n a g e m e n t b e s i d e st h i sc o m p i l i n gs y s t e m ，i no r d e rt oh a v er e a d e r sh a v eac l e a rk n o w l e d g e t ot h er o l eo fc o m p i l i n gs y s t e mi nh i g h - l e v e ls y n t h e s i s ，w ea l s om a k eas i m p l e i n t r o d u c et h ef u l lf l o wo fh i g h - l e v e ls y n t h e s i si nc h a p t e ro n e o u rc o m p i l i n gs y s t e mh a v ep a s s e dm a n ye x a m p l e s i th a v et h ep e r f e c ts u p p o r t f o r t h ec o m m o nl o g i ca r i t h m e t i c 、c o n d i t i o nb r a n c ha n dr e p e a t i n gs t a t e m e n t 、 p r o c e s s m e n ts t a t e m e n t 、a n do t h e r b a s i cs t r e e t b e c a u s eo ft h es p e c i a l n e s s ，o u rs y s t e m h a v ea d v a n t a g e ss u c ha ss m a l ls i z e 、r a p i ds p e e do fc o m p i l i n ga n ds oo n t h ec d f g g e n e r a t e dh a v ec o m p l e t e di n f o r m a t i o na n d c l e a rs t n l c t g i v i n gp e r f e c ts u p p o r tf o rt h e l a t t e rd e v e l o p m e n to fs y n t h e s i sa n ds i m u l a t i o ns y s t e m k e y w o r d ：v h d ll e x i c a la n a l y s i sg r a m m a ra n a l y s i s c d f g 4 四川大学硕士学位论文 一_ _ _ _ _ _ _ _ - - 一 第一章引言 1 1v h d l 语言简介 v h d l 是v h s i ch a r d w a r ed e s c r i p t i o nl a n g u a g e ( 超高速集成电路硬件描 述语言) 的缩写，诞生于1 9 8 2 年。1 9 8 7 年底，v h d l 被i e e e ( t h ei n s t i t u t eo f e l e c t r i c a la n de 1 一e c t r o n i c se n g i n e e r s ) 和美国国防部确认为标准硬件描述语言。自 i e e e 公布了v h d l 的标准版本( i e e e 1 0 7 6 ) 以后，各e d a 公司相继推出了 自己的v h d l 设计环境，或宣布自己的设计工具可以和v h d l 接口。此后v h d l 在电子设计领域得到了广泛的接受，并逐步取代了原有的非标准硬件描述语言。 1 9 9 3 年，i e e e 对v h d l 进行了修改，从更高的抽象层次和系统描述能力上扩 展v h d l 的内容，公布了新版本的v h d l ，即i e e e 标准的工业标准硬件描述 语言，又得到了众多e d a 公司的支持，在电子工程领域，已经成为事实上的 通用硬件描述语言。 v h d l 语言是一种功能全面的硬件描述语言，支持数字系统设计的搜计、 验证、综合、测试，以及硬件设计数据的交换、维护和修改，它可以从行为、 功能或结构等不同的层次描述硬件电路。由于v i - i d l 语言可以用前后一致的语 法和语义描述数字系统的多个层次，并且可以在同一设计中混合各种层次的描 述，所以它特别适合于对同一系统的不同层次的设计实现进行模拟验证，以支 持系统的维护和重新设计。在t o p d o w n 设计的全过程中，设计者均可方便地使 用同一种语言。v h d l 设计并不十分关心一个具体逻辑是靠何种方式实现的， 设计人员不需通过门级原理图描述电路，而是针对目标进行功能描述，把开发 者的精力集中到逻辑所实现的功能上，将设计人员的工作重心提高到了系统功 能的实现与调试上，只需花较少的精力用于物理实现。由于摆脱了电路细节的 束缚，设计人员可以专心于设计方案和构思，使得设计工作省时省力，加快了 设计周期。 v h d l 语言的主要特点： 四川大学硕士学位论文 一_ _ _ _ _ _ - _ - - _ _ _ - _ 一 ( 1 ) 与其他的硬件描述语言相比，vh dl 具有更强的行为描述能力。强 大的行为描述能力避开了具体的器件结构，是在逻辑行为上描述和设计大规模 电子系统的重要保证。v h d l 的宽范围描述能力使它成为高层次设计的核心， 从而决定了它成为系统设计领域最佳的硬件描述语言，并可进行系统的早期仿 真以保证设计的正确性。 ( 2 ) v h d l 丰富的仿真语句和库函数，使得在任何大系统的设计早期 就能查验设计系统功能的可行性，随时可对设计进行仿真模拟。 ( 3 ) v h d l 语句的行为描述能力和程序结构，决定了它具有支持大规 模设计的分解和已有设计的复用功能。 ( 4 ) 对于用v h d l 完成的一个确定的设计，可以利用eda 工具进行 逻辑综合和优化，并自动地把v h d l 描述设计转变成门级网表。 ( 5 ) v h d l 对设计的描述具有相对独立性，设计者可以不懂硬件的结 构，也不必管最终设计实现的目标器件是什么，而进行独立的设计。 ( 6 ) v h d l 的设计不依赖于特定的器件，方便了工艺的转换。 ( 7 ) v h d l 是一个标准语言，为众多的eda 厂商支持，移植性好。 v h d l 描述系统时，一般有三种描述层次：行为描述、数据流描述、结 构描述。行为级描述注重描述对象的功能，表示输入与输出之间的转换行为， 不包含结构信息；数据流描述用逻辑方程描述对象的关系；结构描述( 门级描 述) 直接给出实体实现的逻辑网表。 下面我们使用行为级描述来表示一个带有使能控制端的半加器 设计描述：输入输出为1 b i t 使能端e n a b l e 为1 时，r e s u l t 为x + y ，c a r r y 为x + y 的进位； 使能端e n a b l e 为0 时，输出全为0 ； e n a b l x v 图1 1 半加器 r e s u l t c a r r y 一 里型查兰矍圭兰竺笙兰 行为级源描述如下： e n t h yh a l fa d d e ri s p o r t ( x ，y ：i nb i t ； r e s u l t ，c a r r y ：o u tb r r ) ； e n d h a l f _ a d d e r ； a r c h e c t u r eb e ho fh a l fa d d e ri s b e g 呵 p r o c e s s ( e n a b l e ) b e g i n i fe n a b l e = 1 t h e n r e s u l t = xx o r y ； c a r r y - - - - xa n dy ； e l s e r e s u l t = 0 ； c a r r y = 0 ； e n d i f ； e n dp r o c e s s ； e n d b e h ； 图1 2v h d l 描述的总体结构 3 四川大学硕士学位论文 1 2 v h d l 高层次综合 高层次综合的研究工作起始于2 0 世纪6 0 年代，当时i b m 公司的t j w a t s o n 研究中心开发了a l e r t 系统。但早先对高层次综合的研究还主要局限于高校 和公司的研究室中，真正得到发展则是在近1 0 几年，学术界和工业界开发了一 系列行为级综合工具。其中比较有影响的有法国t i m a i n p g 实验室的 a m i c a l 、荷兰埃因霍温工业大学的e s c a p e 等，最为成熟并且首先商业化的是 美国s y n o p s y s 公司的b c ( b e h a v i o rc o m p i l e r ) i s 。 高层次综合的优点在于设计者在更高层次设计电路，而从高层次向低层次 的转换，由综合工具完成。这可以加快设计速度，能够在更短的时间内建模、 验证、综合、模拟，缩短了设计周期，提高了产品在市场上的竞争力。 1 2 1 高层次综合的基本概念 高层次综合是指由e d a 工具经过一系列自动转换，从行为级描述出发， 生成寄存器传输级( r t l ) 描述。其中，行为级描述是设计对象的功能或算法 表示，而寄存器传输级描述则是实现这些功能或算法的某个硬件结构的表示。 图1 3 是高层次综合的基本流程图，由图所示，高层次综合大致上共包括 四个步骤：编译( c o m p i l i n g ) 、调度( s c h e d u l i n g ) 、分配( a l l o c a t i o n ) 、装配 ( b i n d i n g ) 。 4 四川大学硕士学位论文 1 2 2 高层综合举例 图1 3高层次综合流程图 下面我们通过对个算术表达式的综合来介绍整个综合流程。 其v h d l 源代码如图1 2 所示： e n t n y e x pi s p o r t ( a ，b ，c ，d ，e ：i ni n t e g e r ； s t a r t ，s ：i nb r r ； f ：o u ti n t e g e r ； d o n e ：o u tb i t ) ； 5 四川大学硕士学位论文 e n d e x p ； a r c h 髓( u r eb e h a v i o ro f e x pi s b e g 甜 p r o c e s s 、 ，a n lu n n ls t a r t = l ； i f ( s = 0 、t h e n f ( = ( a + b ) + c + d + e ； e l s e f 顺序语句 ，顺序语句 e n dc a s e ； 4 0 l o o p 语句：= w h i l e 表达式l o o p 顺序语句 ，顺序语句) e n d l o o p ； l f o r 标志符i n 范围限制l o o p 顺序语句 ，顺序语句) e n d l o o p ； 4 1 r e t u m 语句：= r e t u m ( 表达式】； 1 6 四川大学硕士学位论文 4 2 接口表：= 接口元素 ；接口元素 4 3 接口元素：= c o n s t a n t 接口元素说明 l s i g n a l 接1 3 元素说明 v a r i a b l e 接口元素说明 4 4 c o n s t a n t 接口元素说明：= c o n s t a n t 标志符表： i n 】标志符【：= 表 达式1 4 5 s i g n a l 接口元素说明：= s i g n a l 标志符表：【模式】标志符 b u s 】 ：= 表达式1 4 6 v a r i a b l e 接口元素说明：= v a r i a b l e 标志符表：【模式】标志符 = 表达式1 4 7 表达式：= 关系 a n d 关系， l 关系 o r 关系 l 关系 x o r 关系) l 关系 n a n d 关系 l 关系 n o r 关系 4 8 关系：= 简单表达式【关系操作符简单表达式 4 9 关系操作符：= = i = i i k v a l ) ； 第二种：根据下面所讲的l e x 规则： l e x 的源程序中可能有多于一条的规则与同一个字符串匹配，在这种情况 下，l e x 有两个处理原则： 能匹配最多字符的规则优先。 能匹配相同数目的字符的规则中，先给出的规则优先。 既然如此，我们就可以将匹配保留字的规则写在前面，而匹配标志符的正 则表达式写在后面。这时遇到保留字输入时则直接匹配，遇到标志符时则与标 志符的正则表达式匹配。 下面给出简单示例： a a b b s s 【n n a a n n d d 】 【s s e e l l i e e l c c t t 】 【a - z a _ z _ a z a z 0 - 9 】4 r e t u m ( v _ a b s ) ； r e t u m ( v _ n a n d ) ； r e t u m ( v s e l e c t ) ；) 四川大学硕士学位论文 y y l v a l y _ s y m = s y m l o o k ( y y t e x t ) ； r e t u r n ( i d e n t i f i e r ) ； ) 两种方法比较： 使用上面两种方法都可以实现对标志符和保留字的词法分析，他们的最大 区别在于规则的数目，第一种方法使用查找保留字的方法，识别规则较少，而 第二种方法利用匹配的优先顺序进行识别，故规则就增加了9 7 条。 l e x 是将正规表达式转化为确定有限状态机d f a ，为了节省空间，自动机 是解释的而不是编译的，但它仍然是个快速分析器。特别地，识别与划分一 个输入流所用的时间是与输入的长度成正e e 的。规则的多少对速度的影响并不 是非常重要。但是，有限自动机的规模以及l e x 生成的程序，则随着规则数目 的增多而增多。 故由上看出，第二种方法使的词法分析器的规模要比第一种大很多。所以 我们这里选用第一种方法来对标志符和保留字进行处理。 3 4 预处理和辅助定义 预处理 就是在进行词法分析、语法分析等等动作前，先对v h d l 源描述文件进行 一次扫描，输出一个经过重写的新描述文件，这个文件作为后面分析的输入， 它是与源文件完全等价的。 它主要完成的任务有下面几个： ( 1 ) 滤除以“”开头的注释语句： f 2 1 因为v h d l 不区分大小写，所以这里要先统一转换为小写( 或大写) 字母； ( 3 ) 字面量中的下划线在程序中可以出现，但实际上是无意义的，所以在 这里要先把它去掉。 四川大学硕士学位论文 ( 4 ) 将多余的空格或制表符合并成为一个空格 $ 辅助定义 在l e x 源程序中，可以用一个名字代替一个复杂的正则表达式，即辅助定 义。辅助定义必须在第一个之前给出，并且必须从第一列开始写。在引用 辅助定义时，需要把它写在 ) 里边。我们根据v h d l 语言的语法，进行了一些 辅助定义，在书写规则时用这些名字来替代这样会使规则的结构清晰、阅读性 增强。这些辅助定义必须要写在第一个之前。 l e t t e r 【a - z a - z 】 d i g i t 0 - 9 】 u n d e r l i n e ”一” d i 百t s 0 9 4 e x p o n e n t e e 】 + 一 ? d i g i t s e x t e n d e d _ d i g i t d i g i i l l e t t e r s i g n【+ 一】 b a s e _ s p e c i f i e rb i o i x i n t e g e r d i g i t u n d e r l i n e d i g i t 4 e x p o n e n t ? 3 5 词法分析与语法分析的接口 由于我们使用y a c c 和l e x 联合编译的方式来生成v h d l 语言的编译系 统，所以有些功能需要在y a c c 中定义。l e x 源程序经过编译后会生成词法分 析程序的代码l e x e r c ，我们需要在y a c c 程序的开头部分使用# i n c l u d e 语句导 入该文件。 词法分析识别出一个单词时，在完成 中相对应的动作后，就会向后面的 语法分析程序返回一个单词属性值( r e r u m 单词类属) ，同时它也会通过对变 量y y l v a l 进行赋值来返回相应的单词值给语法分析程序，单词值将压入系统内 部所维护的数值堆栈，当语法或语义分析程序要使用某项单词值时，y a c c 使 用$ i ( i 为正整数) 的方式取得所需要的值。这部分要结合y a c c 源程序的定 义部分来完成。 四川i 大学硕士学位论文 如下面格式 u n i o n i n t m ： c h a r n ； s t r u c t s y m t a b l ； 向语法分析器传递单词值时，就要使用例如 y y l v a l m = x x ；y y l v a l n = x x ；y y l v a l s y m t a b = x x 的方式。 3 6 、l e x 的多文件输入和输出 默认情况下，在k x 生成的词法分析程序中，输入是s t d i n ，输出为s t d o u t 。 如下所示： f i l e + y y i n = s t d d i n + y y o u t = s t d o u t 因为我们现在要从v h d l 源描述文件读入，结果也要输出到一个新的文 件，所以这里我们需要把这两个变量重新赋值。 为了方便进行程序设计。编译系统接受多文件输入。这需要通过重写l e x 中自带的y y w r a p o i 函数来实现。这里不再赘述。 四川大学硕士学位论文 第四章语法分析模块 语法分析是v h d l 编译系统的核心部分。它接受前面词法分析得到的单词 ( 语法属性流) ，依据语言的语法产生式，完成对v h d l 语言的语法检查，因 为采用一次编译的方法，所以，在检查语法没有错误后，需要时我们还要进行 相应的语义处理。我们使用p a r s e rg e n e r a t o r 中的a y a c c 来实现语法分析器的 设计。 下面的图4 1 是v h d l 语法分析器生成的流程图 y a c c 源程序 i c 挖码语法分析器 l l俑译 i i i 可执行的语法分析器 图41 v h d l 语言语法分析器的实现流程图 4 1y a c c 简介 y a c c 是y e ta n o t h e rc o m p i l e rc o m p i l e r 的缩写，y a c c 可以处理能用l a l r ( 1 ) 文法表示的上下文无关语言【”1 。在y a c c 源程序中，用户用一种类b n f 的语言 描述要处理的语言的语法，y a c c 会自动地把用户的源程序转换成一个c 语言源 文件，在该源文件中，有一个函数y y p a r s e ，它是一个l r 方法进行语法分析的 语 四川大学硕士学位论文 法分析程序除了对输入进行语法分析之外。它还可以在某条规则得到匹配时 完成指定的动作( 执行一段程序) 。 一个y a c c 源程序一般包括三部分：说明部分；语法规则部分：程序段部分， 它们之间用分隔： f 说明部分) 语法规则部分 程序段部分) 在上述三部分中，说明部分和程序段部分在不必要时都可以省去，当没有 程序段部分时，第一个是必须有的。 其中说明部分包括c 语言程序说明和文法规则的说明等等，一般包括下面 几类信息： ( 1 ) 变量定义，内容为有关文件的引用说明和全局变量表的说明； ( 2 ) 语法分析器命名部分，使用n a m e 的形式为语法分析器定义一个名 字 ( 3 ) 起始符号定义，文法开始符号由说明符号s t a r t 引出，若起始定义缺 省，则系统采取第一条语法规则的左部符号作为起始符号； ( 4 ) 词汇表定义，在这部分用户可定义终结符号表、联合( u n i o n ) 和 类型( t y p e ) 说明； ( 5 ) 优先级和结合性定义。 y a c c 生成的语法分析程序用的是l r 分析方法，它在做语法分析时除了有 一个状态栈之外，还有一个语义值栈，存放它所分析到的非终结符和终结符的 语义值，这些值有些是从词法分析程序传回来的，有些是在语义动作中赋予的。 要存取语法符号的语义值，用户要在语义动作中使用以$ 开始的伪变量，这些伪 变量是在y s c t 内部提供的，用户不用定义。伪变量$ $ 代表产生式左边的非终结 符的语义值，产生式右边的各个语法符号的语义值按从左到右的次序依次为$ 1 ， $ 2 ，。 y a c c 产生的分析程序是由一个有限状态机和一个栈所组成，它还能读入和 四川大学硕士学位论文 记住下一个输入单词( 也称作先行单词) 。当前状态总是栈顶元素，确定状态机 的状态是些小整数标号。初始状态机处在零状态，栈也仅包含零状态，没有读 入先行单词。 有限状态机有4 种可用的动作，分别称为移进、归约、接收和出错。语法 法分析程序的进一步动作进行如下： 1 语法分析程序根据它所处的当前状态，决定是否还需要一个先行单词 才能确定应做什么动作；如果需要一个先行单词且还没获得，就调用y y l e x 来 得到下一个单词。 2 语法法分析程序根据当前状态，有时还得考虑先行单词，选定它下一 步的动作，并执行之；这可有导致一些状态进栈、退栈、处理或者保留先行单 词。 4 种动作的作用分别是 ( 1 ) 移进( s h i f t ) 移位动作是分析程序执行的最通用的动作，它指出在当前状态下后继终结 符是可以接受的。新的状态推入到堆栈中而变成当前状态。 ( 2 ) 接收( a c c e p t ) 接收动作指整个输入已看到，并与规范说明相匹配；这个动作仅在先行单 词为结束符时出现，并指出语法分析程序已成功地完成了它的工作 ( 3 ) 归约( r e d u c e ) 此时，只要是与该产生式右边符号相关的状态，均予以弹出，呈现在栈顶 的状态就成为当前状态，并把代表此产生式的非终结符用在后继终结符之前。 ( 4 ) 出错( e r r o r ) 出错动作表示出现了文法分析程序不再能根据规范说明继续往下进行分析 的情景，分析程序已找到的输入单词，以及先行单词不可能会导致合法的输入 了，语法分析程序报告出错试图恢复局势，_ 并重新开始分析。 归约在处理语义动作中是非常重要的。当一个产生式归约时，与其相应的 语义动作将在堆栈调整之前予以执行。除了保持状态的堆栈外，与其同时使用 的还有另外一个栈( 数值堆栈) ，它用来保存由词法分析器和语义动作返回的值。 当一个移进动作发生时，外部变量y y l v a l 就拷贝到该数值堆栈中。当语义子程 = = = = = ：= = 燮塑型鬯l 序返回时归约就完成了。 4 2 说明部分的内容 y a c c 源程序的说明部分定义语法规则中要用的终结符，语义动作中使用 的数据类型和变量以及语法规则中运算符的优先级等。这些内容的组织方式如 下： 照抄部分 语法开始符定义 语义值类型定义) 终结符定义 运算符优先级和结合性定义 ( 1 ) 照抄部分 y a c c 把照抄部分直接照抄到生成的c 语言源程序中去，所以这一部分要符 合c 语言的语法规定。用户可以在这一部分写要包含的前导文件表、宏定义、 数据类型定义和全局变量定义等。 ( 2 ) 开始符号定义 上下文无关文法的开始符是个特殊的非终结符，所有的推导都从这个非 终结符开始在y a c c 源程序中，语法开始符定义语句是： s t a r t 如果没有说明开始符，y a c c 自动把语法规则部分中第条语法规则左部的 非终结符作为语法开始符。 ( 3 ) 终结符定义和定型 在y a c c 源程序中语法规则部分出现的所有终结符( 文字字符除外) 都必须先 定义，定义办法如下例： t o k e n t i n 眨0 u r v j n o u tv b u f f e r 四川大学硕士学位论文 t o k e n i n t l i t e r a lf l o a t _ p o i n t _ l i t e r a l c i a ri e 鼬蛆， c h a r _ s t r i n g j t e r a l b i t _ s t r i n g _ l i t e r a l t o k e n i d e n t i f i e r 另外也使用这样的形式来定义保留字 t o k e n v _ a b s虼后l s e v _ n a n d vs e l e c t 眨_ c c e s s v _ e l s i f 。 。这一部分在编译时会被转换为宏定义放到中间文件y a c c h 中。 ( 4 ) 非终结符定型 类似于前面对终结符的定义。我们将所有$ i 和$ $ 引用到的非终结符定义数 据类型。这可以使用t y p e 来定义。 t y p e m o d e t y p e t y p e _ m a r ks u b t y p e _ i n d i c a t i o n t y p e p r i m a r y f a c t o rt e r ms i m p l ee x p r e s s i o nr e l a t i o ne x p r e s s i o n c h o i c ein d e xp a r a m ( 5 ) 运算符优先级和结合性的定义 y a c c 允许用户定义运