（基础数学专业论文）面向应用的编译原理实验系统的设计与实现.pdf

独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢 的地方外，论文中不包括其他人已经发表或撰写过的研究成果， 也不包含为获得西北师范大学或其他教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：日期 关于论文使用授权的说明 本人完全了解西北师范大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅； 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其 他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名 导师签名：垂! 墨竖： 日期 导师签名：垒! 至篓： 日期 面向应用的编译原理实验系统的设计与实现 摘要： 编译程序是现代计算机系统的基本组成部分，从功能上看，一个编译程序 就是一个语言翻译程序它把一种语言( 称作源语言) 书写的程序翻译成另一 种语言( 称作目标语言) 书写的等价的程序，编译原理是计算机专业的核心课 程，而实验是学好这门课的关键之一。本论文的目标是设计与实现一个面向 应用的编译原理实验系统，并将其应用于编译原理实验课的教学中。文章在 介绍编译程序工作原理的基础上，以符号串为例，详细讨论了词法分析、语 法分析、语义分析、代码优化及目标代码生成的完整过程。 关键字： 编译原理实验系统设计实现 d e s i g na n di m p l e m e n t a t i o no fa p p l i c a t i o n o r i e n t e d e x p e r i m e n ts y s t e mo nc o m p i l ep r i n c i p l e a b s t r a c t ： c o m p i l i n gp r o g r a mi saf u n d a m e n t a lo fc o m p u t e rs y s t e mt o d a y f r o m f u n c t i o na s p e c t ，ac o m p i l e ri sal a n g u a g et r a n s l a t o r ，w h ic ht r a n s l a t e s ap r o g r a mw r i t t e nb yo n el a n g u a g e ( o r i g i n a l l a n g u a g e ) i n t oa ne q u i v a l e n t p r o g 。a mw r i t t e nb ya n o t h e rl a n g u a g e ( o b j e c tl a n g u a g e ) t h ec o u r s eo f c o m p i l ep r i n c i p l ei sac e n t r a lc o m p u t e rc o u r s e ，a n dt h eb e s t w a yo f g r a s p i n gi ti sd o i n g e l li ne x p e r i m e n t s t h i sa r t i c l ei s d e s i g na n d i m p l e m e n t a t i o no f a p p l i c a t i o n o r i e n t e dc o m p i l ep r i n c i p l ee x d e r i m e n t s y s t e m d e s i g n i n gt h i ss y s t e mi st oa p p l yt h ep r i n c i p l et ot h ec o u r s e o fe x p e r i m e n t s ot h et h e s i se x p l a i n sp r i n c i p l eo fc o m p i l e ri nd e t a i l s b yt h es t r i n g ，a n di m p l e m e n t sas e r i e so fw o r ki n c l u d i n g ：l e x i c a l n a l y s i s 8 y n t a xa n a l y s i s ，s e m a n t i ca n a l y s i s ，c o d eo p t i m i z a t i o na n do b j e c tc o d e g e n e r a t i n g k e yw o r d s ： c o m p i l ep r i n c i p l e d e s i g n e x p e r l m e n ts y s t e m i m p l e m e n t a t i o n 4 第一章概述 计算机以其处理数据容量大、速度快、精度高而且有自动判别功能等显著 特点，作为一种工具被广泛应用于各个领域。例如：公交车的打卡机、超市收 银处、银行、医院等这些和我们的生活息息相关的地方。除了硬件基础外，在 其上安装的软件才是最重要的东西，而这些软件又都是通过高级语言来实现的。 高级语言接近人的自然语言，计算机无法直接识别，只有通过编译程序将之转 换为相应的低级语言，计算机才能“读懂”，即编译程序就是将高级语言“翻译” 成低级语言。每种高级语言都有自己特有的编译程序，在编译程序的支持下高 级语言才可能得以实现。所以我设计了这个编译原理实验系统，其中共有2 0 个 实验演示，并将它运用到编译原理实验课中，以帮助学生更好的理解编译原理。 1 1 什么是编译程序 编译程序是现代计算机系统的基本组成部分。从功能上看，一个编译程序 就是一个语言翻译程序，它把一种语言( 称作源语言) 书写的程序翻译成另一种语 言( 称作目标语言) 的等价的程序。 图1 - i 从图卜1 说明了在计算机系统中编译系统的位置，我们首先会在裸机上安装 操作系统，由它来管理计算机系统的硬件和软件，然后安装驱动程序、应用程 序等软件。包括操作系统在内的软件都是靠编译程序来支撑的。 编译程序就是把高级语言的符号程序翻译成计算机可直接接受和运行的二 进制代码程序。如图卜2 所示： 7 图卜2 每种高级语言都有自己的编译程序，例如图1 - 3 ： j a v a 医五习一晰甜e c + + 区蚤 一c 图1 3 语言处理的过程如图卜4 所示： 骨架程序 l语 源曼序 言处理过程 目标汇编程序 可重定位机器代玛 可重定位目标文件库 l 一匝雪 j 绝对机器玛 图l - 4 1 2 编译过程和编译程序的结构 编译逻辑过程可分为两部分：前端是词法分析、语法分析、语义分析；后 端是代码优化和目标代码生成，下面就分别论述各个部分的功能： ( 1 ) 词法分析 编译程序分析工作从词法分析开始，完成词法分析工作的部分称词法分析 程序，又称扫描程序。词法分析程序从左到右逐个字符地扫描源程序正文的字 符，根据词法规则识别开具有独立意义的各个最小语法单位一符号( 或称单 词) ，如标识符、无正负号数与界限符等，并把它们转换成通常是等长的内部形 式( 称属性字) ，以供下一阶段语法分析程序使用。词法分析程序往往还完成那 些在语法分析之前需做的其他工作，如删除注解之类非必要信息、处理编译程 序控制指示、把标识符登录入符号表及加工宏功能等各项预处理工作。某些编 译程序甚至把说明部分的处理也归于词法分析中。 ( 2 ) 语法分析 完成语法分析的部分称语法分析程序，又称识别程序。它读入由词法分析程 序识别出的符号，根据给定的语法规则，识别出各个语法结构。在进行语法分析 时，识别出语法结构的同时也就检查了语法的正确性。如果存在语法错误，给出 相应的出错处理信息。当不存在语法错误时，语法分析程序将从词法分析程序产 生的属性字序列生成另一种内部表示，如语法分析树或其他中间表示。 ( 3 ) 语义分析 语义分析工作由一些语义子程序对语法分析树或其他内部中间表示进行静 态语义检查并生成目标代码。首先检查每个语法结构的静态语义，换言之，验证 语法结构是否合法和有意义。例如，所涉及的变量是否有定义、类型是否正确等。 为此要确定类型、即确定标识符所代表对象的数据类型，进而检查运算分量类型 的一致性与运算的合法性。当某语法结构的语义正确时，语义子程序完成相应的 翻译，即生成正确地实现该结构含义的目标代码。例如对于加法运算，首先检查 两个运算分量是否都有定义，它们的类型是否相等，能否进行加法运算，然后生 成执行加法的目标代码。但为了改进目标代码的质量，在语义分析阶段生成的往 往不是目标代码，而是内部中间表示代码。因此内部中间表示代码是语义分析的 产物，它可以是抽象语法树，但更经常生成的是逆波兰表示、三元式序列与四元 式序列等。概括起来，语义分析完成四项功能，即确定类型、类型检查、识别含 义与相应的语义处理，以及其他一些静态语义检查。 ( 4 ) 代码优化 是指编译时刻为改进目标代码质量而进行的各项工作。优化时对语义子程 序生成的中间表示代码进行分析，把它变换成功能相同，但功效更高的优化了 的中间表示代码。之所以需要进行优化，是因为前面几个阶段处理的是源语言 的共性，按照一般情况来生成中间表示，而源程序中各个语法结构往往可能是 一些特殊情况，包含有个性。要提高功效必须按个性而不是按共性来生成中间 表示代码。例如：假定有赋值语句l e n g t h = 2 * p i * r ：其中p i 由常量定义c o n s t p i = 3 1 4 1 6 ：定义为常量3 1 4 1 6 。优化编译程序对此赋值语句将生成等价于下列 赋值语句的目标语言代码：l e n g t h = 6 2 8 3 2 r ：如果这个语句在1 0 0 次的循环中， 则可以少计算9 9 次的3 1 4 1 6 2 ，使得缩短了程序处理的时间。 ( 5 ) 目标代码生成 9 目标代码可以在语义分析时生成，如果语义分析的结果是中间表示代码，就 必须把中间表示代码变换成等价的目标程序，即目标语言代码。这就是目标代码 生成部分的工作。显然目标代码生成总是与机器相关的，为了设计与实现目标代 码生成程序，必须提供关于目标机器的细节信息。所以，可以用下面的图卜5 说 明编译的构造： 图1 5 1 3 编译技术的发展和应用 1 3 1 编译程序的发展 ( 1 ) 从实现方式看，编译程序早期是手工阶段：采用机器语言、汇编语言、程序 设计语言；然后就有了自动构造工具，如l e x 、y a c e 、g c c 等。 ( 2 ) 语言范型( p a r a d i g m s ) a 命令式( i m p e r a t i v el a n g u a g e ) 程序特点： 语句l ： 语句2 ； 语句3 ； 与万诺曼机的体系结构一般 b 应用式( a p p l i c a t i v e ) 程序特点： l o f u n c t i o n ( f u n e t i o n 2 ( f u n e t i o n l ( d a t a ) ) ) 程序执行： 执行一个个函数施用在数据上的变换最终得到的结果 c 基于规则的( r u l e b a s e d ) 程序特点： 使能条件1 斗动作l 使能条件2 一动作2 使能条件3 斗动作3 d 面向对象的( o b j e c t o r i e n t e d ) 抽象数据类型，继承机制 ( 3 ) 编译程序执行环境 a 批处理：将源程序作为整体处理，排除程序错误不能依靠用户的外部帮助 b 交互环境：增量式编译 c 嵌入系统环境：交叉编译 1 3 2 编译技术的应用 程序分析工具、广泛的语言领域( 数据库系统查询、脚本语言、置标 语言( s g m l h t m l x m l ) ) 。 第二章系统的设计 2 1 设计思路 2 1 1 概述 本系统首先以简单的符号串( 例如算术表达式) 为例演示一遍编译的过程： 经历词法分析、语法分析、语义分析、优化及目标代码生成。将源符号串送入 词法分析程序得到相应的属性字，再将属性字送入语法分析程序得到中间表示， 然后将中间表示传给语义分析程序，最后优化，即而最终得到目标代码。然后， 又详尽的将每一部分所涉及到的内容作了设计。 2 1 2 本系统的实验大纲。本系统精心设计了2 0 个实验项目，见下表2 一l ： 表2 1 1 一个简单的编译器 词法分析2 压缩文法等价变换 3 将n f a 转换为d f a 、确定化、最小化 4 一个简单的词法分析程序 语法分析自顶向下5 消去文法左递归 6 带回溯的自顶向下识别程序 无回溯的自7 递归下降识别程序 顶向下技术8 预测分析程序 自底向上简单优先分析技术9 优先矩阵的构造程序 1 0 优先函数的构造程序 11 完整的简单优先分析程序 算符优先分析技术 12 算符优先关系的构造程序 1 3 完整的算符优先分析程序 l r ( k ) 分析技术1 4 s l r ( 1 ) 分析表的构造 1 5 s l r ( 1 ) 识别程序 语义分析 16 逆波兰式的转换 1 7 l l 分析器 1 8 l r 分析器 代码优化1 9 合并已知量的算法 目标代码2 0 + 元组的代码生成器 1 2 2 1 3 本系统首页 图2 1 2 2 具体实现的过程 2 2 i 一个简单的编译程序 本系统设计了一个简单的编译程序，目地是使读者在整体上有个了解。这 个程序把由加号和减号分隔的数字所构成的表达式转换成后缀表达式。在这个 编译器里，词法分析器首先把输入字符流转换成记号流。然后记号流作为下一 个阶段( 语法制导翻译一由一个语法分析器和一个中间代码生成器组成) 的 输入，产生源程序的中间表示。具体它的代码部分在第三章中。以下给出这个 编译器的描述： 1 表达式由数字、标识符、操作符( + 、一、d i v 、m o d ) 构成。 2 记号i d 用来表示一个由字母开始的非空字母数字序列，h u m 是一个数字序列。 e o f 是文件结束的标记。记号由空格、制表符和换行符分隔。 3 翻译器的代码由7 个模块组成，程序的执行从m a i n 模块开始，该模块调用 i n i t 0 进行初始化，然后调用p a r s e 0 进行翻译。其余的6 个模块如下图所示： 中缀刊后缀翻译器的模块 图2 - 2 4 中缀到后缀翻译器的规格说明如下： s t a r t 一1 i s te o f 1 i s t e x p r ：1 i s t e e x p r e x p r + t e r m e x p r t e r m | t e r m t e r m t e r m 女f a c t o r 1 t e r m f a c t o r t e r md i vf a c t o r lt e r mm o df a c t o r f f a c t o r f a c t o r 一( e x p r ) p r i n t ( f p r i n t ( p r i n t p r i n t p r i n t p r i n t 十) t ) 半) ) ) ) d i v ) ) m o d ) ) i d p r i n t ( i d 1 e x e m e ) h u m p r i n t ( n u m v a l u e ) ) 5 词法分析器模块l e x e r ：其中有一个l e x a n 0 函数，l e x a n ( ) 每次读入一个字 符，并将它发现的记号返回给语法分析器，这些记号有：+ 丰d i vm o d0 i dn u md o n e ( 文件末尾字符) 。空白符已被词法分析器去除。下表给出了每 个源程序语言的词素对应的记号和属性值 表2 - 2 词素记号属性值 空格 数字序列 n u m序列的数值 d i vd i v m o dd 其他字母打头的字母数字的序列 i d 符号表索引 文件结束符 d o n e 任何其他字符该字符 n o n e 词法分析器使用符号表程序l o o k u p 判定一个标识符词素是否曾经出现过。i n s e f t 程序把词素存储到符号表中。每当读到一个换行符，全局变量l i n e n o 加1 6 语法分析器模块p a r s e r ：首先消除左递归。转换后的翻译模式如下： s t a r t l i s te o f 1 4 l i s t e x p r ：l i s t f e x p r + t e r mm o r e t e r m s m o r e t e r m s 一十t e r mf p r i n t ( + ) ) m o r e t e r m s | - t e r m p r i n t ( 。) m o r e t e r m s e t e r m f a c t o rm o r e f a c t o r s m o r e f a c t o r s 一半f a c t o r p r i n t ( 木) m o r e f a c t o r s l f a c t o rf p r i n t ( ) m o r e f a c t o r s d i vf a c t o r ( p r i n t ( d i v ) m o r e f a c t o r s m o df a c t o r p r i n t ( m o d ) m o r e f a c t o r s f a c t o r 一( e x p r ) i d ( p r i n t ( i d 1 e x e m e ) ) n u m p r i n t ( n u m v a l u e ) ) 函数p a r s e ( ) 实现文法的起始符号，在它需要一个新的记号时调用l e x a n 函数。语法分析器使用e m i t 函数产生输出并用e r r o r 函数报告语法错误。 7 输出模块e m i t t e r ：它由单个函数e m i t 组成。它为具有属性值t v a l 的记号t 产生输出。 8 符号表模块s y m b o l 和i n i t ：数组s y m t a b l e 的每一项由一个指向l e x e m e s 数组 的指针和一个表示记号的整数编码组成。i n s e r t ( s ，t ) 操作返回词素s ( 词素 s 构成记号t ) 在s y m t a b l e 中的索引。l o o k u p ( s ) 函数返回词素s 在s y m t a b l e 中项的索引，如果s 不存在，返回0 。i n i t 模块用于为符号表s y m t a b l e 项加 载关键字。所有关键字的词素和记号表示都保存在k e y w o r d s 数组中，k e o r d s 数组于s y m t a b l e 数组有相同的类型。i n i t0 函数顺序扫描k e y w o r d s 数组， 利用i n s e r t 0 操作将关键字插入符号表。下图是符号表和存储字符串的数组： 数蛆跚i t a b l e l e a p t rt o k c n 属性 图2 3 1 5 9 错误处理模块e r r o r ：错误处理模块负责错误的报告，一旦语法错误被发现， 编译器将显示一条消息说明当前输入行出现错误，并停止分析。 2 2 2 词法分析( 1 e x i c a la n a l y s i so rs c a n n i n g ) 词法分析程序在生成属性字序列过程中，需要使用下列表：字符表、特定 符号及其机内表示表、标识符表及无正负号整数表。所以，例如未定义就使用 的错误就是在词法分析中发现的。属性字一般是一个二元组：l 符号类l符号值 符号类一般用数字表示，符号值则是这个符号在对应的符号表中的序号。如下 表所示的编码和符号类对应： 表2 3 符号类编码助记符符号类编码助记符 无定义 o$ u n d ( 1 7 s l p a r 标识符 1$ i d ) 1 8 $ r p a r 整数2$ n u m 1 9 s l s + 3 s p l u s2 0 s r s 4$ m i n u s 2 l s l b 采 5$ s t a r 2 2 s r b |6$ s l a s h2 3s c o l o n =1 2 s g e c h a r2 9$ c l a r 1 3 s a d d r i f3 0 $ i f 1 4$ a d de l s e3 l $ e l s e | i 1 5 $ o r w h i l e3 2 $ 删i l e 1 6 s a s s i g n d o3 3s d o 例如：为程序写出相应的属性字： 1 6 v o i dm a i n ( ) i n tx ，a b ，c ： x = ( a b + c * c ) 8 ： ) 得到的属性字为：( 为方便符号值为它本身) 单词属性字序列单词 v o i d 2 6 v o i d = 1 n i n t x ， a b ， e 1 m a i n 1 7 ，( 1 8 ，) 2 i ，7f 2 7 i n t 1 ，x 2 5 ，7 ， 1 a b 2 5 ， 1 ，c 2 4 ，： x 1 ，x 词法分析控制流程图如图2 - 4 歹 ， ， 粥一 。至呈，二、尸j，r 字 ， ， ， ， 雠 巩rr城强况 髅引 巩rr城强况 舡+c$c)8 f 在词法分析中，文法( 就是某语言的语法规则) 可转变为等价的状态转换 图，再到n 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 ) ，然后确定化为d f a ( 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 ) ，再最小化。其中d f a 上能接收的符号串 集合称为正则集，而程序设计语言的单词都能用正则式来定义。所以，进行词 法分析就是运行d f a ( 即从开始状态出发，有一条路径能到达终止状态，使得所 经历的弧上标的符号和要判断的符号串相等，则说明这个符号串是该文法的句 子) 。例如，下图就是一个文法与之对应的d f a ： 图2 - 5 因此，这部分的实验安排了：n f a 转换为d f a 以及最小化，和一个完整的 词法分析程序，如下图2 6 所示： 图2 - 6 2 2 3 语法分析( s y n t a xa n a l y s i so rp a r s i n g ) 功能：层次分析。依据源程序的语法规则把源程序的单词序列组成语法短语 ( 表示成语法树p a r s et r e eo rd e r i v a t i o nt r e e ) 。即这部分就是判断源程序是 否符合它的语法规则，比如编译一个程序时，如果程序员漏洞了一个( ， 则语法分析部分可以发现并给出提示信息。即这里不带( 的源程序符号串 是不符合源程序的语法规则的。例如：表达式p o s i t i o n ：= i n i t i a l + r a t e 木6 0 ： 规则： ：= “：= ” ：= “+ ” ：= “丰” ：= “( ” “) ” ba 旧引b 叫引 b a i b川引她川岫毡地卜s b d 睢 g ：= ：= ：= 语法树 图2 - 7 本例中的表达式是形如：i d l ：= i d 2 + i d 3 * n 。 它的语法树是右图所示。语法分析有两种技一 术：自顶向下分析技术和自底向上分析技术a h 】1+ 从语法树角度看，自项向下分析过程将以识 别符号为根结点，试图向下构造一个语法树， 1 以 2 其末端结点符号串正好与输入符号串相同； i j、n 而自底向上分析技术将以输入符号串为语法 树的末端结点符号串，试图向着根结点方向图2 - 8 往上构造语法树，使识别符号正是语法树的根结点。本系统对这部分的设计见 下图： 图2 - 9 自顶向下分析技术 分析：在自顶向下分析中采用的推导是最左推导。正因为此，就要求文法不能 有左递归，但往往有些文法有左递归，例如： ：= ( 加法运算符 可简化为：e ：= e 十t ，这样就会发生推导中最 左边会永远推下去而无法结束，如右图所 示。 设计：由于文法带有左递归，最终导致自顶 向下的分析失败，所以要先消去文法的左递 归( 一般采取变左递归为右递归) 。故，在 本系统中设计了消去文法左递归的程序以 及带回溯和不带回溯的自顶向下的语法分 析程序，如下图： l i 蕤滁 ，肇举世经! id l i 毪7 l 罩j ，k 广h e + t 图2 1 0 际5 ：二法分析技术 蹩 ；豢橐斋豢麓鲁薏笔i 譬鬻篓筹辚薏习 图2 一1 1 ( 1 ) 带回溯的自顶向下分析技术 带回溯的自顶向下分析就是从识别符出发，试图得到一个推导序列，使得要判 断的符号串和这次推导出的句子相等，这样就说明要判断的符号串就是该文法 的句子，即它无语法错误。所以，这是一个不断试探的过程，当一个试探失败 了，则回溯到上层进行另一个试探。在算法中，采用语法树作为数据结构，树 中每个结点对应于一个五元组( g o a l ，i ，f a t h e r ，s o n ，b r o t h e r ) ，其中g o a l 是一 个结点所欲达到的目标，即结点的名字，此目标是由父结点f a t h e r 所确定的。 任何一个结点只有一个父结点，但可能有若干个子结点。如果给定了每个结点 的父结点( f a t h e r ) 、它的最右子结点( s o n ) 及最右相邻兄弟( b r o t h e r ) ，就 能确定整个树状家谱及任何一个结点在该树状家谱中的位置。i 指明对应于正在 工作之目标的规则右部中符合在文法中的位置( 序号) 。 为了指明符合在文法规则中的位置，将文法排列在一维数组g r a m m a r 中， ， 其中每个规则u ：= x i y 卜i z 用u x i y | iz i $ 的形式存放。$ 是一个规则再无 选择的标志。例如：对应文法g s ： s ：= a b cb ：= i b i b c ：= d e l f g icd ：= d e ：= e hf ：= d eg ：= t 则g r a m m a r = s a b c | $ b i b l b l $ c d e l f g ic l $ d d l $ e e h $ f d e i $ g t i $ ，s 的位置为1 ，t 的 位置为3 9 。为了实现算法，引进一个栈s ，用来存放五元组结点。 ( 2 ) 不带回溯的自顶向下分析技术 无回溯的自顶向下分析中，要求文法满足两个条件：1 无左递归( 如果存 在左递归，则先消去左递归) 2 无回溯性( 对于任一非终结符号u 的规则右部 x ，l x ：| x 。，相对于x 。，x 2 ，x 。的各自的头终结符号集合总是两两不相交的) 。 本系统在这里有两个分析技术，分别是：递归下降分析技术和预测分析技术。 如图2 1 2 所示： a 递归下降分析技术 它的实现思想是：让一个识别程序由一个子程序组成，每个子程序对应于文法 的一个非终结符号：根据文法的递归定义，这些子程序往往是递归子程序，由 此命名。 b 预测分析技术 比递归下降分析技术更有效的方法。它使用一张分析表和一个栈联合进行控制 来实现递归下降分析技术。见图2 - 1 3 所示预测分析程序的构成。可见预测分析 表是实现预测分析技术的重要工具。其中分析表是一个二维数组a ，第一维对应 于非终结符号，第二维对应于终结符号或输 入结束标志符号# ，其元素a u i t 或者是 一个关于u 的规则，指出当非终结符号u 面 临输入符号t 时应选取的选择，或者是一个 报错标志，表明让u 于t 匹配是错误的。栈 用来存放分析过程中动态产生的文法符号序 列，因而记录了活动经历。这里# 作为输入 符号串的结束标志。 预测分析表的生成 大体上，预测分析表的生成有三个步骤： 为文法符号x 构 造f i r s t ( x 1 为终结符号x 构 造f o l l o w ( x ) 预测分析程序 圈2 1 3 根据构造算法产 生预狈4 分析表 l 、f i r s t ( u ) = t f u 一丰t ，t 蚶，特别地，如果u 一卓，则规定f i r s t ( u ) 简单的说，f i r s t ( u ) 就是求u 能推倒出的首符号集。 2 、f o l l o w ( u ) = t f z 一$ u t ，t ev tu # ) ) ，特别地，如果z 一卓u ，则规定 # f o l l o w ( u ) ，f o l l o w ( u ) 就是求在推导中可能出现在u 后面并紧跟着u 的 符号集。 3 、预测分析表的构造算法 为文法g 构造预测分析表的步骤如下： 步骤1 对文法的每个规则u ：= u ，执行步骤2 和3 ； 步骤2 对每个终结符号a f i r s t ( u ) ，让a u a = u ：= u ： 步骤3 如果f i r s t ( u ) ，则对f o l l o w ( u ) 中的每个终结符号b 或# ，让 h o b = u ：= u 或a u # = u ：= u ： 步骤4 把a 的每个未定义元素置为e r r o r ( 一般用空白表示) 。 a 就是所需的预测分析表。 例如：有文法g e ：e ：= t e 7 e ：= + t e 7 i t ：= f t 7 t ：= f t l f ：= ( e ) li 它的预测分析表如下表2 4 ： 表2 - 4 规嗡入 昶 + 丰 () # e e ：= t e e ：= t e e e7 ：= + t e e7 ：2 e ：= b tt ：= f t t ：= f t t ， t7 ：2 t 。：= f t 7 t ：= t7 ：2 e ff ：= i f ：= ( e ) 4 、生成预测分析表的部分源代码如下( 全部代码在第三章中) ： 注：g z 这个二维数组存放输入文法的所有规则，z f 口口存放所输文法中出 现的所有符号。如上列所示，g z 和z f 就分别为： ete e + te e tft e( t(1 e f( 这里仅给出求所有符号f i r s t 集合的程序： 表明f i r s t ( e ) = ( ，i 1 # i n c l u d e v o i d p u t ( i r a x , c h a rc ) ，将c 放入z f 的x 行 c h a rg z 1 0 b o ，z f 【1 0 】 i o j 全局变量 f o r ( j u ti = l ；i 1 0 j h ) i n t p o s i t i o n ( c h a r c w 求c 是d 中的第几个字符 i f ( ( z x 】【i 】f _ ”) & ( c p z t i x 】 ”m o n t i n u e ； f o r ( i n ti - - o ；i l o ；i + + ) i 球一z f 【f j o ) r e t u m 皤e l s e ；缸f i x j a 】2 = ) 瞎啪； e l s e 珥x 】【i 】2 c ；r e t u m ； v o i dc l e a r ( c b a ra 1 0 i o ) 初始化数组v o i dt o g e t h e r ( i n t j ，i n tx ) i n t i d ； 将j 行的字符放入x 行，且保持无重复 f o “i = = o ；i 1 0 ；i + + )i n t i ，t ； f b r 0 铷j 1 0 0 + + )f o r ( 滓l ；i l o ；i + + ) a i 】啪。；，f o r ( t = 1 ， 1 0 ；什+ ) f f 酝f 【f j “j ：- z 取j 【t j ) b f e a k ； e l s ep u t ( x , z f 【j 】【i 1 ) ； ， v o i df i r s t ( c h a rc , i n tx w 用递归的方法求出 v o i dm a i n o f i r s tf i n ti j ；c l e a t ( z f ) ； i n t i g ；c o u t ”输入文法：” e n d l ； i f ( c z ) r e t u r n ； f o r ( 净0 ；i 1 0 ；i 十+ ) e l s e c i f l ”g z 【i ；i f 【蹄 i 】 0 】= = 、) b r e a k ； f b “i 如：i l o ；卜千)f o r ( i = o ；i 6 ；i 什1 l c o u t g z i ； i f ( c = = g z 【】【0 】) c o u t ”输入这个文法的符号：” z 珏讲0 7 ； p u t ( x , g z i 【4 】) ；f o r ( i = o ；i 1 0 & & z t i i o ! = ；i - h - ) f i r s t ( z t i o ，i ) ； e l s e j = p o s i t i o n ( g z i 4 ) ；f o r ( i = o ；i l o & & z t i 【0 】! - ；i + + ) f t r s t ( g z i l 【4 】j ) f o 哟= 0 0 z o j c o u t z t i i j ”； t o g e t h e r ( j ，蹴 c o u t a a c d ej o a b c d e j a b b c d e 规约时在栈里的句型的前缀规约前可在栈里的规范句型( 不含句柄) 的前缀 a b 2 a a a b 3 a ，a a a a c d 4 a ，a a ，a a c a a c b e 1 a ，a a ，a a c ，a a c b l r 分析的特征： 规范的 。符号栈中的符号是规范句型的前缀，且不含旬柄以后的任何符号( 活前缀) 分析决策依据一一栈顶状态和现行输入符号。 四种技术：l r ( 0 ) 、s l r ( 1 ) 、l r ( 1 ) 、l a l r ( 1 ) a ) l r ( 0 ) 文法：能力最弱，理论上最重要，存在f a 识别活前缀。 ( 1 ) 构造l r ( 0 ) 项目集规范族 l r ( 0 ) 项目集规范族( 构成识别一个文法的活前缀的d f a 的状态的全体) 。 l r ( 0 ) 项目或配置( i t e mo rc