河北工大《编译原理》实验指导书与参考程序.doc

《编译原理》实验指导书

适用实验课时：30

适用对象：计算机科学与软件学院
实验目的与内容

编译原理实验的目的是使学生将编译理论运用到实际当中，实现一个简单语言集的词法分析程序、语法分析程序与简单语义处理程序，验证实际编译系统的实现方法，并加深对编译理论的认识。
基本实验分为三个部分，实验一词法分析器设计实现、实验二LR语法分析器设计实现，实验三语义处理程序实现，总的实验学时为30课时。要求每个学生独立完成所有实验要求。
每部分基本实验还包括若干扩展实验，供编程能力较强的学生自愿进行。
实验一 词法分析程序实现
一、实验目的与要求
通过编写与调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。
二、实验内容
根据教学要求并结合学生自己的兴趣与具体情况，从具有代表性的高级程序设计语言的各类典型单词中，选取一个适当大小的子集。例如，可以完成无符号常数这一类典型单词的识别后，再完成一个尽可能兼顾到各种常数、关键字、标识符与各种运算符的扫描器的设计与实现。
输入：由符合与不符合所规定的单词类别结构的各类单词组成的源程序文件。
输出：把单词的字符形式表示翻译成编译器的内部表示，确定单词串的输出形式，并将其结果放到某个文件中。要求所输出的每一单词均按形如（CLASS，VALUE）的二元式编码。对于变量与常数，CLASS字段为相应的类别码；VALUE字段则是该标识符、常数的具体值或在其符号表中登记项的序号（要求在变量名表登记项中存放该标识符的字符串；常数表登记项中则存放该常数的二进制形式）。对于关键字与运算符，采用一词一类的编码形式；由于采用一词一类的编码方式，所以仅需在二元式的CLASS字段上放置相应的单词的类别码，VALUE字段则为“空”。不过，为便于查看由词法分析程序所输出的单词串，要求在CLASS字段上放置单词类别的助记符。
三、实现方法与环境
词法分析是编译程序的第一个处理阶段，可以通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义（如BNF），用手工的方式（例如可用C语言）构造词法分析程序。一般地，可以根据文法或状态转换图构造相应的状态矩阵，该状态矩阵连同控制程序一起便组成了编译器的词法分析程序；也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序的另外一种途径是所谓的词法分析程序的自动生成，即首先用正规式对语言中的各类单词符号进行词型描述，并分别指出在识别单词时，词法分析程序所应进行的语义处理工作，然后由一个所谓词法分析程序的构造程序对上述信息进行加工。如美国BELL实验室研制的LEX就是一个被广泛使用的词法分析程序的自动生成工具。
总的来说，开发一种新语言时，由于它的单词符号在不停地修改，采用LEX等工具生成的词法分析程序比较易于修改与维护。一旦一种语言确定了，则采用手工编写词法分析程序效率更高。
四、基本实验题目
题目1：试用手工编码方式构造识别以下给定单词的某一语言的词法分析程序。
语言中具有的单词包括五个有代表性的关键字begin、end、if、then、else；标识符；整型常数；六种关系运算符；一个赋值符与四个算术运算符。参考实现方法简述如下。
单词的分类：构造上述语言中的各类单词符号及其分类码表。
表I 语言中的各类单词符号及其分类码表
单词符号
类别编码
类别码的助记符
单词值
begin
1
BEGIN

end
2
END

if
3
IF

then
4
THEN

else
5
ELSE

标识符
6
ID
字母打头的字母数字串
整常数
7
INT
数字串
<
8
LT

<=
9
LE

=
10
EQ

<>
11
NE

>
12
GT

>=
13
GE

:=
14
IS

+
15
PL

-
16
MI

*
17
MU

/
18
DI

处理过程：在一个程序设计语言中，一般都含有若干类单词符号，为此可首先为每类单词建立一张状态转换图，然后将这些状态转换图合并成一张统一的状态图，即得到了一个有限自动机，再进行必要的确定化与状态数最小化处理，最后据此构造词法分析程序。在此为了使词法分析程序结构比较清晰，且尽量避免某些枝节问题的纠缠，假定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符；在源程序的输入文本中，关键字、标识符、整常数之间，若未出现关系与算术运算符以及赋值符，则至少须用一个空白字符加以分隔。作了这些限制以后，就可以把关键字与标识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期获得一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字表已事先造好），若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为一标识符。采用上述策略后，针对表I中部分单词可以构造一个如图1所示的有限自动机（以状态转换图表示）。在图1中添加了当进行状态转移时，词法分析程序应执行的语义动作。根据图1，可用C语言编写出符合以上几项要求的一个相应的扫描器程序，如程序一所示。

图1 识别表I所列语言中的部分单词的DFA及相关的语义过程
图1及程序一中所出现的语义变量及语义函数的含义与功能说明如下：
函数GETCHAR：每调用一次，就把扫描指示器当前所指示的源程序字符送入字符变量ch，然后把扫描指示器前推一个字符位置。
字符数组TOKEN：用来依次存放一个单词词文中的各个字符。
函数CAT：每调用一次，就把当前ch中的字符拼接于TOKEN中所存字符串的右边。
函数LOOKUP：每调用一次，就以TOKEN中的字符串查保留字表，若查到，就将相应关键字的类别码赋给整型变量c；否则将c置为零。
函数RETRACT：每调用一次，就把扫描指示器回退一个字符位置（即退回多读的那个字符）。
函数OUT：一般仅在进入终态时调用此函数，调用的形式为OUT(c，VAL)。其中，实参c为相应单词的类别码或其助记符；当所识别的单词为标识符与整数时，实参VAL为TOKEN（即词文分别为字母数字串与数字串），对于其余种类的单词，VAL均为空串。函数OUT的功能是，在送出一个单词的内部表示之后，返回到调用该词法分析程序的那个程序。
程序一 根据图1编写的扫描器
# include <stdio.h>
# include <ctype.h>
# include <string.h>
# define ID 6
# define INT 7
# define LT 8
# define LE 9
# define EQ 10
# define NE 11
# define GT 12
# define GE 13
char TOKEN[20]；
extern int lookup (char*);
extern void out (int, char*);
extern report_error (void);
void scanner_example (FILE *fp)
{
char ch; int i, c;
ch=fgetc (fp);
if (isalpha (ch)) /*it must be a identifer!*/
{
TOKEN[0]=ch; ch=fgetc (fp); i=1;
while (isalnum (ch))
{
TOKEN[i]=ch; i++；
ch=fgetc (fp);
}
TOKEN[i]= ′＼0′
fseek(fp,-1,1); /* retract*/
c=lookup (TOKEN);
if (c==0) out (ID,TOKEN); else out (c," ")；
}
else
if(isdigit(ch))
{
TOKEN[0]=ch; ch=fgetc(fp); i=1;
while(isdigit(ch))
{
TOKEN[i]=ch; i++;
ch=fgetc(fp);
}
TOKEN[i]= ′＼0′；
fseek(fp,-1,1);
out(INT,TOKEN);
}
else
switch(ch)
{
case ′＜′: ch=fgetc(fp);
if(ch==′=′)out(LE," ");
else if(ch==′＞′) out (NE," ");
else
{
fseek (fp,-1,1);
out (LT," ");
}
break;
case ′=′: out(EQ, " "); break;
case ′＞′: ch=fgetc(fp);
if(ch==′=′)out(GE," ");
else
{
fseek(fp,-1,1);
out(GT," ");
}
break;
default: report_error( ); break;
}
return;
}
提示：扫描器所用的若干函数以及主程序有待于具体编写，并需事先建立好保留字表，以备查询。例如：
/* 建立保留字表 */
#define MAX_KEY_NUMBER 20 /*关键字的数量*/
#define KEY_WORD_END “waiting for your expanding” /*关键字结束标记*/
char *KeyWordTable[MAX_KEY_NUMBER]={“begin”, “end”, “if”, “then”, “else”, KEY_WORD_END};
/* 查保留字表，判断是否为关键字 */
int lookup (char *token)
{
int i=0;
while (strcmp(KeyWordTable[n], KEY_WORD_END)) /*strcmp比较两串是否相同，若相同返回0*/
{
if (!strcmp(KeyWordTable[n], token)) /*比较token所指向的关键字与保留字表中哪个关键字相符*/
{
return n+1; /*设置正确的关键字类别码，并返回此类别码的值*/
break;
}
n++;
}
return 0; /*单词不是关键字，而是标识符*/
}
另外，在扫描源程序字符串时，一旦识别出关键字、标识符、整常数以及运算符中之一，即以二元式形式（类别编码，值）输出单词到指定文件中。每次调用词法分析程序，它均能自动继续扫描下去，形成下一个单词，直至整个源程序全部扫描完毕，并形成相应的单词串形式的源程序。
题目2：将表I单词集中的整常数改为无符号常数，修改题目1中已开发的扫描器。
无符号常数的单词分类码助记符：UCON；其值为无符号常数的机内二进制表示。
描述无符号数的正规文法与状态转换图：
无符号数的右线性文法G[<无符号数>]如下：
〈无符号数〉→ d〈余留无符号数〉
〈无符号数〉→ ·〈小数部分〉
〈无符号数〉→ d
〈余留无符号数〉→ d〈余留无符号数〉
〈余留无符号数〉→ ·〈十进小数〉
〈余留无符号数〉→ E〈指数部分〉
〈余留无符号数〉→ d
〈余留无符号数〉→ ·
〈十进小数〉→ E〈指数部分〉
〈十进小数〉→ d〈十进小数〉
〈十进小数〉→ d
〈小数部分〉→ d〈十进小数〉
〈小数部分〉→ d
〈指数部分〉→ d〈余留整指数〉
〈指数部分〉→ +〈整指数〉
〈指数部分〉→ -〈整指数〉
〈指数部分〉→ d
〈整指数〉→ d〈余留整指数〉
〈整指数〉→ d
〈余留整指数〉→ d〈余留整指数〉
〈余留整指数〉→ d
图2所示为上述文法的状态转换图，其中编号0、1、2、…、6分别代表非终结符号<无符号数>、<余留无符号数>、<十进小数>、<小数部分>、<指数部分>、<整指数>及<余留整指数>。

图2 文法G[<无符号数>]的状态转换图
实现无符号数识别的参考方法：在计算机内实现状态转换图的方法之一，是以状态图中的各个状态为行，以可能输入的各个输入符号为列，组成一个状态矩阵。其中，矩阵的元素用来指明下一个状态与扫描器应完成的语义动作（如拼接字符、数制转换、查填符号表以及输出单词的内部表示等）。由于在一个状态矩阵中，通常有许多状态都是出错状态，为了节省存放状态矩阵的存储空间，在具体实现时，常常采用更为紧凑与有效的数据结构。例如，对于文法G[<无符号数>]的状态转换图，可按表II的形式来存放其状态矩阵。表II中的第一列为各状态Si的编号，第二列分别列出了在每一状态下可能扫视到的输入符号aj（其中“other”是一个符号集合，用来表示在相应状态所属的那一栏中，除其前所列字符之外的全部其它字符），第三列指出当（Si,aj）出现时应执行的语义动作（通常用若干个语句来实现，若其后空，则表示不进行任何处理），最后一栏用来指明下一状态的编号（若其后NULL或“结束”则表示无后继状态）。状态矩阵中所嵌入的语义动作，其功能是在扫描源程序字符串的过程中，把识别出的字符串形式的无符号数的值，逐步转换为相应的二进制整数（ICON）或二进制浮点数（FCON）的内部形式，方法详见教材第56页。（注：考虑能否采用C语言的库函数实现此语义处理工作。）
表II 包含语义处理过程的识别无符号数的状态矩阵

根据加入语义过程说明的状态转换图直接编写词法分析程序，部分实现代码如下：
程序二 单词分类码为UCON的无符号数的识别程序
1 #include <stdio.h>
2 #include <ctype.h>
3 #include <math.h>
4 #define LETTER 0
5 #define DIGIT 1
6 #define POINT 2
7 #define OTHER 3
8 #define POWER 4
9 #define PLUS 5
10 #define MINUS 6
11 #define UCON 7 //Suppose the class number of unsigned constant is 7
12 #define ClassOther 200
13 #define EndState -1
14 int w,n,p,e,d;
15 int Class; //Used to indicate class of the word
16 int ICON;
17 float FCON;
18 static int CurrentState; //Used to present current state, the initial value:0
19
20 int GetChar (void);
21 int EXCUTE (int,int)；
22 int LEX (void)；
23 int HandleOtherWord (void)
24 {return ClassOther;
25 }
26 int HandleError (void)
27 {printf ("Error!＼n"); return 0;}
28
29 int GetChar (void)
30 {
31 int c;
32 c=getchar ( );
33 if(isdigit(c)) {d=c-′0′;return DIGIT;}
34 if (c==′.′) return POINT;
35 if (c==′E′||c==′e′) return POWER;
36 if (c==′+′) return PLUS;
37 if (c==′-′) return MINUS;
38 return OTHER;
39 }
40 int EXCUTE (int state, int symbol)
41 {
42 switch (state)
43 {
44 case 0:switch (symbol)
45 {
46 case DIGIT: n=0;p=0;e=1;w=d;CurrentState=1;Class=UCON;break;
47 case POINT: w=0;n=0;p=0;e=1;CurrentState=3;Class=UCON;break;
48 default: HandleOtherWord( );Class=ClassOther;
49 CurrentState=EndState;
50 }
51 break;
52 case 1:switch (symbol)
53 {
54 case DIGIT: w=w*10+d;break; //CurrentState=1
55 case POINT: CurrentState=2;break;
56 case POWER: CurrentState=4;break;
57 default: ICON=w;CurrentState=EndState;
58 }
59 break；
60 case 2:switch (symbol)
61 {
62 case DIGIT: n++;w=w*10+d;break;
63 case POWER: CurrentState=4;break;
64 default: FCON=w*pow(10,e*p-n);CurrentState=EndState;
65 }
66 break;
67 case 3:switch (symbol)
68 {
69 case DIGIT: n++;w=w*10+d;CurrentState=2;break;
70 default: HandleError( )；CurrentState=EndState;
71 }
72 break；
73 case 4:switch (symbol)
74 {
75 case DIGIT: p=p*10+d;CurrentState=6;break;
76 case MINUS: e=-1;CurrentState=5;break;
77 case PLUS: CurrentState=5;break;
78 default: HandleError( );CurrentState=EndState;
79 }
80 break；
81 case 5:switch (symbol)
82 {
83 case DIGIT: p=p*10+d;CurrentState=6;break;
84 default: HandleError( );CurrentState=EndState;
85 }
86 break;
87 case 6:switch (symbol)
88 {
89 case: DIGIT:p=p*10+d;break;
90 default: FCON=w*pow(10,e*p-n);CurrentState=EndState;
91 }
92 break;
93 }
94 return CurrentState;
95 }
96 int LEX (void)
97 {
98 int ch;
99 CurrentState=0;
100 while (CurrentState!=EndState)
101 {
102 ch=GetChar( );
103 EXCUTE (CurrentState,ch);
104 }
105 return Class;
106 }

五、扩展要求
有余力的同学，可选作以下内容（上机实验成绩有加分）：
1、在词法分析过程中建立变量名表与常数表，以备以后的编译过程（如语法分析）查询；扩充关键字的数目、增加单词类别（如逻辑运算符等）、将常数分成字符串常量、整型常量与实型常量等；添加词法分析中单词出错的位置、加细错误类型的检查，以及删除注释部分等。
2、识别一个程序设计语言（如C语言或其大小适宜的一个子集）所有单词的词法分析程序设计。建议利用LEX系统。
六、注意
1、上机前的准备：完成词法分析程序的程序流图，并选择好相应的数据结构。
2、编程：用C语言或你熟悉的其它高级程序设计语言编写一个规模适当的扫描器。
3、调试：将各个模块连接成一个完整程序，并整体调试成功。
4、测试：用于测试扫描器的实例源文件中应有词法正确的，也应有错误的字符串，并至少应包含两行以上的源代码。
5、输出结果：对于输入的测试用例的源程序文件，以对照的形式将扫描器的分析结果在输出文件中表示出来，必要时给出正误信息。

实验二 语法分析程序实现
一、实验目的与要求
通过设计、编制、调试一个典型的语法分析程序（任选有代表性的语法分析方法，如算符优先法、递归下降法、LL(1)、SLR(1)、LR(1)等，作为编制语法分析程序的依据），对扫描器所提供的单词序列进行语法检查与结构分析，实现并进一步掌握常用的语法分析方法。
二、实验内容
选择对各种常见高级程序设计语言都较为通用的语法结构作为分析对象，给出其文法描述（注意应与所采用的语法分析方法比较贴近），设计并实现一个完整的语法分析程序。
输入：源程序以文件的形式输入。
输出：对于所输入的源程序，如果输入符号串是给定文法定义的合法句子，则输出“RIGHT”，并且给出每一步归约的过程；如果不是句子，即输入串有错误，则输出“ERROR”，并且显示已经归约出的各个文法符号，以及必要的出错说明信息。
三、基本实验题目
以如下文法G1所定义的算术表达式的赋值语句作为分析对象，编写并调试一个语法分析程序。
G1[<复合语句>]：
<复合语句> → begin<语句表>end
<语句表> → <语句>|<语句>;<语句表>
<语句> → <赋值语句>
<赋值语句> → <变量>:=<算术表达式>
<算术表达式> → <项> | <算术表达式>+<项> | <算术表达式>-<项>
<项> → <因式> | <项>*<因式> | <项>/<因式>
<因式> → <变量> | <常数> | (<算术表达式>)
<变量> → <标识符>
<标识符> → <标识符> <字母> | <标识符> <数字> | <字母>
<常数> → <整数> | <浮点数>
<整数> → <数字> | <数字> <整数>
<浮点数> → • <整数> | <整数> • <整数>
<字母> → A|B|C|…|X|Y|Z|a|b|c|…|x|y|z
<数字> → 0|1|2|…|9
说明：1）可将以上文法G1[<复合语句>]中的语法范畴<常数>替换为实验一中的文法G[<无符号数>]，并将单词类型——无符号常数进一步细分成整数与浮点数两类单词。2）注意修改实验一中的词法分析程序，并将它编写为子程序的形式，以便供语法分析程序调用，从而在对源程序的一遍扫描过程中，同时完成词法与语法分析任务。3）要求加强错误检查，对输入符号串中有词法、语法错误的语句，给出必要的错误说明信息，尽可能多地、确切地指出错误的位置、原因与性质。例如，在词法分析阶段，对当前正在处理的字符ch，可进一步定义一些与该字符相关的信息row与col，分别表示该字符所在的行与列，这些内容在出错处理时用来提供与源程序位置相关的信息。即定义：
char ch; /*The current character*/
int row; /*The line number position of the current character*/
int col; /*The column number position of the current character*/
四、示例
示例一：对算术表达式的一个简化子集，采用具有递归功能的高级语言编制递归下降法的语法分析程序。分析过程暂不嵌入任何的语义动作。分析对象<算术表达式>的BNF定义如下：
G2[<算术表达式>]：
<算术表达式> → <项> | <算术表达式>+<项> | <算术表达式>-<项>
<项> → <因式> | <项>*<因式> | <项>/<因式>
<因式> → <变量> | (<算术表达式>)
<变量> → <标识符>
<标识符> → <字母>
<字母> → A|B|C|…|X|Y|Z
算法：若将非终结符号<算术表达式>、<项>、<因式>分别用E、T、F代表，并利用扩充的BNF消除E与T的左递归后，采用递归下降法分析上述算术表达式的框图见图3。其中ZC过程为总控程序，被设计成可以分析无穷多个算术表达式，主要完成：1）通知外界键入算术表达式。2）控制E过程分析算术表达式。3）根据分析结果之正误，分别输出不同的信息。
E、T与F三个过程分别对应<算术表达式>、<项>与<因式>三个产生式的处理。它们利用到两个公共函数：一个是函数SYM，它负责从输入字符串ST中取出下一个字符，并存入SYM中等得分析；另一个是ADVANCE过程，负责剔除ST中的首字符，可通过挪动字符串指针的办法来实现（实际上是通过调用词法分析程序来实现的）。变量TZ之值标志分析的结果（表达式是否有错）。

图3 递归下降法分析算术表达式的框图
(a) ZC过程 (b) E过程 (c) T过程 (d) F过程 (e) SYM函数 (f) ADVANCE过程
示例二：用C语言编制算符优先分析法的语法分析程序。分析对象可为赋值语句或算术表达式等。
算法：算符优先分析的算法如程序三所示。其中使用了分析栈stack，用来在分析过程中存放当前句型的某一前缀，一旦句型的最左素短语在栈顶形成，便立即进行归约。
程序三 算符优先分析算法
#define RIGHT 1
#define ERROR 0
#define MAXINPUT 300
#define MAXSTACK 100
#define STARTSYMBOL ′S′
int stack[MAXSTACK]，a[MAXINPUT]; /* a[ ] is input line */
int IsHigherThan (int, int); /* prioriy detection */
int IsLowerThan (int, int); /* prioriy detection */
int IsEqualTo (int, int); /* prioriy detectin */
int Reduce (int begin, int end, int len);
int parser (void)
{
int i, k, r, NewVn; /* NewVn holds left side of a production */
i=0; k=0; /* i, k is index of a[ ] and stack[ ] separately */
stack[0]= ′#′;
do
{
int j;
r=a[i++];
if (IsVt(stack[k])) j=k; else j=k-1;
while (IsHigherThan(stack[j],r))
{
int q;
do {
q=stack[j];
if (IsVt(s[j-1])) j--; else j-=2;
} while(!IsLowerThan(stack[j],q);
NewVn=Reduce(stack[j+1],stack[k],k-j);
k=j+1; /* reduce the leftmost prime phrase */
stack[k]=NewVn; /* it is stack[j+1] stack[j+2] … stack[k] */
} /*end of while*/
if (IsLowerThan(stack[j],r)) || IsEqualTo(stack[j],r))
stack[++k]=r;
else return ERROR;
} while (r!=′#′);
return RIGHT;
}
说明：首先，对于所选定的文法（例如G1[<复合语句>]或G2[<算术表达式>]），应确定一种合适的数据结构，以构造所给文法的机内表示。然后，构造该文法的算符优先关系矩阵。可以通过以下两种途径：一是根据各算符的优先级与结合性，直接手工构造算符优先关系；二是通过编写程序，计算出所给文法的算符优先关系矩阵。计算优先矩阵程序的主要步骤简述如下：1）分别编写计算布尔矩阵B>，B=及B<的程序，为此，还需要编写计算布尔矩阵B的闭包B+的子程序，供计算上述各布尔矩阵时调用。2）编制判定优先矩阵是否有多重定义元素的程序，用来判断所给文法是否为算符优先文法。3）输出各优先关系的布尔矩阵以及有关的判定结果信息。最后，编写程序三中所用到的各个函数，完成整个算符优先语法分析程序的开发。
另外，如果我们希望在分析过程中为句子建立一棵“语法树”，则可在每移进一个终结符号时，就建立一个末端结点；而在用某一产生式将句型的最左素短语归约为某个非终结符号N时，就建立以N为标记的结点，此结点的各子结点（从左到右）依次是最左素短语的各个符号。
五、扩充要求
1、完成两种以上典型的语法分析程序的设计与实现。
2、在基本题目所给文法G1[<复合语句>]的基础上，可适当扩大分析对象，增加功能。例如，赋值语句的左部不再只局限于简单变量，可以是数组元素；右部的算术表达式中可以包括函数调用、数组元素等。除算术表达式外，还可进一步是关系表达式等。语法分析的结果以语法树的形式输出，或者输出分析过程的信息（如分析栈、符号栈、当前应被归约的最左子串、归约后所得的符号等）。
3、学习编译器的自动生成工具LEX、YACC（或其它类似工具）的使用方法，运用LEX与YACC编写并生成以下文法G3[<程序>]所定义语言的词法与语法分析程序。
G3[<程序>]：
<程序> → PROGRAM<标识符>;<分程序>
<分程序> → <变量说明>BEGIN<语句表>END.
<变量说明> → VAR<变量说明表>;
<变量说明表> → <变量表>:<类型> | <变量表>:<类型>;<变量说明表>
<类型> → INTEGER | REAL
<变量表> → <变量> | <变量>,<变量表>
<语句表> → <语句> | <语句>;<语句表>
<语句> → <赋值语句> | <条件语句> | <WHILE语句> | <复合语句>
<赋值语句> → <变量>:=<算术表达式>
<条件语句> → IF<关系表达式>THEN<语句>ELSE<语句>
<WHILE语句> → WHILE<关系表达式>DO<语句>
<复合语句> → BEGIN<语句表>END
<算术表达式> → <项> | <算术表达式>+<项> | <算术表达式>-<项>
<项> → <因式> | <项>*<因式> | <项>/<因式>
<因式> → <变量> | <常数> | (<算术表达式>)
<关系表达式> → <算术表达式> <关系符> <算术表达式>
<变量> → <标识符>
<标识符> → <标识符> <字母> | <标识符> <数字> | <字母>
<常数> → <整数> | <浮点数>
<整数> → <数字> | <数字> <整数>
<浮点数> → • <整数> | <整数> • <整数>
<关系符> → < | <= | = | > | >= | <>
<字母> → A|B|C|…|X|Y|Z|a|b|c|…|x|y|z
<数字> → 0|1|2|…|9
六、注意
1、上机前的准备：结合所选择的基本或扩充题目的要求，确定语法分析程序的流程图，同时考虑相应的数据结构，用C或其它高级语言初步编写一个语法分析源程序。
2、调试：将词法、语法分析合在一起构成一个完整的程序，并调试成功。
3、测试：供测试的例子应包括符合语法规则的语句，以及分析程序能够判别的若干错例。
4、结果输出：对于所输入的字符串，不论对错，都应有明确的信息告诉外界。
5、编写的源程序中应有较为详细的说明与注释。例如，对文法机内表示的解释、数据结构的说明、函数的作用、全局变量的含义等等。

实验三 语义分析程序实现
一、实验目的与要求
在实现词法、语法分析程序的基础上，编写相应的语义子程序，进行语义检查，加深对语法制导翻译原理的理解，进一步掌握将语法分析所识别的语法范畴变换为某种中间代码（四元式）的语义分析方法，并完成相关语义分析器的代码开发工作。
二、实验内容
语法制导翻译模式是在语法分析的基础上，增加语义操作来实现的。对于给定文法中的每一产生式，编写相应的语义子程序。在语法分析过程中，每当用一产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作之外，还要调用相应的语义子程序，以便完成生成中间代码、查填有关表格、检查并报告源程序中的错误等工作。每个语义子程序需指明相应产生式中各个符号的具体含义，并规定使用该产生式进行分析时所应采取的语义动作。这样，语法制导翻译程序在对源程序从左到右进行的一遍扫描中，既完成语法分析任务，又完成语义分析与中间代码生成方面的工作。
高级语言的语法结构类型很多，例如说明语句、程序流程控制语句、子程序结构语句、格式语句等，可选择其中一类进行语义分析程序的开发。
输入：作为测试用例的源程序文件。
输出：将源程序转换为中间代码形式表示，并将中间代码序列输出到文件中。若源程序中有错误，应指出错误信息。
三、基本实验题目
针对实验二中定义的文法G1[<复合语句>]，首先根据需要进行的语义工作，完成对文法的必要拆分与语义动作的编写，从而为每个产生式都配备相应的语义子程序。然后编写并调试相应的语法制导翻译程序。在此，中间代码以四元式表示，并且对于不同数据类型的运算对象，在进行算术运算前须转换为相同的数据类型。
要求从编译器的整体设计出发，重点通过对实验二中语法分析程序的扩展，将编译程序前端涉及的词法、语法与语义分析的各个模块组合在一起