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

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

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

3、:=2*x+l/3;e nd #,则词法分析器对应输出的结果是：(1, begin) (10, x) (18, ：=) (11, 9) (26, ;) (2, if) (10, x) (23, (11, 0) (3,then) (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 sea nn er (void);char progLS, toke n 8, ch;int syn , p, m, sum;char *rwtab6 = begin ” if ” “hen ” while ” do ” end; void mai n

5、(void)P=o；printf ( n please in put stri ng:n ” ；do sea nn er ();switch(s yn) case 11:输出整型数的二元组，z/break;case：输出错误；break;default:输出其它单词的二元组； while(s yn);void sea nn er (void)for(m二0, n二0;n8;n+) tokenn=NULL;ch二读取下一个字符；while (ch=)ch二读取下一,个字符；辻(ch是字符)wh订e(ch是字符或数字符号)ch拼到token ;ch二读取下一个字符；tokenm+二0;回退一个输入

6、字符；syn=10;for(n=0;n ) syn=21; tokenm+=ch;else if (ch=二)syn=22; tokenm+=ch; else syn=20;回退一个输入字符； break;case : m=0;tokenm+ =ch; ch=读取下一个字符；if (ch二二=)syn=24; tokenm+=ch; else syn=23;回退一个输入字符； break;case: m=0;tokenm+ =ch; ch=读取下一个字符；if (ch= = ) syn=18; tokenrm+=ch; else syn=25;回退一个输入字符； break;case + :

7、syn二13; token0=ch; break;case -：syn=14; token_0=ch; break;case: syn二15; token0=ch; break;case /:syn=16; token0=ch; break;case: syn=0; tokenL0=ch; break;default : syn=l;实验二语法分析1实验目的设计编制并调试一个语法分析程序，加深对构造自顶向下的语法分析器的原理和 技术理解 与应用。2实验要求简单语言至少包括赋值语句和复合语句，其屮表达式至少包括算术表达式。设计语言文 法，运用递归下降分析技术，设计和实现语法分析器。具有出错处理功

8、能。选择子语言方法举例。以教材选取的PASCAL语言为例，确定其子语言涉及的语法，以扩充 的BNF方法描述如下：(1)程序T bengin 语句串end(2)语句串T语句； 语句(3)语句T 赋值语句(4)赋值语句TV 标识符 ：= 表达式(5)表达式T项 + 项 丨一 项(6)项T因子* 项丨/项(7)因子T标识符|整型常数IV 表达式)3算法设计语法分析器的输入是由词法分析器从源程序字符串屮分离输出的单词串，如果源 程序字符串是文法正确的句了，则输出success,否则，输出error”。例如：(1)输入：begin a: =9;x: =2*3;b: =a+x end #输出：succes

9、s(2)输入：begin a: =9; x: =2*3; b: =a+x #输出：error主程序和每个非终结符(语法单位)对应的递归子程序的算法流程图如下。这里注意的是A)词法分析器(seaner)作为子程序，由语法分析器调用，即系统选择的是词法分析和语法分析一趟 的方案；B)约定每个非终结符(语法单位)对应的递归子程 序进入时，均已读入一个单词。4程序框架/*程序 对应的递归子程序*/lrparser () if(syn=l) sea nn er () ; yucu ();if(sy n=6)scanner ();V 表达式A调用 V 项否调用scanerJ调用 v 项if (synO &

10、amp; kk=O)输出success ielseif (kk!=l)输出缺end!； kk=l; else 输出缺begin ! kk=l;return;/*语句串 对应的递归子程序*/yucu () statement();while(syn=26) scanner ();statement ();return;/*语句 对应的递归子程序*/statement () if (syn=10) scanner ();辻(syn18) scanner ();expression();else输出“赋值符错！ ” ;kk=l; else输出“语句错！ ”； kk=l; return;/* 表达式 对应的递归子程序*/expression ()term();whi.1 e (syn=13 I 14) scanner ();term();return;/*项对应的递归子程序*/term() factor ();while(syn=15| 16)scanner ();facto