编译原理实验指导书(2008-2009)

1、编译原理实验指导书合肥学院计算编译原理实验指导书实验一 词法分析一、实验目的： 通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）二、实验预习提示 1、  词法分析器的功能和输出格式词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式(单词

2、种别码，单词符号的属性值)。本实验中，采用的是一类符号一种别码的方式。2、  单词的BNF表示<标识符><字母><字母数字串><字母数字串<字母><字母数字串>|<数字><字母数字串>|<下划线><字母数字串|<无符号整数<数字><数字串><数字串><数字><数字串> |<加法运算符> +<减法运算符> -<大于关系运算符>><大于等于关系运算符>>=3

3、、“超前搜索”方法词法分析时，常常会用到超前搜索方法。如当前待分析字符串为“>=”,当前字符为>，此时，分析器倒底是将其分析为大于关系运算符还是大于等于关系运算符呢？显然，只有知道下一个字符是什么才能下结论。超前读了一个字符=，所以要回退一个字符，词法分析器才能正常运行。在分析标识符，无符号整数等时也有类似情况。4、模块结构三、实验过程和指导： （一）准备：1.阅读课本有关章节，明确语言的语法，写出基本保留字、标识符、常数、运算符、分隔符和程序例。2.初步编制好程序。3.准备好多组测试数据。（二）上课上机： 将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。（三）程

4、序要求：程序输入/输出示例：如源程序为C语言。输入如下一段：main()                                            

5、                             int a,b;a = 10; b = a + 20;要求输出如下图。（2，”main”）（5，”（“）（5，”）“）（5，”“）（1，”int”）（2，”a”）（5，”,”）（2，”b”）（5，”;”）（2，”a”）（4，”=”）（3，”10”）（5，”;”）

6、（2，”b”）（4，”=”）（2，”a”）（4，”+”）（3，”20”）（5，”;”）（5，”“）要求：识别保留字：if、int、for、while、do、return、break、continue；单词种别码为1。其他的都识别为标识符；单词种别码为2。常数为无符号整形数；单词种别码为3。运算符包括：+、-、*、/、=、<、=、<=、!= ；单词种别码为4。分隔符包括：,、;、(、)； 单词种别码为5。（四）程序思路（仅供参考）：这里以开始定义的C语言子集的源程序作为词法分析程序的输入数据。在词法分析中，自文件头开始扫描源程序字符，一旦发现符合“单词”定义的源程序字符串时，将它翻译

7、成固定长度的单词内部表示，并查填适当的信息表。经过词法分析后，源程序字符串（源程序的外部表示）被翻译成具有等长信息的单词串（源程序的内部表示），并产生两个表格：常数表和标识符表，它们分别包含了源程序中的所有常数和所有标识符。0.定义部分：定义常量、变量、数据结构。1.初始化：从文件将源程序全部输入到字符缓冲区中。2.取单词前：去掉多余空白。3.取单词后：去掉多余空白（可选，看着办）。4.取单词：利用实验一的成果读出单词的每一个字符，组成单词，分析类型。（关键是如何判断取单词结束？取到的单词是什么类型的单词？）5.显示结果。（五）练习该实验的目的和思路：程序开始变得复杂起来，可能是大家目前编过的

8、程序中最复杂的，但相对于以后的程序来说还是简单的。因此要认真把握这个过渡期的练习。本实验和以后的实验相关。通过练习，掌握对字符进行灵活处理的方法。（六）设计要求1、 用Java编写,最好有图形界面2、给出各单词符号的类别编码。3、词法分析程序应能发现输入串中的错误。4、词法分析作为单独一遍编写，词法分析结果为二元式序列组成的中间文件。5、设计两个测试用例（尽可能完备），并给出测试结果。 6、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。实验二 递归下降分析法一、实验目的：     根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进

9、行分析。本次实验的目的主要是加深对递归下降分析法的理解。二、实验预习提示 1、递归下降分析法的功能词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。2、递归下降分析法的前提改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法，3、递归下降分析法实验设计思想及算法为G的每个非终结符号U构造一个递归过程,不妨命名为U。U的产生式的右边指出这个过程的代码结构：(1)若是终结符号，则和向前看符号对照，若匹配则向前进一个符号；否则出错。(2)若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现。具体为：（1）对于每个非终结符号UX

10、1| X2| Xn处理的方法如下：U( )Read(ch);/当前符号If ch in First(X1) 调用X1的子程序;else if ch in First(X2) 调用X2的子程序;else error()（2）对于每个右部X1Y1 Y 2Y n的处理架构如下：调用Y1的子程序;调用Y 2的子程序；调用Y n的子程序（3）如果右部为空，则不处理。（4）对于右部中的每个符号Yi 如果Yi为终结符号：if(Yi= = 当前的符号) Read(ch);/ return; else error() 如果Yi为非终结符号，直接调用相应的子过程Yi()三、实验过程和指导： （一）准备： 1.阅读

11、课本有关章节，2.考虑好设计方案；3.设计出模块结构、测试数据，初步编制好程序。（二）上课上机： 将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。（三）程序要求：程序输入/输出示例： 对下列文法，用递归下降分析法对任意输入的符号串进行分析： （1）ETG（2）G+TG|TG（3）G（4）TFS（5）S*FS|/FS（6）S（7）F(E)（8）Fi输出的格式如下：(1)递归下降分析程序，编制人：姓名，学号，班级(2)输入一以#结束的符号串(包括+*/（）i#)：在此位置输入符号串例如：i+i*i# (3)输出结果：i+i*i#为合法符号串  备注：输入一符号串如i+i

12、*#,要求输出为“非法的符号串”。引用也要改变）。注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符I，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；3.对学有余力的同学，可以详细的输出推导的过程，即详细列出每一步使用的产生式。  （四）程序思路（仅供参考）：0.定义部分：定义常量、变量、数据结构。1.初始化：从文件将输入符号串输入到字符缓冲区中。2.利用递归下降分析法分析，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。（五）练习该实验的目的和思路： 程序开始变得复杂起来，需要利用到程序设计语言的知识和大量编程技巧，递归下降

13、分析法是一种较实用的分析法，通过这个练习可大大提高软件开发能力。通过练习，掌握函数间相互调用的方法。（六）为了能设计好程序，注意以下事情：1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。实验三 LL(1)分析法一、实验目的：      根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL（1）分析法的理解。二、实验预习提示 1、LL（1）分析

14、法的功能LL（1）分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号以及LL（1）分析表，对输入符号串自上而下的分析过程。2、LL（1）分析法的前提改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法，3、LL（1）分析法实验设计思想及算法三、实验过程和指导： （一）准备： 1.阅读课本有关章节，2.考虑好设计方案；3.设计出模块结构、测试数据，初步编制好程序。（二）上课上机： 将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。（三）程序要求：程序输入/输出示例： 对下列文法，用LL（1）分析法对任意输入的符号串进行分析： （1）ETG（2）G

15、+TG|TG（3）G（4）TFS（5）S*FS|/FS（6）S（7）F(E)（8）Fi输出的格式如下：(1)LL（1）分析程序，编制人：姓名，学号，班级(2)输入一以#结束的符号串(包括+*/（）i#)：在此位置输入符号串 (3)输出过程如下：  步骤 分析栈 剩余输入串 所用产生式 1Ei+i*i#E-TG  (4)输入符号串为非法符号串(或者为合法符号串)  备注：(1)在“所用产生式”一列中如果对应有推导则写出所用产生式；如果为匹配终结符则写明匹配的终结符；如分析异常出错则写为“分析出错”；若成功结束则写为“分析成功”。(2) 在此位置输入符号串为用户自行输

16、入的符号串。(3)上述描述的输出过程只是其中一部分的。   注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符i，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；  （四）程序思路（仅供参考）：模块结构：（1）定义部分：定义常量、变量、数据结构。（2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；（3）控制部分：从键盘输入一个表达式符号串；

17、（4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。（五）练习该实验的目的和思路： 程序相当复杂，需要利用到大量的编译原理，也用到了大量编程技巧和数据结构，通过这个练习可大大提高软件开发能力。（六）为了能设计好程序，注意以下事情：1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。实验四 算符优先文法处理 一、实验目的掌握算符优先分析法的原理

18、，利用算符优先分析法将赋值语句进行语法分析，翻译成等价的四元式表示。二、实验内容： 1.算术表达式的文法可以是（你可以根据需要适当改变）：  EE+E|E-E|E*E|E/E|（E）|i 2.根据算符优先分析法，将表达式进行语法分析，判断一个表达式是否正确。 3.将赋值语句进行语法分析，翻译成等价的一组基本操作，每一基本操作用四元式表示。 三、实验预习提示 1.实验原理  我们要分析的表达式满足下面的算符优先矩阵 21 +  -  *  /  (  )   +  >&#

19、160; >  <  <  <  >  > -  > >  <  <  <  > >  *  >  >  >  >  <  >  >  /  >  >  >  >  <  > 

20、0;>  (  <  <  <  <  <  =  )  >  >  >  >  >  >   <  <  <  <  <  =为实现算符优先算法，可以使用两个工作栈。一个叫做OPTR，用以寄存运算符，一个叫OPND,用以寄存操作数或结果。算法描述如下：  1首先置操作数栈为空

21、栈，将表达式起始符;作为运算符栈的栈底元素。 2依次读入表达式中每个单词，若是操作数则进OPND栈，若是运算符则转3。  3将此运算符1与OPTR栈顶元素2进行比较，即查上表，若 12，则：1进栈，转2 若 12 ,如1为；，则分析成功，否则OPTR栈顶元素出栈，并转2 若 1<2,则出栈OPND栈顶元素至b，又出栈其栈顶元素至a，出栈OPTR栈顶元素至t，进行运算r=a t b(t 为运算符)，并将结果r存入栈OPND后转3。 若1和2之间无优先关系，则报错。  四、实验步骤（一)准备：

22、 1. 阅读课本有关章节，花一周时间确定算术表达式的文法，设计出算符优先关系表； 2.考虑好设计方案； 3. 设计出模块结构、测试数据，初步编制好程序。 (二)上课上机：上机调试，发现错误，分析错误，再修改完善。教师根据学生的设计方案与学生进行探讨，以修改方案和代码。(三）程序要求： 程序思路（仅供参考）： 1.借用实验一的结果，可将其中的取字符函数几乎原封不动地移植过来，其中的分割和分析单词的方法可借用过来分割现在这个实验的运算符、常量和变量。2.模块结构：（1）初始化：设立算符优先关系表（或优先函数）、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；（2

23、）控制部分：将一个表达式从文件中读出；（3）词法分析：将表达式分割成单词序列；（4）利用算符优先文法进行表达式处理：根据算符优先关系表（或优先函数）对表达式单词序列进行堆栈（或其他）操作，得到并保存四元组，如果遇到错误则显示错误信息；（5）输出四元组。 3.程序输入/输出示例： 如参考C语言的运算符。输入如下表达式（以分号为结束）和输出结果： （1）10; 输出：正确 （2）1+2; 输出：正确 （3）(1+2)/3+4-(5+6/7); 输出：正确（4）(1-2)/3+4 输出：错误 （5）1+2-3+(*4/5) 输出：错误 注意：1.为降低难度，表达式中不含变量（只含无符号整数）；2.如

24、果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 3.测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照； 4.对学有余力的同学，可增加功能：当判断一个表达式正确时，输出计算结果，计算过程用浮点表示，但要注意不要被0除。附实验报告范例实验名称：词法分析 一、实验目的和要求 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。 二、实验内容和步骤：实验内容 对于这个实验，我总共用了四个函数，即主函数、扫描函数、建立缓冲区、取单词。主要完成的

25、功能是从缓冲区中识别出一个个单词，并能够区分所取的单词是什么类型。 实验步骤 1、基于实验的内容，构造程序所需的模块 2、根据已建构的模块，写出各个模块的相应程序代码 3、在主函数中调用模块来完成所要得到的效果 在此，我想先介绍一下我的三个子模块，第一个是扫描函数。扫描函数scanner()，其实大家都比较熟悉了，就是我们上次实验内容，可以原封不动的拿来用。它的功能是调用一次就从缓冲区中取一个字符出来。这为我们的取字符提供了基础，因此如果这个程序不会设计的话，那么这个实验就没法设计了。至于建立第二个模块，就是从文件中把一个个字符读到缓冲区，比较简单，我在这里就不想说了。接下来，我想比较地说一下

26、第三个模块，也就是本实验的主要要求。这个模块的函数程序代码如下： char getsym()/从缓冲区中取一个单词  bool flag=false;/用来表示取出的单词是否为关键词，如果是则flag的值为true,否则为false  int k=-1; /表示取出的字符放在单词数组的指针  CType='0' /预先定义的取出的单词的类型 Lasttype='0' /初始化先前的类型，此变量为判断正负数用  while (ch<=32&

27、#160;&& ch>0)/去掉不能显示的字符 Fbuffer=scanner();  if (ch>='a'&& ch<='z'| ch>='A'&& ch<='Z')/取出标识符或者是关键词   k=-1;  while(true)/取出的单词长度不超过WMaxlen，如果超过，则其后的字符无效    if(+k)<WMaxl

28、en)/(+k)为了使取出的单词最长为WMaxlen   Wordk=ch;   Fbuffer=scanner(); /如果取出的当前的字符不是字母或是数字，则此次取单词结束 if (!(ch>='a'&& ch<='z'| ch>='A'&& ch<='Z'|ch>='0' && ch<='9')  br

29、eak;     Word+k='0'/以'0'标识取出单词的结束，以方便后面的判断此单词是标识符还是关键词  for (int i=0;i<KEY_No;i+)/用来判断取出的当前单词是不是关键词 if (strcmp(Word,KEYi)=0)     flag=true; break;    if (flag) CType='1'/如果是关键词，则把此单词的类型定义为1型 &#

30、160;else CType='2' /否则是标识符，其类型为2      else if (ch>='0' && ch<='9')/判断是不是为整数     Word+k=ch;  Fbuffer=scanner();  while(true)/如果是数字，则一直接受，且定义它的类型为3  if(ch>='0' &&am

31、p; ch<='9')    Word+k=ch; Fbuffer=scanner();    else CType='3'break;/不是数字则跳出循环 /如果以字母开头，且长度不超过WMaxlen，且下面跟有字母，则此整数非法，输出类型为8，在主程序中输出出错信息  if (k<WMaxlen)  if (ch>='a'&& ch<='z'| ch

32、>='A'&& ch<='Z')    Word+k=ch;  Fbuffer=scanner();  /取这个非法整数的单词，其中可包含英文字母和数字 while (ch>='a'&& ch<='z'| ch>='A'&& ch<='Z'| ch>='0' &&

33、; ch<='9'|Fbuffer=-1)  if (k<WMaxlen)  Word+k=ch;  Fbuffer=scanner();    else     Fbuffer=scanner();  k+;    if (k>WMaxlen)/如果长度大于取出单词定义的最大长度，则返回类型为8，在主程序中打出出错信息  CType=Longtype;  else CType=Errtype

34、;/否则返回类型7，在主程序出错，并明确写出此单词的具体内容    Word+k='0'     else if (ch='+'|ch='-'|ch='*'|ch='/')/取出是运算符号的单词     Word+k=ch;  if (ch='+' | ch='-')/如果是+号或者是-号，则还要判断是不是正负数if (Lasttype

35、='6')/判断其取出的当前字母的前一个单词是6号类型的，即是<、>、<=、>=、=、=时则可判断现在取出的是整数     Fbuffer=scanner();  while(ch>='0' && ch<='9')/取出整数    Word+k=ch;  Fbuffer=scanner();    CType='3'/如果正负整数，则直接返回类型为3,则表示此单词为整数

36、 return(CType);    else Fbuffer=scanner();/如果不是整数，则定义当前取出的单词是运算符，定义此类型为4 Word+k='0'  CType='4'    else if (ch='>'|ch='<'|ch='='|ch='!')/取出运算符的另几类，即<、<=、>、>=、=、=、!=     W

37、ord+k=ch;Fbuffer=scanner();  if( ch='=')/判断是不是<=、>=、=、!=     Word+k=ch;  Fbuffer=scanner();    Word+k='0'  for (int i=0;i<Sign_No;i+)/判断取出的单词是不是运算符  if (strcmp(Signi,Word)=0)     flag=true;  break;    if (flag) CType='4'   Lasttype='6'     else if (ch=','|ch=''|ch=''|ch=''|ch='(&#