《编译原理上机实验指导》

1、编译原理上机实验指导实验一词法分析1实验目的设计编制并调试一个词法分析程序，加深对构造词法分析器的原理和技术理解与 应用。2实验要求选择一种计算机高级程序语言子语言，运用恰当的词法分析技术线路，设计和实 现其子语言的词法分析器。语言选择，建议为计算机程序设计课程所采用的语言。 技术线路建议如下两种之一：正则式t NFADFQ min DFQ程序设计和正则文法宀 NFA t DFAt min DFAt程序设计。分析器输出结果存入到磁盘文件中。具有出错处理功能。选择子语言方法举例。以教材选取的PASCAL语言为例，确定其子语言涉及的单词类如下：(1) 关键字begi n end if the n

2、while do(2) 运算符和界符:=+ * / =；() : #(3) 标识符正则式：ID=letter(letter|digit)*(4) 整型常数正则式：NUM= digit(digit)*3算法设计(1) 单词种别码设计单词种别码对照表单词符号种别码单词符号种别码begin1:17If218the n320while421do523标识符10=24整型常数11=25+1326一14(27*15)28/16#0(2) 输出形式设计词法分析器的输入是源程序字符串，输出是对应的单词串。每个单词按照二元组 (种别码，单词符号本身)格式输出。例如：假设源程序为begi n x:=9; if x

3、0 then x:=2*x+1/3;e nd # ，则词法分析器对应输出的结果是：(1,begi n)(10,x)(18,:=)(11,9)(26,;)(2,if)(10,x)(23,)(11,0)(3,the n)(10,x)(18,:=)(11,2)(15, *)(10,x)(13, + )(11,1)(16, / )(11,3)(26,;)(6,e nd)(0,#)(3) 算法思想依据建立的识别单词的DFA，设计算法，其框架如下。其中，syn存放单词的种别码；token存放符合标识符规则的单词；sum存放整型常量的单词。实现技术细节注意的几个要点：A )标识符和关键字，属于同一构词规则，

4、识别方法是建立一个关键字表，在识别出标识符单词时，查关键字表，以确认或区别是否 是关键字，还是标识符。B)对前导空格符、制表符和换行，均须过滤。详细处理技术 请参见陈火旺等编写程序设计语言编译原理 (第三版)；C)约定标识符单词8位有 效。主算法流程图扫描子程序流程图4程序框架#in clude#in cludevoid sca nn er(void);char prog8,toke n 8,ch;int syn ,p,m,sum;char *rwtab6=begin ” if ” “hen ” while ” do ” end;void mai n(void)p=0;printf( n pl

5、ease in put stri ng:n ”；dosca nn er();switch(s yn)case 11:输出“整型数的二元组;break;case :输出错误；break;default:输出其它单词的二元组； while(s yn);void sca nn er(void)for(m=0,n=0;n8;n+) tokenn=NULL;ch=读取下一个字符；while(ch= )ch=读取下一个字符；if(ch 是字符 )while(ch 是字符或数字符号 )ch 拼到 token ；ch=读取下一个字符；tokenm+= 0;回退一个输入字符；syn=10;for(n=0;n6;

6、n+) if(strcmp(token,rwtabn)=0)syn=n;break; elseif(ch 是字符 )while(ch 是数字符号 )sum=sum*10+ch; 0；ch=读取下一个字符；回退一个输入字符； syn=11;elseswitch(ch)case )syn=21; tokenm+=ch;else if(ch= =)syn=22; tokenm+=ch;elsesyn=20; 回退一个输入字符； break;case : m=0;tokenm+=ch; ch=读取下一个字符；if(ch= =)syn=24; tokenm+=ch;elsesyn=23; 回退一个输入字

7、符； break;case : : m=0;tokenm+=ch; ch=读取下一个字符；if(ch= =)syn=18; tokenm+=ch;elsesyn=25; 回退一个输入字符； break;case + : syn=13; token0=ch; break;case - : syn=14; token0=ch; break;case * : syn=15; token0=ch; break;case /:syn=16; token0=ch; break;case # : syn=0; token0=ch; break;default : syn=-1;实验二 语法分析1 实验目的设

8、计编制并调试一个语法分析程序，加深对构造自顶向下的语法分析器的原理和 技术理解与应用。2 实验要求简单语言至少包括赋值语句和复合语句，其中表达式至少包括算术表达式。设计 语言文法，运用递归下降分析技术，设计和实现语法分析器。具有出错处理功能。选择子语言方法举例。以教材选取的 PASCAL 语言为例，确定其子语言涉及的语 法，以扩充的 BNF 方法描述如下：(1) 程序 t bengin 语句串 end(2) 语句串 t 语句； 语句(3) 语句 t 赋值语句(4) 赋值语句 t 标识符 := 表达式(5) 表达式 t 项 + 项 | 项(6) 项 t 因子 * 项 |/ 项 (7) 因子t 标

9、识符 |整型常数|(表达式)3 算法设计语法分析器的输入是由词法分析器从源程序字符串中分离输出的单词串，如果源程序字符串是文法正确的句子，则输出success，否则，输出error”。例如:( 1 )输入: begin a:=9;x:=2*3;b:=a+x end #输出: success( 2)输入: begin a:=9;x:=2*3;b:=a+x #输出: error主程序和每个非终结符(语法单位)对应的递归子程序的算法流程图如下。这里 注意的是 A)词法分析器(seaner)作为子程序，由语法分析器调用，即系统选择的是 词法分析和语法分析一趟的方案； B) 约定每个非终结符(语法单位)

10、对应的递归子程 序进入时，均已读入一个单词。4程序框架/* 对应的递归子程序*/lrparser()if(syn=1)sca nn er(); yucu();if(sy n=6)scanner();if(syn=0 & kk=0)输出“ success！”；elseif(kk!=1) 输出“缺 end！”； kk=1; else输出缺 begin !kk=1;return;/* 对应的递归子程序*/yucu()statement();while(syn=26)scanner();statement();return;/*语句 对应的递归子程序*/statement ()if(syn=10)scanner();if(syn=18)scanner();expression();else 输出“赋值符错！ ”；kk=1; else 输出“语句错！ ”； kk=1; return;/* 表达式 对应的递归子程序*/expression()term();while(syn=13 | 14)scanner();term();return;/*项对应的递归子程序*/term()factor();while(syn=15 | 16)scanner();