编译原理实验递归下降分析器设计含源代码和运行结果.doc

《编译原理》实验报告
实验3 递归下降分析器的设计
姓名 学号　 　 　班级 　计科１00１班
时间：　2012/４／15 　　 　 地点：文波
同 组 人：无
指导教师:朱少林
实验目的
使用递归子程序法设计一个语法分析程序,理解自顶向下分析方法的原理,掌握手工编写递归下降语法分析程序的方法.
实验内容
运用所学知识,编程实现递归下降语法分析程序。使用递归下降分析算法分析表达式是否符合下文法：
exp → exp　ａddop　tｅrｍ |　ｔerｍ
Adｄop →+ | -
tｅrm→ term muloｐ factoｒ　| ｆaｃtor
ｍulop →　* | /
faｃtoｒ → （eｘp）　｜ ｉd　｜　nuｍber
其中numｂer可以是多位的十进制数字串（整数即可)，因此这里还需要一个小的词法分析器来得到id 和nuｍｂｅr的值.
从数据文件中读出符号串，输出表达式并给出其正误评判.
实验数据文件中应该有多个表达式,可能有正确的也应该有错误的表达式；,以回车结束.
实验环境
软件:VＣ＋+6．0　
实验前准备
方案设计：
准备模拟数据：本实验中使用 “work..ｃｐｐ" 　　 　 　 　　 　
程序思想：
为了使用递归向下的分析,为每个非终结符根据其产生式写一个分析程序,由于写入读出的操作频繁。所以程序中还有一个matｃh（ｃhａｒ t)函数,该函数是将字符写入文件打印输出同时从文件中读取下一个字符,而由于iｄ和nuｍbeｒ可能是多个字符构成，故写了number（）和iｄ(）来分析数字和标识符，它们的功能仅仅是把整个number或ｉｄ完整的读取出来并写入文件，打印输出。
由于分析的文件中可能出现非法字符，而一旦发现非法字符就无需再接着分析，所以在每次读取一个字符时调用islegal函数判断是否是合法字符,并返回0或1.
在mａｉn()函数中,wｈｉle（(ｌoｏkaheaｄ＝=’\n＇｜｜lookaheaｄ＝＝＇ ’）＆&looｋahead!=ＥOＦ) 　　 　 　　 ｆscanf(resource，"%c",＆lookaｈｅad);
是为了忽略分析文件中的换行或空格，之后进入分析阶段,根据返回值判断是否是合法的表达式。在该程序中只有发现了非法字符才会返回0,否则就返回１，而对于合法的表达式，递归程序最后分析的字符就是换行符,不合法的表达式在未分析到换行符就会停止分析,所以根据最后分析的字符是否为换行符进一步确定是否为合法的表达式。
实验步骤
首先将上述文法改写成LL(1）文法
消除左递归：
exp →term ｔｅxp
ｔexp →　addop ｔerm tｅxp ｜　ε
Addｏp →+ |　-
term→factｏｒ tｔerm
ttｅrm　→mulop faｃtor tterm｜ε
mulop →　* ｜ /
factor →　（exp） ｜ ｉd | nuｍber
求出每个非终结符的FIRST集合和FOＬLOW集合：
FIRＳＴ(exｐ）= FIRＳT（ｔeｒm)＝ FIRＳT(ｆａcｔor)＝｛iｄ, numｂer， （ ｝
FIRＳT(teｘp)={ ε,+， -　}
ＦＩRSＴ（Addoｐ）={+, — ｝
FIRST(ｔｔerm)=｛ ε,*,　/ }
ＦIRＳT(muｌｏp）=｛＊, / }
求出每个非终结符的ＦＯLLOＷ集合：
ＦOLＬOW（exp）=FOLLOＷ(tｅｘp）＝{#， ）｝
ＦＯLLＯW(Addop）＝FOLLOW（muloｐ）=｛iｄ, nｕｍber, （ ｝
FOＬLOW(term)=ＦOLＬＯW（tterm）=｛+，　-，#， ) ｝
FOLLＯW（faｃtor)＝｛ ＊,／,+,－,＃，) ｝
对于texｐ → adｄop　term　texp ｜ ε:FIRST（Aｄdop　tｅｒm　texp）∩FOLLＯW(tｅxp）= φ；
对于tterm →ｍｕlｏｐ faｃtor tｔerm｜ε：FIRST(muloｐ factor tteｒm）∩ＦＯLLOW(tterm）＝ φ；
而Addｏp　→+ ｜　- mｕlop → ＊ ｜ /　 　facｔoｒ → （ｅxp）　| id | numbｅｒ 显然也是符合ＬＬ（1）文法要求的，所以改写后的文法符合LL（1）文法,可以用自上而下的递归分析方法。
为每个非终结符根据其产生式写一个分析子程序;
编写数字和字母识别程序,以便分离数字