编译原理实验报告-语法分析

1、编译原理课程实验报告实验2:语法分析姓名院系软件学院学号任课教师指导教师实验地点软件学院三楼机房实验时间2016/10/30/星期日实验课表现出勤、表现得分实验报告 得分实验总分操作结果得分一、需求分析得分要求：采用至少一种句法分析技术(LL(1)、SLR(1)、LR(1)或LALR(1)对类高级语言中的基本语句进行句法分析。阐述句法分析系统所要完成的功能。本语法分析器是在词法分析器的基础上实现对类高级语言中的基本语句进行句法分析，基本功能如下：(1)能识别以下几类语句：?声明语句(包括变量声明、数组声明、记录声明和过程声明)?表达式及赋值语句(包括数组元素的引用和赋值)?分支语句：if_th

2、en_else?循环语句：do_while? 过程调用语句(2)本语法分析器采用自顶向下的分析技术，能根据导入的文法，自动计算 first集和follow集，能够生成每个产生式的select,并自动生成预测分析表。(3)本语法分析器具备语法错误处理能力，可以进行错误检测，如果检测到在出错时，采用恐慌模式，能够给出错误提示信息，格式：错误项错误原因行号a)忽略输入中的一些符号，直到输入中出现选定的同步词法单元集合中的某个词法单元，同步集合的选取是非终结符的follow集；b)如果终结符在栈顶而不能匹配，弹出此终结符。c)输入栈中缺少某些应有的符号，比如只有右括号没有左括号等，会给出相应的提示。(

3、4)系统的输入形式多样：可以通过文件导入文法和测试用例，可以通过用户界面显示并编辑测试用例。测试用例涵盖了第(1)条中列出的各种类型的语句，并设置了一些语法错误。(5)系统的输出分为两部分：一部分是打印输出语法分析器的FIRST集、FOLLOW集、select集和LL(1)分析表。另一部分是打印输出语法分析结果。（6）本系统还实现了输出语法分析树的功能，让语法分析的过程更清晰。二、文法设计得分要求：给出如下语言成分的文法描述。?声明语句（包括变量声明、数组声明、记录声明和过程声明 ）?表达式及赋值语句（包括数组元素的引用和赋值）?分支语句：if_then_else?循环语句：do_while?

4、 过程调用语句本语法分析器主要针对C语言进行文法设计，下面给出各语言成分的文法描述。程序入口：Program->PP->D P 支持连续声明P ->S PP-> £1）声明语句：D proc id ; D S| T id;支持过程声明和变量声明T 一 X C | record D支持结构体声明X 一 short|int | long|float|double|char|string支持多种基本类型的声明C 一 numC | £支持数组的声明2）表达式及赋值语句：S id = E ;| L = E ;E E + E | E * E | E | （E）

5、| id | digit | LL idE | LE支持数组元素的引用和赋值3）控制流语句：S if B then S1 else S2 | while B do S1B 一 B | B/或语句| B && B且语句| !B非语句| (B)使用括号| E relop E关系语句| true/bool 型| false/bool 型relop 一 < | <= | = | != | > | >=关系符号4)过程调用语句S call id (Elist)ElistElist, EElistE下面给出整个程序的无二义性，无左递归的LL (1)文法：Progra

6、m->PP->D P|S P|emptyD->proc T id ( M ) P |T id A ;|record id P M->X id M'M'->, X id M'|emptyA->= F|empty|, id AF->digit|id|char| G |stringG->H G'G'->, H G'|emptyH->digit|charT->X CX->short|int|long|float|double|char|void|string|booleanC->

7、; digit C|emptyS->L = E ;|if B then S else S|while B do S|call id ( Elist ) ;|return E ;E->- E E'|( E ) E'|digit E'|L E'|string E'E'->+ E E'|* E E'|emptyL->id L'L'-> digit L'|emptyB->! B B'|( B ) B'|E relop E B'|true B'|fa

8、lse B'B'->or B B'|and B B'|emptyrelop-><|<=|=|!=|>|>=日ist->E Elist'Elist'->, E 曰ist'|empty注：此处用empty代表空得分、系统设计要求：分为系统概要设计和系统详细设计。(1) 系统概要设计：给出必要的系统宏观层面设计图，如系统框架图、数据流图、功能模块结构 图等以及相应的文字说明。1)系统的数据流图: 说明说明：本语法分析器是基于上一个实验词法分析器的基础上，通过在界面写或者是导入源程序，词法分析器将源

9、程序识别的词法单元传递给语法分析器，语法分析器验证这个词法单元组成的串是否可以由源语言的文法生成，能够输出语法分析的结果，文法的first集、follow集和预测分析表，当然也可以以易于理解的方式报告语法错误。2)系统框架图富通利分所表IT列器生式亶月到产坐成成才一信得到产生或里/费本系统框架主要是三部分,部分是词法分析， 负责识别源程序的词法单元识别，并将其存储，以供语法分析时读取；第二部分是文法分析部分，负责将导入的文法进行分析，得出文 法的first集和follow集，以及自动构造出预测分析表，在语法分析时进行查询；第三部分 是用户界面，提供源程序输入功能，以及语法分析结果的显示，显示语

10、法分析树，还有first集、follow集和预测分析表的展示。(2)系统详细设计：对如下工作进行展开描述核心数据结构的设计核心数据结构主要有两种：1) Tuple三元组为了存储预测分析表，我使用Tuple<string,string,string>三元组的数据结构，分别存储产生式 的头部，产生式体，输入符号。2) Stack 栈为了能够在语法分析时根据预测分析表来进行分析，我写了一个CStack的类用来实现栈的数据结构，在进行语法分析时，一个栈用来存储文法符号，一个栈用来存储输入符号，然后 根据预测分析表进行语法分析。主要功能函数说明 主要功能函数：1) IDContent 类：功

11、能：充当符号表的角色，主要是用来保存关键字，运算符，界符，转义字符等各类单词。主要函数：bool isConstCh( string str)/判断是否转义字符bool isLetter_( char c)/判断是否字母或下划线bool isDigit( char c)/ 判断是否数字bool isBlank( char c)/判断是否是空格、制表符、换行、回车bool isKeyWord( string str)/判断是否关键字bool isBoundary( char c)/判断是否是边界符号bool isOperator( string ch)/ 判断是否运算符2) Identifier

12、 类功能：识别单词的核心类主要函数：string isID( string str, ref int i)/ 是否是标识符string isSixteen( string str, ref int i, out bool right)/ 是否 16 进制数string isEight( string str, ref int i, out bool right)/ 是否 8 进制数string isNumber( string str, ref int i, out bool right)/ 是否是常数stringisOperator( stringstr,stringisNote( stri

13、ng str,refstringisBoundary( stringstr,stringisChar( string str,refref int i, out bool right)/ 是否是运算符int i,out bool right)/是否注释ref int i, out bool right)/ 是否界符int i,out bool right)/是否字符常数3)FirstAndFollow 类功能：得到first集、follow集、select集、预测分析表public void getFirstCollection()/ public void getFollowCollecti

14、on()/ public void getSelectCollection()/得到first 集合得到follow集合得到预测分析表public void getAnalysisTable( string str1, string str2, public void errorHandle()/ 加入同步词法单元string str3)/得到预测分析表4)CStack 类功能：栈结构public bool isEmpty()/ 判断栈是否为空public void push( object item)/ 往栈中加入一个元素public object pop()/ 从栈中弹出一个兀素publi

15、c object peek()/ 返回栈顶对象5)Form 类public void analysis( string str)/词法单元识另 1public void parse()/语法单元识别privatevoid 导入文法 ToolStripMenuItem_Click( object sender, EventArgs e)/ 导入文法privatevoid 显示语法分析树 ToolStripMenuItem_Click(object sender, EventArgs e)/ 输出语法分析树privatevoid addListview1Item()/输出 first 集和 fol

16、low 集privatevoid addListview3Item()/输出预测分析表? 程序核心部分的程序流程图 语法分析核心部分流程图：开始将文法开始符号压入文法栈中从输入栈中读取词法单元11从文法栈中取出栈顶的符号输出语法分析树报错弹出文法栈栈顶对的左部栈顶是否阂，弹出文法栈顶对弹出输入栈栈顶对象弹出文法栈栈顶对象和输入栈栈顶对象四、系统实现及结果分析得分要求：对如下内容展开描述。(1)系统实现过程中遇到的问题；实现过程中主要遇到的问题有：1)如何修改文法使其时 LL (1)文法通过对文法的修改，主要是对文法消除左递归，消除二义性，以及提取公因式等，最终 对于相同左部的产生式他们的sel

17、ect集不相交，得到了 LL (1)文法。2)如何得到文法符号的first集对于终结符，其first集就是本身，但是对非终结符，在遍历的时候依赖于其他的非终结符，于是我采用循环遍历的方法，如果当前某个非终结符的first集依赖于其他非终结符，且其他非终结符的first集还没有求出来，则跳过当前的非终结符求下一个非终结符的first集，直到其依赖的非终结符的first集求出来后再求解。直到所有的非终结符的first集求出来后，循环结束，就得到了所有文法符号的first集合。3)如何得到非终结符的follow集为了使思路清晰，我采用两遍遍历的方式来求非终结符的follow集。第一遍之后，所有非终结

18、符都将得到一个暂时的follow集(不是最终的follow集)，第二遍的目标就是发现其中是否有非终结符的follow集发生了改变，如果改变，则继续遍历整个文法，直到没有新的符号加入follow集中。求follow集的具体思想就是：不断应用下列规则，直到没有新的终结符可以被加入到任何FOLLOW集合中为止?将$放入FOLLOW ( S )中，其中S是开始符号，$是输入右端的结束标记? 如果存在 一个产 生式 A-aB0那么 FIRST ( 3 )中除e之外的所有符号 都在 FOLLOW ( B )中?如果存在一个产生式A一 “B,或存在产生式 A- a B3且FIRST ( 3 )包含£

19、;,那么FOLLOW ( A )中的所有符号都在 FOLLOW ( B )中4)如何根据预测分析表进行语法分析这里主要依赖于栈的结构，将经过词法分析得到的词法单元压入输入栈，将文法起始符号压入文法栈，然后根据预测分析表得到各个产生式进行语法分析。(2) 输出该句法分析器的分析表；文法符号$procshortintlongfloatdoubleProgramFrogr«n->PFrogram->FFrograiri->PFrogr«m->PFrogram->FProgrM-”Program-?PP->enptyP-D PP->D PP

20、->D PP->D PP->D PP->D PD，yikchD->pr oc .D->T U A ；D->T id A .D->7 id A .5->T id A .D->T id A ；MM->X id MM->X id KM->X id /M->X id .M->X idJT£A FGGHTT->X CT->X CT-X CT->X CT->X CXX->shortX->intX->lon5X->£loatX-doubleCS Esy

21、tchsynchsynchsynchsynchsynchsynchF LLzB*relcpElistElist/charProgram->P ?->D ?D-)T id A ;M->X idvoidFrogrwn->? P->D PD->T id A ; M->X id MstringProgran->PP->D PD->T id A ： M->X id M,recordPro5rwn->P P->D PD->recor.idProgram-？ P->S P synchifProgram-" P

22、->S ? synchwhileFrogrtm">? P->S P synchcallProgra»->P P->S P synchFcherfstringF-)idG->H CM->chfirr->x CT->X CT-X CsynchX->charX")voidX->strin.synchC->enptysynchsynchsynchsynchS->1 = E :S->i£ B .S->whil«.S->c<ll .f->string

23、E->L E' ->emptyL->id L'L' ->emptyB->E rel.卜)出 rel.synchsynchEli st")E.Ilist->E.<re Iura1J)*<li 5； t(IPro5roniPr->s PP->e«ptysgcEsynchszyneh阪-3 X .K* > enp tykr>, id XA->- FA->enptysynchF-)diei tF-> G S>Ti?kG->X GC -JenptyCf HUs

24、ynoksyncliX->digitsynchC> di;5->r«tuz.synah5ynchsynchs yr chE-刈 g t E'synchE cptyP -、onp tyE -> emptyE -Jcrrpty3yxichsynclsyxvcksyx.clisrxichL' ->e«pt/V ->enptyl/">enptyL -HnptyL-> E .synchL九rel .F ->onptysyncksynchEliW-)(list -).(*J<<=!=R-A E

25、IzE-X E ) Izgyrvyhrynohsynohsynohsyn?hsyn?hcyaohF-X E KF -X E +T->cnptyE'一>e”ptyE' ->cnptyI? ->cnyty1 ->o»tyjyxwhayrwAxynoh,ynshsynch>ynckl/->e»p：yl/->en?ty1/-Xnpty1/ ->«npty1/ ->efiptyL/_>«nptyL-XnptyB->E rel.B-X B )甘synckzynehcLq-Xr&#

26、171;lop"><=nlopr«lop->!=EL： st->Z. ELi st->z.oraimtru anyncs(3)01234567890123123456 7 8QJ11111111112222rw- F T 餐 liptyL "JeiiptyswobZ -:电力FtyE./ELqIjJL -ciip ty1Z-1 ->«nptTSi卯工L TeFip bSyiW F anriptyEynch Dsii54追s' T呻" EMch.E 74 巾 ly工 一)«rpty x.jnc

27、iiL 7g均cynthmxh兰加注synth->«r E V日 TajsdH. f.才ytTb7fl I因为预测分析表实在是过于庞大，因此本处分段截取预测分析表，下面的表是接在上面表的 右侧。针对一测试程序输出其句法分析结果；测试程序：输入区intmJ*变量声明* /ckar 匕='N ;stiing 3二7息/：字符串声明/«惇*/int 3 c = I, 2,3：/噬组声明(施管/a0 = L/潼组囊蚩的弓t用*/:if (外1)支著句号then a *3: |Q ggwhile (a<l) /*嵌套的循环语句*/do a=a+2;call add

28、S所(1, 2),八球喝用叨前*/*过程声明，声明一样两力量我新的函数*/pioc int addSu>(int a, int h) int c, d：。=&，比变蚩之间的赋值率/d = h：Tetvurn c+d:4支持返回值以表达式的形式瓶/*记录声明*/record "int 3：char c:语法分析结果:语法分析结果ProgrM (1)p (1)D (1)TX (1)int (1) id： a (1) ；(1)P (2)D (2)T (2)X (2) chai (2) id： c (2) A=(2)F (2) chai ： 'a' (2) ;(

29、2)P (3)D (3)T (3)Xstzlag (3)id： s (3)A (3)=(3)F，“stxing： ,aaa" (3):(3)P (4)DT (4)X (4)int (4)C (4)(4)digit： 3 (4)id: c (4)A (4)=F (4)G (4)H (4)： 1 (4)G，H (4)digit： 2 G' (4)，(4)H (4)digit ： 34)(4) :(4) PS (5)L id： a L_(5)(5)E (5) digit: 0 (5)J=(5)Edigit： 1 ：PS if (6) B (B (6)EL id: a xelop &

30、gt;Edigit: 1 S) )(6) then (7)S (7)L (7) £d: a (7)二(7)E (7)L id: a E, (7)* (7)E (7) digit: 3 (7) ;(7) else (8)S (9) while (9) B (9)(9)BE (9)L (9) id： a relop (9)<E (9)Xigit： 1 ) do (10) S (10)L (10) id： a (10) =(10) E (10)L (10) id： a (10)E (10) 十(10) E (10) digit: 2 (10) ：(10)p (11)s (11) ca

31、ll (11) id： addSum (11) (ID Elist (11)E (11)digit： 1 (11)ElistJ (11)(11)E (11) digit： 2 (11) )(11) :(11)P (13)D (13) pioc (13) T (13)X (13) int (13) id： addSujii (13) (13)M (13)X (13) int (13) id： a (13) (13),(13)X (13)int (13) id: b (13)s (17)letum C17 jE (17)L (17)id: (17)E (17)十UT)E C17)L C17)id:

32、 d (17) :(17)1 (ie)P (20)D (20)record (20)id： m (20)()F (21)D (21)T C21)K (21)int (21)id: a (21):C21)F (22)D (22)T (22)义(22) char (.22) id; c (22) ;(22)(22)语法分析树:Frogi,ain白DI I分工语法分析树- int1 =白. F0- stringitogM«1 >LJa a E 1 idL.联二. 白0-sn s rlrh «111 1 ! *1«.分t 1 1 g idi=E 一 »*x

33、 tee 1-ala LILLdop> :&el: E c rt , i E .s;r 日t 1 1X g.1laa u L * E - idL0f L.A. LS-= EB-El-£ths sr-0 -.白j- else白5while.Bk(白/(=|-Ei白l O- i d：I0-relop，E) EQ digi t 1；-).doE0 L 白-id白E自d；/t白“PSL-2call自;d- addSuni臼.Elist(BE白 dig”LlB-ElisfBE日Fi二p=® idJTq t -三l.flqQP 72o由qmq”由h a由u 向 h w-d . ,由L-ii. ; ;I» « *!，*9；Bl*9* »»*«*« S UJ3d 0出力由F? E三” L目;dBl III自ELi_dherd自沱j- m(4) 输出针对此测试程序对应的语法错误报告; 带错误的测试程序：1011121314151617