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

《编译原理》实验报告 实验3 递归下降分析器的设计 姓名 学号 班级 计科1001班 时间： 2012/4/15 地点:文波 同 组 人：无 指导教师：朱少林 实验目的 使用递归子程序法设计一个语法分析程序，理解自顶向下分析方法的原理，掌握手工编写递归下降语法分析程序的方法。 实验内容 运用所学知识，编程实现递归下降语法分析程序。使用递归下降分析算法分析表达式是否符合下文法： exp → exp addop term | term Addop →+ | - term→ term mulop factor | factor mulop → * | / factor → (exp) | id | number 其中number可以是多位的十进制数字串（整数即可），因此这里还需要一个小的词法分析器来得到id 和number的值。 从数据文件中读出符号串，输出表达式并给出其正误评判。 实验数据文件中应该有多个表达式，可能有正确的也应该有错误的表达式；表达式有形式简单的也应该有复杂的。每个表达式写在一行，以回车结束。 实验环境 软件：VC++6.0 实验前准备 方案设计： 准备模拟数据：本实验中使用 “work..cpp” 程序思想： 为了使用递归向下的分析，为每个非终结符根据其产生式写一个分析程序，由于写入读出的操作频繁。所以程序中还有一个match(char t)函数，该函数是将字符写入文件打印输出同时从文件中读取下一个字符，而由于id和number可能是多个字符构成，故写了number()和id（）来分析数字和标识符，它们的功能仅仅是把整个number或id完整的读取出来并写入文件，打印输出。 由于分析的文件中可能出现非法字符，而一旦发现非法字符就无需再接着分析，所以在每次读取一个字符时调用islegal函数判断是否是合法字符，并返回0或1. 在main()函数中，while((lookahead==\n||lookahead== )lookahead!=EOF) fscanf(resource,%c,lookahead); 是为了忽略分析文件中的换行或空格，之后进入分析阶段，根据返回值判断是否是合法的表达式。在该程序中只有发现了非法字符才会返回0，否则就返回1，而对于合法的表达式，递归程序最后分析的字符就是换行符，不合法的表达式在未分析到换行符就会停止分析，所以根据最后分析的字符是否为换行符进一步确定是否为合法的表达式。 实验步骤 首先将上述文法改写成LL（1）文法 消除左递归： exp →term texp texp → addop term texp | ε Addop →+ | - term→factor tterm tterm →mulop factor tterm|ε mulop → * | / factor → (exp) | id | number 求出每个非终结符的FIRST集合和FOLLOW集合： FIRST(exp)= FIRST(term)= FIRST(factor)={id, number, ( } FIRST(texp)={ ε,+, - } FIRST(Addop)={+, - } FIRST(tterm)={ ε,*, / } FIRST(mulop)={*, / } 求出每个非终结符的FOLLOW集合： FOLLOW(exp)=FOLLOW(texp)={#, ）} FOLLOW(Addop)=FOLLOW(mulop)={id, number, ( } FOLLOW(term)=FOLLOW(tterm)={+, -,#, ) } FOLLOW(factor)={ *,/,+,-,#,) } 对于texp → addop term texp | ε：FIRST（Addop term texp）∩FOLLOW(texp)= φ； 对于tterm →mulop factor tterm|ε：FIRST(mulop factor tterm)∩FOLLOW(tterm)= φ； 而Addop →+ | - mulop → * | / factor → (exp) | id | number 显然也是符合LL（1）文法要求的，所以改写后的文法符合LL（1）文法，可以用自上而下的递归分析方法。 为每个非终结符根据其产生式写一个分析子程序； 编写数字和字母识别程序，以便分离数字和标识符。； 主函数调用递归程序进行分析，根据分析结果判断是否是合法表达式，并将所有识别到的表达式输出。 程序设计： #include stdio.h