《编译原理》实验报告实验3 递归下降分析器的设计学号班级计科1001班时间：2012/4/15 地点:文波同组人：无指导教师：朱少林实验目的使用递归子程序法设计一个语法分析程序，理解自顶向下分析方法的原理，掌握手工编写递归下降语法分析程序的方法。

实验容a.运用所学知识，编程实现递归下降语法分析程序。

使用递归下降分析算法分析表达式是否符合下文法：exp →exp addop term | termAddop →+ | -term→term mulop factor | factormulop →* | /factor →(exp) | id | number其中number可以是多位的十进制数字串（整数即可），因此这里还需要一个小的词法分析器来得到id 和number的值。

b.从数据文件中读出符号串，输出表达式并给出其正误评判。

实验数据文件中应该有多个表达式，可能有正确的也应该有错误的表达式；表达式有形式简单的也应该有复杂的。

每个表达式写在一行，以回车结束。

实验环境软件：VC++6.0实验前准备1、方案设计：①准备模拟数据：本实验中使用“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 texptexp →addop term texp | εAddop →+ | -term→factor ttermtterm →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>#include <string.h>number();id();int exp();int texp();int addop();int term();int tterm();int mulop();int factor();int islegal();void match(char t); FILE *resource;//测试文件FILE *result;//结果文件char lookahead;//全局变量void match(char t)//写入result文件,打印输出，并读取下一个{fprintf(result,"%c",lookahead);//向result写入printf("%c",lookahead);fscanf(resource,"%c",&lookahead);//读数据}number()//识别数字，如果遇到数字就一直接着读直到不是数字{while('0'<=lookahead&&lookahead<='9'){fprintf(result,"%c",lookahead);//写入printf("%c",lookahead);fscanf(resource,"%c",&lookahead);//读出}}id(){//识别标识符while((lookahead<='z'&& lookahead>='a')||(lookahead>='A'&& lookahead<='Z')||lookahead=='_'){while((lookahead<='z'&& lookahead>='a')||(lookahead>='A'&& lookahead<='Z')||lookahead=='_'||lookahead>='0'&&lookahead<='9'){fprintf(result,"%c",lookahead);//写入printf("%c",lookahead);fscanf(resource,"%c",&lookahead);//读}}}int addop()//Addop →+ | -{//分析+，-int i;if(lookahead=='+')//+{match('+');i=islegal();//判断下一个是否是合法字符，如果不是则返回0if(i)return 1;elsereturn 0;}else if(lookahead=='-')//-{match('-');i=islegal();if(i)return 1;elsereturn 0;}elsereturn 0;}int mulop()//mulop →* | / {//分析*，/int i;if(lookahead=='*'){match('*');i=islegal();if(i)return 1;elsereturn 0;}else if(lookahead=='/'){match('/');i=islegal();if(i)return 1;elsereturn 0;}elsereturn 0;}int exp()//exp →term texp{int i,j;while(!feof(resource)){if(lookahead=='('||'0'<=lookahead&&lookahead<='9'||(lookahead<='z'&& lookahead>='a')||(lookahead>='A'&& lookahead<='Z')||lookahead=='_')//FIRST(term)={id, number, ( }{i=term();if(i){j=texp();if(j){return 1;//当且仅当term和texp都返回1时才返回1 }else{return 0;}}else{return 0;}}else{return 0;;}}}int factor()//factor →(exp) | id | number{int i,m,n;if(lookahead=='('){match('(');i=exp();//返回1则继续分析if(lookahead==')'&&i){match(')');return 1;}elsereturn 0;}else if((lookahead<='z'&& lookahead>='a')||(lookahead>='A'&& lookahead<='Z')||lookahead=='_'){id();n=islegal();//判断读出的是否合法，不合法则不必接着分析if(n)return 1;elsereturn 0;}//id分析中自会匹配else if('0'<=lookahead&&lookahead<='9'){number();m=islegal();//判断读出的是否合法，不合法则不必接着分析if(m)return 1;elsereturn 0;}elsereturn 0;}int tterm()//tterm →mulop factor tterm|ε{//mulop,factor都为空或mulop,factor都为真则返回1int i,j,k;i=mulop();j=factor();if(i&&j){k=tterm();//调用自己继续分析直至mulop,factor都为空或仅其中之一返回真值，此时推出该函数return 1;}else if(!i&&!j) //mulop,factor都为空{return 1;}elsereturn 0;}int term()//term→factor tterm {//factor,tterm都为真则返回1 int i,j;i=factor();if(i){j=tterm();if(j)return 1;elsereturn 0;}elsereturn 0;}int texp()//texp →addop term texp | ε{//addop,term为空或addop，term为真int i,j,k;i=addop();j=term();if(i&&j){k=texp();//调用自己继续分析直至addop,term都为空或仅其中之一返回真值，此时推出该函数return 1;}else if(!i&&!j){return 1;//没必要继续向下分析，否则死循环}elsereturn 0;}int islegal()//当为'(',')','+','-','*','/',换行，字母，数字，下划线才合法{if(lookahead=='('||(lookahead<='9'&&lookahead>='0')||lookahead==')'||looka head=='/'||lookahead=='*'||lookahead=='+'||lookahead=='-'||(lookahead<='z'&& lookahead>='a')||(lookahead>='A'&& lookahead<='Z')||lookahead=='_'||lookahead=='\n'){return 1;}elsereturn 0;}void main(){int i;resource=fopen("work.cpp","r");if(resource==NULL){printf("fail to open!");}result=fopen("结果.txt","w");fscanf(resource,"%c",&lookahead);//读一个字符while(lookahead!=EOF){while((lookahead=='\n'||lookahead==' ')&&lookahead!=EOF)//空格或换行则接着读fscanf(resource,"%c",&lookahead);if(lookahead!=EOF){i=exp();//判断}if(i) //返回1{if(lookahead!='\n') //若没有分析到换行，则说明表达式不正确{while(lookahead!='\n')//打印该行{fprintf(result,"%c",lookahead);printf("%c",lookahead);fscanf(resource,"%c",&lookahead);}fprintf(result," error!\n");printf(" error!\n");}else //表达式分析到换行符正确{fprintf(result," right!\n");printf(" right!\n");}}else //返回0{while(lookahead!='\n')//打印该行{fprintf(result,"%c",lookahead);printf("%c",lookahead);fscanf(resource,"%c",&lookahead);}fprintf(result," error!\n");printf(" error!\n");}fscanf(resource,"%c",&lookahead); //读取下一个字符}fclose( result);fclose( resource);}实验结果及其分析：结果：被分析的文件work.cpp#include "stdio.h"#include "string.h"#include<stdio.h>main(){int i;3+466/9e/i&&;(666+op)*y;(p+8+9+i)*lprintf("%c",&i)((y+i)+p)*8i=1fgetc(fp)6+re==1y-6_a1}输出到“结果.txt”中的容：#include "stdio.h" error! #include "string.h" error! #include<stdio.h> error! main() error!{ error!int i; error!3+4 right!66/9 right!e/i right!&&; error!(666+op)*y; error!(p+8+9+i)*l right!printf("%c",&i) error! ((y+i)+p)*8 right!i=1 error!fgetc(fp) error!. .6+re==1 error!y-6 right!_a1 right!} error!分析：这个实验是每行一个表达式，且每行以换行符终结，故需要按行分析并打印输出，且对于每个非终结符的子程序要有返回值以便确定是否继续向下分析。