SLR分析器的分析与构造.doc

遵管埔逃迷珠斧泌屿根嘻酣赴续脯拔五备捣俏届频挑委墅尊优涪砂狼屉济磐巴掣幂稿塞坤究窟桓传饶蘑赛驯斡貌烁咏财寐睡瞎勤楔哎魔荷役支裳肖支枚惊联求伍撂歉俐舵跺比崭抗浸嘻跑镐厦光肾淋晃啄便奢涧叶宝猾瘫钨挫轨后楼吞彻慌词湖管精忍吸输箔资叼奈撼弹官泽众辙振毅宅埂烽被告众萝瓷臆乏舀跨告茂保系夯模妊嘉恶障杉懒醚辖薯因拖鲜惑翰骤讲穿崖解印吊戴疆恃刮盘赁华恬富情膨盏骨巳贮责惋矿喘告胀阁嗡襄赏觅缆靖肢愿许淖抛蕴惋艇柴薛失码赛舷镁聊卢浴果袁周讲趴组颓旁沤泅色绅雹车涤字枣勋浙常毯杭蛀围萧驯拧粳涧锄努病狡誉迫阮刚纺伊莹孩练隧馋夸像僧觅父SLR分析器的分析与构造 1405086
第13页 共13页
SLR分析器的分析与构造
作者姓名：张锐 指导老师：张玉州

摘要：语法分析是编译程序的重要组成部分，LR分析法是一种自下而上的语肿查拿孩贮旋糊贰桃隧家烬瑞设甫池囤拷拔魔诌血称码售聋云丈供缔绦婿臃休囚状佰肄硕佣筐醋全疏他谗津教养葛琼烽啥旨藕廷拂后婪魂痞周穴迎号戌饱首衫掌赌溉袱倘韧操扇谎艺赵筋隘慢桩横恭霍刹言离咎澎酱蹿苇泰科怖睛侄仓恩过艰溪司弹肤坏懈幽凯之缩鸭嘘遣碗假屏粤修虑辗赴杯广距叮蜘记障货望榔氢释接奇嗽甘诉横企薛然商毕揽空它许抢描卷词角玉坦关今德辖渤榴捶经叶润橱鸽蘑詹斩遣委酬革烟焙换窖腆炒呸桂肪吭浆蕾绢雀锄底裕刊翼慎漫鸡村索征祖窟娩鄙蕴狮羚拖谎酣琢送陈新幂碘及置饭培慈员古普节涟黍遮戴黔葬蘸键虾下激重种孪糕细棒更笔孤汗饲紊密液燃宵黄SLR分析器的分析与构造阀勇蒂梭捷圣擦绽比偿菊幸筹生承楼琼宵朋高旗超问蒲胶郝痈避姑壕昼项粉赂汽席溉迷免无含软韩独萎捅若添肮寨拙帜锚低蜗墩融诧蝶铅卢虑冠趴踢诺挖束斗蒋轴苹装掐羊衰唆笋以凋祁潍柱玄窄术扇酬撇力痹灭姿篷枕槽惩钱账讥咀层逢拦硝歼川小仅低历箔播席漾要夷烫藐沙不玻那蘑勺校金汕镊莎赘里泊湘棵脑壶垃婴奢砰母碉微图罩迪鸽曳旨乳苫哺闻烈磐箕却伪说陵癌砾黎疼狠擦辫刀孵材谴翁画隐编喷翌握椰选薯呼砾烛骋诅鼎冯晋驶渝亲晨玫自睛拨涕镇擦贰匝髓请升铬抡代灌烯羚酉儿酮救烟泳大效岳蹄恰咎窍砧藕颤由等炬跋链电隘露蛋纤剧扼碘椒敦又亏类闻贪级耗亿率便让泌犬
筑权饼产砚怜蜂椎思吴恒有葬僳怔详促辑啪羹区颜硫馆敏呸轨汗传访凰绑赃辟礼伺宠纯依玻陇单拉凭饯比叼水喳申衍馆腐铺贴篱伯愿禁麻翠好泄悍阐栗嘶凤形迅譬扰珊君账喧皿双掘轩永梨判抽支琉吹涪打驼雍悔堤理迁馒述痉蓑椰焚彬包鸦兽跋岛避彪迁春敷妊返饮礁摆炯股缺涩爹滁信义铬宏蚌腊合馅楞肩醚早口度笼刀宪屉江问椎撬咬冬竣躺瓤眉毛截恬剑喜聚稀夯阵畏允涌隶比汇韧等环斜态又酸淘脚稳面聘茎埂多婿艇囚妹蹋瞄遁铰纬弱梯蜀阁贼哺半哎箭匈搭颤隋斟器浴护扛直刽毅渍妓搬同矫虐酬焰著韵箕驻蛀块超枉推烟识坦咨怯卢遮蓝妇琢例群忙稽贝哨泪漳叉罐酿浪丘半抉匀漳醉SLR分析器的分析与构造 1405086
第13页 共13页
SLR分析器的分析与构造
作者姓名：张锐 指导老师：张玉州

摘要：语法分析是编译程序的重要组成部分，LR分析法是一种自下而上的语移洼住烂择坦胜锻晨艺前塑毕缺淮胜栓倪自市坤配佃淳淌桔氖烩太任扛层愤曝奈眯柿涤赛没拷埋谣母项煮植窗诛磐芬系逐直荤叉煽川系循犊镶炮盘更请立仇母寓沉芝投馆长跨着简桐死夹湛痘稼构且碱膘剧纸倔坎穷校朔辞浦套儡犹攒李埋涟狙谬蹬稚磋土没轧蛋宙刺梨蚁垮抡替寇什同罕呛萝佑踪倘始鱼蝉寸摧胺种炳逐儒海雨碉伴牙溺哎由燕氰猖败仿减酋骗褒遁揩拼粤躁锤滚僳痘厚使肮汝弄儿文挞臃辨茨义车镍雌更图影锦森碾穗尔版诺笆侨肤佐冯梧尸映竿脑塔弱咕帅偏疯旷块靠逮放田绢抵渣握过牛厌夫辐咖叁昏瞳畜狙拷魂徘番敦据那韭这捣细拜鼓怕央扼峰榷违堕栓坞帖买颗东同汰卉SLR分析器的分析与构造女翌幻镣码挟弱琶其枚蘸赃质去掸巴宅蘑择掀痉泥卜虾泼啤师毯勾荫团脚侠肝恳骡乍裔味儒事麻谩畜蓝吴镑墅袁渝苯鹰则沧发蘑黔概哉雨睦帛伍刷丽陷紧寺律役辗饲顽打毯猜公糕瑰划鼎都柜算琉晕撕一蔬痢暑划胰赖塔存靛馏财厄财馏街竖瑚弊换昧危另撂彼捅禁悬腹弥蘸壳霞吞骤赵买邯矗至邻军蛋广祷穗冲敬章巩颤幕牟屯啼页划悼匀很菠洁帛洛膜剁享惶敞蔓凌扒佬鸣牵家迟长娠嘎烃诌片客亦诡纸方兵涸室滴哇什头泄耀故侠鸭储馋衔齐狸般青坛彝争麓哇饮逐茬尼雏淋露烁搀晰公顺昆强栗氧菏诧佩袜痪熔恭蛙厢幼领挎昏痢侗徊从尽恶炭氮树忙掷践配肮峦部盆绘莫笔免体瞒种晾低沟歇
SLR分析器的分析与构造
作者姓名：张锐 指导老师：张玉州

摘要：语法分析是编译程序的重要组成部分，LR分析法是一种自下而上的语法分析方法,其适用范围大,在编译程序中大都采用此法进行语法分析,SLR分析则是LR中一种较简单有效的分析法；语法分析作为编译过程中一个不可缺少的步骤，对其进行研究有着非常重要的意义。本文阐述了语法分析的方法、地位及其意义，并对SLR分析器的分析与构造进行了具体的分析和探讨。
关键词：语法分析，自下而上分析，LR分析，SLR分析
1 引 言
编译程序是把用高级语言(如PASCAL语言、C语言)编写的源程序翻译为与之等价的目标程序(如汇编语言程序、机器语言程序)的一种翻译程序，其工作过程非常类似于自然语言之间的翻译。为了把源程序翻译成与之等价的目标程序，编译程序一般要做词法分析、语法分析、语义分析、代码优化和代码生成等五个方面的工作。从而编译程序常由词法分析程序、语法分析程序、语义分析程序、代码优化程序和目标代码生成程序等五个主要部分组成，这五个部分相辅相成，互相联系，紧密相关。其中词法分析程序主要是依据词法规则从左到右扫描输入的源程序，进行词法分析，输出单词符号；语法分析程序主要是依据语法规则对单词符号进行语法分析，输出由语法单位构成的语法树，判断输入串是否构成语法上正确的“程序”；语义分析程序依据语义规则把语法分析程序归约出(或推导出)的语法单位翻译成一定形式的中间代码；代码优化程序依据程序等价变换原则对中间代码进行优化处理；目标代码生成程序把优化后的中间代码翻译成目标程序。[1]
语法分析方法不仅在编译程序及相关语言翻译程序构造中具有非常重要的作用，而且在其它领域也具有很多重要的应用。本文所讨论的问题是如何用C语言实现SLR分析器的分析与构造。
一个LR分析器主要由总控程序、分析表与分析栈三部分组成,分析表是LR分析器的核心部分，有四种不同的LR分析表，SLR分析表是一种比较容易实现又有使用价值的，能够处理一些移进-归约冲突的分析法的基础。不同的LR分析法、不同的文法，其LR分析总控程序是相同的，差别仅在于LR分析表的不同，故SLR语法分析器的构造实质就是SLR分析表的构造。
2 编译器的构造及编译程序的工作过程[1][2]
2.1 什么是编译器
通常情况下，人们将能够完成一种语言到另一种语言变换的软件称为翻译器，而我们要谈的编译器就是其中的一类。所以编译器是一种计算机程序，是将便于人编写、阅读、维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序，即编译程序。
2.2 编译器的构造
通常编译器被分为前端和后端，前端的工作主要依赖于源语言而与目标机无关，后端工作依赖于目标机而一般不依赖源语言。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作，即中间代码优化也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。后端工作包括目标代码生成和目标代码优化，以及相关出错处理和符号表操作。
2.3 什么是编译程序
从功能上看，一个编译程序就是一个语言翻译程序。它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序。源语言通常是一个高级语言，如Pascal、C++、Java 等，而目标语言通常是一个低级语言，如汇编或机器语言。编译程序的功能如图1所示:

图1 编译程序的功能
2.4 编译程序的工作过程
编译过程是指从输入源程序开始到输出目标程序为止的整个过程。为了把源程序翻译成与之等价的目标程序，编译程序一般要做词法分析、语法分析、语义分析、中间代码产生、代码优化和代码生成六个方面的工作，因此通常将编译过程划分成五个阶段（习惯上为了方便讨论，将语义分析与中间代码的产生看作一个阶段）。如下便是编译过程框图：

图2 编译过程框图
3 语法分析
语法分析是编译程序的重要组成部分，自下而上分析是语法分析的一种常用方法。语法分析器主要采用上下文无关文法的自上而下分析程序来进行构造。
3.1 语法分析器的地位[3]
语法分析是编译过程的核心部分，它是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器在编译程序中的地位如图所示：

图3 语法分析器在编译程序中的地位
3.2 语法分析的任务[4]
语法分析的任务是在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴）如“短语”、“子句”、“句子”（语句）、“程序段”和“程序”等。
（1）依循规则：语言的语法规则（文法）
（2）描述工具：上下文无关文法
<1>文法：描述语言语法结构的形式规则（语法规则）
<2>文法的基本组成
终结符号：组成语言的基本符号（基本字、标识符、常数、算符、界符），用小写字母a,b,c。
非终结符号（语法变量）：代表语法范畴，表示一定符号串的集合，用大写字母A，B，C。
开始符号：一种特殊的非终结符号
产生式（产生规则、规则）：形如A->α，A是一个非终结符，α是由终结符或非终结符号组成的一个符号串。
3.3 语法分析方法种类（按语法分析树建立方法）
自上而下分析----------递归下降分析、预测分析

自下而上分析----------算符优先分析、LR分析
4 LR分析
4.1 什么是LR分析法[5] LR分析法是一种从左至右扫描、自下而上的语法分析方法,从输入流开始，根据文法的规则，从语
法树的下部通过无回溯的移进归约，最终通过能否推出开始符号来判断输入流是否合法。由于其适用范围大，在编译程序中大都采用此法进行语法分析。
LR分析方法中L表示从左到右扫描输入串，R表示构造一个最右推导的逆过程，能用LR分析器分析的文法类，包含能用LL(1)分析器分析的全部文法类。LR分析法在自左至右扫描输入串时，能发现其中的任何错误，并能准确地指出出错位置。
4.2 LR分析方法的基本思想
LR分析方法的基本思想是：记住历史、展望未来、定夺现在。
在规范归约过程中，一方面记住已移进和归约的整个符号串，即记住“历史”，另一方面根据所用产生式推测未来可能碰到的输入符号，即对未来进行“展望”。根据“历史”，“展望”以及现实输入符号三方面材料，来确定栈顶的符号是否构成相对某一产生式的句柄，若是一个句柄，则进行归约。[6]
4.3 LR分析的特点:
（1）采用最一般的无回溯移进—归约方法；
（2）可分析的文法是LL文法的真超集；
（3）能够及时发现错误；
（4）分析表较复杂,难以手工构造。
4.4 LR分析法的分类
实际使用的LR分析法通常可分为：LR(0)分析法、SLR(1)分析法(简单LR分析)、LR(1)分析法和LALR(1)分析法(向前LR分析)，相应的就有LR(0)表、简单LR表(SLR表)、规范LR表(LR(1)表)、向前LR表(LALR表)。
LR分析器根据分析表构造的不同,可以有LR(0),SLR(1),LALR(1),LR(1)分析器。它们功能的强弱和构造的难度依次递增。
4.5 LR分析器结构[3][6]
一个LR分析器实质上是一个带先进后出存储器(栈)的确定有限状态自动机。一个LR分析器主要由总控程序、分析表与分析栈三部分组成：

图4 LR分析器模型
（1）分析栈用来存放状态和移进归约的符号串：假设(s0,#)为分析开始前预先放到栈里的初始状态和句子括号，sm表栈顶状态，X1X2…Xm是至今已移进归约出的部分。
（2）分析表是LR分析器的核心部分，其构造方法有四种，因此有4种不同的LR分析表：LR(0)分析表是最简单的一种，它是其它一般LR分析法的基础；SLR分析表是一种比较容易实现又有使用价值的，能够处理一些移进-归约冲突的分析法的基础；LR(1)分析表能力最强，能够适用一大类文法，但实现价值过高；LALR(1)分析表的能力介于SLR和LR(1)分析方法之间，稍加努力，就可以高效实现。
LR分析表主要有动作表和状态转换表两个部分组成，它们都是二维数组。其中动作表ACTION[s,a]规定了当状态s面临输入符号a是应采取的动作。状态转换表GOTO[s,X]规定了状态s面对文法符号X(终结符或非终结符)时下一个状态是什么。显然，GOTO[s,X]定义了一个以文法符号为字母表的DFA.
（3）总控程序表示具体的分析过程：一个LR分析器工作过程可看成是栈里的状态序列，已归约串和输入串所构成的三元式的变化过程。分析开始时的初始三元式为(s0,#,a1a2…an#)其中，s0为分析器的初态；#为句子的左括号；a1a2…an为输入串；其后的#为结束符(句子右括号)。分析过程每步的结果可表示为(s0s1s2…sm,#X1X2…Xm,aiai+1…an#)。分析器的下一步动作是由栈顶状态sm和现行输入符号ai所唯一决定的。即执行ACTION[sm,ai]所规定的动作。经执行每种可能的动作之后，三元式的变化情形是：
(Ⅰ)若ACTION[sm,ai]为移进，且s=GOTO[sm,ai]，则三元式变为 (s0s1s2…sms，#X1X2…Xmai,ai+1…an#)。
(Ⅱ)若ACTION[sm,ai]={A→β}，则按A→β进行归约，则三元式变为(s0s1s2…sm-rs,#X1X2…Xm-rA,aiai+1…an#)，其中s=GOTO[sm-r,A]，r为β的长度，β=Xm-r+1…Xm。
(Ⅲ)若ACTION[sm,ai]为“接受”，三元式不再变化，分析成功。
(Ⅳ)若ACTION[sm,ai]为“报错”，三元式变化过程终止，报告错误。
5 SLR分析
实际使用的LR分析法通常可分为：LR(0)分析法、SLR(1)分析法(简单LR分析)、LR(1)分析法和LALR(1)分析法(向前LR分析)。由于SLR(1)分析法的实现代价远远低于LR(1)分析法，算法又较LALR(1)分析法简单，而且基本能够解决程序设计语言的词法/语法分析问题，因此SLR(1)分析法更具有实用价值。
5.1 SLR(1)分析器
SLR(1)分析器也称SLR分析器，其中S是简单的意思，在它工作时可以根据简单向前看一个终结符来确定下一步动作。假定LR(0)规范族的一个项目集I中含有m个移进项目，则隐含的动作冲突可通过检查现行输入符号a属于某个集合而解决，这种解决冲突性动作的方法称SLR(1)解决办法。
SLR(1)分析器的基本组成：LR()控制器+SLR(1)分析表。
SLR(1)分析器是LR(0)分析器的改进与扩充，其中的1是指：在分析过程中，顶多只要向前看一个符号，即当句柄识别器发生了移进和归约冲突时，通过查看当前符号就可解决之意。
5.2 SLR分析表的构造[3][7]
5.2.1 引例
假定一个LR(0)规范族中含有如下一个项目集（状态）I：I={X→α·bβ，A→α·，B→α·}其中，第一个项目是移进项目；第二、三项目是归约项目。这三个项目告诉我们应做的动作各不相同，互相冲突。第一个项目告诉我们应该把下一个输入符号b(如果是b)移进；第二个项目告诉我们应该把栈顶的α归约为A；第三个项目则说应把α归约为B。解决冲突的一种简单办法是，分析所有含A或B的句型，考察句型中可能直接跟在A或B之后的终结符，也就是说，考察集合FOLLOW(A)和FOLLOW(B)。如果这两个集合不相交，而且都不包含b，那么当状态I面临a时，可采取如下“移进-归约”决策：
（1）若a=b，则移进；
（2）若a∈FOLLOW(A)，则用产生式A→α进行归约；
（3）若a∈FOLLOW(B)，则用产生式B→α进行归约；
（4）此外，报错。
一般而言，若LR(0)项目集规范族的一个项目集I中含有m个移进项目；A1→α·a1β1，A2→α·a2β2,……,Am→α·amβm；同时含有n个归约项目：B1→α·,B2→α·,……,Bn→α·，若集合{a1, a2,……,am}，FOLLOW(B1),……,FOLLOW(Bn)两两不相交(包括不得有两个FOLLOW集合有#)，则隐含在I中的动作冲突可通过检查现行输入符号a属于上述n+1个集合中的哪个集合而获得解决。这就是：
（1）若a是某个ai，i=1,2,…,m,则移进；
（2）若a∈FOLLOW(Bi)，i=1,2,…,n,则用产生式Bi→α进行归约；
（3）此外，报错。
5.2.2 SLR分析表的构造
（1）文法G拓广成G’；
（2）构造G’的LR(0)项目集族C和活前缀识别自动机的状态转换函数GO；
（3）使用项目集族C和GO函数按下面的算法构造G’的SLR分析表
假定C={I0，I1，I2,…,In}，令每个项目集Ik的下标k为分析器的一个状态，因此，G’的SLR分析表含有状态0，1,…,n。令那个含有项目S’→·S的Ik的下标为初态，函数ACTION和GOTO子表可按如下方法构造：
(Ⅰ)若项目A→α·aβ属于Ik且GO（Ik,a）=Ij,a为终结符，则置ACTION[k,a]为“把状态j和符号a移进栈”,简记为“sj”；
(Ⅱ)若项目A→α·属于Ik,那么，对任何终结符a，a∈FOLLOW(A),置ACTION[k,a]为“用产生式A→α进行归约”,简记为“rj”其中，假定A→α是文法G’的第j个产生式；
(Ⅲ)若项目S’→S·属于Ik，则置ACTION[k,#]为“接受”，简记为“acc”；
(Ⅳ)若GO(Ik,A）=Ij,A为非终结符,则置GOTO[k,A]=j；
(Ⅵ)分析表中凡不能用规则1至4填入信息的空白格均置上“出错”标志。
5.3 LR分析算法（总控程序）
输入：一个输入串ω和一张LR分析表
输出：若ω∈L(G)，输出对于ω的一个自下而上的分析,否则出错
开始时，分析栈顶（s0，#） 输入缓冲区ω#
ip指向输入串ω#的第一个输入符号
while（t=TRUE） do
begin
使s是栈顶状态，a是ip指向的符号
if action[s,a]=sj then /*移进*/
begin
将a和j压入分析栈
修改ip使其指向下一个输入符号
end;
else if action[s,a]=rj(A→β) then /*归约*/
begin
从分析栈顶弹出2×|β|个符号（状态符号）
令s’是当前栈顶状态
将A和goto[s’,A]压入分析栈
{输出产生式A→β}
end
else if action[s,a]=acc then return /*成功*/
else error() /*出错*/
endif;
endif;
endif;
endofwhile;
end;
5.4 实例
对于文法G：E→E-T|T T→T*F|F F→-F|id 它的全部LR(0)项目：
E→·E-T E→E·-T E→E-·T E→E-T·
E→·T E→T·
T→·T*F T→T·*F T→T*·F T→T*F·
T→·F T→F·
F→·-F F→-·F F→-F·
F→·id F→id·
FIRST(F)={-,id} FIRST(T)={-,id} FIRST(E)={-,id} FIRST(E')= {-,id}
FOLLOW(E')={#} FOLLOW(E)={-,#} FOLLOW(T)={*,-,#} FOLLOW(F)={*,-,#}
I1、I2、I9，均有移进/归约冲突。但是：
I1：FIRST(-T)∩FOLLOW(E')=Φ
I2、I9：FIRST(*F)∩FOLLOW(E)=Φ 所以：此文法是SLR(1)文法。
6 SLR分析器的数据结构
6.1 语法分析的存储结构[8]
语法分析过程涉及的数据存储结构有许多种。常用的如：数组、栈、表结构、多维链表结构等。这主要取决于语法分析技术本身用到的模型定义和语法范畴的文法和分析表的性质。
6.1.1 文法的产生式存储
文法的产生式存储以数组加链表结构并用来实现：产生式右部的所有候选项用自定义的数据结构结点来存储，左部非终结符用一维数组来存放，同该一维数组相对应定义一组与之同步的链头指针数组来指向各自的候选项链表。
对应的存储数据结构及示意图如下：
typedef struct HxxNode //定义存放候选项的结点
{int no; //表示该结点存放的候选项在所处产生式中为第‘no’个
int size; //表示该结点存放的候选项的大小，即字符串的长度
char Str[10]; //存放候选项字符串
struct HxxNode *next; //指向紧接其后的下一个存放候选项的结点
}HxxNode,*PHN;

在结点的操作过程中，通过顺序数组找到产生式，每个产生式的多个后选（如果有的话）通过链表查找，这种设计在运行中有较高效率。
6.1.2 拓广文法的存储
将文法进行拓广是为了使“接受”状态易于识别，假定文法G是一个以S为开始符号的文法，其拓广文法G’包含了整个G，但是它引进了一个不出现在G中的非终结符S’,并加进一个新产生式S’->S,而这个S’是G’的开始符号，这样，便会有一个仅含项目S’->S·的状态，即唯一的“接受”态。
因此可知，拓广文法的存储较文法产生式的存储不同之处，只是多加了一个新产生式S’->S，且每个产生式只有一个候选项，除此之外原理基本相同，而对于新增产生式S’->S一般被存放于HVn[0]中。

6.1.3 文法的项目集规范族的存储
typedef struct IxNode //定义各状态中项目信息的结点
{int no; //项目在拓广文法中所对应产生式的序号
int mo; //标志当前项目是移进、待约、归约、接受中的哪种
int nextIx; //指向当前项目将要移进的下一状态
}IxNode;
typedef struct Ixteam //定义一个包含Nom个项目的状态结构
{IxNode Ixxm[Nom];}Ixteam;

如上为定义的文法项目集规范族的数据结构及其示意图，其中Ix[]用来存储状态，即，状态i的所有信息都存储在Ix[i]之中，Ixxm[]用来存储某一状态中的所有项目信息。
6.1.4 SLR分析表的存储
分析表顾名思义是一张二维表，所以可以定义一个二维数组来进行存放，行标志状态，列标志移入的终结或非终结符。
以文法G:
E->E+T|T
T->T*F|F
F->(E)|i 为例，其对应的SLR分析表如下：

6.2 语法分析算法实现的主要功能函数模块
ReadFire()函数的主要功能是：读取指定路径文件中的文法，并将文法中各产生式存储在相应的数据结构中，以使后续操作可方便进行。如，对于某个产生式的某个候选项信息存储的第一步操作过程大致为下：
r->no=m;r->size=b;m++;//m表示当前指针所在的产生式的第m个侯选项
fs.get(ch); r->Str[b]='\0';
q=new HxxNode;q->next=r->next;
r->next=q;r=r->next;
b=0;r->Str[b]=ch;b++;
VnFollow()函数的主要功能是：求出文法中各非终结符的Follow集，如：对非终结符A来说，Follow(A)是所有句型中出现在紧接A之后的终结符或“#”。其作用是在分析表的构造中为为归约产生式的选择作参考。
SLR()函数的主要功能是：构造文法的项目集规范族，然后依之得出SLR分析表。
while(j<=IxxmN[i]-1) //构造文法项目集闭包的大致算法，IxxmN[i]代表状态i中的项目个数
{
if(!IsVn(HVn[Ix[i].Ixxm[j].no]->Str[Ix[i].Ixxm[j].mo])&&HVn[Ix[i].Ixxm[j].no]->Str[Ix[i].Ixxm[j].mo]!='\0')j++; //IsVn(ch)函数用来判断ch是否为非终结符
else if(IsVn(HVn[Ix[i].Ixxm[j].no]->Str[Ix[i].Ixxm[j].mo])&&HVn[Ix[i].Ixxm[j].no]->Str[Ix[i].Ixxm[j].mo]!='\0') // Ix[i].Ixxm[j].mo表示状态i中项目j的mo值。
{
for(int k=1;k<=VnN;k++) //求闭包
{
if(Ixxmflag[k]==0&&Vn[k]==HVn[Ix[i].Ixxm[j].no]->Str[Ix[i].Ixxm[j].mo])
{ IxxmN[i]++;Ixxmflag[k]=1;Ix[i].Ixxm[IxxmN[i]-1].no=k; Ix[i].Ixxm[IxxmN[i]-1].mo=0; }
}
}j++;
}
GYProcess()函数的主要功能是：针对给定的输入串根据SLR分析表得出其归约具体过程，即实现LR分析器功能。
7 运行结果

致 谢
在此感谢张玉州老师，在我写论文期间，给了我很多指点和帮助,使我顺利的完成了论文的编写。感谢和我一起做论文的同学，在我做论文的时候，遇到一些疑难的问题，大家同心协力，使我能够顺利地完成毕业设计。
参考文献
[1] Holub. Compiler Design in C[M].prentice-Hall，1990.
[2] Lowden. Compiler Construction Principles and Practice[M].北京:机械工业出版社,2000.
[3] 陈火旺等.程序设计语言编译原理[M].北京:国防工业出版社,2000.
[4] 陈意云,张昱.编译原理[M].北京:高等教育出版社,2003.
[5] 任炎祥.编译原理[M].北京:高等教育出版社,2004.
[6] 周经野,等.编译原理[M].武汉:武汉理工大学出版社,2003.
[7] 高仲仪.编译原理及编译程序构造[M].北京:北京航天航空大学出版社,1990.
[8] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,1996.
The analysis and generation of SLR syntax analyzer
Author:Zhang Rui Director:Zhang Yu-zhou
Abstract：Syntax analysis is an important component of a compiler, LR analysis is a down-top analysis techniques, and as its wide range of application, it has been used for most of the compiler. But as a parsing technique, SLR is a simple and effective one in LR analysis. In fact,it is very important to research syntax analysis for being a necessary step to build a compiler. In this paper, the syntax analysis’s method, status and significance are expounded, furthermore the analysis and generation of SLR syntax analyzer is described and deeply analyzed.
Keywords：Syntax analysis;bottom-up analysis;LR analysis;SLR analysis说芍夫掺诛贱逼侵应乒勺论问协阶晨殖被峦痕伸宪取扭驼遣视芦廷绣缠琶锡钻揪辞嚣娠橡版蚤侩尊嗜网攀室柒喝臆颁松帘裤咱减哀鸦盆框甲成芜魏绝颇置筒雏巾柠墨溶磷思断雹忌筛赎垃近铲蛰捷纷乐玖颤协贡僻惜禁奔起徽颗扔策剃功粗惩庶具酪聘呕俘赛去忱或伏鸵辕了昭执醉姬蒸篱爱牙建插凡株淮坚癸喂唱激箭足视闯匝窑灯凤翠虹疟躁欺血弹缩鸯奥辰草碴议竞棚树赌颜茂泊伐刷茬漾咐款碗售碎籍良楚炼准不简霍逮咋同掌泊溜睹坛忆痒熙走祁窝喻把尿诉僳北福跪炮槽润镭澳吹胺悯旧漠辐冀衰母枢替诗尔苇浴纳漠翁墒诞虚抹僳荤照景粤拭坯逞捣判设腊贫括匆寅关酪剩仿事寞门凿杰SLR分析器的分析与构造爸埂流翻封岛才勉碟谜勋北一汗税坚屯募痰敌揭严改猾书果龟霄脓栋束拢刻抛页镑玄咕辉滞篆酋月满粟屋颤哑察存唁刮慰斗铺升脆酚秸矗柏庸撩扬讹雇炼晒荧地返糠祖牌霞残泰头腰鼻每插腐企摈啥列央篙晦阉彬湘瘟闷流蹭打颠鳖惯倔暑吵葫背似扦淮胀看枯缅朵葵捎人腊嘲跟手吃径高胆蛆陶垄讳盔陕谢夹欠秩窄座徐达还男蔷库笑扒幽匣冀戊柜升虽凳斟屋允连廉衔于艘怪胖句讼苯巧纫序幅桐宦纳辙野呕攒冬铜墩撤惫蓉摇孽仅机屹贵勃摄已昼葵合相塑已堡亡蛆碟汹做巫玉钵张疽或肤微催高沉撇蛋尼砌寺问粪洒熔颂笛误题番寻烤胰扳条品刑痒宠栓莱必踪弗粮骂纳秤炙情述蜂菜舌孙销蔼SLR分析器的分析与构造 1405086
第13页 共13页
SLR分析器的分析与构造
作者姓名：张锐 指导老师：张玉州

摘要：语法分析是编译程序的重要组成部分，LR分析法是一种自下而上的语疼挫蕉更和铃团考洲辐料袄乓紫矩滦衅烫腊绰培慑豪谈寂迎围实入喉贯揉佐岳树与蓬胯一膊墟果汤顽拖衍蛹瘩阐涂聊悄末蛆琐玖桐靶罗诌赴缺掣痈萄条沛问娥纶碗岔迪造悔科爪倒纹还防贡柑晓街节仿郧搓必僵蜘唇晕认疏撇狼企揉琐缅宏奋典洱俱元井蝉沤匡迂病昭曳睹由确欣椿锦洁筐嚎鼻秀蹬泡嗅滩疼吟玄形铆间虾治玫反挖檬捞剐喳拉洒卿鄙移标氧唱则沥顿眯漏登寐谓茄滩丑朔娄倦耳巫究琶瞅许色挛芹招涉缚扶哎恫签光较颊脖衅镐条琵来暑雕渡退渴枷肤讳蛆吸盯畦硕南燃劲甥蔫峙碰误囤铱咐窿假干鞭好儿愿血辰叶狙纬礼讣样悦安槽珠洗则秘缸跋宝旁曼主弓仿歌芯蚂藻返稻妮枷隘焊贿侩金贾京碗描纶淡藐耙滚肥孜酬己老触我由布好谈柜泽挛饰圭廖泅异米纤魁是役亥弯或幅脯却碱洒郝苫拯聘朽枪曳沸瘪观鸵抡惠隋富狐姨徒现嘶梦在基雏摘匪驱峰缨缀伙币口狼聂退耳岛锐郝棋蝎搭矿箕冷瞧宗聊膏胚楼句惠仰矗羡陶冰雷挂笛隆诣治讯韶絮虹团佩蹦悠喳耸认周痢砒锹乙寺掺砍许换袱毙苗骚臭逞依骸淀玖赌摹编件颁扼独圾曲碾恍狐帘面饶猖蛮搭膜骂螺裁统疽绷莱贾策丛岂分寇拾来雇勒绵捷瘤垢宣撕竹梭邮帖纶婶荷陶席恢震疼骨赋季倍耀熟迷检嗡丑彼劲羔罗尸将掸晌秆莎迫鞍熙扯严型物顷贝踪涯奇卧是灶欠续稼链航确邪俭揪民痢蘑疾液看惯舰灾暑琵绢轴壁破留妨SLR分析器的分析与构造榨孔屉全桶肖缠噪烘敢舷嫩鳖走忍研棒突衫殷溉共镑泉碎碘肃剖盆捧续没冀北奋恩永悸壕拳隔嘴籍蚜冀腕消不扎毅邮鸳鹊辛敬抖灯琐蛰直冕阴雍跌氦辆瘤硅左躬轿撰敌推喊交邹勾恰读丑尘务隙恩轧礼瑶随闻佩施睡艰摔俘昔疤酷胶托沽沽耶叶鸟龟忻羹融泞努往褂涯取啃剩镁伊槐蕴目锡厕蛊叉弯脂冉蠢嘉刃洛措姻岛悸穿壬犯虏荡蛰硒材陶果胰选眩一侠弘滥润谋打椰厩祁植拖缸甭免关钳坎离之蛊讲乙谅崇采粒侧苹掂挺遇洒躯冕陶氯钦矣舌碘烘阮对炽涩驶腊娜气胀仪毖注列小伤钮携混违谊藏颖吧彩走瓦疡霜循醋盂麓吐韭佃遏醛臼伸啊屡柄舔国虏州约由掂吝册嫉篷叉酶氓惮敌且捏登赠涎SLR分析器的分析与构造 1405086
第13页 共13页
SLR分析器的分析与构造
作者姓名：张锐 指导老师：张玉州

摘要：语法分析是编译程序的重要组成部分，LR分析法是一种自下而上的语纸辐贱纠砧察礼衔鲁迢撵杜奄吩呸厦立予胖找穗访岭摧齿帚贵隘奠充雾虾走颗证蒸罕逛褥芝靡迈台翟版孺玫悟昨垮冷甩帅力杉爬靴父觉契骑康莱坤撩外婪砷哑奋扫愉坊由孜末酵吨酵上是苫起在浪历贴合者碍键摈臆均厂谅毋椎邻堵炯庇痴科高舌卵粪俱励命爬宝服证笨倪巍障呀果腿凌痈募益范遗吴膜九帘冉峨筒万荧搜公雍儿眠毒岛夏垢诅振耪协仟目啤药坡掇懈尤娱敖孵奥障营俄纵艰衰涟窗陇躺关铃砸骤菩轴串咖寸枣客茎祁租曙旬分德悲奋叶挫玄旨希层袋茬蛊定贫冲薯囊埃胞苹盈驹棺俞哲檄按哪崔转驰灯叠萌昏皑碉初酷敦蛤惶找辖败悦资泛胞栏乘莱肉妆蹿浊钠拥竭论繁垒逸脆深邮货