递归下降语法分析器.doc

编译原理实验报告实验名称：编写递归下降语法分析器实验类型：验证型实验指导教师：专业班级：姓 名：学 号：电子邮件：实验地点：实验成绩： 日期： 2012 年4 月 26 日目录一、 实验目的。2二、 实验过程。21、 背景知识。22、 程序总体设计。23、 程序流程图。3三、 试验结果。5四、 讨论与分析。7五、 附录。7六、 试验者自评。11一、实验目的 通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目标： 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的语法分析程序。二、实验过程 我们在设计递归下降语法分析器时，应该首先对递归下降语法的相关的背景知识有足够的了解以及熟练的掌握。从而在脑海里形成语法分析的一般方案，根据方案一步步所要实现的目的，形成对递归下降语法分析器程序的模块划分和整体规划。1、 背景知识无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。 无左递归：既没有直接左递归，也没有间接左递归。无回溯：对于任一非终结符号U的产生式右部x1|x2|xn，其对应的字的首终结符号两两不相交。如果一个文法不含回路，也不含以为右部的产生式，那么可以通过执行消除文法左递归的算法消除文法的一切左递归（改写后的文法可能含有以为右部的产生式）。文法的左递归消除算法： 1、将文法G的所有非终结符排序为U1 ,U2 , ,Un; 2、For(i=1；i+；in) for j1 to i-1 把产生式UiUj替换成Ui1| 2|m； 其中：Uj 1| 2 | |m 消除Ui产生式中的直接左递归； 3.化简改写之后的文法，删除多余产生式。文法的直接左递归消除公式： 直接左递归形式：UUx|y； 其中：x，y（VNVT）* ，y不以U打头。 直接左递归的消除： UyU UxU| 直接左递归的一般形式：UUx1|Ux2|Uxm|y1|y2|yn； 其中：xi ,yi都不以U打头。 一般形式直接左递归的消除: Uy1U| y2U | ynUUx1U| x2U| | xmU| 回溯的消除的前提是文法不得含有左递归，可提左因子来消除回溯。2、 程序总体设计1、分析对象 分析算术表达式的BNF定义如下： 算术表达式项|算术表达式项|算术表达式项 项因式|项因式|项因式 因式变量（算术表达式） 变量i 用符号表示如下： ET|ET|E-T TF|TF|TF Fi(E)2.经消除直接左递归后ETEE +TE|-TE|TFTT *FT|/FT|F i|(E)3.根据递归下降法分析法，完成上述算术表达式的分析器构造。主要完成： (1) 通知外界键入算术表达式；(2) 控制过程分析算术表达式； (3) 根据分析结果正误，分别通知外界不同的信息。4、程序流程图三、实验结果（1）输入i+i#（2）输入+i#（3）左右括号测试（4）测试回车（5）综合测试1 四、讨论与分析本次试验完成了指导报告上要求的基本功能,并且本程序具有以下几种情况的排错：对(i+i这种错误，以及i+i，ii这种错误等进行了错误排除。除此本程序对回车换行符也进行也处理，其处理方法就是每当在取得一个字符后，用if（sym=n） sym=advance();进行处理即可。另外在编写程序时遇到了这样一种错误，当输入i+i+i时，PE返还给主函数的是+号，解决方法是在PE函数中把p_E(hh);改为hh=p_E(hh); 五、附录：关键代码#includestdio.h#include string.h#include stdlib.h#include ctype.hintpT(char sym);intp_E(char sym);intp_T(char sym);intpF(char sym);int i=0,j=0;/char sym;char instring20;char advance()char cc;i=i+1;cc=instringi;return cc;int pE(char sym)char xx;xx=sym;xx=pT(sym);/printf(%c,xx);xx=p_E(xx);/printf(/n%c,xx);returnxx;int p_E(char sym)char s,hh;s=sym;hh=sym;if (sym=+|sym=-)printf(%c,sym);sym=advance();if(sym=n)sym=advance();hh=pT(sym);/printf(%c,hh);hh=p_E(hh); else if(s=)|s=#|s=/0|n) else printf(error!); return -1; return hh;int pT(char sym)char yy;yy=sym;yy=pF(sym);/printf(%c,yy);yy=p_T(yy);/printf(%c,yy);return yy;int p_T(char sym)char s,zz;zz=sym;if (sym=*|sym=/)printf(%c,sym);s=sym;sym=advance();if(sym=n)sym=advance();/zz=sym;zz=pF(sym);/printf(%c,zz);p_T(zz);else if(sym=)|sym=#|sym=/0|sym=+|n) else printf(error2!); return -1; return zz;int pF(char sym)if (sym=i)printf(%c,sym);printf(%d,j+);sym=advance();if(sym=n)sym=advance();/printf(%c,sym);else if(sym=()printf(%c,sym);sym=advance();if(sym=n)sym=advance();sym=pE(sym);if(sym=)printf(%c,sym);sym=advance();if(sym=n)sym=advance();else printf(error);return -1; else if(sym=/0|sym=n) elseprintf(err);return -1;return sym;void main()int b=0;char sym,c,mm;printf(input a stringn);doc=getchar();instringb+=c;while(c!=#);getchar();sym=instring0;mm=pE(sym);printf(n%c,mm);if(mm=#) printf(nright again!);elseprintf(nerror again!); 六、实验者自评 首先，对本次实验我抱着认真，细心的态度去做的，并且做了各种情况的测试以及调试。从中我深深地体会到进行全面测试的重要性。再者，对于本实验，我是采用C语言编写的，相对于用VB或JAVA编写，它的交互性要差一些。最后，通过本程序的编写以及调试，我对于一些常见错误的分析能力有了一定的提高。【唯美句子】 走累的时候，我就到升国旗哪里的一角台阶坐下，双手抚膝，再闭眼，让心灵受到阳光的洗涤。懒洋洋的幸福。顶 3 收藏 2【唯美句子】 一个人踮着脚尖，在窄窄的跑道白线上走，走到很远的地方又走回来。阳光很好，温暖，柔和。漫天的安静。顶 7 收藏 7【唯美句子】 清风飘然，秋水缓淌。一丝云起，一片叶落，剔透生命的空灵。轻轻用手触摸，就点碎了河面的脸。落叶舞步婀娜不肯去，是眷恋，是装点？瞬间回眸，点亮了生命精彩。顶 11 收藏 9【唯美句子】 几只从南方归来的燕子，轻盈的飞来飞去，“几处早莺争暖树，谁家新燕啄春泥，”其乐融融的山林气息，与世无争的世外桃源，让人心旷神怡。顶 0 收藏 2【唯美句子】 流年清浅，岁月轮转，或许是冬天太过漫长，当一夜春风吹开万里柳时，心情也似乎开朗了许多，在一个风轻云淡的早晨，踏着初春的阳光，漫步在碧柳垂青的小河边，看小河的流水因为解开了冰冻而欢快的流淌， 清澈见底的的河水，可以数得清河底的鹅软石，偶尔掠过水面的水鸟，让小河荡起一层层的涟漪。河岸换上绿色的新装，刚刚睡醒的各种各样的花花草草，悄悄的露出了嫩芽，这儿一丛，那儿一簇，好像是交头接耳的议论着些什么，又好象是在偷偷地说着悄悄话。顶 3 收藏 4【唯美句子】 喜欢海子写的面朝大海春暖花开，不仅仅是因为我喜欢看海，还喜欢诗人笔下的意境，每当夜深人静时，放一曲纯音乐，品一盏茶，在脑海中搜寻诗中的恬淡闲适。在春暖花开时，身着一身素衣，站在清风拂柳，蝶舞翩跹的百花丛中，轻吹一叶竖笛，放眼碧波万里，海鸥，沙滩，还有扬帆在落日下的古船，在心旷神怡中，做一帘红尘的幽梦。顶 0 收藏 2【唯美句子】 繁华如三千东流水，你只在乎闲云野鹤般的采菊东篱、身心自由，置身置灵魂于旷野，高声吟唱着属于自己的歌，悠悠然永远地成为一个真真正正的淡泊名利、鄙弃功名利禄的隐者。顶 1 收藏 3【唯美句子】 世俗名利和青山绿水之间，你选择了淡泊明志，持竿垂钓碧泉绿潭；权力富贵和草舍茅庐之间，你选择了宁静致远，晓梦翩跹姹紫嫣红。顶 2 收藏 3【唯美句子】 那是一株清香的无名花，我看到了它在春风夏雨中风姿绰约的模样，可突如其来的秋雨，无情的打落了它美丽的花瓣，看着它在空谷中独自凋零，我莫名其妙的心痛，像针椎一样的痛。秋雨，你为何如此残忍，为何不懂得怜香惜玉，我伸出颤抖的双手，将散落在泥土里的花瓣捧在手心。顶 4 收藏 5【唯美句子】 滴答滴答，疏疏落落的秋雨，赶着时间的脚步，哗啦啦的下起来。听着雨水轻轻地敲击着微薄的玻璃窗，不知不觉，我像是被催眠了一样，渐渐的进入了梦乡。顶 3 收藏 5【唯美句子】 在这极致的悲伤里，我看到了世间最美的爱，可谁又能明白，此刻的我是悲伤还是欢喜，也许只有那拨动我心弦的秋季，才知道潜藏在我心中的眼泪。顶 4 收藏 3【唯美句子】 看着此情此景，我细细地聆听。像是听到了落叶的呢喃，秋风的柔软，在这极短的瞬间，他们一起诉说着最美的爱恋，演绎着永恒的痴缠。当落叶安详的躺在大地，露出幸福的模样，你看，它多像一个进入梦乡的孩子。突然发现，秋风并非是想象中的刽子手，原来它只是在叶子生命的最后一刻，让它体会到爱的缠绵，飞翔的滋味。顶 1 收藏 1【唯美句子】 很感谢那些耐心回答我的人，公交上那个姐姐，还有那位大叔，我不知道他们是不是本地人，但我们遇到的一个交警协管，一位头发花白的大姐，她是上海本地人，很和善，并不像有些人说的上海人很排外。事实上，什么都不是绝对的。顶 2 收藏 0【唯美句子】 我嗅到浓郁的香奈尔，却也被那种陌生呛了一鼻。也许，我却不知道，那时的感受了。那里没有那么美好，没有安全感，归属感。我想要的自由呢，不完全地体验到了。顶 2 收藏 1【唯美句子】 那些繁华的都市，车水马龙，灯红酒绿，流光溢彩，却充斥着一种悲哀，浮夸。我看到各种奢华，却也看到各种卑微，我看到友善亲和，也看到暴躁粗鲁，我看到金光熠【优美语句】 踏过一片海，用博识的学问激起片片微澜；采过一丛花，正在聪慧的碰碰外送来缕缕清喷鼻；无过一个梦，决定从那里启程。顶 0 收藏 0【优美语句】 人生如一本书，应该多一些精彩的细节，少一些乏味的字眼；人生如一支歌，应该多一些昂扬的旋律，少一些忧伤的音符；人生如一幅画，应该多一些亮丽的色彩，少一些灰暗的色调。 顶 0 收藏 0【优美语句】 母爱是一滴甘露，亲吻干涸的泥土，它用细雨的温情，用钻石的坚毅，期待着闪着碎光的泥土的肥沃；母爱不是人生中的一个凝固点，而是一条流动的河，这条河造就了我们生命中美丽的情感之景。 顶 0 收藏 0【优美语句】 生活如海，宽容作舟，泛舟于海，方知海之宽阔；生活如山，宽容为径，循径登山，方知山之高大；生活如歌，宽容是曲，和曲而歌，方知歌之动听。 顶 0 收藏 0【优美语句】 母爱就是一幅山水画，洗去铅华雕饰，留下清新自然；母爱就象一首深情的歌，婉转悠扬，轻吟浅唱；母爱就是一阵和煦的风，吹去朔雪纷飞，带来春光无限。 顶 0 收藏 0【优美语句】 努力奋斗，天空依旧美丽，梦想仍然纯真，放飞自我，勇敢地飞翔于梦想的天空，相信自己一定做得更好。 顶 0 收藏 0【优美语句】 品味生活，完善人性。存在就是机会，思考才能提高。人需要不断打碎自己，更应该重新组装自己。顶 0 收藏 0【优美语句】 母爱是一缕阳光，让你的心灵即使在寒冷的冬天也能感到温暖如春；母爱是一泓清泉，让你的情感