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

编译原理课程实验报告实验2 :语法分析姓名1院系1软件学院学号任课教师指导教师实验地点软件学院三楼机房实验时间2016/10/30/ 星期日实验课表现出勤、表现得分实验报告得分实验总分操作结果得分一、需求分析得分要求：采用至少一种句法分析技术（LL（1）、SLR（1、LR（1）或LALR（1）对类高级语言中的基本语句进行句法分析。阐述句法分析系统所要完成的功能。本语法分析器是在词法分析器的基础上实现对类高级语言中的基本语句进行句法分析，基本功能 如下：（1）能识别以下几类语句：声明语句（包括变量声明、数组声明、记录声明和过程声明 ）表达式及赋值语句（包括数组元素的引用和赋值）分支语句：if_then_else循环语句：do_while过程调用语句（2） 本语法分析器采用自顶向下的分析技术，能根据导入的文法，自动计算first集和follow集， 能够生成每个产生式的select集，并自动生成预测分析表。（3）本语法分析器具备语法错误处理能力，可以进行错误检测，如果检测到在出错时，采用恐慌模式，能够给出错误提示信息，格式：错误项错误原因行号a）忽略输入中的一些符号，直到输入中出现选定的同步词法单元集合中的某个词法单元，同步集合的选取是非终结符的follow集；b）如果终结符在栈顶而不能匹配，弹出此终结符。c）输入栈中缺少某些应有的符号，比如只有右括号没有左括号等，会给出相应的提示。（4）系统的输入形式多样：可以通过文件导入文法和测试用例，可以通过用户界面显示并编辑测试用例。测试用例涵盖了第（1）条中列出的各种类型的语句，并设置了一些语法错误。（5） 系统的输出分为两部分：一部分是打印输出语法分析器的FIRST集、FOLLOW集、select集和LL（1）分析表。另一部分是打印输出语法分析结果。（6）本系统还实现了输出语法分析树的功能，让语法分析的过程更清晰。二、文法设计得分要求：给出如下语言成分的文法描述。声明语句（包括变量声明、数组声明、记录声明和过程声明 ）表达式及赋值语句（包括数组元素的引用和赋值）分支语句：if_then_else循环语句：do_while过程调用语句本语法分析器主要针对C语言进行文法设计，下面给出各语言成分的文法描述。程序入口：Program-PP-D P /支持连续声明P -S PP-1）声明语句：D proc id ; D S| T id;/支持过程声明和变量声明T t X C | record D/支持结构体声明X t short|int | Iong|float|double|char|string/ 支持多种基本类型的声明C t numC | &II支持数组的声明2）表达式及赋值语句：S id = E ;| L = E ;E E + E | E * E | E |（E） | id | digit | LL idE | LEII支持数组元素的引用和赋值3）控制流语句：S if B then Slelse S2 | while B do S1B t b | bII或语句| B & BII且语句| ! BII非语句1(B)| E relop E| true| false/使用括号 /关系语句/bool 型/bool 型/关系符号relop t | | =4)过程调用语句S call id (Elist)Elist Elist, EElist E下面给出整个程序的无二义性，无左递归的LL (1)文法：Program-PP-D P|S P|emptyD-proc T id ( M ) P |T id A ;|record id P M-X id MM-, X id M|emptyA-= F|empty|, id AF-digit|id|char| G |stringG-H GG-, H G|emptyH-digit|charT-X CX-short|i nt|l on g|float|double|char|void|stri ng|boolea nC- digit C|emptyS-L = E ;|if B the n S else S|while B do S|call id ( Elist ) ;|return E ;E- E E|( E ) E|digit E|L E|string EE-+ E E|* E E|emptyL-id LL- digit L|emptyB-! B B|( B ) B|E relop E B|true B|false BB-or B B|a nd B B|emptyrelop_|=Elist-E ElistElist-, E Elist|empty注：此处用empty代表空、系统设计得分要求：分为系统概要设计和系统详细设计。(1) 系统概要设计：给出必要的系统宏观层面设计图，如系统框架图、数据流图、功能模块结构 图等以及相应的文字说明。1)系统的数据流图：说明蛊取下一个 词建单元说明：本语法分析器是基于上一个实验词法分析器的基础上，通过在界面写或者是导入源程序，词法分析器将源程序识别的词法单元传递给语法分析器，语法分析器验证这个词法单元组成的串是否可以由源语言的文法生成，能够输出语法分析的结果，文法的first集、follow集和预测分析表，当然也可以以易于理解的方式报告语法错误。2)系统框架图本系统框架王要是三部分,馬户岸面电演W出百斗测仔崭击显小区Ft获来占rn豐显示懐部分是词法分析， 负责识别源程序的词法单元识别，并将其存储，以供语法分析时读取；第二部分是文法分析部分，负责将导入的文法进行分析，得出文 法的first集和follow集，以及自动构造出预测分析表，在语法分析时进行查询；第三部分 是用户界面，提供源程序输入功能，以及语法分析结果的显示，显示语法分析树，还有first集、follow集和预测分析表的展示。(2)系统详细设计：对如下工作进行展开描述核心数据结构的设计核心数据结构主要有两种：1) Tuple三元组为了存储预测分析表，我使用Tuple三元组的数据结构，分别存储产生式的头部，产生式体，输入符号。2) Stack 栈为了能够在语法分析时根据预测分析表来进行分析，我写了一个CStack的类用来实现栈的数据结构，在进行语法分析时，一个栈用来存储文法符号，一个栈用来存储输入符号，然后 根据预测分析表进行语法分析。主要功能函数说明 主要功能函数：1) IDContent 类：功能：充当符号表的角色，主要是用来保存关键字，运算符，界符，转义字符等各类单词。主要函数：bool isConstChstring str)/判断是否转义字符bool isLetter_(char c)判断是否字母或下划线bool isDigit(char c) 判断是否数字bool isBlank(char c)判断是否是空格、制表符、换行、回车bool isKeyWord(string str)/ 判断是否关键字bool isBoundary(char c)/判断是否是边界符号bool isOperator(stri ng ch)/ 判断是否运算符2) Identifier 类功能：识别单词的核心类主要函数：string isID(string str, ref int i)/是否是标识符string isSixteen(string str, ref int i,out bool right)/ 是否 16 进制数string isEighttring str,ref int i,out bool right)/ 是否 8 进制数string isNumber(string str, ref int i, out bool right)/ 是否是常数string isOperator(string str, ref int i, out bool right)/ 是否是运算符string isNote(string str, ref int i, out bool right)/ 是否注释string isBoundary(string str, ref int i,out bool right)/ 是否界符string isChartring str, ref int i, out bool right)/ 是否字符常数3) FirstAndFollow 类功能：得到first集、follow集、select集、预测分析表public void getFirstCollection()/ 得到 first 集合public void getFollowCollection()/ 得到 follow 集合public void getSelectCollection()/ 得到预测分析表public void getAnalysisTable(string str1, string str2, string str3)/ 得到预测分析表public void errorHandle()加入同步词法单元4) CStack 类功能：栈结构public bool isEmpty()判断栈是否为空public void push(object item)/ 往栈中加入一个元素public object pop()从栈中弹岀一个元素public object peek() 返回栈顶对象5) Form 类public void analysis(string str)/ 词法单元识另Vpublic void parse()语法单元识别private void 导入文法 ToolStripMenultem_Click(object sender. EventArgse)/ 导入文法private void 显示语法分析树 ToolStripMenultem_Click(object sender, EventArgs e)/输岀语法分析树private void addListview1ltem() 输岀 first 集和 follow 集private void addListview3ltem() 输岀预测分析表程序核心部分的程序流程图语法分析核心部分流程图：输出语法分析树开始将文法开始符号压入文法栈中从输入栈中读取词法单元空从文法栈中取出顶的符号报错弹出文法栈栈顶对扫描预测分析表象弹出文法栈栈顶对 象和输入栈栈顶对象结束否是同步词曰 法单是将产生式的右部替 换文法栈中产生的左部a栈顶是否为、和输入栈的输否入字符是否匹否配弹出文法栈顶对弹出输入栈栈顶对象四、系统实现及结果分析得分要求：对如下内容展开描述。（1）系统实现过程中遇到的问题；实现过程中主要遇到的问题有：1）如何修改文法使其时 LL（ 1）文法通过对文法的修改，主要是对文法消除左递归，消除二义性，以及提取公因式等，最终对于相同左部的产生式他们的select集不相交，得到了 LL（ 1）文法。2） 如何得到文法符号的first集对于终结符，其first集就是本身，但是对非终结符，在遍历的时候依赖于其他的非终结 符，于是我采用循环遍历的方法，如果当前某个非终结符的first集依赖于其他非终结符，且其他非终结符的first集还没有求出来，则跳过当前的非终结符求下一个非终结符的first集，直到其依赖的非终结符的first集求出来后再求解。直到所有的非终结符的first集求出来后，循环结束，就得到了所有文法符号的first集合。3） 如何得到非终结符的follow集为了使思路清晰，我采用两遍遍历的方式来求非终结符的follow集。第一遍之后，所有非终结符都将得到一个暂时的follow集（不是最终的follow集），第二遍的目标就是发现其中是否有非终结符的follow集发生了改变，如果改变，则继续遍历整个文法，直到没有新的符号加入follow集中。求follow集的具体思想就是：不断应用下列规则，直到没有新的终结符可以被加入到任何FOLLOW集合中为止将$放入FOLLOW（ S ）中，其中S是开始符号，$是输入右端的结束标记如果存在一个产生式 Aa B0那么FIRST（份中除&之外的所有符号都在 FOLLO% B ） 中如果存在一个产生式AaB,或存在产生式Aa BB且FIRST （ 3 ）包含 &那么FOLLOW A ）中的所有符号都在 FOLLOW（ B ）中4）如何根据预测分析表进行语法分析这里主要依赖于栈的结构，将经过词法分析得到的词法单元压入输入栈，将文法起始符 号压入文法栈，然后根据预测分析表得到各个产生式进行语法分析。（2）输出该句法分析器的分析表；文法符号$procshortProgramFrogrn-PFrogram-FFrograin-PFP-enptyP-D PP-D PDMD-pr ocD-T id A ； M-X id MK*AFGGHTT-X CXX-shortCSEsytchsynchsynchintFrogrm-P P-D P D-T id A ； M-X id Mlong Program-?P-D P D-7 id A ； M-X id Zfloat Frogrwn-FP-D P5-T id A M-X id M*doubleFrogram-FP-D P D-T id A . M-X idM*T-X CT-X CT-X CT-X CX-intX-lon$X-loatX-doublesynchsynchsynchsynchLzB b relcp Elist ElistcharProgram-FP-D PD-)T id A :M-X idvoidFrogrtm-?P-D P TT id A : M-X id Itstring Progran-PP-D P D-T id A : M-X il MrecordPro5ram-PP-D P D-recorLcharG-H GfstringK-char r-x C X-charT-X C X)voidT-X CXstrin.synchsynchsynch f-stringsynchB-E rel.synchEli st：E.idifwtilecallProgram-?Program-PFrogrtm?Progra-PP-S PP-S PP-S PP-S PsynchsynchsynchsynchHidsynch synch C*enpty S-1 = E :E-L EE -empty L-id L L -empty rel.S-i BS-whil.S-cd. 1synchEli stE.re turn1/)(Ir-s PPeptysjnclsynchzynehK* enp tykr, id XA- FA_etiptysyrchF-)diei tF- G tynohC-Jenptyd X CG-X GsynokSYIkdlX-digitsynch C dig.5rtuz.synah5ynchsynch5 yr chEdi g t EsynchE cptyF onp tyE emptyE JcrrptysynchsynclsyxvcksyxxhsrxichL ept/L -enptyl/enpty L -mptyL*- E synchf-E rel .V an; tysyncksynchIlisfI.(list -).(*J- E IzE-X E ) Iz%yxv?hcyn-?xsynohsynchsyn?hsyn?hF-” E re 丁1* -cnptyF-cptyT -cnptyI? -cnytyt onptysyxwX、ynohsynsklyndynckl/_ep：yl/_en?ty1/-Xnpty1/ -npty1/ efiptyL/_nptyL/_nptyB-E reL.B-!=EL： stZ. ELi st-z.因为预测分析表实在是过于庞大，因此本处分段截取预测分析表，下面的表是接在上面表的 右侧。(3) 针对一测试程序输出其句法分析结果；测试程序：百的0123456789012312345678911111111112222语法分析结果:int霊严变量声明ckar c -string 3 -int 3a0 = 1:/ 狂(al) /*分爲律吐：庐字符串声明不=X声哺對蛆査量的施用吋tken a *3 : |s Ise聊hil匕(忒1)户嵌套的循环语句*/do a=a+2;call addSun (1, 2).户过程声明，声明一策两羊童 pioc int addSu(int a, int b) int c, d：c=M变量 之间的赋值盯d = b;letvurn c+d;/*支持返回值以表达式的形式縊/”记录声明榔record mint 3：char c：语法分析结杲DT (4)X (4) int (4)C(4)digit： 3 id: c (4)A (4)=F (4)G (4)Hdigit： 1 (4),(4)Hdigit： 2 G (4)、Hdigit: 3 )(4):(4)PS (5)Lid： a L (5)E (5)digit: 0 (5) =E digit: 1 : PS if B( BELid: a xelop E digit： 1 )(6)then (7)S (7) L (7) id： a (7) 二 EL id： a *E (7) digit: 3 (7) ; else (8)S (9) while (9) B(9)B (9)E (9) Lid： a (9) relop (9) E (9) digit: 1 )(9) 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)call (11) id： addSum (11) (IDElist (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: addSuA (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 (1?)L (1?)id: u (17)(17)十UT)E C17) L C17) id: d (17):(17)1 ( P (20)C (20) record (20) id： m (20) (20)F (21) r (21)T (21 K (21)int (21) id: a (21) :(21)F (22)D (22) T (22)X (22) char (.22) id; c C22) ;(22)语法分析树:(22)语法析树；“30-FGEg|曰hE di gi t13 (jSH| 0 digii_2自G曰H曰I * ?s E0E -a u L * E - UL L & r,.s- n LS-= E&-曰-二 - - ：白digi taj- else& Swhile.Bk(S-B(=|-Ei白l m i jI0-reloph E) E Q digi t 1；-),do;Ll then /*少 1 a = 09/错误嗣 else vhile(a慣误的宇付串.缺少17*參余的字待2+參金的享待5id參金的宇符5i參金的宇待E垦否缺少Ttempty是否離少Y7addSum缺少（12号“bk是舌缺少13是酉镁少/17语法错误报告:对实验结果进行分析。总结：本语法分析器具有强大的语法分析功能允许变量的连续声明，比如int a,b,c;允许声明的同时赋值，比如string c =你好”允许对数组的声明和引用，同时进行赋值，比如char4 a = a , ;a0=, m , d支持多种类型的声明和赋值， 比如 int, short, lo ng, flaot, double, char, stri ng , boolean 的声明和赋值；允许声明和使用一个过程函数，比如：/*过程声明，声明一个求两个整数和的函数*/proc int addSum(i nt a,i nt b) int c,d;c = a;/*变量之间的赋值*/d = b;return c+d;/*支持返回值以表达式的形式*/call addSum(1,2);/* 函数调用功能 */ 允许声明一种数据结构，比如：/*记录声明*/record stackint a;/*表示位置*/char c;/*表示取值*/强大的错误处理能力：能够识别非法字符，如：中文，中文的标点符号；能够弹出多于的输入字符，如：int a = 1* ；能够处理词法单元的错误，比如：错误的16进制数，错误的字符串，错误的字符常数,错误的常数，错误的注释，错误的8进制等；能够判断是否缺少分量，比如:int a /*此处缺少分号*/，能够给出提示缺少分号；能够进行括号的匹配等，比如：只有左括号无右括号，只有右括号无左括号等，都能进 行识别和提醒；在栈顶的输入符号与文法栈中的符号不匹配时能够根据同步词法单元来弹出非终结符 等，继续进行语法分析；当连续不匹配出现错误时，比如某一行连续错误，能够在下一行重新开始语法分析，避 免因为某一行的连续错误导致语法分析停止。注：其中的测试样例需先用已编写的词法分析程序进行处理。指导教师评语:日期: