编译原理实验

1、1.PL/01.PL/0编译程序编译程序 PL/0编译程序编译程序 PL/0 语言程序语言程序 类类 pcode 代码代码源语言源语言(PL/0) 目标语言目标语言( (类类pcodepcode) )实现语言实现语言（C/pascalC/pascal）PL/0PL/0编译程序编译程序类类 pcodepcode解释解释程序程序类类 pcode代码代码PL/0源程序源程序输入输入输出输出PL/0PL/0编译系统的结构框架编译系统的结构框架2.PL/02.PL/0语言语言z PL/0 PL/0语言特征语言特征z PL/0PL/0的的语法描述图语法描述图z PL/0PL/0语言语言文法的文法的EBNF

2、EBNF表示表示z PL/0PL/0程序示例程序示例 PL/0 PL/0语言是语言是PASCALPASCAL语言的语言的子集子集z数据类型数据类型, ,只有只有整型整型z数据结构数据结构 , ,只有只有简变简变和和常量常量z整数最多为整数最多为1414位位z标识符的有效长度是标识符的有效长度是1010位位z过程最多可过程最多可嵌套嵌套三层三层z作用域规则（内层作用域规则（内层可引用包围它的外层定可引用包围它的外层定义的义的标识符），标识符），过程可过程可嵌套定义，可递归嵌套定义，可递归调用调用 内的文字或符号表示内的文字或符号表示非终结符非终结符或或内的文字或符号表示内的文字或符号表示终结符终

3、结符2.2 语法描述图constidentnumbervaridentprocedureident分程序分程序语句语句分程序分程序例：用例：用语法描述图语法描述图描述分程序的定义描述分程序的定义 EBNF EBNF 引入的符号引入的符号( (元符号元符号) )： ：用左右尖括号括起来的语法成分为：用左右尖括号括起来的语法成分为非终结符非终结符 = ：定义为定义为 =的的左部左部由由右部右部定义定义 | | ：或或 ：表示花括号内的语法成分：表示花括号内的语法成分可重复可重复任意次或限任意次或限 定次数定次数 ：表示方括号内的语法成分为：表示方括号内的语法成分为任选项任选项 ( ) ( ) ：表

4、示圆括号内的成分：表示圆括号内的成分优先优先2.3 EBNF范式例：用例：用EBNFEBNF描述分程序的定义描述分程序的定义 = = CONST= CONST , , ; = = = VAR = VAR , , ; PL/0PL/0程序程序示例示例 CONST A=10; ( CONST A=10; (* * 常量说明部分常量说明部分 * *) )VAR B,C; (VAR B,C; (* * 变量变量说明部分说明部分 * *) )PROCEDURE PROCEDURE P;P; ( (* * 过程过程说明部分说明部分 * *) ) VAR D; VAR D; PROCEDURE PROCED

5、URE Q;Q; VAR X; VAR X; BEGINBEGIN READ(X); READ(X); D:=X; D:=X; WHILE X#0 DO WHILE X#0 DO CALL P; CALL P; END; END; BEGINBEGIN WRITE(D); WRITE(D); CALL Q; CALL Q; END; END;BEGINBEGIN CALL P; CALL P;END.END.Q的过程体的过程体P的过程体的过程体主主程序程序体体 3.PL/0编译程序的总体设计词法分析程词法分析程序序语法语义分析程序语法语义分析程序代码生成程序代码生成程序表格管理程序表格管理程序

6、出错处理程序出错处理程序PL/0PL/0源程序源程序目标程序目标程序z其编译过程采用其编译过程采用一趟扫描方式一趟扫描方式z以语法以语法、语义分析语义分析程序程序为核心为核心 词法分析词法分析程序和程序和代码生成代码生成程序都作为一个程序都作为一个过过程程，当语法分析需要读单词时就调用词法分，当语法分析需要读单词时就调用词法分析程序，而当语法析程序，而当语法、语义分析正确，需要生语义分析正确，需要生成相应的目标代码时，则调用代码生成程序。成相应的目标代码时，则调用代码生成程序。z表格管理表格管理程序实现程序实现变量变量，常量常量和和过程过程标识符标识符的的信息的登录与查找信息的登录与查找。z出

7、错处理出错处理程序，对词法和语法程序，对词法和语法、语义分析遇语义分析遇到的错误给出在源程序中到的错误给出在源程序中出错的位置出错的位置和与和与错错误误性质有关性质有关的编号，并进行错误恢复。的编号，并进行错误恢复。 4.词法分析分析过程所要完成的任务： z 读源程序（读源程序（getch)z 滤空格滤空格z 识别保留字识别保留字z 识别标识符识别标识符z 拼数拼数z 拼双字符单词拼双字符单词z 识别单字符单词识别单字符单词z 符号表符号表 type symbol=( nul, ident, number, plus, , varsym, procsym )；z 保留字保留字表：表：word1

8、:=BEGIN；word2:=CALL； .word13:=WRITE；z 单字符表：单字符表：ssym+:=plus; ssym-:=minus; ssym;:=semicolon;重要变量及过程重要变量及过程注意：按ASCII顺序存储保留字。查到时找到相应的查到时找到相应的内部表示内部表示wsym1:=wsym1:=beginsymbeginsym; ; wsym2:=wsym2:=callsymcallsym； wsym13:= wsym13:=writesymwritesym；z全局变量全局变量 1 1）SYMSYM：存放单词的类别：存放单词的类别 如：有程序段落为：如：有程序段落为：

9、 begin initial := 60begin initial := 60；endend 对应单词翻译后变为：对应单词翻译后变为： begin begin beginsymbeginsym, initial , initial identident, , := := becomesbecomes, 60 , 60 numbernumber, , ； semicolonsemicolon， end end endsymendsym 。2 2）IDID： 存放用户所定义的标识符的值存放用户所定义的标识符的值 如：如：initial initial （在（在SYMSYM中放中放identiden

10、t，在，在IDID中放中放initialinitial）3 3）NUMNUM：存放用户定义的数：存放用户定义的数 如：如：60 60 （在（在SYMSYM中放在中放在numbernumber在在NUMNUM中放中放6060）zGETSYM框图（见教材框图（见教材P19图图2.5）重要变量及过程任务一：读程序z内容内容y读程序读程序GetSym()z 识别保留字识别保留字z 识别标识符识别标识符z 拼数拼数z 拼双字符单词拼双字符单词z 识别单字符单词识别单字符单词z要求要求y每班前十名同学给予检查每班前十名同学给予检查任务二：扩充单词z内容内容y增加保留字：增加保留字：FOR、DOWNTO和T

11、Oy增加双字符单词：增加双字符单词：*=和/=z要求要求y设计测试方式，测试单词是否能被识别设计测试方式，测试单词是否能被识别y每班前十名同学给予检查每班前十名同学给予检查 5. 语法分析 递归子程序法z 对应对应每个非终结符每个非终结符语法单元，编一个独立的处语法单元，编一个独立的处 理过程（或子程序）。理过程（或子程序）。z 沿语法描述图沿语法描述图箭头箭头所指出的方向进行分析：所指出的方向进行分析： 1 1）遇到遇到分支点分支点时，将当前的单词与分支点上多个终时，将当前的单词与分支点上多个终结符结符逐个相比较逐个相比较，若都不匹配时可能是进入下一个非，若都不匹配时可能是进入下一个非终结符

12、语法单位或是出错。终结符语法单位或是出错。 2 2）当遇到）当遇到非终结符非终结符时，则时，则调用调用相应的相应的处理过程处理过程； 3 3）当遇到描述图中是）当遇到描述图中是终结符终结符时，则判断当前读入的时，则判断当前读入的单词是否与图中的终结符单词是否与图中的终结符相匹配相匹配，若匹配，再读取下，若匹配，再读取下一个单词继续分析一个单词继续分析。 程序程序 pl0分程序分程序 block语句语句 statement条件条件 condition表达式表达式expression项项 term因子因子 factor语语法法调调用用关关系系图图语句语句例：条件语句（不带例：条件语句（不带else

13、else子句）子句）的的递归子程序递归子程序if条件thenstatement()statement() if( SYM = ifsym )/ if( SYM = ifsym )/处理条件语句处理条件语句 getSym();getSym(); condition();condition(); if( SYM = thensym ) getSym(); if( SYM = thensym ) getSym(); else Error(); else Error(); statement();statement(); else / else /处理其它语句处理其它语句 语句任务三z 扩充条件语句（

14、带扩充条件语句（带else子句）子句）y 画出语法描述图画出语法描述图y 写出递归子程序写出递归子程序z 类类pcodepcode代码代码z 语句的语义分析和处理语句的语义分析和处理 6. 语义分析z目标代码目标代码类类pcodepcode是一种是一种假想栈式计算机假想栈式计算机的的汇编语言汇编语言。 指令格式：指令格式：z类类pcodepcode代码是由过程代码是由过程 GEN GEN 生成的，放在数组生成的，放在数组CODECODE中。中。f l af 功能码功能码l 层次差层次差 （标识符（标识符引用层引用层减去减去定义层定义层）a 根据不同的指令有所区别根据不同的指令有所区别6.1 类

15、pcode代码L LI IT T 0 0 a a 将将常常数数值值取取到到栈栈顶顶，a a为为常常数数值值 L LO OD D l l a a 将将变变量量值值取取到到栈栈顶顶，a a为为偏偏移移量量，l l为为层层差差 S ST TO O l l a a 将将栈栈顶顶内内容容送送入入某某变变量量单单元元中中，a a为为偏偏移移量量，l l为为层层差差 C CA AL L l l a a 调调用用过过程程，a a为为过过程程地地址址，l l为为层层差差 I IN NT T 0 0 a a 在在运运行行栈栈中中为为被被调调用用的的过过程程开开辟辟a a个个单单元元的的数数据据区区 J JM MP

16、 P 0 0 a a 无无条条件件跳跳转转至至a a地地址址 J JP PC C 0 0 a a 条条件件跳跳转转，当当栈栈顶顶布布尔尔值值非非真真则则跳跳转转至至a a地地址址，否否则则顺顺序序执执行行 O OP PR R 0 0 0 0 过过程程调调用用结结束束后后, ,返返回回调调用用点点并并退退栈栈 O OP PR R 0 0 1 1 栈栈顶顶元元素素取取反反 O OP PR R 0 0 2 2 次次栈栈顶顶与与栈栈顶顶相相加加，退退两两个个栈栈元元素素，结结果果值值进进栈栈 O OP PR R 0 0 3 3 次次栈栈顶顶减减去去栈栈顶顶，退退两两个个栈栈元元素素，结结果果值值进进栈

17、栈 O OP PR R 0 0 4 4 次次栈栈顶顶乘乘以以栈栈顶顶，退退两两个个栈栈元元素素，结结果果值值进进栈栈 O OP PR R 0 0 5 5 次次栈栈顶顶除除以以栈栈顶顶，退退两两个个栈栈元元素素，结结果果值值进进栈栈 O OP PR R 0 0 6 6 栈栈顶顶元元素素的的奇奇偶偶判判断断，结结果果值值在在栈栈顶顶 O OP PR R 0 0 7 7 O OP PR R 0 0 8 8 次次栈栈顶顶与与栈栈顶顶是是否否相相等等，退退两两个个栈栈元元素素，结结果果值值进进栈栈 O OP PR R 0 0 9 9 次次栈栈顶顶与与栈栈顶顶是是否否不不等等，退退两两个个栈栈元元素素，结

18、结果果值值进进栈栈 O OP PR R 0 0 1 10 0 次次栈栈顶顶是是否否小小于于栈栈顶顶，退退两两个个栈栈元元素素，结结果果值值进进栈栈 O OP PR R 0 0 1 11 1 次次栈栈顶顶是是否否大大于于等等于于栈栈顶顶，退退两两个个栈栈元元素素，结结果果值值进进栈栈 O OP PR R 0 0 1 12 2 次次栈栈顶顶是是否否大大于于栈栈顶顶，退退两两个个栈栈元元素素，结结果果值值进进栈栈 O OP PR R 0 0 1 13 3 次次栈栈顶顶是是否否小小于于等等于于栈栈顶顶，退退两两个个栈栈元元素素，结结果果值值进进栈栈 O OP PR R 0 0 1 14 4 栈栈顶顶值

19、值输输出出至至屏屏幕幕 O OP PR R 0 0 1 15 5 屏屏幕幕输输出出换换行行 O OP PR R 0 0 1 16 6 从从命命令令行行读读入入一一个个输输入入置置于于栈栈顶顶 指指令令功功能能表表 CONST a=10;CONST a=10;VAR b,c;VAR b,c;BEGINBEGIN READ(b); READ(b); WHILE WHILE b#0b#0 DO DO BEGIN BEGIN READ(b); READ(b); END ENDEND.END.( 0)( 0) int 0 5int 0 5( 1) opr 0 16( 1) opr 0 16( 2) st

20、o 0 3 ( 2) sto 0 3 ( 3) lod 0 3( 3) lod 0 3( 4) lit 0 0( 4) lit 0 0( 5) opr 0 9( 5) opr 0 9( 6) ( 6) jpc 0 16jpc 0 16( 7) opr 0 16( 7) opr 0 16( 8) sto ( 8) sto 0 0 3 3( 9) jmp 0 3( 9) jmp 0 3(10) opr 0 0(10) opr 0 0例：例：pcodepcode代码示例代码示例解释器的结构解释器的结构z 一维整型数组一维整型数组S S作为作为运行栈运行栈 RA RA DL DL SL SLbt每次调

21、用过程时会在栈顶分配每次调用过程时会在栈顶分配3 3个个存储单元：存储单元：RARA：返回地址返回地址，记录调用该过，记录调用该过程时程时目标程序的目标程序的断点断点；DLDL：动态链动态链，指向，指向调用调用过程的过程的ARAR基地址；基地址；SLSL：静态链静态链，指向，指向定义定义该过程该过程的的 直接定义外过程直接定义外过程的的ARAR基地基地址址当前AR的基地址栈顶位置 CONST a=10;CONST a=10;VAR b,c;VAR b,c;BEGINBEGIN READ(b); READ(b); WHILE WHILE b#0b#0 DO DO BEGIN BEGIN READ

22、(b); READ(b); END ENDEND.END.( 0)( 0) int 0 5int 0 5( 1) opr 0 16( 1) opr 0 16( 2) sto 0 3 ( 2) sto 0 3 ( 3) lod 0 3( 3) lod 0 3( 4) lit 0 0( 4) lit 0 0( 5) opr 0 9( 5) opr 0 9( 6) ( 6) jpc 0 10jpc 0 10( 7) opr 0 16( 7) opr 0 16( 8) sto 0 3( 8) sto 0 3( 9) jmp 0 3( 9) jmp 0 3(10) opr 0 0(10) opr 0 0

23、例：例：pcodepcode代码的解释执行代码的解释执行 c c b b 0 0 0 0 0 0 20 20 20 20 0 0 1 1 0 0 0 0 := if := if then then if( SYM = ident )/ if( SYM = ident )/处理条件语句处理条件语句 getSym();getSym(); condition();condition(); if(SYM = thensym) getSym(); if(SYM = thensym) getSym(); else Error(); else Error(); statement();statement()

24、; else / else /处理其它语句处理其它语句6.2 条件语句的语义分析和处理(a b)lod 0 alod 0 bopr 0 12write(a)lod 0 aopr 0 14opr 0 15 := if := if then then if( SYM = ident )/ if( SYM = ident )/处理条件语句处理条件语句 getSym();getSym(); condition();condition(); if(SYM = thensym) getSym(); if(SYM = thensym) getSym(); else Error(); else Error(); statement();statement(); else / else /处理其它语句处理其它语句6.2 条件语句的语义分析和处理C CS S(a b)lod 0 alod 0 bopr 0 12write(a)lod 0 aopr 0 14opr 0 15Y YN Nlod 0 alod 0 bopr 0 12lod 0 aopr 0 14opr 0 15jpc 0 0 := if := if then then if( SYM = ident )/ if( SYM = ident )/处理条件语句处理条件语句 getSym();ge