编译原理实验指导书(2010版)

PAGEPAGE10编译原理实验指导书北方工业大学信息工程学院计算机系原著：谭熹微改编：赵会群2006年3月1实验目的编译原理着重介绍设计和构造编译程序的原理和方法，作为一门技术课程，既有很强的理论性又有很强实践性，实验的目的是为了通过实验实践，加深对课堂讲授知识的理解和掌握几个主要编译阶段的处理方法，增强实践能力，达到初步的设计，编制和调试编译系统的能力。2实验手段在信息工程学院网络中心计算机实验室或计算中心，利用所学过的C语言和VC++语言编写程序并调试通过。3实验次数和时间实验分两次共16小时实验一词法分析8+8小时实验二语法分析8+8小时4实验考核每次实验结束都必须写出实验报告，报告内容包括：实验课题、实验目的和要求，实验的实现(包括主要设计思想、实现算法、主要技术问题的处理方法，及实验结果)结论分析。实验报告格式（A4）：实验题目词法分析器构造实验要求对一个简单的Fortran语言实现其编译器，输出符号表。实现算法问题及处理实验结论学生姓名班级学号指导教师实验成绩

实验一词法分析器构造一、目的和要求通过对给定源语言词法分析程序的设计，加深对词法分析原理的理解，掌握源语言的接受、存贮、预处理和扫描分析，生成正确的单词符号串二元式序列。二、内容用直接分析法编制下述C语言子集的词法分析程序，C语言子集的文法描述如下：词句→赋值语句｜条件语句｜转移语句｜带标号的赋值语句带标号的赋值语句→〈标号〉〈赋值语句〉赋值语句→变量=算术表达式条件语句→IF<布尔表达式>THEN语句｜IF<布尔表达式>THEN语句ELSE语句转移语句→GOTO标号变量→标识符标识符→字母｜<标识符><数字>字母→A｜B｜…｜Z｜a｜b｜…｜z数字→0｜1｜…｜9｜算术表达式→项｜算术表达式+项｜算术表达式一项项→因子｜项*因子｜项／因子｜因子↑项因子→变量｜常数｜(表达式)布尔表达式→<算术表达式><关系符><算术表达式>关系符→>｜<｜>=｜<=｜=｜<>标号→常数常数→数字｜<常数><数字>对语言的几点限制：保留字不允许作为标识符使用。保留字、标识符、常数、标号之间若没有确定的运算符或界符，则必须用空格符隔开。源程序书写按C标准格式。续行最多不得超过5行。三、说明与提示3.1本实验要求的直接分析法，即从左向右扫描源程序，一旦发现有独立意义的字符串时，即将其改造统一长度的二元组(t,i)输出，其中t表示单词种别，i为相应内部表示，本题t分为四类：K(关键字)、I(标识符)、C(常数)、P(界符)，i为特定项的指针值，对应于每一类属性的单词均放入相应的表格，在识别过程中每识别出一个单词，则将其顺序放入相应的符号表中。3.2C源程序利用行编辑录入，以TEXT文件形式存贮在盘上，词法分析程序，先对源程序作预处理扫描生成新的TEXT文件。预处理的功能是剔除无用的空白、跳格、回车和换行等编辑性字符；去掉注解部分，连接继续行，给出句未符。预处理程序参考结构框图扫描程序参考结构框图(请参考编译原理书第三章)表格的参考数据结构可描述为：框图中A为数组A(1…80){输入缓冲区}R为数组R(1…160){扫描缓冲区}“；”为句未符#defineKeylen10#definePlen20#defineClen40#defineIlen30#defineIdentlen10StructOutform{charty; intPoint;}；StructLabel{intum; intad;};charK[keylen][10]，P[Plen][2]，I[Ilen][10];intC[Clen];StructLabelL[Ilen];本实验作为编译过程的第一阶段和后续两个实验的前提，所有生成结果都必须作为永久文件存贮。

实验二语法分析器构造一、目的和要求借助于词法分析程序提供的分析结果，编写一个算符优先语法分析程序，程序能进行语法结构分析和错误检查并产生相应的归约信息。同时给出出错信息和错误类型，从而加深对语法分析的理解。二、题目给定文法G和算符优先分析法，构造其算符优先分析程序文法G：语句→赋值语句｜条件语句｜转移语句｜带标号的赋值语句带标号的赋值语句→<标号><赋值语句>赋值语句→变量=算术表达式条件语句→TF→<布尔表达式>THEN语句｜TF<布尔表达式>THEN语句ELSE语句转移语句→GOTO标号变量→标识符标识符→字母｜<标识符><数字>字母→A｜B｜…｜Z｜a｜b｜…｜z｜数字→0｜1｜…｜9｜算术表达式→项｜算术表达式+项｜算术表达式一项项→因子｜项*因子｜项／因子｜因子↑项因子→变量｜常数｜(表达式)布尔表达式→<算术表达式><关系符><算术表达式>关系符→>｜<｜>=｜<=｜=｜<>标号→常数常数→数字｜<常数><数字>三、说明和提示1.本实验的优先表可以手工先设计好。2.本实验要求中提出的“产出相应的归约信息”意指在语法分析的过程中，一旦产生归约，在程序上产生并最终输出归约产生式序号。3.出错类型的产生可预先对应优先表中出错栏列表说明其出错类型，并分别编序，当分析中产生错误时以字符串输出相应表中错误信息。4.算法采用一个符号栈的数据结构，既用它存放终结符，也用它存放非终结符。设K为符号栈使用深度，其参考算法如下：K:=1S［K］:=#Repeat把下一人输入符读入a中；IfS［K］∈VTthenj:=Kelsej:=K-1;whileS［j］>adoBeginRepeatQ:=S［j］;IfS［j-1］∈VTthenj:=j-1elsej:=j-2;UntilS［j］<Q;把S［j+1］……S［K］归约为某个N；记录归约产生式序号；K：=j+1S［K］:=NendofwhileIfS［j］<aORS［j］=athenBeginK:=K+1;S［K］:=aendelseERROR{查表打印出错信息}Untila='#'输出归约产生式序列号；实验三中间代码生成一、目的要求掌握语学制导下的中间代码生成技术，在第一、第二次实验的基础上完成中间代码生成程序。二、题目给定文法G，完成其词法、语法和中间代码生成程序。文法G：词句→赋值语句｜条件语句｜转移语句｜带标号的赋值语句带标号的赋值语句→<标号><赋值语句>A(赋值语句)→变量=E（算术表达式）E→E+E|E*E|E/E|E-E|（E）|E*E|i转移语句→GOTO标号变量→标识符标识符→字母｜<标识符><数字>字母→A｜B｜…｜Z｜a｜b｜…｜z｜数字→0｜1｜…｜9｜标号→常数常数→数字｜<常数><数字>E（布尔表达式）→EAE|E0E|！E|idropid|idEA→E∧E0→E∨条件语句：S→CS|TPS|A|GOTO标号C→IFETHENTP→Celserop（关系符）→>|<|>=|<=|=|<>三、说明和提示1.实验必须充分体现语法制导下的中间代码生成思想，也即必须以实验二为基础加以扩充。2.本实验题中转移语句可作为特例单独处理。3.中间代码形式采用四元式。补充实验一、球类描述语言词法分析实验1、实验描述根据球类比赛的特点和脚本描述语言的设计要求，把球类比赛分为两种：其一是比赛需主、客队同台（场）竞技。如沙滩排球、乒乓球、篮球、足球和网球等；其二是主、客队轮流上场，比赛对手不是同台竞技。如台球和保龄球等。第一种球类比赛具有以下特点：（1）进攻/防守形成博弈；（2）博弈双方的技术动作具有相似性。为此，我们可以把第一种比赛的相关技战术描述抽象成如下形式：队员+技术动作+技术动作发生区域+技术动作结束区域我们的设计目标主要针对第一种比赛。为此脚本表述语言的语法结构如图1.1所示。XXXXXXXX●XXXX●.…..●XXXX●XXXX.单词句子（型）图1-1脚本描述语言语法结构图单词单词其中：单词由英文字母构成，可以采用汉语拼音的字首进行编码。句子由单词加分隔符“●”构成。下面是一个乒乓球比赛脚本描述语言的案例。脚本对照脚本对照：主队：发左路近网下旋球，ZX16客队：反手摆短到左路近网，FB66主队：反手挑中路远台，FT62客队：正手弧圈球至正手远台，ZH23主队：正手弧圈球至正手远台形成相持，ZH33客队：正手弧圈球至正手远台，ZH33主队：正手弧圈球冲左路得分。ZH31输入码：ZX16●FB66●FT62●ZH23●ZH33●ZH33●ZH31图1-2乒乓球脚本输入码2解释器的设计与实现根据球类比赛技战术分析的需求，设计的解释器由词法器、语法器和语义分析模块三部分组成，如图2-1所示。其中：词法分析器负责词法分析的预处理和输入单词的解释；语法分析输入码的语法结构检查和解释；在词法和语法分析器的基础上，语义分析模块负责比赛技战术的分类与统计工作。下面分别介绍上述逻辑部件的设计与实现。图2-1脚本描述语言图2-1脚本描述语言分析器词法分析器语法分析器语义分析分析报告2.1词法分析器根据第1节对球类比赛脚步描述语言语法结构的设计，以及球类比赛描述的特点，对该描述语言的单词符号进行设计。单词符号由以下四种：（1）技术动作描述符：一般由四类字符组成，英文字母、数字、“+”和“-”。其中，英文字母是技术动作的编码，由一个编码映射表支持词法解释；数字用于描述技术动作发生的区域，该语言总是把比赛场地分割成若干个不同的区域；“+”和“-”是两个特殊符号，一般用于一些极其特殊的技战术描述，如乒乓球中的“擦边球”或“擦网”等。（2）间隔符：用于区分不同的技术动作，一般用“●”表示。（3）保留字：为了明确标示比赛视频的开始和结束，每一小节或单局比赛的开始和结束，比赛中的暂停和开始，设计了一些保留字，如Match:Start、Match:End、Set1:Start、Set1:End等；（4）控制符：用于比赛中的比分调整。例如，ap03:05、*p02:05。上述单词符号构成单词的词法分析状态转换描述如图2-2所示。00区域码123方式码动作码间隔符图2-2控制符的状态转换图上述词法分析的算法如下：算法2.1一个乒乓球脚本描述语言的词法分析算法：Input:基于乒乓球比赛脚本简码的技战术输入码Output:描述语言完全码Step1:词法检测、运动区域补偿Word=Read(code);//输入一个单词符号//Dowhileword<>‘’Iffield(word,Last_position)=‘●’thenbreakelseiffield(word,start_position)andfield(word,target_position)=numthenreturn//词法检测结束//elseiffield(previous_word,target_position)=numthenfield(word,start_position)=field(previous_word,target_position);word=read(code);enddoStep2:词法检测、动作补偿Word=Read(code);//输入一个单词符号//Dowhileword<>‘’Iffield(word,style_position)<>‘’thenbreak;elseifword.artribute=offenceandfield(word,start_position)=right_domain//该动作为进攻动作//thenfield(word,style_position)=‘z’;elseifword.artribute=offenceandfield(word,start_position)=left_domain//该动作为进攻动作//thenfield(word,style_position)=‘f’;elseprint(‘anerrorbefound’);word=read(code);enddoend在上面的算法中，每一个单词由四位码构成field(word,style_position)是单词的第一位，表示动作的方式、field(word,act_position)是单词的第二位，表示动作的类型、field(word,start_position)是单词的第三位，表示球的起点、field(word,target_position)是单词的第四位，表示球飞行的结束位置。该算法需要两次遍历输入码，因此算法的复杂性为O(L)。2.2语法分析器根据图1-1所示的脚步描述语言结构，它的文法G如下：S→TS’S→TS’S’→●TS’∣εT→W∣εW→w图2-3(c)不含左递归的文法图2-3’简化的S→T∣S●TT→W∣εW→w图2-3(b)简化的G文法S→T∣S●TT→C1C2N1N2∣C1→iC1→iN1→n1N2→n2图2-3(a)G文法其中：S为开始符号，表示一个输入码，T为非终结符，它可以是ε字；C1为动作方式码，它只能产生一个表示动作方式终结符号；C2为动作分类码，它只能产生一个表示动作的终结符号；N1为动作起始区域，它只能产生一个表示区域的终结符号，N2为动作终止区域，它只能产生一个表示区域的终结符号。例如：乒乓球比赛的输入码为：ZX16●FB66●T62●ZH23●ZH33●ZH33●ZH31。它表示：正手发下旋球从1区到6区●对方反手摆短从6区到6区●反手挑到2区●对手正手弧圈球从2区到3区●正手弧圈球从3区到3区●对手正手弧圈球从3区到3区●正手弧圈球至对方1区后得分。定理：文法G是LL（1）文法。证明：为每一个非终结符求FIRST()集和FOLLOW()集如下：FIRST(S)={w,ε};FIRST(T)={w，ε};FIRST(S’)={●，ε};FIRST(W)={w};FOLLOW(S)={#},FOLLOW(T)={●,#};FIRST(S’)={#};FOLLOW(W)={●,#}由LL(1)文法的条件可知，G文法满足：FIRST(αi)FIRST(αj)=;FOLLOW(A)FOLLOW(A)=因此，G是LL(1)文法。对文法G的语法分析可以采用递归下降法或预测分析表法。由于脚步描述语言中采用的文法符号可以自定义，符号的数量并不多，所以建议采用预测分析表来实现。下面是一个改进的预测分析表算法。算法2-2：基于预测分析的语法分析算法首先把“#”，然后把文法开始符号“S”推进栈charstack；把第一个输入符号读进a（char类型）；Flag=TRUE;Dowhile(Flag){取栈（charstack）顶的元素放入X（char类型）中 If（X是文法中终结符号中的一个） {If(X==a)Then把下一个符号读进a把栈顶的元素删除 elseFlag=FALSE;//词法错误}elseif(X==’#’){if(X==a)thenFlag=TRUE;//词法分析结束 elseFlag=FALSE;//词法分析错误}else{找出X在二维数组中的行数Row；//用二维数组表示预测分析表找出a在二维数组中的列数Column；//CStringm_strTemp[4[6]If(m_strTemp[Row][Column]!=“”&&m_strTemp[Row][Column]!=“E”)//E代表ε把栈顶元素删除；把m_strTemp[Row][Column]中的元素从后往前推入栈中；elseif(m_strTemp[Row][Column]==“E”)then删除栈顶元素； elseFlag=FALSE;}}算法2-2的执行时间为O(M*N)，M和N分别为预测分析表的行和列下标。3实验设计根据第2节对球类脚步描述语言中词法、语法分析器的讨论，为同学设计了两个实验。如下：实验一：基于球类脚步描述语言的词法分析器的设计与实现。实验目的：通过本实验使同学掌握词法分析器的体系结构、各功能部件的设计与实现方法，为进一步学习语法分析器奠定基础，使得同学能够