吉林大学《编译原理课程设计》满分实验报告

1、2016级编译原理课程设计总结报告（组）_2019_年_5_月 _25_日性别班级学号所占比例个人成绩男04%男04%男04%任务分工：（请用小四号宋体填写）编译系统的总体分析与设计- 具体功能的设计与实现- 对应的测试与验证过程- 系统界面的设计与美工-成绩评定：词法分析自底向上语 法分析中间代码生 成自顶向下语 法分析语义分析目标代码生 成团队成绩教师签章备注填写说明：1、请将首页红色部分信息填全，其中：班级为 2位数字，保留首位的0;学号 为8位数字，软件学院以54开头；所占比例为百分数，精确到个位数，且所有 人的所占比例之和为100%；不足3人的分组请保留后面的多余空行，请勿修改 该表

2、的结构。2、请根据实际情况填写任务分工部分，主要任务包括：编译系统的总体分析与 设计，4个具体功能的设计与实现，对应的测试与验证过程（报告正文需要列出 若干组具体测试样例与对应结果），系统界面的设计与美工，以及辅助工具、视 图和文件等。3、成绩评定部分由指导教师填写，请勿填写和修改。报告正文（请用小四号宋体填写，自行组织章节和段落）目录第一部分实验成果统计表 1第二部分实验简介 2第三部分词法分析3第四部分语法分析64.1 LL（1）语法分析 74.2 LR语法分析 10第五部分程序测试 22第一部分实验成果统计表 见首页 第二部分实验简介实验目的分组（每组最多3人）完成对SNL语言的以下两个

3、程序：词法分析程序， 语法分析程序（方法不限）。察并锻炼学生的团队协作能力，代码编写能力，加 深同学对编译原理中SNL编译系统的理解，帮助同学理解整个编译原理的机制 实验容本实验中实现了 SNL编译系统中的词法分析、语法分析。其中语法分析包 括LL （1）分析方法和LR分析方法词法分析，以源程序为输入，生成单词的部表示TOKEN序列。语法分析，以TOKEN序列为输入进行语法分析，并生成整个源程序的语法 分析树。在SNL编译程序中，采用了两种语法分析方法实现：LL （1）和LR，前者为自顶向下的，后者为自底向上的。两种语法分析的结果是一样的。 实验步骤编译系统的总体分析（算法分析，数据结构设计，

4、优化）一代码实现，分工进行词法分析，语法分析部分一代码测试一结果反馈,修正一系统界面优化设计f第三部分词法分析源程序一般表现为字符串(机器语言称其为ASCII码)序列的形式，而编译程序的翻译工作应该在单词一级上进行，这与自然语言的翻译理解过程是类似 的。因此要进行编译工作，首先要把源程序的字符序列翻译成单词序列。词法分析是编译过程的第一阶段。它的任务就是对输入的字符串形式的源程序按顺序进行扫描，根据源程序的词法规则识别具有独立意义的单词(符号)，并输出与其等价的TOKEN序列。TOKEN是单词(符号)的部表示。完成词法分 析任务的程序称为词法分析程序，通常也称为词法分析器或扫描器(sea nn

5、e)。TOKEN是单词在编译程序处理过程中的一种部表示，也是词法分析程序对程序 中各类单词进行处理之后的输出形式。对于一种语言而言，如何对它的单词进行分类，每一类单词的TOKEN数据结构的形式如何，都没有固定的模式，可以随 编译程序的不同而不同。通常TOKEN的结构可以分成两部分，单词的语法信息 和语义信息。其中语法信息记录的是这个单词的种类，语义信息则记录着这个单词的具体信息。这样，就能为以后的语法分析和语义分析处理单词做好准备。SNL语法分析对每类单词的分析结果的 TOKEN结构为三元组(词法信息、语义 信息以及该单词在源程序中的行号)。实现词法分析器的注意事项：1保留字和标识符名字的区分

6、2复合单词的处理3. 向前搜索及回退4. 数字的转换5. 输入时边界的处理6. 注释的处理词法分析主要的类有DoToken、Data、Rule、TokenDoToken是最主要的类，它包括identifier标识符列表、INTC常量列表、isIde ntifier()标识符自动机、islNTC()数字常量自动机。Data 类包括 tokenShow 显示 token 用 StringBuffer、tokenShow2 测试 token 用 StringBuffer、token token 列表、separator 分隔符列表等、以及 LL ( 1)分析表， 终极符，非终极符等。Rule表示SN

7、L的语法规则。 doToken ()函数是最主要的函数，它每次调用词法分析方法时要先重新初始化 各列表和缓冲字符串，然后从源程序中一个字符一个字符地进行读取，并逐个分离出单词，然后构造它们的机表示 Toke n。如果该字符不是分隔符则直接追加到 sb中，如果该字符是分隔符，贝U处理分离出的单词。如果是数字常量，贝U对数 字常量进行处理，如果数字常量列表INTC中没有该数字常量则添加。若程序结 束时分离出的单词长度不为零，则处理为相应的Token (尽管词法分析已失败，因为程序未能成功结束)，并重新初始化用以分离单词的缓冲字符串。当整个源 程序都分析完成的时候，将 TOKEN链表中各个TOKEN

8、存入文件Tokenlist.txt 中，将来输出显示 TOKEN时再从Tokenlist.txt中读取。isIdentifier ()函数被doToken ()函数调用，如果分隔出的字符串是标识符则 在token和tokenShow都要追加。isINTC ()函数被doToken ()函数调用，对数字常量列表进行判断，如果数字 常量列表中没有该数字常量则添加。Token()函数中，i表示类型，1为分隔符，2为保留字，3为标识符，4为数字主要函数doToken()的流程图如下:第四部分语法分析语法分析是编译程序的第二阶段，也是编译程序的核心部分。语法分析的任 务是，根据语言的语法规则，对源程序进

9、行语法检查，并识别出相应的语法成分。 按照SNL编译程序的模型，语法分析的输入时从词法分析器输出的源程序的 TOKEN序列形式，然后根据语言的文法规则进行分析处理，语法分析的输出是 无语法错误的语法成分，表示成语法树的形式。语言是具有独立意义的单词根据一定的语法规则组成的句子的集合，句子的结构由语法规则给出，句子的含义由语义规则给出，而对语言的语法分析就是对 语言的句子结构的分析。归于程序设计语言而言，它的句子就是程序，程序设计 语言定义的是符合其语法规则的程序的集合，因此程序设计语言的语法分析的关 键是识别程序(句子)的语法结构。完成语法分析任务的程序成为语法分析程序，也称为语法分析器或简称

10、分析器。编译器的语法分析采用自顶向下的语法分析 LL( 1)和自底向上的语法分析。 LL (1)语法分析LL (1)语法分析方法是一种自顶向下的语法分析方法，它是LL (k)分析方法的特例，其中k表示向前看k个符号的意思。LL (1)分析程序工作过程首先初始化，即把开始符压入栈中，以后的每步分析 必是下面的四种情况之一：(1) 分析栈的栈顶元素是终极符，则看其是否与输入流的头符相匹配，如果匹 配成功，则去掉栈顶元素并读入下一个单词；若匹配不成功，则报错。(2) 栈顶是非终极符，则用栈顶和输入流的当前单词去查当前矩阵，如果查得 的值是产生式编号，则把对应的产生式右部逆序压入栈中；如果查得的值为错

11、误 信息，则报错。(3) 栈已空，输入流不空，这时输入流报错。(4) 若栈已空，输入流也空，则语法分析成功。SNL语法程序的实现采用手工操作构造 LL (1)分析表。LL (1)分析表用一个 二维矩阵表示，其中每个非终极符对应一行，每个终极符对应一列，一个非终极 符和一个终极符可以确定矩阵中的一个元素。SNL的LL (1)语法分析程序共用到四个栈，分别称为：符号栈、语法树栈、操作符栈和操作数栈。LL (1)语法分析的主要函数有：doGrammar()、Grammar。、findRulelndex()、getVariables()、getStartVariable()、computeFirstS

12、ets()、computeFollowSet()、 getRuledByLeftVariable()、getTerminals()、getFirstSets() getFallowSets()等等 doGrammar()函数是最主要的函数。它利用LL ( 1)分析表和符号栈进行语法分析，并处理终极符不匹配和文件提前结束错误。函数处理完成后，得到整个语法树。Grammar。函数主要进行Rule格式转换。XILL I)驱动程序abcxiefgh - “# 输人的Tokenff列XI X2X3特号栈自底向上语法分析LR(0)分析方法实现过程结构如下LR(0) ->LROItem在每个产生式的右

13、部适当位置添加一个点构成项目 ->LR0Item(Rule r)以文法规则初始化构造->getDotPoi nter() 返回点的位置->goTo()判断能否移动->getCurre ntTermi nal()得到点后终极符->LROState/LR(O)状态->closure(Grammar grammar)/求 文法闭包 ->LROParser为LR( 0)分析过程建立相应的表 ->createStates()/创建相关状态形成NFA对Token的操作有如下几种Action->ACCEPT 接受->SHIFT/ 移入->RE

14、DUCE/ 规约LR(1)分析方法实现过程，结构如下LALR(1)->LR1Item/在每个产生式的右部适当位置添加一个点构成项目->LR1Item(Rule r,Lookahead l) ->getDotPoi nter()/ 返回点的位置 ->closure(Grammar grammar)/求 文法闭包 ->LR1Parser为LR(1)分析过程建立相应的表 ->createStatesForLALR1()/创建相关状态形成 NFA ->createGoToTable()/创建 goto 表->createActionTable()/创建

15、action 表LR分析驱动程序第五部分程序测试正确情况：（1）词法分析:(2) LL (1)语法分析:(3) LR(0)语法分析:砧驹二？工归询EXP三蔚境质才丸 二Tfi代帝工几 总勵克裔知阴 肖前就东龙11沾归我Oth” 丁 LTT!勺前杭盒才沁iRF.jq:m 前卅;虽K"1 归LissigniDEn m師肝佥；tx刍帀廿宏比即nHi汁二厂祐 二怖汰击厂汀心的3仏 璋入I吁釣衰砖二注 归的壬FT： lm匸fil.V. 11 l fi* Strtterc m曲轨总摆“归l勺EM_L：t 弓苗卅二才】厂*? endwh 酋前朋工 弓前M辜北昔= FHr2t布"也J “

16、号愉曲奇史fil IhlDZ fiftStaritore 弓前扰毎抵1归釣StNLiot 肖前狀态XjlDW归*5trffcrr=BJ 'A 61 l.I.iJSUtLLSt m丙也茬力K2曲兰£丄呂 刍希圧枣”畀0JI；lilLL-些前沽走Ep旧釣厂岂讪*屯力ID艺旧荚SEk:ft .e nd 归 Fr ctaaS. d-f Q.1旦釣；*"MiX习檢咏蠢为1書送分忻険加1 tcoeFtJdQCpStK归诃g »A 旧悶七二h二二mit： 1 m”，：-亡用伙r益？ 51 aft27 前曲玉尤瞪 iisilAii 二前址丢广2：(4) LALR( 1)语

17、法分析Afi的入fflw 尋疔归惨归(IELALH11) Augr#ri：«dJ GnmiTisrFirrt S«tcFoN&W &KECinanicil CdltionGoToTfltAction Tibh£urt十前菽金商牙 廿前址內严I我 当前狀蕊杓沁 占苛才亡厂于 勻协找茂力鸵肖前状巻力丄二'Urc订冶1 t-=i jl 吉可狀恋刀昭邸g当前;IX帝为 131 CA»igneatRc3t 当前很含打M吒拦弟无HL 当前挨奁約亍！I：坨三任 当削世佥卩览£ &X当叨取茂拘3, fi«5T=More

18、 当前状峦R$】(=f?5Lrtli 当 Wtt疏为3i3tnMoirc 当常I曲対显归妁313(11,= 当前狀总为二三% .24 当前我蛊为1据帕罚LoopStBi 当帕制期色lE«£ai 肖前状霑力工w ©A.勺祈状怎刀金U : phpM * 步祈牯冉戸£1呃妁2曲12上 当前赠的102 13再5BW：沖 当 aittZJil l.l：Str<Li = t 比 fll 狀Sfc崛 1'. = (3拘SwnM: EC m'lXZJbi归坍上3丄尢 耳 WHS为io:灯约m um . t - 甘葡狀亦力也lip：、.LTJ&quo

19、t; 当前我育如旧finaHczc 当前状誉酋汇I匕英2 5丄丄讥 当苛址态为1呃柏约3tnHore 当帕狀态刈显lEft£L18t 甘前状浊力3八皿 肖祈状 .ZJ/ij lJ ' ? ： ;i -urT' I 当前状拖力11 fix, 当丙状鈕A此jrrocran 当苗够再1酋主分析战璃！ iu=ct=Pt!2.错误情况(由于篇幅原因这里仅以删除冒泡排序倒数第二行endwh为例):(1) 词法分析：-L-iJSLxJllSji-jbrM:.H Y-Snnrr*ffgln5liTnujWrniPn.irRunH4".33 swnftM-:t-1：13

20、9;S4fl>arj£3r 'M> iD.ngimi- I卜H nw4f*=rtKH t =sH34 irnc vai=i飙mM1.ttbst=015- lD.aamt!-iit3S d«flafJbr <1( 叭捧1qnwii筠 lD>9ni4=nuoiil:=l*119 saqarXir *Ifitfwti$捕，T甸:-iiegri3-3rE5*M± t/vt.tiionfr&acum3&na«h«a Wmwhiab,1l注爭出IW 1Mtwlt i-nCrijn+1|r9S lDnanie=

21、g.rDadfj3A E4pjrjfior 4-1W轴址林”l：afr«l样 iDH«am#=ien«>wtiW ae-ardsr 4MiniKF IDUMIMalt-sl；3J串出砂.卓 fiile ilnitriT-i i da37.IHIG21uu：3draE«hiii3 Ward.and1*1谣狎沖樹<endTLLl&M曲 (2) LL( 1)语法分析:HlJ ensntl上“；wt=K 枫* rtsetRIt用 flRMi ll：=b*1 entfwtiMtwlt i-nOun+il domadUK T-ien<hMi

22、申 CIjEhik!i-i：|niam>-1 Ida im I如fefflTw&i-氐、艸鼻注惑匕wMb存目,踊8讥AJk Mis，畑虫曲孟j O0J H-i R氛辭中宙杓<Rfflraaa. he. eat耘U (1*咼TWJ站91,零空嚷式0tfsgraaa- mSTnat- 耳好.叭聊、1&iflXHjiXi * 日m 昭生=?=rf. INTE B*MLC= JBS-. 91 bJ ID愛"B论電吐)XiTR>a挣甲匸霽詩帕丁空昭 阳亍刑. 轉* 1闲亍耳冃)、赠诚h ID69»呻生电曲：- 阳“ 31 92±5firfj

23、 IOWfc w-*Mi MKDO0： ITCAuginieriL-ed Gram marFdbw SetsCarKini lbI Col -rctionGo To t ableA£.tjcin lableF rat iris>tar£.-、用狀齐为央EMT 2齐+匸打；昭.£訂饥:.灯氓二 日貳计蛊-苛" 与前1-: 艺前琥熔*Ji- -!-片瓷71 * 日前咲眾勺口 mtf：吒臥対-'了转扣iz阻 帝入加 tXv£%V ftX 捋入R 轄k询伏去対科IfViilH r>! 自薜勒尸 旧约命X 肖曲喩条対51旧妁Fact

24、口 h岂阐总璇旳n Whtmctc 弍带冲恋为笄17«=20m祐址蛊为X舟上 NNM*An "HbEkumB n前*衣対x ir:nt tKI汁左前：i 0-) 肖前然遐为"1 W OirtpirtStta 冷吃£为“ -M-1-717- 號竝菩： M七二-d前叫备勺申, 1策衣奇为-3 的 St.t>A=n<3tvaiiHbie »A：-核 54 话 IISA fltvulttoa 爭匕如&兀話 Jf -?7Cc»XAtr-> -：_雲IK轨送为訂 勻前牝®曲o M片冲芒勺$、 与命扰話为El 胃

25、前笊泰苛"r"："=： 筑苣貞応勺" 削前的壽対站 I貳诂寺为巧(4) LALR( 1)语法分析 LR ParserAu召rnent* GrarnHJirFclliDW SetsCan&raiczi 亡口 IterticinGo Ta TahSe-ActiDniTtiJe-Startw曲:立伫为卄3 N 册 *1- -L Jj*r. :E1UX=LL Mfi：世r+?9 3re；2A1;三禎选迅为走a =ni级乂 “：t:e-iWS.t'.L 9X（, 1常疑为甘TP mst忒总内汕爭去做樂馬虢自均Vaxdt：" 三 F；A.：2 丈：$''：b：=±lj.= n心宀八”"匸i -i.- 为訓垂宵竪«A 兰触:烷左-2 zinot.-=r-c=zcr 芯心注弓幻申粉 曹时咅为讦*?A=1*r3 玉 P1：y=：=h 勻甫赧奈为駅cmw m*城si为：Lt WA）SKViSMiiii iSHoucpQtmn 当fif軼苗为=* R«j5t» 兰触造总対；E tl/ : 冒苗加SUMo ¥Am 力费冷石力几¥A 为苜械誅気皆右帥BTlHore 三魚试奔光去冯：.： = 二U寓訐为：聘拯ID-