《《编译原理》设计方案报告》由会员分享,可在线阅读,更多相关《《编译原理》设计方案报告(12页珍藏版)》请在金锄头文库上搜索。
1、编译原理课程设计报告设计题目:pio编译器设计一、PL0程序的文法及,指令及属性翻译简化c语言文法定义(LL (1)文法)C 程序:=void main () 函数体函数体:=变量定义部分 语句列变量定义部分:=变量定义 变量定义部分| ?变量定义:=int变量表变量表:=标识符|标识符,变量表语句列:=语句语句列| ?语句:=条件语句|循环语句|读语句|写语句|复合语句|表达式语句|空语句 条件语句:=if (表达式)语句循环语句:=while (表达式)语句读语句:=read (变量表);写语句:=write (表达式表);复合语句:=语句列;表达式语句:=表达式;空语句:=;表达式定义(
2、算符优先文法)表达式:=变量=表达式|变量+=表达式|变量-=表达式|变量*=表达式|变量/=表达式|变量%=表达式|表达式1表达式1 :=表达式1 |表达式2 |表达式2表达式2:=表达式2&表达式3 |表达式3表达式3:=表达式3=表达式4 |表达式3!=表达式4 |表达式3=表达式4 |表达式3表达式4 |表达式3=表达式4 |表达式3表达式4 |表达式4表达式4:=表达式4+表达式5 |表达式4-表达式5 |表达式5表达式5:=表达式5*表达式6 |表达式5/表达式6 |表达式5/表达式6 |表达式6表达式6: =!表达式7表达式7:=(表达式)|变量|常量PL0文法定义程序:=分程序
3、.分程序:=常量定义;常后分程序|常后分程序常后分程序:=变量定义;变后分程序|变后分程序变后分程序:=过程定义;变后分程序|语句常量定义:=const常量定义表常量定义表:=id = number | id = number,常量定义表变量定义:=var变量表变量表:=id | id,变量表过程定义:=procedure id ;分程序语句:=赋值语句I条件语句I循环语句I读语句I写语名I复合语句 |过程调用语句I 赋值语句:=id :=表达式读语句:=read(变量表)写语句:=write(表达式表)表达式表::=表达式 I表达式,表达式表条件语句:=if条件表达式then语句循环语句:=
4、while条件表达式do语句复合语句:=begin 语句列 end过程调用语句:=call id参量表:=有参表I 有参表:=表达式,有参表I表达式表达式:=+表达式1卜表达式1I表达式1表达式1:=表达式1+表达式 2I表达式1-表达式 2I表达式 2表达式 2:=表达式2*表达式3I表达式 2/表达式 3I表达式2mod表达式 3|表达式 3表达式 3:=id | number | (表达式)条件表达式=条件表达式or条件表达式1|条件表达式1条件表达式1:=条件表达式1and条件表达式 2|条件表达式2条件表达式2:=not 条件表达式3|条件表达式3关系表达式 关系表达式 关系表达式
5、关系表达式 关系表达式 关系表达式条件表达式3:=(条件表达式)|关系表达式=表达式表达式=表达式=表达式=表达式表达式=表达式=表达式=表达式=表达式=表达式#表达式PL0栈式机指令指令格式:指令码(f)所在层数差(I),操作数(a)PL0栈式机指令:LIT :将常数a取到栈顶LOD :将位于(当前层-l)层处的变量a取到栈顶STO:将栈顶处值存储到指定位置,l,a同上CALL调用当前-l层处的过程aINT :为调用过程在栈中开辟数据区,a为单元个数JMP:无条件转移指令,a目标地址JPC:条件转移指令,栈顶值的布尔值为非真时转移到a处,否则执行下面语句OPR:关系运算或算术运算义开始),C
6、ALL (call:过程调用语句)BEGIN ( begon:复合语句开始)PL0属性翻译MCONST ( con st:常量定义开始)VAR(var:变量定义开始),PROCEDURE (procedure:过程定END (end:复合语句结束), IF (if :条件语句开始),THEN(then :条件结束),WHILE (while :循环语句开始) DO (do:循环条件结束),READ (read :读语句), WRITE (write :输出语句), ODD ( odd :判奇运算),分隔符、运算符号DOT (点:.),COMMA (逗号:,), SEMICOLON (分号:;)
7、,LPAREN (左括号:(), RPAREN (右括号:),ASSIGNOP (赋值::=), PLUSOP (加法运算符号:+) MINUSOP (减法运算符:-),MULTOP (乘法运算符:*) DIVOP (除法运算符:/), GT (大于:),GE (大于等于:=),LT (小于:),LE (小于等于:=),EQ (等于:=),NE (不等:#),ENDF (输入结束符),分析过程中需要的非终结符号SERVERKEY (保留字),FACTOR (因子),ROP (关系运算),CONSTANT (常量部份定义) VARIABLE (变量部份定义) IDENT (自定义标识符),NUM
8、BER (常数)二、符号表的结构,组织,填写及查找1、符号表结构const char*pName;符号名称intki nd;符号类别,由上面单词分类确定intval;/符号表中的位置值intlevel;符号的层数intpare nt;符号的作用域intsize;/过程长度char strBuffMAXLENSTR;/符号堆2、符号表的组织符号表的组织方式有: 线性表、散列表、树结构等,其必须维持源程序中的作用域信息。 栈符号表:函数或分程序的嵌套结构, 使得程序中出现的符号的处理(内层可引用外层符号、同名变量内层优先) 与栈的操作相一致。一个过程结束时将释放相应的子符号表-解决作用域检查问题。
9、3、符号表的填写及查找词法分析子程序名为getsym,功能是从源程序中读取一个单词符号(taken),把他的信息放入全局变量sym id和num中,词法分析器需要单词时,直接从这三个变量中获得。Getsym过程通过反复调用 getch子过程从源程序获取字符,并把它们拼成单词。Getch过程使用了缓冲技术提高了运行效率。三、扫描器(词法分析器)1、词法分析子程序分析词法分析子程序名为getsym,功能是从源程序中读出一个单词符号( token),把它的信息放入全局变量 sym、id和num中,语法分析器需要单词时,直接从这三个变量中获得注意:语法分析器每次用完这三个变量的值就立即调用getsym
10、子程序获取新的单词供下一次使用。而不是在需要新单词时才调用getsym过程。getsym过程通过反复调用 getch子过程从源程序过获取字符,并把它们拼成单词。getch过程中使用了行缓冲区技术以提高程序运行效率。2、词法分析器的分析过程调用getsym时,它通过getch过程从源程序中获得一个字符。如果这个字符是字母,则继续获取字符或数字,最终可以拼成一个单词,查保留字表, 如果查到为保留字,则把sym变量赋成相应的保留字类型值;如果没有查到,则这个单词应是一个用户自定义的标识符(可能是变量名、常量名或是过程的名字),把sym置为ide nt,把这个单词存入id变量。查保留字表时使用了二分法
11、查找以提高效率。如果getch获得的字符是数字,则继续用getch获取数字,并把它们拼成一个整数,然后把sym置为number,并把拼成的数值放入 num变量。如果识别出其它合法的符号(比如:赋值号、大于号、小于等于号等),则把sym则成相应的类型。如果遇到不合法的字符,把 sym 置成 nul。3、词法分析函数getsym(所识别的单词:保留字或关键字:如:BEGIN、 END、 IF、 THEN等运算符:女口: +、-、*、人:=、#、=、=等标识符:用户定义的变量名、常数名、过程名常数: 女口: 10、25、100等整数界符: 女口: , 、 ;、 ( 等在编译程序中,单词的表示方式:(
12、sym, id/num)四、语法分析的设计1、语法分析子程序分析语法分析子程序采用了自顶向下的递归子程序法,语法分析同时也根据程序的语意生成相应的代码,并提供了出错处理的机制。语法分析主要由分程序分析过程(block)、常量定义分析过 程(constdeclaration )、变量定义分 析过 程(vardeclaration )、语句分析过程(statement)、表达式处理过程(expression)、项处理过程(term)、因子处理过程(factor) 和条件处理过程(condition )构成。这些过程在结构上构成一个嵌套的层次结构。除此之外,还有出错报告过程(error)、代码生成过
13、程(gen)、测试单词合法性及出错恢复过程(test)、 登录名字表过程(enter)、查询名字表函数(position)以及列出类PCODE代码过程(listcode) 作过语法分析的辅助过程。2、语法分析的设计与实现递归子程序法(递归下降分析器recursive-descent parser):对应每个非终结符(语法成分),编一个独立的处理子程序。由 程序开始,按规则右部(语法描述图箭头方向)进行分析:遇到非终结符,则调用相 应的处理过程;遇到终结符,则判断当前读入的单词是否与该终结符相匹配,若匹配,再读取下一个单词继续分析。图1 语法调用关系图五、代码生成和分配变量PL/O编译程序不仅完
14、成通常的词法分析、语法分析,而且还产生中间代码和目标”代码。PL/0处理机有两类存贮,目标代码放在一个固定的存贮数组code中,而所需数据组织成一个栈形式存放。PL/0处理机的指令集根据 PL/0语言的要求而设计,它包括以下的指令:(1)LIT /*将常数置于栈顶 */(2) LOD /*将变量值置于栈顶*/(3) STO /*将栈顶的值赋与某变量*/(4) CAL /*用于过程调用的指令*/(5) INT /*在数据栈中分配存贮空间*/(6) JMP, JPC /*用于if, while语句的条件或无条件控制转移指令*/(7) OPR /* 一组算术或逻辑运算指令*/FLaINT常最LIT常aLOD层次差数据地址STO层次差数据地址