编译原理课程设计报告.docx

一：课程设计功能需求分析编译课程设计的基本任务是设计一个mini-pascal语言的编译器，将mini-pascal 语言的源程序翻译成等价的中间代码。要求输入mini-pascal语言写的源程序（以文件形式存储），首先经过词法分析，输出原程序分析后的二元式文件，供语法制导翻译用。经过语法制导翻译将词法分析器产生的二元式翻译成等价的四元式形式，也就是中间代码的生成。要求能进行正常的关键字如：begin,end, if ,else 等的识别。例：程序结构为： program ; procedure begin end;begin end. 过程可以嵌套定义，每个过程最后以“；”为结束符，主程序最后以“”为结束符。可执行语句：赋值语句、条件语句（ifthen 和 if then.else 两种形式）、当型循环语句、for语句(此语句可不必做)、过程调用语句（有参和无参两种）、读语句、写语句、复合语句。数据类型：只有一种整型数据。数据结构：只有简单变量（整型）二：课程设计总体设计 编译程序的任务是将高级语言程序翻译成低级语言程序(汇编语言或者机器语言).也就是说编译程序接受的对象是以字符串形式存在文件中的高级语言,经过编译处理生成一个等价的汇编语言或者机器语言程序.三 课程实际模块详细设计 词法分析器模块的详细设计词法分析器的任务词法分析器的任务是将一个字符流文件按词法规则改造成一个单词流文件，也就是说输入词法分析器的是一个由字符组成的源文件，通过词法分析器识别分析后输出由若干个单词名称和单词编码组成的记录文件：单词符号用如下二元组表示：（单词名称， 单词种类） 词法分析原理及程序设计词法分析原理采用直接分析法进行词法分析，根据单词的第一个字符划分单词类型： 若第一个字符为字母，这将紧接在字母后面的字母、数字逐一拼接成“字母数字串”直到遇到非字母也非数字的其他字符为此单词拼接完成，这可能是用户定义的标识符和保留字。 若第一个字符为数字，同样向后识别，将紧接在后面的数字和前面的数字拼接在一起，直到非数字的其它字符为止，这个单词为整数。 若第一个字符为其它类型，则根据字符本身就可识别，有的双字符运算符（如= , :=等）需要再向后设备一个字符才能识别。测试简例beginab2a:=9;if x=0 then x:=x+1;while a=0 do b:=a*x/33455;end#词法分析测试结果递归下降分析法模块详细设计递归下降法的设计思想：用递归下降法进行语法分析时对文法的产生式有两点限制：1.文法的产生式不含有左递归2.提取文法中的公因子mini pascal 语言中的程序结构部分符合上述限制，用递归下降法进行分析。以下为mini pascal 语言“程序结构”部分的文法表示： 中内容可有可无， 中内容重复0次到1 次, n0 中内容重复0次到n 次(1) program ； .PROG program ident ; PP.(2) begin endPP IDP PRP begin PL end(3) procedure ； PRP procedure ident PARL ; PP;(4) var IDP Var ident , ident ;(5) （ ）PARL ( ident , ident )递归下降法即是对文法的每一个非终结符（一般代表某一语法范畴）编一个子程序用来识别由此非终结符所推导出的符号串。由于文法的产生式往往是递归定义的，因此，所编写程序往往引起递归调用。产生式(1) PROG program ident ; PP .的示意性子程序Procedure progBeginIf sym = program then getword else 出错处理 ；If sym = ident then begin 填符号表; getword end else 出错处理 ；If sym = ; then getword else 出错处理 ；调PP过程If sym = . then 判断二元式文件是否结束，若没有结束则出错，否则结束。 else 出错处理 ；end产生式 (2) 和（3）是递归定义的，因此其相应的子程序也是递归调用的。以下为这两个程序的示意性形式PP IDP PRP begin PL endProcedure PP begin 调IDP过程；while sym = procedure then 调PRP过程if sym = begin then 调PL过程 else 出错if sym = end then 结束 else 出错endPRP procedure ident PARL ; PP;Procedure PRP 调PP过程递归下降分析中的语义处理符号表的填、查工作 利用过程名表来查找变量。通过上一个例子了解怎样利用过程名表来查找变量。 符号按出现的顺序填入符号表-设置填变量表模块，填过程名表模块。 变量名填入变量表之前，应先查变量表，以确定该变量在本过程是否重复定义-设置查变量表模块1。 过程名填入过程名表之前，应先查过程名表，以确定该过程名是否已定义(重复定义) -设置查过程名表模块。 当引用变量时需确定该变量是否已定义，此时要用另一查变量表模块2，查变量表模块2在变量表中查找某个变量时，如果在本过程中查不到，就必须到它的外过程中去找。查到后，给出该变量在变量表的位置。递归下降分析法的详细的模块设计递归分析的详细设计从二元式文件中读入单词种类的编码，根据编码判断单词种类，并做相应的程序处理void procProcess(FILE *fpread,int level)/递归的过程 struct record temp;skipLine(fpread);/跳过换行符fread(&temp,sizeof(struct record),1,fpread);/读一条记录，记录是二元式形式if(temp.kind=1)&(level=0)|(temp.kind=3)&(level0)if(temp.kind=1)/这个单词是program/printf(nprogram.);processProg(fpread,level);/处理program这一行程序else if(temp.kind=3)/这个单词是procedure/printf(nprocedure.);processProc(fpread,level);/处理procedure这一行程序processShift(fpread,level);/程序转移处理elseif(level=0)/如果处理的是主程序，主程序是第零层printf(nERROR: line- %d 缺少program.,lineLocation);/输出错误信息skip(fpread);/出错后就跳过若干个单词再处理processShift(fpread,level);/程序转移处理这是递归程序的主要过程，其中递归子程序：void processShift(FILE *fpread,int level)/按照程序的不同形式采取不同的处理方式，这是由于一些程序的模块可以有，也可以没有 struct record temp;skipLine(fpread);fread(&temp,sizeof(struct record),1,fpread);/读一个二元式，（词法分析的结果）switch(temp.kind)/查看读出的单词的编码，按照编码决定程序的走向case 2:/处理var定义变量，这是处理变量定义的过程do/printf(nvar.);processVariable(fpread,level);/处理变量，将变量填入符号表skipLine(fpread);/跳过换行符，增加了程序的灵活性，一行代码可以写在若干行fread(&temp,sizeof(struct record),1,fpread);/读一条记录while(temp.kind=2);/如果有多条定义变量的语句switch(temp.kind)case 3:/处理过程procedure定义do/printf(nprocedure.);fseek(fpread,recordLength,SEEK_CUR);/*回退一条记录*/if(varLocation!=-1)backPatch();/*当前过程有参数但没有填写过程表的就填写*/procProcess(fpread,level+1);/递归调用，处理过程skipLine(fpread);fread(&temp,sizeof(struct record),1,fpread);while(temp.kind=3);/如果有多个过程定义if(temp.kind=4)/处理begin-end这段代码过程/printf(nbegin.);if(varLocation!=-1)backPatch();/*当前过程有参数但没有填写过程表的就填写*/processPL(fpread);/处理代码过程，在lR分析阶段这一过程是主要的过程elseprintf(nERROR: line- %d缺少关键字begin.,lineLocation);skip(fpread);/错误处理processShift(fpread,level);/程序再次转移，看后续代码的形式break;case 4:/处理begin的过程/printf(nbegin.);if(varLocation!=-1)backPatch();/*当前过程有参数但没有填写过程表的就填写*/processPL(fpread);break;case 17:/定义的是变量（17是标识符的编码）printf(nERROR: line- %d缺少关键字var或procedure.,lineLocation);skip(fpread);processShift(fpread,level);break;default:/出错了，这是出错的处理printf(nERROR: line- %d,lineLocation);skip(fpread);processShift(fpread,level);/转移处理break;break;case 3:/这是在一个过程中没有变量定义的时候的处理的情况，有些子程序可以没有变量定义do/printf(nprocedure.);fseek(fpread,recordLength,SEEK_CUR);/*回退一条记录*/if(varLocation!=-1)backPatch();/*当前过程有参数但没有填写过程表的就填写*/procProcess(fpread,level+1);skipLine(fpread);fread(&temp,sizeof(struct record),1,fpread);while(temp.kind=3);if(temp.kind=4)/printf(nbegin.);if(varLocation!=-1)backPatch();/*当前过程有参数但没有填写过程表的就填写*/processPL(fpread);elseprintf(nERROR: line- %d缺少关键字begin.,lineLocation);skip(fpread);processShift(fpread,level);break;case 4:/这是当子程序既没有变量定义，又没有子过程定义的时候的处理方法/printf(nbegin.);if(varLocation!=-1)backPatch();/*当前过程有参数但没有填写过程表的就填写*/processPL(fpread);break;case 17:printf(nERROR: line- %d缺少关键字var或procedure.,lineLocation);skip(fpread);processShift(fpread,level);break;default:printf(nERROR: line- %d,lineLocation);skip(fpread);processShift(fpread,level);break; /递规模块分析结束上面两段程序是对递归模块的详细设计还有为完成详细设计需要用到的一些函数及功能void processPL(FILE *fpread)/这个过程不处理具体的代码，代码的分析有LR语法分析阶段完成void processVariable(FILE *fpread,int level)/处理变量的过程，包括判断变量是否重定义和将变量填入符号表void processProc(FILE *fpread,int level)/处理过程的定义void processID(FILE *fpread,int level)/处理过程的参数定义，并将过程的部分信息填入过程表void processProg(FILE *fpread,int level)/专门处理program开头的这条语句，也就是分析程序的开头void skip(FILE *fpread)/这个函数用于出错的情况下跳过若干个字符，直到遇到var,procedure,begin为止void skipLine(FILE *fpread)/*跳过换行符*/int searchprocTable(char procName)/查找是否有同名的过程void enterProcTable(char procName,int level,int exProc)/将过程中定义的过程名填入过程表void backPatch()/将过程定义的变量和参数信息填入过程表int searchVarTable(char varName)/在变量表中查找变量void enterVarTable(char varName,int level,int relative)/将变量填入变量表void displayVarTable()/将变量表的内容在屏幕上显示出来，方便调试以及测试程序运行是否正确void displayProcTable()/将过程表的内容在屏幕上显示出来void ishaveLast(FILE *fpread)判断文件是否读完测试内容1正确程序结构和各种说明语句是否可顺利分析,检查变量表,过程名表填写的内容是否正确。测试程序分别是不同嵌套结构，不同变量定义的源程序。2逐渐在测试程序中加入各种语法错误，看其能否正确识别。3对lookupv1, lookupv2重点检查变量的作用域识别是否正确4与LR分析器接口的调试测试简例program A;var x1,y1;procedure AB(x2,y2);var x3,y3;beginendprocedure ABC(x7,y7);var x4,y4;procedure ABCD(x5,y5);var x6,y6;beginendbeginendbeginend.测试结果LR分析器模块详细设计1. 概述：LR分析法是利用一张LR分析表和一个分析栈进行自下而上的语法分析法，分析程序开始会读入一个二元式，调用查ACTION表的子程序，得到相应得动作ACT。因为LR分析器只分析可执行语句，所以只对mini-pascal语言的可执行语句部分进行语法分析，在分析过程中加上适当的语义处理，实现“边分析，边翻译”，当一条语句分析完也同时生成符合此语句语义的四元式代码。在输入文件中自定义非终结符，终结符和产生式集合。通过对非终结符，终结符和产生式的定义，得出其语法描述。基本思想从待输入的符号串开始，利用文法的产生式步步向上归约，试图归约到文法的识别符号。如果从语法树的角度看，它的过程是以输入符号串作为末端结点符号串，向着根结点的方向往上构造语法树，使识别符号正好是该语法树的根结点。如果最终跟结点是识别符号，输入符号串被识别出是相应语言的一个句子：否则不是。LR分析算法LR分析器包括输入、输出、栈、驱动程序和含动作和转移两部分的分析表。驱动程序对所有的LR分析方法都一样，不同的分析方法构造的分析表不同。分析程序每次从输入缓冲区读一个符号，它使用栈存储形式为s0X1s1X2s2Xmsm的串，sm在栈顶。Xi是文法符号，si是叫做状态的符号，状态符号概括了栈中它下面部分所含的信息。栈顶的状态符号和当前的输入符号用来检索分析表，以决定移进-归约分析的动作。真正实现时，文法符号不必出现在栈里，不过在我们的讨论中总是包含它们以帮助解释LR分析的行为。分析表由两部分组成，动作函数action和转移函数goto。LR分析驱动程序的行为是：LR分析表的存放LR分析表示LR分析法的基本依据，在分析程序运行过程中，需要不断地查LR分析表中的动作和转向状态，为此必须把LR分析表存放在一定的数据结构中。在LR分析过程中，所有的单调(终结符)均用其单词编码来识别。对于规约状态，应适合所有单词，对于移进状态，则只列出与状态有关的单词。一般将ACTION表和GOTO表分开存放。ACTION表的存放在实际存放时只存放表格中具有移进或归约、接受动作的单词编码及其相应的动作，用0代表所有出错的情况。二维数组SA存放ACTION表中的单词种类及动作，第一列存放单词编码，第二列存放动作。另外设一个一维数组SL作为指示器，Sl的下标为状态号，SL存放的是此状态从SA数组的第几行开始。例如SA数组行号第一列单词编码第二列动作11322430043999500616727800913102411001213132314001531160017SL数组下标（状态号）0 11 42 63 94 125 156 17789GOTO表的存放 GOTO表也可如ACTION表一样存放。用一个二维数组GL存放GOTO表，第一列为原状态，第二列为GOTO后的下一个状态。GOTO同样用一个一维数组NL作为指示器，NL的下标为产生式的编号，庶族的内容指向此产生式左部非终结符的GOTO表从GL数组的第几行开始。例如GL表行号现状态下一个状态1012183694125710613NL数组1 1 2 13 34 35 56 52. 总体设计LR分析器的主要模块：1、LR分析总控程序 LRANALYSE2、查ACTION表模块3、查GOTO表模块4、显示分析栈信息模块（用于测试）5、出错处理模块,6、初始化模块：主要是将LR分析表按设计好的存贮方式输入其余模块是与递归下降分析器共同的，例如读单词模块，显示错误的信息模块等。3.详细设计：主要程序模块如下：LRAnalysise 功能：LR分析器总控程序，即递归下降中PL函数searchActionTable 功能：查ACTION表模块searchGoToTable 功能：查GOTO表模块printAct 功能：显示分析栈信息模块（用于调试）searchPL 功能：调用产生式长度表fseek 功能：回退一条记录dealWithExpression 功能：语义处理push 功能：进行压栈操作pop 功能：执行出栈操作4. 分析程序分析程序比较简单，开始将状态0进栈，读入一个二元式（包括单词符号和编码），调用查ACTION表的子程序，得到相应的动作ACT（正数，负数，999，0 四种情况）。（1）正数：表示移进，将状态及单词编码等进栈（2）负数：表示归约，做相应归约动作。归约的动作包含下面几个步骤：a.按ACT（产生式编码）查PL数组，得到产生式长度n，即把栈指针SP回退n。b.按当前的栈顶状态k和产生式编号从NL数组查GL数组，得到下一个状态K, K 进栈.（3）999：分析结束，表示语句部分分析结束（当状态为1并且已到单词“end”时）（4）0： 表示出错，转出错处理程序。5. 调试在我们设计的语法制导翻译器中，LR分析程序公用于分析mini-pascal语言的可执行语句部分，它在递归下降分析程序分析到可执行语句时被调用。同时，为了生成中间代码，在分析过程中每执行完归约动作调用相应的语义子程序，执行语义动作。为此，LR分析器与递归下降分析器及语义处理程序密切相关，但它又可以进行独立调试。独立调试调试可分为二步，第一步是用语法正确的测试程序测试LR分析程序可否正确分析。第二步人为在测试程序中加一些语法错误来检查LR分析器出错处理是否成功。独立调试时，一些与递归下降分析器共享的模块也必须设置，而不能用一个空过程代替，如读单词模块，显示错误信息模块。因为子程序是在LR分析过程执行归约动作后调用的，当LR分析器独立调试时可以用一个显示程序代替语义处理程序，显示程序根据归约的产生式编码显示出相应的产生式，这样可以跟踪LR分析器分析过程。为了跟踪程序执行过程，还可以在程序中适当处加一些打印语句，比如打印出分析栈中的状态号，符号栈中的符号等，从分析栈和符号栈的情况可以判断LR分析器是否正常运转。与其它模块连接 A与递归下降分析器连接 当递归下降分析器，LR分析器分别独立调试成功后，可以将这两个模块连接起来，这时应首先将它们共同的模块合并，如两个模块均用到读单词程序。当它们分别调试时都要设置此模块，一旦把这个模块连接调试，显然不必用两个同样功能的读单词模块 B与语义程序连接递归下降分析器与LR分析器连接成功后再与语义程序相连接并借此以调试语义子程序。因为语义子程序无法单独测试，它的语义处理是在LR分析过程中进行的。连接工作包括：LR分析器归约动作后调用的显示程序用语义处理程序代替，模块的位置安排应该考虑到它被那些模块调用。调试结果LR分析法的语义处理一、语义处理的目的 语义处理目的：语法知道翻译过程中，一条语句语法分析结束时就应当声称与此语句等效的中间代码。中间代码既为本程序的最终输出。二、中间文件的数据分析 1. 中间代码形式 本程序中间代码采用四元式表示，具体格式为： 操作码：第一操作数，第二操作数，第三操作数四元式表 四元式表可为一个记录数组，每一条记录存放一条四元式，每个记录包括如下四项： 操作码OP， 用编码形式表示，为子界类型 三个操作数 opr1 , opr2 , opr3 , 每个操作数又为记录类型，包含下述四个域： 名字name 相对数 offset 类型 type 相对层差 rlevel(1) 操作数的名字: 实际上操作数的名字，如变量名A，临时变量名T2等对目标代码的翻译及运行是不起作用的，由其它三项内容已经可以实现存储分配。但作为调试显示信息用，应保留操作数名字。(2) 操作数类型：分3种类型，用编码表示：0变量1常数2临时变量(3) 操作数的相对数：若是变量，则相对数表示此变量是本过程的第几个变量。若是临时变量，则代表是第几个临时变量。若是常数，则相对数就是常数值。(4) 操作数的相对层数在翻译目标代码时，对变量进行存储分配时,只需要知道变量的相对数，以及使用此变量的过程层次与定义变量的过程层次之差，为此,要设下面一项操作数相对层数： 变量相对层数使用此变量的过程层次定义变量的过程层次 临时变量的相对层数为0，因为临时变量是翻译本过程可执行语句时临时设置的，不会被其它过程引用。 常数的相对数为常数值，相对层数为0如果四元式的某一个操作数空白不用，则相应的这三项内容均置为1。 2. 四元式的数据结构分析：四元式表：因为语法制导翻译过程中，有的四元式的第四元内容不能在声称四元式时就确定下来。因此要将四元式保存到四元式表中以待回填，然后再将四元式添加到四元式文件中以便输出四元式表为一个记录型数组，每一条数组存放一条四元式具体格式如下图 四元式表 操作数表nametypeoffectrlevelOPOPR1OPR2OPR3 其中每个操作数又定义为一个记录型数组，其4个域包括： 1），名字：name为操作数的名称，为调试时检查四元式而设置 2 ），类型：type为操作数的类型分为：0表示变量，1表示常数，2表示临时变量3），相对数：offect为操作数的相对数，若是变量，相对数表示此变量是本过程的第几个变量。若为临时变量，相对数为常数。若为常数，相对数就是常数值。4），相对层差：rlevel定义为使用变量的过程层数定义变量的过程层次。临时变量和常数的相对层数为0若四元式某一操作数空白不用，则其内容均为-1四元式文件：四元式文件是翻译生成的中间文件，其数据格式和四元式表稍有不同，即操作数没有名字域（name）既OPOPR1OPR2OPR3typeoffectrlevel四元式文件 操作数表三、语义分析的流程图LR分析器语义处理的总体设计1.语义动作的实现语义动作的实现是为可执行语句的各条产生式配备相应的语义子程序A: 语义子程序 以下是一些公共子程序： lookupv2 ()即ENTRY查找在符号表中的入口地址(由递归分析器实现) GEN过程：gen(op, opr1adr, opr2adr, opr3adr ,opr1type, opr2type, opr3type)在语义子程序中为emit( ) ，emit“()”中只是表示应生成的四元式。程序实现用GEN过程，应根据应生成的四元式指定相应的7个参数。 变量NEQ 指向下一条将产生的四元式地址，每执行GEN后，NEQ自动加1 newtemp函数过程，产生一个新临时变量名的整数码。如T1，T2，T3。 函数makelist(i)，创建一个仅含i的新链表。 函数merge (P1, P2)，把P1和P2链合为一个链。 过程backpatch (p, t ) ，回填，把P所链接的每个四元式的第四元填上t。.B: 语义动作总控程序各产生式相应的语义子程序可集中在此总控程序：按产生式编号 用case 语句调用。2.语义处理模块设置以及各模块分析：u主模块：生成中间代码的工作是边分析边进行的，与语法分析过程密切相关。每个产生式应配备那些语义动作是根据要生成的四元式而定的。关于语法分析每条产生式所应具备的语义动作，在编译原理书中有介绍，这里不再罗列出来。实现方法可以用一个开关语句列出各个产生式的语义动作例如：switch()case 0: /PL - Lw = yuyi.at(0);return w;。case 36: /LE- EXP ROPEXPLE.CHAN:=NXO；GEN（JROP，ENTEY（i），ENTRY （i），O）申请临时变量NEWTEMP方法：对表达式的翻译必须按其运算顺序生成中间代码，而且一条四元式表示一次运算，因此往往需要设置一些临时变量来存放运算的中间结果。如果我们用T1,T2,.,Tx作为临时变量名的话，那么可以用一个记数器来记录临时变量的序号，NEWTEMP为一个过程，每申请一个临时变量就将x值加1。实际上也不必奢一个过程来实现，因为只要一条语句x:=x+1就可以实现“申请了一个新的临时变量”。临时变量只是编译程序在生成中间代码是产生的，因此源程序的一个过程结束后，可以将x清零，使下一个过程临时变量又可以从T1开始。u合链回填模块回填动作就是对四元式中某一条四元式的第四元做一定修改，注意必须将第四元的名字域和相对数都修改。设置语义栈S.chain表示语句S中的一些四元式在S翻译完后要回填的四元式链，回填工作在处理S的外层环境的某一适当时候完成，所以必须把它作为语义值保存下来。值得注意的是由于mini-Pascal语言没有设置与、或、非等布尔操作，有关布尔表达式的语义分析可以大大简化，不需要设置E.TC和E.FC两个真、假链语义值，只需用一个E.chain来代表假链即可u查变量表模块在递归下降分析后，程序中的变量经分析后将存入变量表中，变量表记录了变量的变量名，变量所在的过程的层次，变量在其过程的相对数。这些属性在填写四元式表和四元式文件时都是必须的属性。u检查过程调用合理性模块对于call语句是否合法应做下面的工作1）此过程是否已定义，参数个数是否相等。2）过程调用关系是否正确，过程调用只允许：外过程调用内一层。同层调用，但被调用段应在调用段之前定义。内过程调用外过程要检查外过程是否为内过程的外过程。这3种情况对于参数个数是否相等，因为实参是依次排列的，在翻译其参数时应当先将参数地址存入一个队列中，设置一计数器parnumber计算参数个数u填四元式模块填写四元式表可以用一个过程GEN来处理，GEN过程参数为操作码，三个操作数的类型和地址共七个。每个操作数的四个域可以有其类型和地址查到。如果某一个操作数无用，那么它的相对数，类型，相对层差都置为-1，名字置为空串，其GEN过程对应得的参数也置为-1。由于对三个操作数个域的填写工作是一样的，为此在GEN过程中可嵌套一个字过程proceopr用于处理操作数的填写工作。 GEN过程：gen(op, opr1adr, opr2adr, opr3adr ,opr1type, opr2type, opr3type)在语义子程序中为emit( ) ，emit“()”中只是表示应生成的四元式。程序实现用GEN过程，应根据应生成的四元式指定相应的7个参数。 四元式表的指针PC开始是赋初值为1，每调用一次GEN过程将一条四元式存入PC所指的记录中，填完后将PC增值1，这样PC得值总是指向下一条是在四元式表的地址。注意：对整数进行填写时，name应转为字符串型注意：对于newtemp申请的临时变量名作为四元式中的一个操作数，在屏幕显示时，对于type等于2的，k转换为字符型，与t合并为tk输出。模块参数形式举例：gen(op,opr1type,opr1offect,opr2type,opr2offect,opr3type,opr3offect)停机指令：gen(9,-1,-1,-1,-1,-1,-1)注： gen获取操作数的属性由查变量表模块进行u输出四元式模块：由于语法规定只有无格式输入输出，为次，只要按所列的变量顺序产生相应得四元式即可。输出输出语句的变量如同call语句中的参数