2021-06-08_山东大学编译原理pl0实验

目录

一、 课内实验要求 1
二、 要求和说明 1
（1）在程序运行界面突出显示： 1
（2）报告内容 1
1）概述: 源、目标语言，实现工具(平台)，运行平台 1
2）结构设计说明 1
3）主要成分描述 1
4）测试用例 1
5）开发过程和完成情况 1
三、实验环境与工具 2
四、设计方案 2
1.结构设计说明 2
（1）PL/0语言编译器 2
（2）各功能模块描述 3
（3）语法分析过程BLOCK是整个编译过程的核心。 5
2、 主要成分描述 6
① 符号表 6
② 运行时存储组织和管理 6
③ 语法分析方法 9
④ 中间代码表示 13
3、测试用例 15
（1） 任务一：读程序getsym() 15
（2） 任务二：扩充和修改单词 18
（3） 任务三：增加条件语句的ELSE子句 20
4、开发过程和完成情况 24
（1）增加单词： 24
（2） 修改单词：不等号# 改为 <> 30
（3） 增加条件语句的ELSE子句，要求：写出相关文法，语法图，语义规则。 30
五、 相关重要代码片段解析 34
六、 总结 38

一、课内实验要求

对PL/0作以下修改扩充：
（1）增加单词：保留字 ELSE，FOR，TO，DOWNTO，RETURN
运算符 *=，/=，++，–，&，||，！
（2）修改单词：不等号# 改为 <>
（3）增加条件语句的ELSE子句，要求：写出相关文法，语法图，语义规则。

二、要求和说明

（1）在程序运行界面突出显示：
设计者的班级、学号和姓名；
开始调试时间；
完成调试时间。
（2）报告内容
1）概述: 源、目标语言，实现工具(平台)，运行平台
2）结构设计说明
各功能模块描述
3）主要成分描述
① 符号表
② 运行时存储组织和管理
③ 语法分析方法
④ 中间代码表示
4）测试用例
5）开发过程和完成情况
三、实验环境与工具

计算机及操作系统：PC机，Windows 10
程序设计语言：C
教学型编译程序：PL/0
设计方案
概述: 源、目标语言，实现工具(平台)，运行平台
源语言：PASCAL
目标语言：假想栈式计算机的汇编语言，可称为类PCODE指令代码
实现工具：C++Builder 6
运行平台：Windows 10

四、设计方案

1.结构设计说明

（1）PL/0语言编译器
PL/0语言可以看成PASCAL语言的子集，它的编译程序是一个编译解释执行系统。PL/0的目标程序为假想栈式计算机的汇编语言，与具体计算机无关。
PL/0的编译程序和目标程序的解释执行程序都是用PASCAL语言书写的，因此PL/0语言可在配备PASCAL语言的任何机器上实现。
其编译过程采用一趟扫描方式，以语法分析程序为核心，词法分析和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就调用词法分析程序， 而当语法分析正确需要生成相应的目标代码时，则调用代码生成程序。
用表格管理程序建立变量、常量和过程表示符的说明与引用之间的信息联系。
用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错位性质。
当源程序编译正确时，PL/0编译程序自动调用解释执行程序，对目标代码进行解释执行，并按用户程序的要求输入数据和输出运行结果。

（2）各功能模块描述
PL/0语言使用PASCAL语言书写的，整个编译程序（包含主程序）是由18个嵌套机并列的过程或函数组成。
函数功能说明表：
过程或函数名 功能简要说明
PL0 主程序
Error 出错处理，打印出错位置和错误编码
GetCh 漏掉空格，读取一个字符
GetSym 词法分析，读取一个单词
GEN 生成目标代码，并送入目标程序区
TEST 测试当前单词符是否合法
ENTER 登录名字表
POSITION 查找标识符在名字表中的位置
ConstDeclaration 常量定义处理
VarDeclaration 变量定义处理
ListCode 列出目标代码清单
FACTOR 因子处理
TERM 项处理
EXPRESSION 表达式处理
CONDITION 条件处理
STATEMENT 语句部分处理
Block 分析程序处理过程
BASE 通过静态链求出数据区的基地址
Interpret 对目标代码的解释执行程序

过程或函数的嵌套定义结构

（3）语法分析过程BLOCK是整个编译过程的核心。
编译程序的总体流程如下图：

2、主要成分描述
①　符号表
为了组成一条指令，编译程序必须知道其操作码及其参数（数或地址）。这些值是由编译程序本身联系到相应标识符上去的。这种联系是在处理常数、变量和过程说明完成的。为此，标识符表应包含每一标识符所联系的属性；如果标识符被说明为常数，其属性值为常数值；如果标识符被说明成变量，其属性就是由层次和修正量（偏移量）组成的地址；如果标识符被说明为过程，其属性就是过程的入口地址及层次。常数的值由程序正文提供，编译的任务就是确定存放该值的地址。我们选择顺序分配变量和代码的方法；每遇到一个变量说明，就将数据单元的下标加一（PL／0 机中，每个变量占一个存贮单元）。开始编译一个过程时，要对数据单元的下标dx赋初值，表示新开辟一个数据区。dx的初值为3，因为每个数据区包含三个内部变量RA，DL 和SL。
②　运行时存储组织和管理
当编译程序经过语法分析，如果未发现错误时，由编译程序调用解释程序，对放在CODE中的目标代码从CODE[0]开始进行解释执行。当解释结束后，记录源程序中标示符的TABLE表已经没有作用了，因此存储区只需要以数组CODE存放的只读目标代码程序和运行时的数据区S，S是由解释程序定义的一维整型数组。由于PL/0语言的目标代码是一种假想的栈式计算机的汇编语言，用PASCAL语言解释执行，解释执行时的数据空间S为假栈式计算机存储空间。遵循后进先出规则，对每个过程当被调用时，才分配数据空间，退出程序时，则所有分配的数据被释放。
解释程序定义了4个寄存器。
I：指令寄存器。存放着当前正在执行的一条目标指令；
P：程序地址寄存器。指向下一条要执行的目标指令的地址（相当于CODE数组的下标）；
T：栈顶寄存器。由于每个过程当它运行时，给他分配的数据空间（数据段）可分为两部分：
静态部分 包括变量存放区和三个联系单元（SL、DL、RA）；
动态部分 作为临时工作单元和累加器使用。需要随时分配，用完后立即释放。栈顶寄存器T指出了当前栈中最新分配单元。
B：基址寄存器。指向每个过程被调用时，在数据区S中给它分配的数据段起始地址。
为了实现对每个过程调用时给它分配数据段，也就是对即将运行的过程所需数据段进栈；过程运行结束后释放数据段，即数据段退栈；以及嵌套过程之间对标识符引用的寻址问题。每个过程被调用时，在栈顶分配三个联系单元：
SL静态链：记录了定义该过程的直接外过程（或主程序）运行时最新数据段的基地址；
DL 动态链：记录调用该过程前正在运行的过程的数据段基地址；
RA 返回地址：记录调用该过程是目标程序的断点，即当时程序的地址寄存器P的值，也就是调用过程指令的下一条指令的地址。
PL/0编译程序给变量分配的地址只是确定变量在数据段内的相对位置。对每个过程从3开始顺序增加。3以前的三个单元为上面指出的三个联系单元。因此静态连接的作用是当一个过程引用包围它的过程所定义的标识符时，首先沿静态链跳过个数为层差的数据段，找到定义该标识符过程的数据段基地址，再加上所给标识符分配的相对位置，就得到该标识符在整个数据栈中的绝对位置（是在一个子过程要引用它的直接或间接父过程的变量时，可以通过静态链，跳过个数为层差的数据段，找到包含要引用的变量所在的数据段基地址，然后通过偏移地址访问它。在过程返回时，解释程序通过返回地址恢复指令指针的值到调用前的地址。）。动态链和返回地址的作用是当一个过程结束后，为恢复调用该过程前的执行状态而设置的。
例如，从后面的图中可以看出，当程序执行进入C过程后，在C中又调用B过程时，数据取栈中的状况，这时过程B的静态链是指向过程A的基地址的，而不是指向C的基地址。因为过程B是由A定义的，他的名字在A层的名字表中，当在C过程中调用B过程时，层差为2，所以这时应沿C过程数据的静态链，跳过两个数据段后的基地址，才是当前调用的B过程的静态链之值。这里可以看出，不管B过程在何时被调用，它的数据段静态链总是指向定义它的A过程的最新数据段基地址。

具体的过程调用和结束，对上述寄存器及三个联系单元的填写和恢复有下列目标指令完成。
（1）INT 0 A
每个过程目标程序的入口都有这样一条指令，用以完成开辟数据段的工作。A域的值指出数据段的大小，即为局部变量个数+3（3个联系单元）。由编译程序的代码生成给出。开辟数据段的结果是改变栈顶寄存器T的值，T：=T+A。
（2） OPR 0 0
是每个过程出口处的一条目标指令。用已完成该过程运行结束后释放数据段的工作。恢复调用该过程前正在运行的过程的数据段基地址寄存器的值，和栈顶寄存器T的值，并将返回地址送到指令地址寄存器P中，以使调用前的程序从断点开始继续执行。
（3）CAL L A
为调用过程的目标指令，其中：L为层差，他是寻找静态链的依据。在解释过程中有base函数来计算；A为被调用过程的目标程序入口。CALL指令还完成填写静态链、动态链、返回地址，给出被调用过程的基地址值，送入基地址寄存器B，目标程序的入口地址A的值送指令地址寄存器P中，式指令从A开始执行。
③　语法分析方法
1.PL/0语言文法的EBNF（巴克斯-瑙尔范式）表示
〈表达式〉::=[+|-]〈项〉{〈加法运算符〉〈项〉}
〈项〉::=〈因子〉{〈乘法运算符〉〈因子〉}
〈因子〉::=〈标识符〉|〈无符号整数〉|‘（’〈表达式〉‘）’
〈加法运算符〉::=+|-
〈乘法运算符〉::=*|/
〈关系运算符〉::==|#|<|<=|>|>=
〈条件语句〉::=IF〈条件〉THEN〈语句〉
〈过程调用语句〉::=CALL〈标识符〉
〈当型循环语句〉::=WHILE〈条件〉DO〈语句〉
〈读语句〉::=READ‘（’〈标识符〉{，〈标识符〉}‘）’
〈写语句〉::=WRITE‘（’〈表达式〉{，〈表达式〉}‘）’
〈字母〉::=a|b|…|X|Y|Z
〈数字〉::=0|1|…|8|9

2.语法分析的任务是识别由词法分析给出的单词符号序列在结构上是否符合给定的文法规则。PL/0编译程序的语法分析采用自顶向下的递归子程序法：对应每个非终结符语法单元，编一个独立的处理过程（或子程序）。
语法分析从读入第一个单词开始由非终结符‘程序’即开始符出发，沿语法描述图箭头方向进行分析。
当遇到非终结符时，调用相应的处理过程。从语法描述图看也就进入了一个语法单元，再沿单迁所进入的语法描述图的箭头方向进行分析。
当遇到描述图中的终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，则执行相应的语义程序（就是翻译程序），再读下一个单词继续分析。
遇到分支点时将当前的单词与分支点上的多个终结符逐个相比较，若不匹配时可能是进入下一个非终结符语法单元或是出错。
如果一个PL/0语言的单词序列在整个语法分析中，都能逐个得到匹配，直到程序结束符‘.’，这就说所输入的程序是正确的。对于正确的语法分析作相应的语义翻译，最终得到目标程序。
从PL/0的语法描述图可以清楚地看到，对PL/0语言进行语法分析时，各个非终结符语法单元所对应的分析过程存在相互调用关系。这种关系可以用图来描述。
PL/0语言的语法描述

程序语法描述图

分程序语法描述图

语句语法描述

条件语句描述图

表达式语法描述

项语法描述

因子语法描述

语法分析主要有两大部分的功能：说明部分的分析与过程体的分析，均在BLOCK过程中进行：

（1）说明部分的分析
由于PL/0语言允许过程调用语句，且允许过程嵌套定义。因此每个过程应有过程首部以定义局部于它自己过程的常量、变量和过程符号，也称局部变量。每个过程所定义的局部变量只能供它自己和它自己定义的内部过程引用。对于同层并列过程的调用关系是先定义的可以被后定义的引用，反之则不行。
说明部分的处理任务就是对每个过程（包括主程序，也可以看成一个主过程）的说明对象造名字表，填写所有层次（主程序为第0层，主程序定义的过程为第1层，随嵌套的深度增加而层次数加大，PL/0最多允许3层）、标识符的属性和分配的相对位置等。登录信息是调用ENTER过程完成。
所造表放在全程量一维数组TABLE中，TABLE的元素为记录型数据。TX为索引表的指针，LEV给出层次，DX给出每层局部变量当前已分配到的相对位置，可称位地址指示器，每说明完一个变量后DX加1。

（2）过程体的分析
程序的主体是由语句构成的。处理完过程的说明后就处理由语句组成的过程体，从语法上要对语句逐句分析。当语法正确时就生成相应语句功能的目标代码。当遇到标识符的引用时就调用POSITION函数查TABLE表，看是否有过正确的定义，若已有，则从表中取相应的信息，供生成代码用，否则出错。

④　中间代码表示

PL/0编译程序所产生的目标代码类PCODE是一个假想栈式计算机汇编语言，它不依赖于任何实际计算机，其指令格式如下：
f l a
功能码 层次差 操作数

其中f为功能码；l表示层次差，即变量或过程被引用的分程序与说明该变量或过程的分程序之间的层次差；a的含义对不同的指令有所区别，可以是常数值、位移量、操作符代码等。

目标指令有8条：
1 LIT 0 a --------------- a为常数 a进栈
2 LOD l a l为调用层与说明层的层差 a为变量在所说明层中的相对位置 变量进栈
3 STO l a l为调用层与说明层的层差 a为变量在所说明层中的相对位置 栈顶的内容给变量
4 CAL l a l为层差 a为被调用过程的目标程序入口地址 调用过程
5 INT 0 a ------------------- a为开辟的单元个数 为被调用的过程在栈中开辟数据区
6 JMP 0 a ------------------- a为转向地址 无条件转移
7 JPC 0 a ------------------- a为转向地址 栈顶布尔值非零时转移
8 OPR l a l为层差 a为操作符编码 栈顶与次栈顶的内容进行运算，结果放次栈顶

OPR的l域为0，a域的内容决定操作含义，具体说明为：
a＝0 过程调用结束后返回调用点，并释放被调过程在运行栈的数据空间
a＝1 栈顶值取反结果在栈顶。
a＝2～5 将栈顶和次栈顶内容做算术运算，结果存放在次栈顶。
a＝2 次栈顶与栈顶相加，退两个栈元素，结果值进栈
a＝3 次栈顶减去栈顶，退两个栈元素，结果值进栈
a＝4 次栈顶乘以栈顶，退两个栈元素，结果值进栈
a＝5 次栈顶除以栈顶，退两个栈元素，结果值进栈
a＝6 对栈顶值做奇偶判断，奇数为真，偶数为假，结果在栈顶。
a＝8～13 将栈顶和次栈顶内容做关系运算，结果存放次栈顶。
a＝14 栈顶值输出到屏幕。
a＝15 屏幕输出换行。
a＝16 从命令行读人一个输入到栈顶。
a 为其他值均为非法指令。
3、测试用例
（1）任务一：读程序getsym()
要求
设计测试方式(将语句必须写在getsym()合适的地方)，测试单词是否能被识别（只完成了词法分析部分，代码运行出错不用理会）
Form1->printfs (“关键字”);
Form1->printfs (“标识符”);
Form1->printfs(“数字”);
Form1->printfs(“双符号");
Form1->printfs(“单字符”);

代码位置插入截图：

图中相应代码，注释掉了

测试源码E01.PL0
PROGRAM EX01;
VAR A,B,C;
BEGIN
A:=88;
READ(B);
C:=A+B*(3+B);
WRITE©
END.

（2）任务二：扩充和修改单词
测试源码NEQL.PL0
PROGRAM NEQL;
VAR A,B;
BEGIN
READ(A);
B:=0;
IF A<>0 THEN B:=1;
WRITE(B);
END.

检测A等于0，不满足if条件：
输入 0

检测A不等于0，满足if条件
输入 1

（3）任务三：增加条件语句的ELSE子句
测试源码ELSE.PL0
PROGRAM EX03;
VAR A,B,C;
BEGIN
A:=1;
READ(B);
IF A=B THEN
WRITE(A)
ELSE WRITE(B);
END.

检测执行THEN语句，不执行ELSE语句，A等于B：
输入 1

检测不执行THEN语句，执行ELSE语句，A不等于B：
输入 2

测试源码ELSE.PL0（去掉ELSE）
PROGRAM EX03;
VAR A,B,C;
BEGIN
A:=1;
READ(B);
IF A=B THEN
WRITE(A)
WRITE(B);
END.

检测执行THEN语句，A等于B：
输入 1

检测不执行THEN语句，A不等于B，剩余语句顺序执行：
输入 0

测试源码ELSE.PL0
PROGRAM EX03;
VAR A,B,C;
BEGIN
A:=2;
READ(B);
IF A=B THEN
WRITE(A+B)
ELSE WRITE(B);
END.

检测不执行THEN语句，执行ELSE语句，A不等于B：
输入0

检测执行THEN语句，不执行ELSE语句，A等于B：
输入2

4、开发过程和完成情况
（1）增加单词：
保留字 ELSE，FOR，TO，DOWNTO，RETURN
运算符 =，/=，++，–，&，||，！
增加5个保留字和7个运算符，合计12个单词。
其中保留字ELSE，FOR，TO，DOWNTO，RETURN分别对应
ELSESYM，FORSYM，TOSYM，DOWNTOSYM，RETURNSYM,
运算符 =，/=，++，–，&，||，！对应
TIMESBECOMES，SLASHBECOMES，PLUSONE，MINUSONE，ANDSYM，ORSYM，NOTSYM。
增加保留字
typedef enum { NUL, IDENT, NUMBER, PLUS, MINUS, TIMES,
SLASH, ODDSYM, EQL, NEQ, LSS, LEQ, GTR, GEQ,
LPAREN, RPAREN, COMMA, SEMICOLON, PERIOD,
BECOMES, BEGINSYM, ENDSYM, IFSYM, THENSYM,
WHILESYM, WRITESYM, READSYM, DOSYM, CALLSYM,
CONSTSYM, VARSYM, PROCSYM, PROGSYM,
/插入/
ELSESYM, FORSYM, TOSYM, DOWNTOSYM, RETURNSYM,
TIMESBECOMES/ = /, SLASHBECOMES//=/, PLUSONE/++/,
MINUSONE/–/, ANDSYM/&/, ORSYM/||/, NOTSYM/!/
//
} SYMBOL;
char *SYMOUT[] = {“NUL”, “IDENT”, “NUMBER”, “PLUS”, “MINUS”, “TIMES”,
“SLASH”, “ODDSYM”, “EQL”, “NEQ”, “LSS”, “LEQ”, “GTR”, “GEQ”,
“LPAREN”, “RPAREN”, “COMMA”, “SEMICOLON”, “PERIOD”,
“BECOMES”, “BEGINSYM”, “ENDSYM”, “IFSYM”, “THENSYM”,
“WHILESYM”, “WRITESYM”, “READSYM”, “DOSYM”, “CALLSYM”,
“CONSTSYM”, “VARSYM”, “PROCSYM”, “PROGSYM”,
/*插入/
“ELSESYM”, “FORSYM”, “TOSYM”, “DOWNTOSYM”, “RETURNSYM”,
“TIMESBECOMES”, “SLASHBECOMES”, “PLUSONE”,
“MINUSONE”, “ANDSYM”, “ORSYM”, “NOTSYM”
//
};
strcpy(KWORD[ 1],“BEGIN”); strcpy(KWORD[ 2],“CALL”);
strcpy(KWORD[ 3],“CONST”); strcpy(KWORD[ 4],“DO”);
/插入/strcpy(KWORD[5],“DOWNTO”);
/插入/strcpy(KWORD[6],“ELSE”);
strcpy(KWORD[ 7],“END”);
/插入/strcpy(KWORD[8],“FOR”);
strcpy(KWORD[ 9],“IF”);
strcpy(KWORD[ 10],“ODD”); strcpy(KWORD[ 11],“PROCEDURE”);
strcpy(KWORD[ 12],“PROGRAM”); strcpy(KWORD[13],“READ”);
/插入/strcpy(KWORD[14],“RETURN”);
strcpy(KWORD[15],“THEN”);
/插入/strcpy(KWORD[16],“TO”);
strcpy(KWORD[17],“VAR”);
strcpy(KWORD[18],“WHILE”); strcpy(KWORD[19],“WRITE”);
WSYM[ 1]=BEGINSYM; WSYM[ 2]=CALLSYM;
WSYM[ 3]=CONSTSYM; WSYM[ 4]=DOSYM;
/插入/WSYM[ 5]=DOWNTOSYM;
/插入/WSYM[ 6]=ELSESYM;
WSYM[ 7]=ENDSYM;
/插入/WSYM[ 8]=FORSYM;
WSYM[ 9]=IFSYM;
WSYM[ 10]=ODDSYM; WSYM[ 11]=PROCSYM;
WSYM[ 12]=PROGSYM; WSYM[13]=READSYM;
/插入/WSYM[ 14]=RETURNSYM;
WSYM[15]=THENSYM;
/插入/WSYM[ 16]=TOSYM;
WSYM[17]=VARSYM;
WSYM[18]=WHILESYM; WSYM[19]=WRITESYM;
SSYM[’+’]=PLUS; SSYM[’-’]=MINUS;
SSYM[’’]=TIMES; SSYM[’/’]=SLASH;
SSYM[’(’]=LPAREN; SSYM[’)’]=RPAREN;
SSYM[’=’]=EQL; SSYM[’,’]=COMMA;
SSYM[’.’]=PERIOD; //SSYM[’#’]=NEQ; 注释掉 改为<>
SSYM[’;’]=SEMICOLON;
/插入/
SSYM[’&’]=ANDSYM;
SSYM[’!’]=NOTSYM;
在STATEMENT(SYMSET FSYS,int LEV,int &TX)函数中增加：
/插入保留字/
case FORSYM:
GetSym();
break;
case TOSYM:
GetSym();
break;
case DOWNTOSYM:
GetSym();
break;
case RETURNSYM:
GetSym();
break;
/*******************/
增加运算符
在GetSym()函数中增加：
/插入/
else
if (CH==’’) {
GetCh();
if (CH==’=’) { SYM=TIMESBECOMES; GetCh(); }
else SYM=TIMES;
}
else
if (CH==’/’) {
GetCh();
if (CH==’=’) { SYM=SLASHBECOMES; GetCh(); }
else SYM=SLASH;
}
else
if (CH==’+’) {
GetCh();
if (CH==’+’) { SYM=PLUSONE; GetCh(); }
else SYM=PLUS;
}
else
if (CH==’-’) {
GetCh();
if (CH==’-’) { SYM=MINUSONE; GetCh(); }
else SYM=MINUS;
}
else
if (CH==’&’) {
SYM=ANDSYM;
GetCh();
}
else
if (CH==’|’) {
GetCh();
if (CH==’|’) { SYM=ORSYM; GetCh(); }
else Error(19);
}
else
if (CH==’！’) {
SYM=NOTSYM;
GetCh();
}
/****************************************/
在STATEMENT(SYMSET FSYS,int LEV,int &TX)函数中增加：
/插入单词/
case TIMESBECOMES:
GetSym();
Form1->printfs("=");
break;
case SLASHBECOMES:
GetSym();
Form1->printfs("/=");
break;
case PLUSONE:
GetSym();
Form1->printfs("++");
break;
case MINUSONE:
GetSym();
Form1->printfs("–");
break;
case ANDSYM:
GetSym();
Form1->printfs("&");
break;
case ORSYM:
GetSym();
Form1->printfs("||");
break;
case NOTSYM:
GetSym();
Form1->printfs("!~~~~");
break;
//
保留字和单词的个数
原保留字个数是14，新增加保留字5个，故const NORW=14;
应改为const NORW = 19;
原单词总数是33，新增加单词12个，故将所有的33改为43（Error（33）除外），
定义sysnum为数值45，将所有的33替换为sysnum（Error（33）除外）。
（2）修改单词：不等号# 改为 <>
首先把源代码中的程序段SSYM[’#’]=NEQ;删除或注释。
然后在GetSym()函数中把<>定义为不等号#。

在GetSym()函数中该位置修改添加代码：
if (CH==’<’) {
GetCh();
if (CH==’=’) { SYM=LEQ; GetCh(); }
/不等号# 改为 <>/
else
if (CH==’>’) { SYM=NEQ; GetCh(); }
/*************************/
else SYM=LSS;
}
（3）增加条件语句的ELSE子句，要求：写出相关文法，语法图，语义规则。

a.相关文法

G(S):S→if S else S | if S | a

b.语法图

c.语义规则
IF语句先判断条件B是否成立，一：条件B成立，顺序执行THEN语句，执行完语句S1后，跳过ELSE语句，执行ELSE语句后面代码；二：条件B不成立，跳过THEN语句，执行ELSE语句及ELSE语句后语句代码。

产生式 语义规则
S→if B then M S1 {
backpatch(E.truelist, M.quad );
S.nextlist:=merge(E.falselist,S1.nextlist)
}
M→ε { M.quad := nextquad; }
N→ε {
M.quad := nextquad;
Gen( j , - , - , 0 )
}
S→if B then M S1
N else M2 S2 {
backpatch(E.truelist, M1.quad );
backpatch(E.falselist, M2.quad );
S.nextlist:=merge(S1.nextlist,N.nextlist,S2.nextlist)
}

d.在TATEMENT(SYMSET FSYS,int LEV,int &TX)函数中代码修改及解析：
〈条件语句〉::=IF〈条件〉THEN〈语句〉
IF ： case IFSYM:/* 准备按照IF语句处理 /
GetSym();
〈条件〉： / 后继符号为THEN或DO*/
/* 调用条件处理 / CONDITION(SymSetUnion(SymSetNew(THENSYM,DOSYM),FSYS),LEV,TX);
/
SymSetNew(THENSYM,DOSYM)得出新的SYMSET S，S[THENSYM]=1; S[DOSYM]=1;
/
/
SymSetUnion(SymSetNew(THENSYM,DOSYM),FSYS)
SymSetNew(THENSYM,DOSYM)对比（后继符号）FSYS，是否存在 S[i]=1
调用CONDITION函数判断〈条件〉布尔值
/
/先确认条件语句是否规范，然后在记录代码位置才有意义/
if (SYM==THENSYM) GetSym();/〈条件〉逻辑真/
else Error(16);/ 缺少then /
CX1=CX;/ 保存当前指令地址 //〈条件〉逻辑假/
GEN(JPC,0,0);
/ 生成条件跳转指令，跳转地址未知，暂时写0 /
/跳掉THENSYM执行的代码/
〈语句〉： STATEMENT(FSYS,LEV,TX);/ 处理THEN后的语句 */

/修改***/
// CODE[CX1].A=CX;
/* 经STATEMENT处理后，CX为THEN后语句执行完的位置，/
/ 它正是前面未定的跳转地址，此时进行回填 /
/**************************/

              CX2=CX;
1

/前面条件为真THEN语句正常执行，直接跳掉ELSE语句/
GEN(JMP,0,0);

/前面条件为假THEN语句不执行，跳到下一语句/
CODE[CX1].A=CX;
/若SYM==ELSE保留字跳到ELSE语句，若SYM！=ELSE语句，
不会报错， 允许IF后无ELSE,IF后语句按顺序执行/

	           if (SYM==ELSESYM){ GetSym();           
              STATEMENT(FSYS,LEV,TX);  
              CODE[CX2].A=CX; }  
             /* 经STATEMENT处理后，CX为ELSE后语句执行完的位置，
                它正是前面未定的跳转地址，此时进行回填 */
              break;
1
2
3
4
5
6

五、相关重要代码片段解析
//---------------------------------------------------------------------------
/* * 词法分析，获取一个符号 */
词法分析程序GETSYM将完成下列任务：
（1）空格；
（2）识别保留字；
（3）识别标识符；
（4）拼数；
（5）拼复合词，如：>=、:=、<=等单词；
（6）输出源程序
在GETSYM中要调用GETCH，其功能是取字符。

void GetSym() {
int i,J,K; ALFA A;
while (CH<=’ ') GetCh(); /* 过滤空格*/
if (CH>=‘A’ && CH<=‘Z’) { /ID OR RESERVED WORD//* 当前的单词是标识符或是保留字 /
K=0;
do {
if (K<AL) A[K++]=CH;
GetCh();
}while((CH>=‘A’ && CH<=‘Z’)||(CH>=‘0’ && CH<=‘9’));
A[K]=’\0’;
strcpy(ID,A); i=1; J=NORW;
do {/ 搜索当前单词是否为保留字，使用二分法查找 /
K=(i+J) / 2;
if (strcmp(ID,KWORD[K])<=0) J=K-1;
if (strcmp(ID,KWORD[K])>=0) i=K+1;
}while(i<=J);
if (i-1 > J) SYM=WSYM[K];/ 当前的单词是保留字 /
else SYM=IDENT;/ 当前的单词是标识符 /
}
else
if (CH>=‘0’ && CH<=‘9’) { /NUMBER// 当前的单词是数字 /
K=0; NUM=0; SYM=NUMBER;
do {
NUM=10NUM+(CH-‘0’);
K++; GetCh();
}while(CH>=‘0’ && CH<=‘9’);/* 获取数字的值 /
if (K>NMAX) Error(30);/ 数字位数太多 /
}
else
if (CH==’:’) {/ 检测赋值符号 /
GetCh();
if (CH==’=’) { SYM=BECOMES; GetCh(); }
else SYM=NUL;/ 不能识别的符号 /
}
else / THE FOLLOWING TWO CHECK WERE ADDED
BECAUSE ASCII DOES NOT HAVE A SINGLE CHARACTER FOR <= OR >= /
if (CH==’<’) {/ 检测小于或小于等于符号 /
GetCh();
if (CH==’=’) { SYM=LEQ; GetCh(); }
else SYM=LSS;
}
else
if (CH==’>’) {/ 检测大于或大于等于符号 /
GetCh();
if (CH==’=’) { SYM=GEQ; GetCh(); }
else SYM=GTR;
}
else { SYM=SSYM[CH]; GetCh(); }/ 当符号不满足上述条件时，全部按照单字符符号处理 */
} /GetSym()/

//---------------------------------------------------------------------------
/* 语句处理 /
void STATEMENT(SYMSET FSYS,int LEV,int &TX) { /STATEMENT/
int i,CX1,CX2;
switch (SYM) {
case IDENT:/ 准备按照赋值语句处理 /
i=POSITION(ID,TX);/ 查找标识符在符号表中的位置 /
if (i==0) Error(11);/ 标识符未声明 /
else
if (TABLE[i].KIND!=VARIABLE) { /ASSIGNMENT TO NON-VARIABLE/分配给非变量/
Error(12);/ 赋值语句中，赋值号左部标识符应该是变量 /
i=0;
}
GetSym();
if (SYM==BECOMES) GetSym();
else Error(13);/ 没有检测到赋值符号 /
EXPRESSION(FSYS,LEV,TX);/ 处理赋值符号右侧表达式 /
if (i!=0) GEN(STO,LEV-TABLE[i].vp.LEVEL,TABLE[i].vp.ADR);
/ expression将执行一系列指令，但最终结果将会保存在栈顶，执行sto命令完成赋值 /
break;
case READSYM:/ 准备按照read语句处理 /
GetSym();
if (SYM!=LPAREN) Error(34);/ 格式错误，应是左括号 /PAREN：括号
else
do {
GetSym();
if (SYM==IDENT) i=POSITION(ID,TX);/ 查找要读的变量 /
else i=0;
if (i==0) Error(35);/ read语句括号中的标识符应该是声明过的变量 /
else {
GEN(OPR,0,16);/ 生成输入指令，读取值到栈顶 /
GEN(STO,LEV-TABLE[i].vp.LEVEL,TABLE[i].vp.ADR);
/ 将栈顶内容送入变量单元中 /
}
GetSym();
}while(SYM==COMMA);/ 一条read语句可读多个变量 /逗号，段落
if (SYM!=RPAREN) {
Error(33);/ 格式错误，应是右括号 /
while (!SymIn(SYM,FSYS)) GetSym();/ 出错补救，直到遇到上层函数的后继符号 /
}
else GetSym();
break; / READSYM /
case WRITESYM:/ 准备按照write语句处理 /
GetSym();
if (SYM==LPAREN) {
do {
GetSym();
EXPRESSION(SymSetUnion(SymSetNew(RPAREN,COMMA),FSYS),LEV,TX);
/ 调用表达式处理 /
GEN(OPR,0,14);/ 生成输出指令，输出栈顶的值 /
}while(SYM==COMMA);/ 一条write可输出多个变量的值 /
if (SYM!=RPAREN) Error(33);/ 格式错误，应是右括号 /
else GetSym();
}
GEN(OPR,0,15);/ 生成换行指令 /
break; /WRITESYM/
case CALLSYM:/ 准备按照call语句处理 /
GetSym();
if (SYM!=IDENT) Error(14);/ call后应为标识符 /
else {
i=POSITION(ID,TX);
if (i==0) Error(11);/ 过程名未找到 /
else
if (TABLE[i].KIND==PROCEDUR)
GEN(CAL,LEV-TABLE[i].vp.LEVEL,TABLE[i].vp.ADR);/ 生成call指令 /
else Error(15);/ call后标识符类型应为过程 /
GetSym();
}
break;
case IFSYM:/ 准备按照if语句处理 /
GetSym();
/ 后继符号为then或do /
CONDITION(SymSetUnion(SymSetNew(THENSYM,DOSYM),FSYS),LEV,TX);
/ 调用条件处理 /
if (SYM==THENSYM) GetSym();
else Error(16);/ 缺少then /
CX1=CX;/ 保存当前指令地址 /
GEN(JPC,0,0);/ 生成条件跳转指令，跳转地址未知，暂时写0 /
STATEMENT(FSYS,LEV,TX);/ 处理then后的语句 /
CODE[CX1].A=CX;
/ 经statement处理后，cx为then后语句执行完的位置，
它正是前面未定的跳转地址，此时进行回填 /
break;
case BEGINSYM:/ 准备按照复合语句处理 /
GetSym();
STATEMENT(SymSetUnion(SymSetNew(SEMICOLON,ENDSYM),FSYS),LEV,TX);
/ 后继符号为分号或end /
/ 对begin与end之间的语句进行分析处理 /
while (SymIn(SYM, SymSetAdd(SEMICOLON,STATBEGSYS)))
/ 如果分析完一句后遇到语句开始符或分号，则循环分析下一句语句 /
{
if (SYM==SEMICOLON) GetSym();
else Error(10);/ 缺少分号 /
STATEMENT(SymSetUnion(SymSetNew(SEMICOLON,ENDSYM),FSYS),LEV,TX);
}
if (SYM==ENDSYM) GetSym();
else Error(17);/ 缺少end /
break;
case WHILESYM:/ 准备按照while语句处理 /
CX1=CX; / 保存判断条件操作的位置 /
GetSym();
CONDITION(SymSetAdd(DOSYM,FSYS),LEV,TX);/ 调用条件处理 /
CX2=CX;/ 保存循环体的结束的下一个位置 /
GEN(JPC,0,0);/ 生成条件跳转，但跳出循环的地址未知，标记为0等待回填 /
if (SYM==DOSYM) GetSym();
else Error(18);/ 缺少do /
STATEMENT(FSYS,LEV,TX);/ 循环体 /
GEN(JMP,0,CX1);/ 生成条件跳转指令，跳转到前面判断条件操作的位置 /
CODE[CX2].A=CX;/ 回填跳出循环的地址 /
break;
}
TEST(FSYS,SymSetNULL(),19);/ 检测语句结束的正确性 */
} /STATEMENT/

六、总结
此次实验本人上网搜索了大量资料，一开始看不懂源代码，我就一字一字把每一行代码都过一遍，遇上哪一行代码看不懂的，比如说定义的变量名，为什么要这样定义变量名；定义的函数，这函数有什么作用等等问题，总体过一遍代码，然后把每一段代码，每一部分函数，都一个一个拿出来单独分析，利用搜索引擎和查看编译原理教科书，努力思考，最终大概理解了源代码每一行代码的意思，比如绝大部分变量定义的意义，各种函数的作用等等。充分感受到看、读、写编译程序对逻辑的挑战，对编译原理产生了更加浓厚的兴趣，提高了自己的代码逻辑思维，加深了对c语言的理解。此链接是该文章的编译原理实验报告下载，过程详细，有三份文件，一份是该原文章的DOC文档实验报告，一份DOC文件是解释每一行源代码，一份txt文本是if-else语句分析如何写