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

《编译原理》实验报告

实验3 递归下降分析器的设计

姓名学号班级计科1001班

时间： 2012/4/15 地点:文波

同组人：无

指导教师：朱少林

实验目的

使用递归子程序法设计一个语法分析程序，理解自顶向下分析方法的原理，掌握手工编写递归下降语法分析程序的方法。

实验内容

a.运用所学知识，编程实现递归下降语法分析程序。使用递归下降分析算法分析表达

式是否符合下文法：

exp → exp addop term | term

Addop →+ | -

term→ term mulop factor | factor

mulop → * | /

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 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

#include

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();//判断下一个是否是合法字符，如果不是则返回0

if(i)

return 1;

else

return 0;

}

else if(lookahead=='-')//-

{

match('-');

i=islegal();

if(i)

return 1;

else

return 0;

}

else

return 0;

}

int mulop()//mulop → * | /

{

//分析*，/

int i;

if(lookahead=='*')

{

match('*');

i=islegal();

if(i)

return 1;

else

return 0;

}

else if(lookahead=='/')

{

match('/');

i=islegal();

if(i)

return 1;

else

return 0;

}

else

return 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;

}

else

return 0;

}

else if((lookahead<='z'&& lookahead>='a')||(lookahead>='A'&& lookahead<='Z')||lookahead=='_')

{

id();

n=islegal();//判断读出的是否合法，不合法则不必接着分析

if(n)

return 1;

else

return 0;

}//id分析中自会匹配

else if('0'<=lookahead&&lookahead<='9')

{

number();

m=islegal();//判断读出的是否合法，不合法则不必接着分析

if(m)

return 1;

else

return 0;

}

else

return 0;

}

int tterm()//tterm →mulop factor tterm|ε

{//mulop,factor都为空或mulop,factor都为真则返回1

int i,j,k;

i=mulop();

j=factor();

if(i&&j)

{

k=tterm();//调用自己继续分析直至mulop,factor都为空或仅其中之一返回真值，此时推出该函数

return 1;

}

else if(!i&&!j) //mulop,factor都为空

{

return 1;

}

else

return 0;

}

int term()//term→factor tterm

{

//factor,tterm都为真则返回1

int i,j;

i=factor();

if(i)

{

j=tterm();

if(j)

return 1;

else

return 0;

}

else

return 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;//没必要继续向下分析，否则死循环

}

else

return 0;

}

int islegal()//当为'(',')','+','-','*','/',换行，字母，数字，下划线才合法

{

if(lookahead=='('||(lookahead<='9'&&lookahead>='0')||lookahead==')'||lookah ead=='/'||lookahead=='*'||lookahead=='+'||lookahead=='-'

||(lookahead<='z'&& lookahead>='a')||(lookahead>='A'&& lookahead<='Z')||lookahead=='_'||lookahead=='\n')

{

return 1;

}

else

return 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

main()

{

int i;

3+4

66/9

e/i

&&;

(666+op)*y;

(p+8+9+i)*l

printf("%c",&i)

((y+i)+p)*8

i=1

fgetc(fp)

6+re==1

y-6

_a1

}

输出到“结果.txt”中的内容：

#include "stdio.h" error!

#include "string.h" error!

#include 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!

分析：

这个实验是每行一个表达式，且每行以换行符终结，故需要按行分析并打印输出，且对于每个非终结符的子程序要有返回值以便确定是否继续向下分析。还有一点就是对于被分析的文件最后一行不要忘了加上换行符，不然会导致程序死循环。

编译原理实验报告算术表达式递归下降分析程序设计

武汉工程大学计算机科学与工程学院 《编译原理》实验报告 专业班级实验地点 学生学号指导教师 学生姓名实验时间 实验项目实验二、算术表达式递归下降分析程序设计 实验类别操作性（）验证性（）设计性（√）综合性（）其它实 验目的及要求（1）掌握自上而下语法分析的要求与特点。（2）掌握递归下降语法分析的基本原理和方法。（3）掌握相应数据结构的设计方法。 成绩评定表 类别评分标准分值得分合计 上机表现积极出勤、遵守纪律 主动完成实验设计任务 30分 实验报告及时递交、填写规范 内容完整、体现收获 70分 说明： 评阅教师： 日期： 实验内容

一、实验目的 （1）掌握自上而下语法分析的要求与特点。 （2）掌握递归下降语法分析的基本原理和方法。 （3）掌握相应数据结构的设计方法。 二、实验内容 编程实现给定算术表达式的递归下降分析器。 算术表达式文法如下：E→E+T | T T→T*F | F F→(E) | i 设计说明：首先改写文法为LL(1)文法；然后为每一个非终结符，构造相应的递归函数，函数的名字表示规则左部的非终结符；函数体按规则右部符号串的顺序编写。 三、设计分析 （1）消去该文法左递归，得到文法： E→TE1 E1→+TE1|ε T→FT1 T1→*FT1|ε F→(E)| I （2）根据LL（1）文法的判断条件，计算这个文法的每个非终结符的FIRST 集和FOLLOW集，经验证，改后的文法已经是LL（1）文法。 （3）最后构造递归下降分析程序，每个函数名是相应的非终结符，函数体则是根据右部符号串的结构编写。 a.当遇到非终结符时，如：+。 则编写语句if(当读来的输入符号== +) 读下一个输入符号 b.当遇到非终结符时，例如：T。则编写语句调用T()。 c.当遇到非终结符→ε规则时，例如：T→ε。 则编写语句 if(当前读来的输入字符不属于FOLLOW(T)) error() d.当某个非终结符的规则有很多个候选式时。 按LL(1)文法的条件能唯一的选择一个候选式进行推导。 （4）递归下降分析法是确定的自上而下分析法，基本思想是，对文法中的每个非终结符编写一个函数，每个函数的功能是识别由该非终结符所表示的语法成分。因此需要分别构造E,E1,T,T1,F函数来执行自己的识别功能，根据文法的内容顺序决定函数的识别功能。Scaner函数用于字符串的推进，input函数用于字符串的输入。

编译原理课程设计

《编译原理》课程设计大纲 课程编号： 课程名称：编译原理/Compiler Principles 周数/学分：1周/1学分 先修课程：高级程序设计语言、汇编语言、离散数学、数据结构 适用专业：计算机科学与技术专业、软件工程专业 开课学院，系或教研室：计算机科学与技术学院 一、课程设计的目的 课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构表示问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的动手能力。 要求学生在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法编制和程序代码的编写。 设计时间： 开发工具： （1） DOS环境下使用Turbo C； （2） Windows环境下使用Visual C++ 。 （3） 其它熟悉语言。 二、课程设计的内容和要求 设计题一：算术表达式的语法分析及语义分析程序设计。 1.目的

通过设计、编制、调试一个算术表达式的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词 法检查和分析。 2.设计内容及要求： 算术表达式的文法： 〈无符号整数〉∷＝ 〈数字〉{〈数字〉} 〈标志符〉∷＝ 〈字母〉{〈字母〉｜〈数字〉} 〈表达式〉∷＝ [＋｜－]〈项〉{〈加法运算符〉〈项〉} 〈项〉∷＝ 〈因子〉{〈乘法运算符〉〈因子〉} 〈因子〉∷＝ 〈标志符〉｜〈无符号整数〉｜‘（’〈表达式〉‘）’ 〈加法运算符〉∷＝ ＋｜－ 〈乘法运算符〉∷＝ ＊｜／ （1） 分别选择递归下降法、算符优先分析法（或简单优 先法）完成以上任务，中间代码选用逆波兰式。 （2） 分别选择LL（1）、LR法完成以上任务，中间代码选 用四元式。 （3） 写出算术表达式的符合分析方法要求的文法，给出 分析方法的思想，完成分析程序设计。 （4） 编制好分析程序后，设计若干用例，上机测试并通 过所设计的分析程序。 设计题二：简单计算器的设计 1．目的 通过设计、编制、调试一个简单计算器程序，加深对语法及语 义分析原理的理解，并实现词法分析程序对单词序列的词法检 查和分析。 2.设计内容及要求 算术表达式的文法：

WHILE循环语句的翻译程序设计(递归下降法、输出三地址表示)

课程设计任务书 学生姓名：赵旭林专业班级：计算机0801班 指导教师：陈天煌工作单位：计算机科学与技术学院 题目: WHILE循环语句的翻译程序设计（递归下降法、输出三地址表示）初始条件： 理论：学完编译课程，掌握一种计算机高级语言的使用。 实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） （1）写出符合给定的语法分析方法的文法及属性文法。 （2）完成题目要求的中间代码三地址表示的描述。 （3）写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。 （4）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。 （5）设计报告格式按附件要求书写。课程设计报告书正文的内容应包括： 1 系统描述（问题域描述）； 2 文法及属性文法的描述； 3 语法分析方法描述及语法分析表设计； 4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计； 5 编译系统的概要设计； 6 详细的算法描述（流程图或伪代码）； 7 软件的测试方法和测试结果； 8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）； 9 参考文献（按公开发表的规范书写）。 时间安排： 设计安排一周：周1、周2：完成系统分析及设计。 周3、周4：完成程序调试及测试。 周5：撰写课程设计报告。 设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。 设计报告书收取时间：设计周的次周星期一上午10点。 指导教师签名： 2010年 11月 13日 系主任（或责任教师）签名： 2010年 11月 13日

编译原理-递归下降分析法的实现-内附源码

编 译 原 理 实 验 报 告 姓名：关海超 学号：200807010209 专业：计算机科学与技术 班级：08—02班

递归下降分析法的实现 实验要求 递归下降分析法是确定的自上而下分析法，这种分析法要求文法是LL(1)文法。它的基本思想是，对文法中的每个非终结符编写一个函数（或子程序），每个函数（或子程序）的功能是识别由该非终结符所表示的语法成分。由于描述语言的文法通常是递归定义的，因此相应的这组函数（或子程序）必然一相互递归的方式进行调用，所以将此种分析方法称为递归下降分析法。 本实验要求构造下述文法的递归下降分析程序： 文法G[S]: S —> a | ^ | (T) T —> T,S | S 实验内容 首先，消去该文法左递归，得到文法G’[S]: S —> a | ^ | (T) T —> ST’ T’—> ,ST’ | 空串 然后，根据LL(1)文法的判断条件，对非终结符S和T’的不同产生式的SSELECT集进行考察，经验证改进后的文法已经是LL(1)文法。 最后构造递归下降分析程序。每个函数名是相应的非终结符，函数体则是根据规则右部符号串的结构编写。 （1）当遇到终结符a时，则编写语句 if (当前读来的输入符号== a) 读下一个输入符号 （2）当遇到非终结符A时，则编写语句调用A（）。 （3）当遇到A —> 空串规则时，则编写语句 if (当前读来的输入字符不属于FOLLOW(A) ) error() （4）当某个非终结符的规则有很多个候选式是，按LL(1)文法的条件能唯一地选择一个候选式进行推导。 实验结果

实验总结 这次实验内容比较简单。由于有固定的模式来构造程序，因此即使对于其他LL(1)文法也很容易构造其相应的递归下降分析程序。 这次实验我学习了如何将递归下降分析思想具体转化为程序来实现，同时也加深了产生式的Follow集在递归下降分析法中的应用，练习了通过SELECT集判断文法是否为LL(1)文法。 附录（源代码） #include #include #include char token[20]; char sym; int p; void S(); void T(); void U(); void Scaner(); void Error();

递归下降语法分析程序设计

编译方法实验报告实验名称：简单的语法分析程序设计

实验要求 1.功能：对简单的赋值语句进行语法分析 随机输入赋值语句，输出所输入的赋值语句与相应的四元式 2.采用递归下降分析程序完成（自上而下的分析） 3.确定各个子程序的功能并画出流程图 4.文法如下：

5.编码、调试通过 采用标准输入输出方式。输入输出的样例如下： 【样例输入】 x:=a+b*c/d-(e+f) 【样例输出】(说明，语句和四元式之间用5个空格隔开) T1:=b*c (*,b,c,T1) T2:=T1/d (/,T1,d,T2) T3:=a+T2 (+,a,T2,T3) T4:=e+f (+,e,f,T4) T5:=T3-T4 (-,T3,T4,T5) x:=T5 (:=,T5,-,x) 【样例说明】程序除能够正确输出四元式外，当输入的表达式错误时，还应能检测出语法错误，给出相应错误提示。 6.设计3-5个赋值语句测试实例，检验程序能否输出正确的四元式；当输入错误 的句子时，检验程序能够给出语法错误的相应提示信息。 7.报告内容包括： 递归程序的调用过程，各子程序的流程图和总控流程图，详细设计，3-5个测试用例的程序运行截图及相关说明，有详细注释的程序代码清单等。

目录 1.语法分析递归下降分析算法............................... 错误!未定义书签。 背景知识............................................. 错误!未定义书签。 消除左递归........................................... 错误!未定义书签。 2.详细设计及流程图....................................... 错误!未定义书签。 函数void V( ) .|z ................................. 错误!未定义书签。 函数void A( ) 错误!未指定书签。错误!未指定书签。错误!未指定书签。错误!未指定书签。错误!未指定书签。试用例及截图........................ 错误!未定义书签。 测试用例1及截图..................................... 错误!未定义书签。 测试用例2及截图..................................... 错误!未定义书签。 测试用例3及截图..................................... 错误!未定义书签。 代码清单................................................. 错误!未定义书签。

编译原理课程设计报告_LL(1)分析过程模拟

课程设计(论文)任务书 软件学院学院软件工程专业07-1班 一、课程设计(论文)题目LL(1)分析过程模拟 二、课程设计(论文)工作自 2010 年 6 月 22日起至 2010 年 6月 28 日止。 三、课程设计(论文) 地点: 四、课程设计(论文)内容要求： 1．本课程设计的目的 （1）使学生掌握LL（1）模块的基本工作原理； （2）培养学生基本掌握LL（1）分析的基本思路和方法； （3）使学生掌握LL（1）的调试； （4）培养学生分析、解决问题的能力； （5）提高学生的科技论文写作能力。 2．课程设计的任务及要求 1）基本要求： （1）分析LL（1）模块的工作原理； （2）提出程序的设计方案； （3）对所设计程序进行调试。 2）创新要求： 在基本要求达到后，可进行创新设计，如改算法效率。 3）课程设计论文编写要求 （1）要按照书稿的规格打印誊写课程设计论文 （2）论文包括目录、绪论、正文、小结、参考文献、附录等 （3）课程设计论文装订按学校的统一要求完成 4）答辩与评分标准： （1）完成原理分析：20分； （2）完成设计过程（含翻译）：40分； （3）完成调试：20分；

（4）回答问题：20分。 5）参考文献： （1）张素琴，吕映芝，蒋维杜，戴桂兰.编译原理（第2版）.清华大学出版社 （2）丁振凡.《Java语言实用教程》北京邮电大学出版社 6）课程设计进度安排 内容天数地点 构思及收集资料2图书馆 编程与调试4实验室 撰写论文1图书馆、实验室 学生签名： 2009 年6 月22 日 课程设计(论文)评审意见 （1）完成原理分析（20分）：优（）、良（）、中（）、一般（）、差（）；（2）设计分析（20分）：优（）、良（）、中（）、一般（）、差（）；（3）完成调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）翻译能力（20分）：优（）、良（）、中（）、一般（）、差（）；（5）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（） 评阅人：职称： 年月日

编译原理-递归下降子程序-课程设计报告

编译原理课程设计报告 2011 年 12 月 2 日 设计题目 递归下降分析程序的实现 学 号 专业班级 计算机科学与技术 学生姓名 指导教师

一、实验目的: （1）掌握自上而下语法分析的要求与特点。 (2）掌握递归下降语法分析的基本原理和方法。 （3)掌握相应数据结构的设计方法。 二、实验内容: 递归下降分析程序的实现 设计内容及要求： 对文法 G： E→E+T｜Ｔ构造出G的递归下降分析程序。程序显示输出T→T*F|Ｆ匹配过程（即自上而下生成语法分析树的步骤， F→（E）|i 输出各匹配产生式序号即可）。 三、设计思路： (１)语法分析: 语法分析是编译程序的核心部分，任务是分析一个文法的句子结构。递归下降分析程序的实现的功能:按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子（合式程序）。 （2)自上而下分析: 从文法的开始符号出发,向下推导,推出句子。可分为带“回溯”的和不带回溯的递归子程序(递归下降)分析方法。 它的主旨是对任何输入串，试图用一切可能的办法,从文法开始符号(根结点）出发，自上而下地为输入串建立一棵语法树。或者说,为输入串寻找一个最左推导。也即从文法的开始符号出发，反复使用各种产生式，寻找"匹配＂的推导。 (3)递归下降分析法： 对每一语法变量(非终结符)构造一个相应的子程序,每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。 (４）分析过程中遇到的问题: a. 分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时,不得不“回溯”。 b．文法左递归问题。含有左递归的文法将使自上而下的分析陷入无限循环。 (5)构造不带回溯的自上而下分析算法： ａ.要消除文法的左递归性：一个文法可以消除左递归的条件是①不含以 为右部的产生式②不含回路。

编译原理课程设计

编译原理课程设计报告 课题名称： C-语言编译器设计（scanner和parser） 提交文档学生姓名： 提交文档学生学号： 同组成员名单：无 指导教师姓名：金军 指导教师评阅成绩： 指导教师评阅意见： . . 提交报告时间： 2011年 6 月 17 日

1.课程设计目标 设计C-Minus编译器分为scanner和parser两个部分。scanner主要作用是对目标代码进行扫描，列出关键字，变量等内容；parser主要对语法进行分析并生成语法树。 2.分析与设计 ●实现方法：代码用C语言编译而成。其中scanner为手工实现，主要采用switch-case结构实现 状态转换；parser部分采用递归下降分析方法实现。 ●扫描器：C-的词法如下： 1、语言的关键字：i f el se i nt return void while 2、专用符号：+ - * /< <= > >= == != =; , ( ) [ ] { } /* */ 3、其他标记是变量（ID）和数字（NUM），通过下列正则表达式定义： ID = letter letter* NUM = di git digi t* letter = a|..|z|A|..|Z digi t = 0|..|9 4、空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开ID、NUM关键字 5. 注释用通常的C语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在 标记内)上，且可以超过一行。注释不能嵌套 其DFA图如下：

分析器：以下为C-的语法规则BNF:

编译原理课程设计报告(一个完整的编译器)

编译原理程序设计报告 一个简单文法的编译器的设计与实现专业班级：计算机1406班 组长姓名：宋世波 组长学号： 20143753 指导教师：肖桐 2016年12月

设计分工 组长学号及姓名：宋世波20143753 分工：文法及数据结构设计 词法分析 语法分析（LL1） 基于DAG的中间代码优化 部分目标代码生成 组员1学号及姓名：黄润华20143740 分工：中间代码生成(LR0) 部分目标代码生成 组员2学号及姓名：孙何奇20143754 分工：符号表组织 部分目标代码生成

摘要 编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译是从源代码（通常为高阶语言）到能直接被计算机或虚拟机执行的目标代码（通常为低阶语言或机器语言）的翻译过程。 一．编译器的概述 1.编译器的概念 编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译器将原始程序作为输入，翻译产生使用目标语言的等价程序。源代码一般为高阶语言如Pascal、C++、Java 等，而目标语言则是汇编语言或目标机器的目标代码，有时也称作机器代码。 2．编译器的种类 编译器可以生成用来在与编译器本身所在的计算机和操作系统（平台）相同的环境下运行的目标代码，这种编译器又叫做“本地”编译器。另外，编译器也可以生成用来在其它平台上运行的目标代码，这种编译器又叫做交叉编译器。交叉编译器在生成新的硬件平台时非常有用。“源码到源码编译器”是指用一种高阶语言作为输入，输出也是高阶语言的编译器。例如: 自动并行化编译器经常采用一种高阶语言作为输入，转换其中的代码，并用并行代码注释对它进行注释（如OpenMP）或者用语

编译原理-编写递归下降语法分析器

学号107 成绩 编译原理上机报告 名称：编写递归下降语法分析器 学院：信息与控制工程学院 专业：计算机科学与技术 班级：计算机1401班 姓名：叶达成 2016年10月31日

一、上机目的 通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目标： 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、基本原理和上机步骤 递归下降分析程序实现思想简单易懂。程序结构和语法产生式有直接的对应关系。因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。 递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。 每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。 自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术，当选择某非终结符的产生时，可根据输入串的当前符号以及各产生式右部首符号而进行，效率高，且不易出错。 无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。 无左递归：既没有直接左递归，也没有间接左递归。 无回溯：对于任一非终结符号U的产生式右部x1|x2|…|x n，其对应的字的首终结符号两两不相交。 如果一个文法不含回路（形如P?+ P的推导），也不含以ε为右部的产生式，那么可以通过执行消除文法左递归的算法消除文法的一切左递归（改写后的文法可能含有以ε为右部的产生式）。 三、上机结果 测试数据： (1)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (2)输出结果：i+i*i#为合法符号串 (3)输入一符号串如i+i*#,要求输出为“非法的符号串”。 程序清单： #include #include char str[50]; int index=0; void E(); //E->TX; void X(); //X->+TX | e void T(); //T->FY void Y(); //Y->*FY | e void F(); //F->(E) | i int main() /*递归分析*/ { int len; int m;

CMinus词法分析和语法分析设计编译器编译原理课程设计报告书

编译原理课程设计报告 课题名称：C- Minus词法分析和语法分析设计 提交文档学生姓名：X X X 提交文档学生学号：XXXXXXXXXX 同组成员名单：X X X 指导教师姓名：X X 指导教师评阅成绩： 指导教师评阅意见： . . 提交报告时间：2015年6月10日

1.课程设计目标 实验建立C-编译器。只含有扫描程序（scanner）和语法分析（parser）部分。 2.分析与设计 C-编译器设计的整体框架，本实验实现扫描处理和语法分析程序（图中粗黑部分）。 2.1 、扫描程序scanner部分 2.1.1系统设计思想 设计思想：根据DFA图用switch-case结构实现状态转换。 惯用词法：

①语言的关键字：else if int return void while ②专用符号：+ - * / < <= > >= == != = ; , ( ) [ ] { } /* */ ③其他标记是ID和NUM，通过下列正则表达式定义： ID = letter letter* NUM = digit digit* letter = a|..|z|A|..|Z digit = 0|..|9 大写和小写字母是有区别的 ④空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开ID、NUM 关键字。 ⑤注释用通常的C语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以超过一行。注释不能嵌套 scanner的DFA

说明：当输入的字符使DFA到达接受状态的时候，则可以确定一个单词了。初始状态设置为START，当需要得到下一个token时，取得次token的第一个字符，并且按照DFA与对此字符的类型分析，转换状态。重复此步骤，直到DONE为止，输出token类型。当字符为“/”时，状态转换为SLAH再判断下一个字符，如果为“*”则继续转到INCOMMENT，最后以“*”时转到ENDCOMMENT状态，表明是注释，如果其他的则是字符停滞于当前字符，并且输出“/”。 2.1.2程序流程图

《编译原理》课程设计题目-2014

《编译原理》课程设计题目 设计题一：正规式r与正规文法G相互转换的程序设计 任意给定一个正规式，求出其对应的正规文法；任意给定一个正规文法，求出其对应的正规式。（参考教材P53～55） 设计题二：布尔表达式的递归下降翻译器 针对布尔表达式的文法： 〈布尔表达式〉∷＝〈布尔项〉{〈与运算符〉〈布尔项〉} 〈与运算符〉∷＝and 〈布尔项〉∷＝〈布尔因子〉{〈或运算符〉〈布尔因子〉} 〈或运算符〉∷＝or 〈布尔因子〉∷＝〈非运算符〉〈布尔因子〉｜〈布尔量〉 〈非运算符〉∷＝not 〈布尔量〉∷＝（〈布尔表达式〉）｜〈标识符〉〈关系运算符〉〈标识符〉｜ true｜false 〈关系运算符〉∷＝＞｜＜｜≥｜≤｜＝｜≠ 〈标识符〉∷＝〈字母〉{〈字母〉｜〈数字〉} 利用递归下降分析法编制、调试其语法及语义分析程序，生成的中间代码为逆波兰式。编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（参考教材P92～93） 设计题三：正规式r与有穷自动机FA相互转换的程序设计 任意给定一个正规式，求出其对应的有穷自动机；任意给定一个有穷自动机，求出其对应的正规式。（参考教材P61～64） 设计题四：赋值语句的LR翻译程序 对教材P180中的赋值语句文法，给出该文法的属性文法，同时实现赋值语句的翻译，生成的中间代码为逆波兰式。（参考教材P179～181） 设计题五：正规文法G与有穷自动机FA相互转换的程序设计 任意给定一个正规文法，求出其对应的有穷自动机；任意给定一个有穷自

动机，求出其对应的正规文法。（参考教材P65～66） 设计题六：条件语句的LR翻译程序 对教材P187中的条件语句文法，给出该文法的属性文法，同时实现条件语句的翻译，生成的中间代码为四元式。（参考教材P186～189） 设计题七：NFA确定化为DFA及化简的程序设计 任意给定一个NFA，将其确定化为DFA，然后化简为最小的DFA。（参考教材P57～61） 设计题八：布尔表达式的LR翻译器 针对布尔表达式的文法： B →B and T | T T→T or F | F F→not F|true｜false |（B）| i rop i 利用LR分析法编制、调试其语法及语义分析程序，生成的中间代码为四元式。编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（参考教材P181～182） 设计题九：生成预测分析表的算法实现 任意给定一个LL(1)文法，生成相应的LL(1)分析表。（参考教材P75第5章） 设计题十：while循环语句的LR翻译程序 对教材P187中的循环语句文法，给出该文法的属性文法，同时实现循环语句的翻译，生成的中间代码为四元式。（参考教材P186～189） 设计题十一：利用LEX自动生成词法分析程序 输入描述某种语言词法规则的正规式，利用LEX自动生成词法分析程序。（参考教材P66～68） 设计题十二：生成LR分析表的算法实现 任意给定一个LR文法，生成相应的LR分析表。（参考教材P123第7章） 设计题十三：布尔表达式翻译为逆波兰式的算法实现 针对布尔表达式的二义性文法： B → B and B | B or B | not B | ( B ) | true｜false| i rop i 将文法拓广为G’[B’]： (0) B’ → B

(重庆理工大学计算机学院)编译原理课程设计报告

编译原理课程设计报告 实验名称编译原理课程设计 班级 学号 姓名 指导教师 实验成绩 2013 年06月

一、实验目的 通过设计、编写和调试，将正规式转换为不确定的有穷自动机，再将不确定的有穷自动机转换为与之等价的确定的有穷自动机，最后再将确定有穷自动机进行简化。 通过设计、编写和调试构造LR(0)项目集规范簇和LR分析表、对给定的符号串进行LR分析的程序，了解构造LR(0)分析表的步骤，对文法的要求，能够从文法G出发生成LR(0)分析表，并对给定的符号串进行分析。 二、实验内容 正规式——>NFA——>DFA——>MFA 1.正规式转化为不确定的有穷自动机 （1）目的与要求 通过设计、编写和调试将正规式转换为不确定的有穷自动机的程序，使学生了解Thompson算法，掌握转换过程中的相关概念和方法，NFA的表现形式可以是表格或图形。 （2）问题描述 任意给定一个正规式r（包括连接、或、闭包运算），根据Thompson算法设计一个程序，生成与该正规式等价的NFA N。 （3）算法描述 对于Σ上的每个正规式R，可以构造一个Σ上的NFA M，使得L(M)=L(R)。 步骤1：首先构造基本符号的有穷自动机。 步骤2：其次构造连接、或和闭包运算的有穷自动机。

（4）基本要求 算法实现的基本要求是： (1) 输入一个正规式r； (2) 输出与正规式r等价的NFA。（5）测试数据 输入正规式：(a|b)*(aa|bb)(a|b)* 得到与之等价的NFA N

（6）输出结果 2.不确定的有穷自动机的确定化 （1）目的与要求 通过设计、编写和调试将不确定的有穷自动机转换为与之等价的确定的有穷自动机的程序，使学生了解子集法，掌握转换过程中的相关概念和方法。DFA的表现形式可以是表格或图形。（2）问题描述 任意给定一个不确定的有穷自动机N，根据算法设计一个程序，将该NFA N变换为与之等价的DFA D。 （3）算法描述 用子集法将NFA转换成接受同样语言的DFA。 步骤一：对状态图进行改造 (1) 增加状态X,Y,使之成为新的唯一的初态和终态。从X引ε弧到原初态结点, 从原终态结 点引ε弧到Y结点。 (2) 对状态图进一步进行如下形式的改变

编译原理-实验报告2-递归下降分析法

计算机硬件实验室实验报告 一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、实验要求： 对下列文法，用递归下降分析法对任意输入的符号串进行分析： （1）E->TG （2）G->+TG|—TG （3）G->ε （4）T->FS （5）S->*FS|/FS （6）S->ε （7）F->(E) （8）F->i 输出的格式如下： (1)递归下降分析程序，编制人：姓名，学号，班级 (2)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (3)输出结果：i+i*i#为合法符号串 备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。 注意： 1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符i，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 三、实验过程：

程序设计： 1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。 2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。 程序编写： 1.定义部分：定义常量、变量、数据结构。 2.初始化：从文件将输入符号串输入到字符缓冲区中。 3.利用递归下降分析法，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。 四、实验结果 （1）程序流程图 （2）运行结果 示例程序： #include <> #include<> #include<> #include<> char a[50] ,b[50],d[500],e[10]; char ch; int n1,i1=0,flag=1,n=5; int E(); int E1(); int T(); int G();

编译原理课程设计

编译原理课程设计 自顶向下语法分析器 学院（系）：计算机科学与技术学院学生姓名：xxxxxxxxx 学号：xxxxxxxxx 班级：电计1102 大连理工大学 Dalian University of Technology

目录

1 系统概论 语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器在编译程序中的地位如图1所示： 图1 语法分析器在编译程序中的地位 语言的语法结构是用上下文无关文法描述的。因此，语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子。这里所说的输入串是指由单词符号（文法的终结符）组成的有限序列。对一个文法，当给你一串（终结）符号时，怎样知道它是不是该文法的一个句子呢？这就要判断，看是否能从文法的开始符号出发推导出这个输入串。或者，从概念上讲，就是要建立一棵与输入串相匹配的语法分析树。 自顶向下分析法就是语法分析办法中的一类。顾名思义，自顶向下就是从文法的开始符号出发，向下推导，推出句子。这种方法是带“回溯”的。 自顶向下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。 实现这种自顶向下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序。每个这种子程序可作为一个布尔过程。一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值；否则，保持原来的语法树和IP值不变，并返回“假”值。 2 需求分析 以前，人们对语法的分析都建立在人工的基础上，人工分析虽然能够做到侧类旁推，但终究人力有限，再精密的分析都会出现或多或少的错误。为减少因人为产生的错误，并加快

递归下降分析器设计与实现

实验二递归下降分析器设计与实现 1、实验目的： （1）掌握自上而下语法分析的要求与特点。 （2）掌握递归下降语法分析的基本原理和方法。 （3）掌握相应数据结构的设计方法。 2、实验内容： 编程实现给定算术表达式的递归下降分析器。 算术表达式文法如下： E-->E+T|T T-->T*F|F F-->(E)|i 3、设计说明： 首先改写文法为LL(1)文法；然后为每一个非终结符，构造相应的递归过程，过程的名字表示规则左部的非终结符；过程体按规则右部符号串的顺序编写。4、设计分析 这个题目属于比较典型的递归下降语法分析。需要先将原算术表达式方法改写为LL(1)文法为： E-->TE' E'-->+TE'|ε T-->FT' T'-->*FT'|ε F-->(E)|i 然后再为每个非终结符设计一个对应的函数，通过各函数之间的递归调用从而实现递归下降语法分析的功能。具体方法为： （1）当遇到终结符a时，则编写语句 If(当前读到的输入符号==a)读入下一个输入符号 （2）当遇到非终结符A时，则编写语句调用A()。 （3）当遇到A-->ε规则时，则编写语句 If(当前读到的输入符号不属于Follow(A))error() （4）当某个非终结符的规则有多个候选式时，按LL(1)文法的条件能唯一地选择一个候选式进行推导. 5、程序代码 #include void E(); void T(); void E1(); void T1(); void F();

char s[100]; int i, SIGN; int main() { printf("请输入一个语句，以#号结束语句（直接输入#号推出）\n"); while( 1 ) { SIGN = 0; i=0; scanf("%s",&s); if( s[0] == '#') return 0; E(); if(s[i]=='#') printf("正确语句！\n"); printf("请输入一个语句，以#号结束语句\n"); } return 1; } void E() { if(SIGN==0) { T(); E1(); } } void E1() { if(SIGN==0) {

编译原理课程设计报告

2011-2012学年第二学期 《编译原理》课程设计报告 学院：计算机科学与工程学院 班级： 学生姓名：学号： 成绩： 指导教师： 时间：2012年5 月

目录 一、课程设计的目的 ---------------------------------------------------------------- - 1 - 二、课堂实验及课程设计的内容 -------------------------------------------------- - 1 - 2.1、课堂实验内容-------------------------------------------------------------- - 1 - 2.2、课程设计内容-------------------------------------------------------------- - 1 - 三、visual studio 2008 简介------------------------------------------------------- - 2 - 四、问题分析及相关原理介绍 ----------------------------------------------------- - 3 - 4.1、实验部分问题分析及相关原理介绍 ---------------------------------- - 3 - 4.1.1、词法分析功能介绍及分析------------------------------------- - 3 - 4.1.2、语法分析功能介绍及分析------------------------------------- - 3 - 4.1.3、语义分析功能介绍及分析------------------------------------- - 4 - 4.2、课程设计部分问题分析及相关原理介绍 ---------------------------- - 5 - 4.2.1、编译程序介绍 ----------------------------------------------------- - 5 - 4.2.2、对所写编译程序的源语言的描述（C语言） -------------- - 6 - 4.2.3、各部分的功能介绍及分析 -------------------------------------- - 7 - 4.3、关键算法：单词的识别-------------------------------------------------- - 8 - 4.3.1、算法思想介绍 ----------------------------------------------------- - 8 - 4.3.2、算法功能及分析 -------------------------------------------------- - 8 - 五、设计思路及关键问题的解决方法 ------------------------------------------ - 10 - 5.1、编译系统------------------------------------------------------------------ - 10 - 5.1.1、设计思路 --------------------------------------------------------- - 10 - 5.2、词法分析器总控算法--------------------------------------------------- - 12 - 5.2.1、设计思路 --------------------------------------------------------- - 12 - 5.2.2、关键问题及其解决方法 --------------------------------------- - 13 - 六、结果及测试分析-------------------------------------------------------------- - 14 - 6.1、软件运行环境及限制--------------------------------------------------- - 14 - 6.2、测试数据说明------------------------------------------------------------ - 14 - 6.3、运行结果及功能说明--------------------------------------------------- - 16 - 6.4、测试及分析说明--------------------------------------------------------- - 16 - 七、总结及心得体会 --------------------------------------------------------------- - 17 - 7.1、设计过程------------------------------------------------------------------ - 17 - 7.2、困难与收获 ------------------------------------------------------------- - 17 - 八、参考文献 ------------------------------------------------------------------------ - 18 -

编译原理-实验二-递归下降分析程序构造

集美大学计算机工程学院实验报告 课程名称：编译原理 指导教师：付永钢 实验成绩： 实验编号： 实验二 实验名称：递归下降分析程序构造 班级：计算12 姓名： 学号： 上机实践日期：2014.11 上机实践时间： 4学时 一、实验目的 通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目标： (1) 掌握从源程序文件中读取有效字符的方法和产生源程序内部表示文件的方法； (2)掌握语法分析的实现方法； (3)上机调试编出的语法分析程序。 二、实验环境 Windows7 x64、VC6.0 三、实验原理 递归下降法是语法分析中最易懂的一种方法。它的主要原理是，对每个非终结符按其产生式结构构造相应语法分析子程序，其中终结符产生匹配命令，而非终结符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。 递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。 自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术，可根据输入串的当前符号以及各产生式右部首符，选择某非终结符的产生式，效率高，且不易出错。 无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。即：假设A 的全部产生式为A →α1|α2|……|αn ，则必须满足如下条件才能保证可以唯一的选择合适的产生式 First(A →αi )∩First (A →αj )=Φ,当i≠j. 无左递归：既没有直接左递归，也没有间接左递归。 无回溯：对于人以非中介符号U 的产生式右部n x x x |...||21，其对应的字的首终结符号两两不相交。 如果一个文法不含回路（形如P P +?的推导），也不含以ε为右部的产生式，那么可以通过执行消除左递归的算法消除文法的一切左递归。 四、实验内容 完成以下描述算术表达式的LL(1)文法的递归下降分析程序构造 G[E]: E →TE ′ E ′→+TE ′|ε T →FT ′