2010编译原理试验指导书

1、编译原理实验指导书适用实验课时：30适用对象： 计算机科学与软件学院实验目的和内容编译原理实验的目的是使学生将编译理论运用到实际当中， 实现一个简单语言集的 词法分析程序、语法分析程序和简单语义处理程序，验证实际编译系统的实现方法，并 加深对编译理论的认识。基本实验分为三个部分，实验一词法分析器设计实现、实验二 LR 语法分析器设计 实现，实验三语义处理程序实现，总的实验学时为 30 课时。要求每个学生独立完成所 有实验要求。每部分基本实验还包括若干扩展实验，供编程能力较强的学生自愿进行。实验一 词法分析程序实现一、实验目的与要求通过编写和调试一个词法分析程序， 掌握在对程序设计语言的源程序进

2、行扫描的过 程中，将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。二、实验内容根据教学要求并结合学生自己的兴趣和具体情况， 从具有代表性的高级程序设计语 言的各类典型单词中，选取一个适当大小的子集。例如，可以完成无符号常数这一类典 型单词的识别后，再完成一个尽可能兼顾到各种常数、关键字、标识符和各种运算符的 扫描器的设计和实现。输入 ：由符合和不符合所规定的单词类别结构的各类单词组成的源程序文件。输出 ：把单词的字符形式表示翻译成编译器的内部表示，确定单词串的输出形式， 并将其结果放到某个文件中。要求所输出的每一单词均按形如（CLASS ，VALUE ）的二元式编码。对于变

3、量和常数， CLASS 字段为相应的类别码； VALUE 字段则是该标识 符、常数的具体值或在其符号表中登记项的序号（要求在变量名表登记项中存放该标识 符的字符串；常数表登记项中则存放该常数的二进制形式） 。对于关键字和运算符，采 用一词一类的编码形式；由于采用一词一类的编码方式，所以仅需在二元式的 CLASS 字段上放置相应的单词的类别码， VALUE 字段则为“空” 。不过，为便于查看由词法分 析程序所输出的单词串，要求在 CLASS 字段上放置单词类别的助记符。三、实现方法与环境词法分析是编译程序的第一个处理阶段，可以通过两种途径来构造词法分析程序。 其一是根据对语言中各类单词的某种描述

4、或定义（如 BNF ），用手工的方式（例如可用 C 语言）构造词法分析程序。 一般地， 可以根据文法或状态转换图构造相应的状态矩阵， 该状态矩阵连同控制程序一起便组成了编译器的词法分析程序； 也可以根据文法或状态 转换图直接编写词法分析程序。 构造词法分析程序的另外一种途径是所谓的词法分析程 序的自动生成，即首先用正规式对语言中的各类单词符号进行词型描述，并分别指出在 识别单词时，词法分析程序所应进行的语义处理工作，然后由一个所谓词法分析程序的 构造程序对上述信息进行加工。如美国 BELL 实验室研制的 LEX 就是一个被广泛使用 的词法分析程序的自动生成工具。总的来说，开发一种新语言时，由于

5、它的单词符号在不停地修改，米用LEX等工具生成的词法分析程序比较易于修改和维护。一旦一种语言确定了，则采用手工编写词 法分析程序效率更高。四、基本实验题目题目1 :试用手工编码方式构造识别以下给定单词的某一语言的词法分析程序。语言中具有的单词包括五个有代表性的关键字begin、end、if、then、else；标识符；整型常数；六种关系运算符；一个赋值符和四个算术运算符。参考实现方法简述如下。单词的分类：构造上述语言中的各类单词符号及其分类码表。表I语言中的各类单词符号及其分类码表单词符号类别编码类别码的助记符单词值begin1BEGINend2ENDif3IFthen4THENelse5EL

6、SE标识符6ID字母打头的字母数字串整常数7INT数字串8LT=9LE=10EQ11NE12GT=13GE:=14IS+15PL-16MI*17MU/18DI处理过程：在一个程序设计语言中，一般都含有若干类单词符号，为此可首先为每 类单词建立一张状态转换图，然后将这些状态转换图合并成一张统一的状态图，即得到 了一个有限自动机，再进行必要的确定化和状态数最小化处理，最后据此构造词法分析 程序。在此为了使词法分析程序结构比较清晰，且尽量避免某些枝节问题的纠缠，假定 要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符； 在源程序的输入文本中，关键字、标识符、整常数之间，若未出

7、现关系和算术运算符以 及赋值符，则至少须用一个空白字符加以分隔。作了这些限制以后，就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字 母，则把后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止,以期获得一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字 表已事先造好），若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为 一标识符。采用上述策略后，针对表I中部分单词可以构造一个如图 1所示的有限自动机（以状态转换图表示）。在图1中添加了当进行状态转移时，词法分析程序应执行的 语义动作。根据图1,可用C语言编写

8、出符合以上几项要求的一个相应的扫描器程序,如程序一所示。STARTtNTT1CATGETCHARCAT GETCHARCATGETCHARt = 0 时CTDpTOKEN)CAT GETCHAR非L和d RETRACT lookup一OUT (TSfT.TOKEN) RETRACT 冬夕JGETCHAROUT CLEZOUT CNEt* ”)爭 _ 和 OUT (LTRETRACT器丘 88 START GETCHAR 图1识别表I所列语言中的部分单词的DFA及相关的语义过程图 1 及程序一中所出现的语义变量及语义函数的含义和功能说明如下：函数GETCHAR :每调用一次，就把扫描指示器当前所

9、指示的源程序字符送入字符变量ch,然后把扫描指示器前推一个字符位置。字符数组 TOKEN :用来依次存放一个单词词文中的各个字符。函数CAT :每调用一次，就把当前 ch中的字符拼接于TOKEN中所存字符串的右边。函数 LOOKUP :每调用一次，就以 TOKEN 中的字符串查保留字表，若查到，就将相应关键字 的类别码赋给整型变量 c；否则将c置为零。函数 RETRACT :每调用一次，就把扫描指示器回退一个字符位置(即退回多读的那个字符) 。函数OUT :般仅在进入终态时调用此函数，调用的形式为OUT(c，VAL)。其中，实参c为相应单词的类别码或其助记符；当所识别的单词为标识符和整数时，实

10、参VAL 为 TOKEN (即词文分别为字母数字串和数字串) ，对于其余种类的单词， VAL 均为空串。函数 OUT 的功能是，在送出一个单 词的内部表示之后，返回到调用该词法分析程序的那个程序。程序一 根据图 1 编写的扫描器# include # include # include # define ID 6# define INT 7# define LT 8# define LE 9# define EQ 10# define NE 11# define GT 12# define GE 13char TOKEN20 ；extern int lookup (char*);extern

11、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!*/TOKEN0=ch; ch=fgetc (fp); i=1;while (isalnum (ch)TOKENi=ch; i+ ；ch=fgetc (fp);TOKENi= 0fseek(fp,-1,1);/* retract*/c=lookup (TOKEN);if (c=0) out

12、(ID,TOKEN); else out (c, )；elseif(isdigit(ch)TOKEN0=ch; ch=fgetc(fp); i=1;while(isdigit(ch)TOKENi=ch; i+;ch=fgetc(fp);TOKENi= O;fseek(fp,-1,1);out(INT,TOKEN);elseswitch(ch)case / ； ch=fgetc(fp);if(ch= ； =； )out(LE,);else if(ch= ； ) out (NE,);elsefseek (fp,-1,1);out (LT, );break;case ； =ut(EQ, ); bre

13、ak;case ； ch=fgetc(fp);if(ch= ； =； )out(GE,);elsefseek(fp,-1,1);out(GT, );break;default: report_error( ); break;return;提示 ：扫描器所用的若干函数以及主程序有待于具体编写，并需事先建立好保留字表，以备查询。例如：/* 建立保留字表 */#define MAX_KEY_NUMBER 2O /*关键字的数量 */#define KEY_WORD_END “waiting for your expanding ” /* 关键字结束标记 */char *KeyWordTableMAX

14、_KEY_NUMBER=“begin”, “end”, “if”, “then”, “else”, KEY_WORD_END;/* 查保留字表，判断是否为关键字 */int lookup (char *token)int i=O;while (strcmp(KeyWordTablen, KEY_WORD_END) /*strcmp 比较两串是否相同，若相同返回 O*/if (!strcmp(KeyWordTablen, token) /* 比较 token 所指向的关键字和保留字表中哪个关键字相符 */return n+1; /* 设置正确的关键字类别码，并返回此类别码的值 */break;n

15、+;return O; /* 单词不是关键字，而是标识符 */另外，在扫描源程序字符串时，一旦识别出关键字、标识符、整常数以及运算符中 之一，即以二元式形式（类别编码，值）输出单词到指定文件中。每次调用词法分析程 序，它均能自动继续扫描下去，形成下一个单词，直至整个源程序全部扫描完毕，并形 成相应的单词串形式的源程序。题目2：将表I单词集中的整常数改为无符号常数，修改题目1中已开发的扫描器。无符号常数的单词分类码助记符 ：UCON ;其值为无符号常数的机内二进制表示。 描述无符号数的正规文法和状态转换图：无符号数的右线性文法 G无符号数 如下：无符号数- d余留无符号数无符号数T 小数部分无符

16、号数T d余留无符号数T d余留无符号数余留无符号数T 十进小数余留无符号数t E指数部分余留无符号数T d余留无符号数T 十进小数t E指数部分十进小数T d十进小数十进小数t d小数部分T d十进小数小数部分t d指数部分T d余留整指数指数部分T +整指数指数部分T -整指数指数部分t d整指数T d余留整指数整指数T d余留整指数T d余留整指数余留整指数t d图2所示为上述文法的状态转换图，其中编号0、1、2、6分别代表非终结符号 无符号数 、余留无符号数 、十进小数 、小数部分 、指数部分 、整指数实现无符号数识别的参考方法：在计算机内实现状态转换图的方法之一，是以状态图中的各个状

17、态为行，以可能输入的各个输入符号为列，组成一个状态矩阵。其中，矩阵的元素用来指明下一个状态和扫描器应完成的语义动作（如拼接字符、数制转换、查填符号表以及输出单词的内部表示等）。由于在一个状态矩阵中，通常有许多状态都是出错状态，为了节省存放状态矩阵的存储空间，在具体实现时，常常采用更为紧凑和有 效的数据结构。例如，对于文法G的状态转换图，可按表II的形式来存放其状态矩阵。表II中的第一列为各状态 Si的编号，第二列分别列出了在每一状态下可 能扫视到的输入符号 aj （其中“ other”是一个符号集合，用来表示在相应状态所属的那 一栏中，除其前所列字符之外的全部其它字符），第三列指出当（Si,a

18、j）出现时应执行的语义动作（通常用若干个语句来实现，若其后空，则表示不进行任何处理），最后一栏用来指明下一状态的编号（若其后NULL或“结束”则表示无后继状态）。状态矩阵中所嵌入的语义动作，其功能是在扫描源程序字符串的过程中，把识别出的字符串形式 的无符号数的值，逐步转换为相应的二进制整数（ICON ）或二进制浮点数（FCON ）的内部形式，方法详见教材第56页。（注：考虑能否采用C语言的库函数实现此语义处理 工作。）表II包含语义处理过程的识别无符号数的状态矩阵当翦戟命诵瓷处瑕H怖壷接曼动悴号业状姦0dn=Oi p=&i e=l | w=d19w0ip=Ojli J3otherNULL1d(

19、桂當 * l&+d(12E4other结束2dn + + i w = w * 10+di2E4ClthtfFCONw pow(10+f3dE +w=w * 104-d i2识则失敗MULL4d6+55otherNUIX5d(pp 10+d J6other识刷点畋NULL6dip=p 10+di6oihtr伺FCON=w * Fow(10*f * pit) i 卜堵棗根据加入语义过程说明的状态转换图直接编写词法分析程序，部分实现代码如下：程序二 单词分类码为 UCON 的无符号数的识别程序 #include #include #include #define LETTER 0#define DI

20、GIT 1#define POINT 2#define OTHER 3#define POWER 4#define PLUS 5#define MINUS 6#define UCON 7 /Suppose the class number of unsigned constant is 7 #define ClassOther 200#define EndState -1 int w,n,p,e,d;int Class; /Used to indicate class of the wordint ICON; float FCON;static int CurrentState; /Used

21、to present current state, the initial value:0 int GetChar (void);int EXCUTE (int,int) ；int LEX (void) ；int HandleOtherWord (void) return ClassOther;int HandleError (void)printf (Error! n); return 0;int GetChar (void) int c; c=getchar ( );if(isdigit(c) d=c- 0 丁eturn DIGIT;if (c=. ) returnPOINT;if (c=

22、E|c= e ) return POWER;if (c=+ ) returnPLUS;if (c= - ) return MINUS; return OTHER;int EXCUTE (int state, int symbol)switch (state)case 0:switch (symbol)case DIGIT: n=0;p=0;e=1;w=d;CurrentState=1;Class=UCON;break; case POINT: w=0;n=0;p=0;e=1;CurrentState=3;Class=UCON;break; default: HandleOtherWord( )

23、;Class=ClassOther;CurrentState=EndState; break;case 1:switch (symbol)123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354case DIGIT: w=w*10+d;break; /CurrentState=155565758596061626364656667686970717273747576777879808182838485868788899091929394959697989

24、9100101102103104105case POINT: CurrentState=2;break;case POWER: CurrentState=4;break;default: ICON=w;CurrentState=EndState;break；case 2:switch (symbol)case DIGIT: n+;w=w*10+d;break;case POWER: CurrentState=4;break;default: FCON=w*pow(10,e*p-n);CurrentState=EndState; break;case 3:switch (symbol)case

25、DIGIT: n+;w=w*10+d;CurrentState=2;break;default: HandleError( ) ； CurrentState=EndState;break；case 4:switch (symbol)case DIGIT: p=p*10+d;CurrentState=6;break;case MINUS: e=-1;CurrentState=5;break;case PLUS: CurrentState=5;break;default: HandleError( );CurrentState=EndState;break；case 5:switch (symbo

26、l)case DIGIT: p=p*10+d;CurrentState=6;break; default: HandleError( );CurrentState=EndState;break;case 6:switch (symbol)case: DIGIT:p=p*10+d;break;default: FCON=w*pow(10,e*p-n);CurrentState=EndState; break;return CurrentState;int LEX (void)int ch;CurrentState=0;while (CurrentState!=EndState)ch=GetCha

27、r( );EXCUTE (CurrentState,ch);return Class;五、扩展要求有余力的同学，可选作以下内容（上机实验成绩有加分） ：1、在词法分析过程中建立变量名表和常数表，以备以后的编译过程（如语法分析） 查询；扩充关键字的数目、增加单词类别（如逻辑运算符等） 、将常数分成字符串常量、 整型常量和实型常量等；添加词法分析中单词出错的位置、加细错误类型的检查，以及 删除注释部分等。2、识别一个程序设计语言（如 C 语言或其大小适宜的一个子集）所有单词的词法 分析程序设计。建议利用 LEX 系统。、，I. 、+:六、注意1、上机前的准备：完成词法分析程序的程序流图，并选择好相

28、应的数据结构。2、编程：用C语言或你熟悉的其它高级程序设计语言编写一个规模适当的扫描器。3、调试：将各个模块连接成一个完整程序，并整体调试成功。4、测试：用于测试扫描器的实例源文件中应有词法正确的，也应有错误的字符串， 并至少应包含两行以上的源代码。5、输出结果：对于输入的测试用例的源程序文件，以对照的形式将扫描器的分析 结果在输出文件中表示出来，必要时给出正误信息。实验二 语法分析程序实现一、实验目的与要求通过设计、编制、调试一个典型的语法分析程序（任选有代表性的语法分析方法，如算符优先法、递归下降法、LL（1）、SLR（1）、LR（1）等，作为编制语法分析程序的依据） 对扫描器所提供的单词

29、序列进行语法检查和结构分析， 实现并进一步掌握常用的语法分 析方法。二、实验内容选择对各种常见高级程序设计语言都较为通用的语法结构作为分析对象，给出其文法描述（注意应与所采用的语法分析方法比较贴近） ，设计并实现一个完整的语法分析 程序。输入 ：源程序以文件的形式输入。输出 ：对于所输入的源程序，如果输入符号串是给定文法定义的合法句子，则输出“ RIGHT ”，并且给出每一步归约的过程；如果不是句子，即输入串有错误，则输出“ERROR”，并且显示已经归约出的各个文法符号，以及必要的出错说明信息。三、基本实验题目以如下文法 G1 所定义的算术表达式的赋值语句作为分析对象，编写并调试一个语 法分析

30、程序。G1 复合语句 ：复合语句 t beginv语句表end语句表 t 语句|语句 ；语句表语句 t 赋值语句赋值语句 t v变量 ：= 算术表达式算术表达式 T v项 | 算术表达式+项 | 算术表达式 - 项项 T v因式 | v项*因式| v项/因式因式 T v变量 I v常数 | （v算术表达式）V变量 T v标识符V标识符 T v标识符 v字母 I v标识符 V数字 I v字母v常数 T v整数 I v浮点数v整数 T v数字 I v数字 v整数v浮点数 T ? v整数 I v整数 ? v整数v字母 T AIBQ IXIYIZIaIbIxIyzv数字 t 0|1|2|9说明：1）可

31、将以上文法 G1v复合语句 中的语法范畴 常数替换为实验一中的文 法Gv无符号数 ，并将单词类型一一无符号常数进一步细分成整数和浮点数两类单词。2）注意修改实验一中的词法分析程序，并将它编写为子程序的形式，以便供语法分析 程序调用，从而在对源程序的一遍扫描过程中，同时完成词法和语法分析任务。3）要求加强错误检查， 对输入符号串中有词法、 语法错误的语句， 给出必要的错误说明信息， 尽可能多地、确切地指出错误的位置、原因和性质。例如，在词法分析阶段，对当前正 在处理的字符ch，可进一步定义一些与该字符相关的信息row和col，分别表示该字符所在的行和列，这些内容在出错处理时用来提供和源程序位置相

32、关的信息。即定义：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 算术表达式 ：算术表达式 T 项 I 算术表达式+项 | 算术表达式 - 项V项

33、 T 因式 | 项*V因式 | 项/因式因式 T V变量 I（V算术表达式）V变量 T V标识符V标识符 T V字母V字母 T A|B|C| |X|Y|Z算法：若将非终结符号V算术表达式、V项、V因式分别用E、T、F代表，并利 用扩充的 BNF 消除 E 和 T 的左递归后，采用递归下降法分析上述算术表达式的框图见 图 3。其中 ZC 过程为总控程序， 被设计成可以分析无穷多个算术表达式， 主要完成： 1） 通知外界键入算术表达式。 2）控制 E 过程分析算术表达式。 3）根据分析结果之正误， 分别输出不同的信息。E、T和F三个过程分别对应 算术表达式 、项和 因式三个产生式的处理。它 们利用

34、到两个公共函数：一个是函数SYM ,它负责从输入字符串 ST中取出下一个字符， 并存入SYM中等得分析；另一个是ADVANCE过程，负责剔除 ST中的首字符，可通过挪动字符串指针的办法来实现（实际上是通过调用词法分析程序来实现的）。变量 TZ之值标志分析的结果（表达式是否有错） 。(a)(b)(c)(d)开jft J（返回j）(e)CZZZ)图3递归下降法分析算术表达式的框图（a） ZC过程 （b） E过程 （c） T过程 （d） F过程 （e） SYM函数 （f） ADV ANCE过程示例二： 用 C 语言编制算符优先分析法的语法分析程序。 分析对象可为赋值语句或 算术表达式等。算法：算符优

35、先分析的算法如程序三所示。其中使用了分析栈stack，用来在分析过程中存放当前句型的某一前缀， 一旦句型的最左素短语在栈顶形成， 便立即进行归约。程序三 算符优先分析算法#define RIGHT 1#define ERROR 0#define MAXINPUT 300#define MAXSTACK 100#define STARTSYMBOL Sint stackMAXSTACK ，aMAXINPUT;/* a is input line */int IsHigherThan (int, int);/* prioriy detection */int IsLowerThan (int, i

36、nt);/* 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 */stack0= #；doint j;r=ai+;if (IsVt(stackk) j=k; els

37、e j=k-1;while (IsHigherThan(stackj,r)int q;do q=stackj;if (IsVt(sj-1) j-; else j-=2; while(!IsLowerThan(stackj,q);NewVn=Reduce(stackj+1,stackk,k-j);k=j+1;/* reduce the leftmost prime phrase */stackk=NewVn; /* it is stackj+1 stackj+2 stackk */ /*end of while*/if (IsLowerThan(stackj,r) | IsEqualTo(sta

38、ckj,r)stack+k=r;else return ERROR; while (r!= #);return RIGHT;说明：首先，对于所选定的文法(例如 G1或G2),应 确定一种合适的数据结构，以构造所给文法的机内表示。然后，构造该文法的算符优先 关系矩阵。可以通过以下两种途径：一是根据各算符的优先级和结合性，直接手工构造 算符优先关系；二是通过编写程序，计算出所给文法的算符优先关系矩阵。计算优先矩 阵程序的主要步骤简述如下：1 )分别编写计算布尔矩阵B, B =及 B的程序，为此，还需要编写计算布尔矩阵 B的闭包B+的子程序，供计算上述各布尔矩阵时调用。2）编制判定优先矩阵是否有多重

39、定义元素的程序，用来判断所给文法是否为算符优先文法。3）输出各优先关系的布尔矩阵以及有关的判定结果信息。最后，编写程序三中所用到的各 个函数，完成整个算符优先语法分析程序的开发。另外，如果我们希望在分析过程中为句子建立一棵“语法树” ，则可在每移进一个 终结符号时，就建立一个末端结点；而在用某一产生式将句型的最左素短语归约为某个 非终结符号 N 时，就建立以 N 为标记的结点，此结点的各子结点（从左到右）依次是 最左素短语的各个符号。五、扩充要求1、完成两种以上典型的语法分析程序的设计与实现。2、在基本题目所给文法 G1 复合语句 的基础上，可适当扩大分析对象，增加功 能。例如，赋值语句的左部

40、不再只局限于简单变量，可以是数组元素；右部的算术表达 式中可以包括函数调用、数组元素等。除算术表达式外，还可进一步是关系表达式等。 语法分析的结果以语法树的形式输出，或者输出分析过程的信息（如分析栈、符号栈、 当前应被归约的最左子串、归约后所得的符号等） 。3、 学习编译器的自动生成工具LEX、YACC （或其它类似工具）的使用方法，运用LEX和YACC编写并生成以下文法 G3程序 所定义语言的词法和语法分析程序。G3 程序 ：程序 T PROGRAMV标识符 ;分程序分程序 t 变量说明BEGIN语句表END.变量说明 t VAR变量说明表；变量说明表 T 变量表:类型 | 变量表:类型;变

41、量说明表类型 T INTEGER | REAL变量表 T 变量 | 变量,变量表语句表 T 语句 | 语句;语句表语句 T 赋值语句 | 条件语句 | WHILE 语句 | 复合语句 赋值语句 T 变量:=算术表达式 条件语句 t |F关系表达式THEN语句ELSE语句WHILE 语句 T WHILE 关系表达式 DO 语句 复合语句 T BEGIN 语句表 END算术表达式 T 项 | 算术表达式 + 项 | 算术表达式 -项项 T 因式 | 项*因式 | 项/因式因式 T 变量 | 常数 | （算术表达式 ）关系表达式 T 算术表达式 关系符 算术表达式 变量 T 标识符 标识符 T 标识

42、符 字母 | 标识符 数字 | 字母常数 T 整数 | 浮点数 整数 T 数字 I 数字 整数浮点数 T ? V整数 | 整数 ? V整数 关系符 T I = I = I I = I V字母 T A|B|C| |X|Y|Z|a|b|q|x|y|z数字 t 0|1|2|9、，I. 、+:六、注意1、上机前的准备：结合所选择的基本或扩充题目的要求，确定语法分析程序的流 程图，同时考虑相应的数据结构，用 C 或其它高级语言初步编写一个语法分析源程序。2、调试：将词法、语法分析合在一起构成一个完整的程序，并调试成功。3、测试：供测试的例子应包括符合语法规则的语句，以及分析程序能够判别的若 干错例。4、

43、结果输出：对于所输入的字符串，不论对错，都应有明确的信息告诉外界。5、编写的源程序中应有较为详细的说明和注释。例如，对文法机内表示的解释、数据结构的说明、函数的作用、全局变量的含义等等。实验三 语义分析程序实现一、实验目的与要求在实现词法、语法分析程序的基础上，编写相应的语义子程序，进行语义检查，加 深对语法制导翻译原理的理解， 进一步掌握将语法分析所识别的语法范畴变换为某种中 间代码（四元式）的语义分析方法，并完成相关语义分析器的代码开发工作。二、实验内容语法制导翻译模式是在语法分析的基础上，增加语义操作来实现的。对于给定文法 中的每一产生式，编写相应的语义子程序。在语法分析过程中，每当用一

44、产生式进行推 导或归约时，语法分析程序除执行相应的语法分析动作之外，还要调用相应的语义子程 序，以便完成生成中间代码、查填有关表格、检查并报告源程序中的错误等工作。每个 语义子程序需指明相应产生式中各个符号的具体含义， 并规定使用该产生式进行分析时 所应采取的语义动作。 这样，语法制导翻译程序在对源程序从左到右进行的一遍扫描中， 既完成语法分析任务，又完成语义分析和中间代码生成方面的工作。高级语言的语法结构类型很多，例如说明语句、程序流程控制语句、子程序结构语 句、格式语句等，可选择其中一类进行语义分析程序的开发。输入 ：作为测试用例的源程序文件。输出 ：将源程序转换为中间代码形式表示，并将中

45、间代码序列输出到文件中。若源 程序中有错误，应指出错误信息。三、基本实验题目针对实验二中定义的文法 G1，首先根据需要进行的语义工作， 完成对 文法的必要拆分和语义动作的编写，从而为每个产生式都配备相应的语义子程序。然后 编写并调试相应的语法制导翻译程序。在此，中间代码以四元式表示，并且对于不同数 据类型的运算对象，在进行算术运算前须转换为相同的数据类型。要求从编译器的整体设计出发，重点通过对实验二中语法分析程序的扩展，将编译 程序前端涉及的词法、语法和语义分析的各个模块组合在一起，初步形成一个将源程序 翻译为四元式序列的编译系统。四、示例对实验二中的示例一给出的文法 G2，在利用递归下降法进

46、行语法分 析的同时，生成四元式形式的中间代码序列。算法： 语法制导翻译程序的核心部分(指表达式、项和因式的处理)的算法思想， 可用程序四所示的框架描述。程序四 利用递归下降法生成简单算术表达式的四元式序列E( ) /* 识别算术表达式 */E1_PLACE=T( ); /*调用 T( ) 分析产生算术表达式计算的第一项 E1*/while (SYM= +| SYM= -)ADVANCE; /* 将输入串指针调整至指向下一输入符号，即调扫描器读入下一个单词符号*/E2_PLACE=T( ); /*调用 T( )分析产生算术表达式计算的第二项 */T1=NewTemp( ); /* 分配一个新的临

47、时变量，以便存储计算结果 */GEN( , E1_PLACE, E2_PLACE, T1); /*根据所给实参产生一个四元式，送入四元式表*/E1_PLACE=T1; /* 将计算结果作为下一次表达式计算的第一项 */return E1_PLACE;T( ) /* 识别 项*/T1_PLACE=F( );while (SYM= *| SYM= /)ADVANCE;T2_PLACE=F( );T1=NewTemp( );GEN(*/, T1_PLACE, T2_PLACE, T1);T1_PLACE=T1;return T1_PLACE;F( ) /* 识别因式 */if (SYM= 标识符 )

48、ADVANCE;return Entry(i. 词文); /*以标识符的词文为名字查、填符号表，可理解为返回标识符的值 */elseif ( SYM= ()ADVANCE;PLACE=E( );if ( SYM= )ADVANCE;return PLACE;else ERROR; /* 例如：输出“缺少) 错误” */else ERROR; /* 例如：输出“算术表达式应以标识符或 (开头” */说明： 1)程序四中出现的主要语义变量和辅助函数的功能为：E1_PLACE :文法符号E1的一个语义属性，用于描述变量在符号表中登记项的序号(0时)或临时变量的编号( 0时)，可理解为代表其值。voi

49、d GEN(char *Op, char *Arg1, char *Arg2, char *Result) :用来生成一个四元式，将其送到四 元式表中。参考代码如下:void GEN(char *Op, char *Arg1, char *Arg2, char *Result)strcpy (pQuadNXQ.op, Op); /*pQuad 为全局变量，是用于存放四元式的数组 */strcpy (pQuadNXQ.arg1, Arg1);strcpy (pQuadNXQ.arg2, Arg2);strcpy (pQuadNXQ.result, Result);NXQ+; /*全局变量 NXQ 用于指示所要产生的下一个四元式的编号 */char *NewTemp(void)