编译原理综合指导书-2011.11.02.doc

第一次上机 词法分析设计与实现一 任务从源程序文件中识别出一个个单词符号，构造标识符表，并按要求输出单词，符号的二元式，要求有出错报告。二 方法与输出编码单词种类： 标识符：假设长度有效为小于8个。 正整数：整数数字串。 保留字：program，var，procedure，begin，end，if，then，else，while，do，call。 单运算符： * / ( ) 双运算符： := = 界符： ； . ， 注释： /* */ 注：字母要小写。文法： | | | |*| / |( )| ；| .| | (非*) |(非) | (非) | |=| * / ： a|b|c|d| |x|y|z 0|1|2|7|8|9编码：标识符：(1，标识符表指针) 正整数(2，正整数值)program：(3,0) procedure：(5,0) var：(4,0)begin： (6,0) end：(7,0) if：(8,0)then：(9,0) else：(10,0) while：(11,0)do：(12,0) call：(13,0) integer：(14,0)real：(15,0) +：(16,0) ：(17,0)*：(18,0) /：(19,0) ：(20,0)：(21,0) ：(22,0) ：(23,0)：(25,0) =：(26,0)= ：(27,0) ：(28,0) :=：(29,0); ：(30,0) . ：(31,0) , ：(32,0)( ： (32,0) ) ：(33,0) : ：(34,0)三 举例调试程序：(行输入) program abc; var x,y,z; begin y:=219; z=37; x:=y*z; ? end. 数据结构定义： 输入缓冲区buf 指针frp 装配单调能用缓冲区：token 标识符表：idtab 保留字表 二元式表四 输出二元式序列：(class,value)(3,0)program (1,1)abc (30,0); (4,0)var(1,2)x (32,0), (1,3)y (32,0),(1,4)z (30,0); (6,0)begin (1,3)y(29,0):= (2,219)219 (30,0); (1,4)z(29,0):= (2,37)37 (30,0); (1,2)x(29,0):= (1,3)y (16,0)* (1,4)z(30,0); *error(1)* (7,0)end (31,0). 标识符表：序列名字地址1abc02x03y04z0注：标识符表结构： Recode Idname : string8 Idaddr : integer; end五 各子程序功能1 组合标识符：将当前的标识符串识别出来，放到token单元中(有效字符的长度不超过8个) 初始化：i=0 真读当前假读字符：Fread（1） 记录该字符到token中：token ( i )= Idtab(frp)，i=i+1 假读下一个有效字符：Readch(ch) 判断：if ch in a z or A Z or 0 9 goto l 重设下一个假读指针：Fread（2） 返回2 组合正整数：组合出当前数字串，并转化为整数 初始化：i=0 , value=0 真读当前假读字符：Fread（1） 记录该字符到token中：token（i）= Idtab(frp)，i=i+1 数值转化：value=value*10+(asc(ch)-asc(0) 假读下一个有效字符：Readch(ch) 判断：if ch in 0 9 goto 1 重设秒一个假读指针:Fread(2) 返回3 查保留关键字：检查当前的标识符为保留字，设保留字共为Mkey个4假读有效字符 若缓冲区不空：，则到：if not bufnil goto 4 若原程序文件结束，则置文件结束标志:fileend=True goto 7 从文件中读一行到缓冲区:read(f,buf) 设置缓冲区假读指针:frp=1 读字符:ch=buffrp,frp+ 判断字符 if ch=回车符 goto 6if ch= goto 4 置缓冲区标志为空:bufnil goto 1; 返回5.越过有效字符:必须在同一行 读字符:ch=buffrp,frp=frp+1 判断字符 if ch* goto 1 连读字符 ch=buffrp,frp=frp+1 判断字符 if ch/ goto 1 返回if ch= goto 46主控 初始化a.各种全程控制变量(bufnil=true,filenend=false,Mkey=?) b.建立保留字表 call Reakwork(code ,codevalue) 判断识别结果: if fileend=ture goto 5 输出或填入新二元式(code ,codevalue) 结束7.错误处理 假读:词法分析程序的错误为1号错误 显示出错单词及错误号:*error(1)*第二次上机 对下面文法编写语法分析程序文法 1. program id ; 2. ；begin end . 3. var ; 4. ： | ：； 5. integer 6. | ； 7. | ; 8. | 9. begin end 10. id:= 11. ifthenifthen else 12. whiledo 13. + 14. * 15. | () |ID | 16. | ！| & | | 17. 18. |=|=|要求：用递归子程序法实现输入：词法分析的二元式文件 第三次上机 语义分析一 数据结构定义 1 表格结构定义 标示符表 IDTAB 名字类型属性地址Name TypKindAddr其中： Typ=1整型 Kind=1简单变量 Typ=2实型 Kind=2临时变量 Kind=3值参变量 Kind=4变参变量指针： Lasent表长度指针层次表 LEVELTAB入口名字外层层次号参数个数标志符表首址活动记录长度InpNameOutrenLnumParnumPointerRecl Currbl当前层指针 Lasebl表长度指针四元式表 QUAD操作操作数操作数结果OpArg1Arg2Result指针：Nxq表长度指针2. 类型定义 string =Array1.8 of char; Idtype=Record name: string; tpy: 1.2 kind: 1.4 addr: integer; end; leveltype=Record name string; outem, lnum, parnum, varaum: integer; pointer, recl, temp, lnp: integer; end; temptype=Record used:Boolean; typ:1.2 taddr: integer; end; argtype=Record f1, f1value: integer; end; quadtype=Record op:integer; arg1, arg2, result : argtype; end;3. 变量定义 idtab:Array1.100 of idtype; leveltab:Array1.20 of leveltype;temptab : Array1.50 of temptype;quad: Array1.100 of quadtype;lasent, lastbl, currbl, tempp, nxq: integer;4.四元式操作编码操作Incalloutret:=I:=RparvalueIvalueR编码123456789操作addrjjjj=j=j1编码101112131415161719操作+R*I*R编码202122二 简化的栈式动态存储分配 语言要求： 允许有递归调用，不允许有分组程序结构和数组定义。1. 栈结构临时变量简化变量display表形式单元参数个数全局display地址返回地址老sp Top2.分配算法A. 执行过程语句时调用子程序： p(x) 保留老SP：TOP+1 (SP) 保留返回地址 记录全局display 地址 : TOP+3 TOP+(SP+3) 记录参数个数： TOP+4 N 构造display表: 设层次数为 level FOR I:=1 to level DO TOP+4+(TOP+4)+1 (SP+3 +(SP+3)+1 ) TOP+4+(TOP+4)+1 TOP+1转入子程序 (call) 传参数： 值参：任意值(value )变参：任意地址(addr)形参 通讯区 实参B. 进入程序后(1) 正式申请栈中空间：SPSP+1(in) TOPTOP+L(L-活动记录长度)(2) 为便量临时便量分配空间C. 退出过程(1) 收回为其分配的栈空间：TOPSP-1,SPTOP+1 (out)(2) 返回. (ret)3.四元式指令放置(1) (call ,n,leve;,p)-调用子程序； n-参数个数 level-层数 p-入口(2) (in,l,_,_)-申请空间；l-活动记录长度(3) (out,_,_,_)-退层；(4) (ret,_,_,_)-返回；(5) (addr,A,_,_)- 变参A完成参数交换(5) (value,A,_,_)- 值参A完成参数交换三、四元式指令1、 算术类： (OP,Arg1,Arg2,Result) 后缀i表示整数 (+I,A,B,T1) (+R,A,B,T1) 后缀 r表示实数 (*I,A,B,T1) (*R,A,B,T1)2、 跳转类： (J,_,_P) 无条件跳转到p (Jrop, Arg1,Arg2,p) 若Arg1 rop Arg2 成立，则跳转到P 其中 rop为,=,=,之一3、 赋值： (:=I,S,A_) s:=A整型赋值；(:=R,S,A_) s:=A 实型赋值;4、 动态分配：(In.L,_,_) I-活动记录长度:(Call,N,Lnum,P) N参加个数 lnum-静态层深度; P-过程入口(Out,_,_,_) 退层 ；(Ret,_,_，) 返回5参数传递：形参 通讯区 实参（Par,Ti_,_） (ValueI,Ti,_,_)(ValueR,Ti,_,_)(Addr,Ti,_,_)通讯区为了保证参与形参的 一致性（顺序性）说明；Arg1,Arg2,Result 在实现时定义为二元识(类型，值)其中:类型 值1-常数 常数值2-指令入口 指令地址3-临时变量 相4-直接访问变量 对5-间接访问变量 地6+i-第I层变量 址四 子过程1， 生成四元式字过程 Gen(Op,Arg1,Arg2,Result)2， 查标识符函数 Lookupv(id,idpoint,idlevel)3， 查层次表函数 lLookupp(Id)id:符号名 idlevel:层次结果：若id已存在:则返回符号表位置;否则返回04， 拉链 link:=merg(link2,link3)5， 回填 Backpatc(Link,point,value)6， 申请一临时变量 NEWTEMP(R:integer;VAR TP:integer)五 语义分析1 - program id;程序体语义动作为1，2，3，之后为5，6，7四元式结构;Res()= (Call,0,02) (in,1,_,_ )(Res() （Res()） （out,_,_,_） (Ret,_,_,_)语义动作：1 进程处理 ；扩充层次表Leveltab Currbl2 生成四元式 Gen(Call,(1,0),(1,0),(2,2)3 申请栈单元，因活动记录长度 L 在分析完后才知道，所以要后填入，记录该四元式 Gen(In,(0,0),(0,0),(0,0)4 调用5 将本主程序的活动记录长度填入第2个四元式BackPatch(Link,2,(2,Leveltabcurrbl.Recl) 其中 Link-链首 2-填四元式的第几项（回填位置） (2-填四元式的第几项-填入值)6 生成四元式： Gen(Out,(0,0),(0,0),(0,0) 生成后退层： Gen(Ret(0,0),(0,0),(0,0)7 修改指针变量 Currbl:=LeveltabCurrbl.Outern（生成返回）2. ；begin end . 四元式结构 Res() Res() = Res() 语义动作: 无3. var ;语义动作: 无4. ： | ：；四元式结构: 无语义动作: 无5. integer四元式结构: 无语义动作: 无6. | ；四元式结构: 无语义动作: 记录当前变量类型: N=0 整数 N=1 实数 对每一个标识符ID查本层的标识符表 若无,填写标识符表: Lasent:=Lasent+1 对IdtabLasent中各项内容 名字:= 类型:=N 属性:=1 分配单元:=LeveltabCurrbl.Recl 修改LeveltabCurrbl 中若干项内容 活动记录长度当 整型1个，实型2个 本层变量个数加1. | ; 四元式结构:Rse( ) = Res( ) Res( ) 语义动作: 无8. | | | | 四元式结构: Rse( ) = Res( ) 或Rse( ) = Res( ) 或Rse( ) = Res( ) 或Rse( ) = Res( )语义动作: 无9. begin end四元式结构: Rse( ) = Res( )语义动作: 无10. id := 四元式结构: Rse( ) = ( :=I, id, , - ) 或( :=R, id, , - )语义动作: 查Idtab表, Idpoint=Lookupv (Id, Idlevel)if Idpoint=0 then error 层深度号 else tl:=IdtabIdpoint.typ 记录类型 kl:=IdtabIdpoint.addr 记录相对地址对操作数分类 if Idlevel = LevelltabCurrbl.lnum 是否为本层 then if IdtabIdpoint.kind=4 是否为变参 then i1 :=4 变参,间接访问 else i1 :=3 局变,值参,直接访问 else il :=Idlevel+4 为第Idlevel外层 记录有关语义值分类: i2:= .Etyp j2:= .Evalue确定对非常数量的类型和相对地址 k2; t2 if i21 then ( k2:=j2, t2:=1 ) 整常量 else if i2=3 then k2:=TEMPtabj.taddr 临时变量 t2:=TEMPtabj.TTYP else k2:=Idtabj.addr t2:=Idtabj.typ 类型相容检查 if t1t2 then error 生成四元式 gen( :=I, (i1,k1), (i2,k2), (0,0) ;t1=1为整型 或 gen( :=R, (i1,k1), (i2,k2), (0,0) ;t1=2为实型 将已使用的临变释放 if i2=3 then TEMPtabj2.used:=false11. if then ifthen else 四元式结构 Res()Res()= TC:Res() (j, -, -, p) Fc:Res() P：为最外层if语句的下一条四元式首址语义值：因为分支结束的跳转地址要到分析完最外层（遇到 时才知 CHAIN需回填，其值为跳到判断所有四元式构成链的链首语义动作：1) 记录的语义值：TCexit=.TC FCexit=.FC2) 回填tc：backpatch（TCexit，4，（2，nxq）3) 记录的语义值（如为if语句） link1：=.CHAIN4) 产生绕过else分支的四元式 link2：=nxq Gen（j，-，-，（2，link1）5) 回填Fc,backpatch(FCexit,4,(2,nxq)6) 记录的语义值(如为if语句) link3:= .CHAIN7) 向前展望：有“；”存在backpatch（CHAIN，4，（2，nxq） .CHAIN：=null 否则.CHAIN12. while do四元式结构： P：res TC：res（ ）Res = （j，-，-，p） FC：res（）语义动作：1) 记录循环入口：loop：=P2) 记录语义值： TCexit：=.TC，FCexit：=.Fc3) 回填真出口： backpatch（TCexit，4，（2，nxq）4) 处理5) 产生循环回跳： gen（j，-，-（2，loop）6) 回填假出口： backpatch（FCexit，4，（2，nxq）13. + 四元式结构 Rea()=/(+,) . (+,) 语义动作: 1.记录语义值 i1:=.Etyp,j1:=.Evalue t1=1,k1=j1 当i1=1,即为常数 t1=TEMPTABj1.typ,k1=TEMPTABj1.addr 当i1=2,即为临变 t1=IDTABj1.Typ, k1=IDTABj1.addr 当i1=其它变量 2.记录语义值 i1:=.Etyp,j1:=.Evalue t2=1,k2=j2 当i2=1,即为常数 t2=TEMPTABj2.typ,k2=TEMPTABj2.addr 当i2=2,即为临变 t2=IDTABj2.Typ, k2=IDTABj2.addr 当i2=其它变量 3.确定中间结果类型 : t:=max(t1,t2) 4.申请一临时变量: j=NEWTEMP(t) j为临变在临变表中的位子 k=TEMPTABj.addr k为临变分配单元地址 确定新语义值: .ETYP:=3 .Evalue:=j 5.生成四元式: 1. ,为常数 gen(+,(1,j1),(1,j2),(3,k) 2. 为常数 gen(+,(1,j1),(i2,k2),(3,k) 3. 为常数 gen(+,(i1,k1),(1,j2),(3,k) 4. 否则 gen(+,(i1,k1),(i2,k2),(3,k) 6.将已使用过的临变释放 if i1=3 then TEMPTABj1.used:=false if i2=3 then TEMPTABj2.used:=false 14. * 四元结构 Res() =/ (*,) . (*,) 语义动作: 1.记录语义值 i1:=.Etyp,j1:=.Evalue t1=1,k1=j1 当i1=1,即为常数 t1=TEMPTABj1.typ,k1=TEMPTABj1.addr 当i1=2,即为临变 t1=IDTABj1.Typ, k1=IDTABj1.addr 当i1=其它变量 2.记录语义值 i1:=.Etyp,j1:=.Evalue t2=1,k2=j2 当i2=1,即为常数 t2=TEMPTABj2.typ,k2=TEMPTABj2.addr 当i2=2,即为临变 t2=IDTABj2.Typ, k2=IDTABj2.addr 当i2=其它变量 3.确定中间结果类型 : t:=max(t1,t2) 4.申请一临时变量: j=NEWTEMP(t) j为临变在临变表中的位子 k=TEMPTABj.addr k为临变分配单元地址 确定新语义值: .ETYP:=3 .Evalue:=j 5.生成四元式: 1. ,为常数 gen(+,(1,j1),(1,j2),(3,k) 2. 为常数 gen(+,(1,j1),(i2,k2),(3,k) 3. 为常数 gen(+,(i1,k1),(1,j2),(3,k) 4. 否则 gen(+,(i1,k1),(i2,k2),(3,k) 6.将已使用过的临变释放 if i1=3 then TEMPTABj1.used:=false if i2=3 then TEMPTABj2.used:=false 15. | () | | 四元式结构:无 语义动作: 第一分支:.Etyp:=.Etyp .Evalue:=.Evalue 第二分支: a.查找id 在标识符表中位置 lookupv( id , idpoint , idlevel) 标识符 表中位置，不在为所属层次号，本层为b判断if idpoint = 0 then errorelse if idlevel = 0 then case IDTABidpoint kind of ;本层处理 4:：Etyp：= ;变参 1.3:：Etyp：=3 ;局变;值参 else Etype：=idlevel+4 ;外层处理 Evalue：=idpoint第三分支：Etyp：=1，Evalue：=; con ;为常数值关于和中的若干问题因无布尔类型，仅用在控制语句中作为真、假分支选择开关，所以两个表达式的结果处理成控制语句中真、假分支的跳转地址，并称其为真出口和假出口，表示为TC和FC翻译方法： AB 含义为 if AB then true else false翻译成 TC P: (j，) FC P+1: (j，_，_，)（AB）含义为if AB then false else true 翻译成FC P： (j, A, B, ) TC P+1: (j, _, _, )（AB）(CD) 含义为if AB then true else if CD then true else false 翻译成 F: (j, A, B, ) P+1: (j, _, _, P+2) TC P+2: (j, C, D, P) FC P+3: (j, _, _, ) (AB)(CD) 含义为 if AB then if CD then true else false else false 翻译成P: (j, A, B, P+2) P+1: (j, _, _, ) TC P+2: (j, C, D, )