编译原理实验报告

更新时间：2023-10-21 14:00:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

编译原理实验报告

班级姓名：学号：

自我评定：

实验一词法分析程序实现

一、实验目的与要求

通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。

二、实验内容

根据教学要求并结合学生自己的兴趣和具体情况，从具有代表性的高级程序设计语言的各类典型单词中，选取一个适当大小的子集。例如，可以完成无符号常数这一类典型单词的识别后，再完成一个尽可能兼顾到各种常数、关键字、标识符和各种运算符的扫描器的设计和实现。

输入：由符合或不符合所规定的单词类别结构的各类单词组成的源程序。

输出：把单词的字符形式的表示翻译成编译器的内部表示，即确定单词串的输出形式。例如，所输出的每一单词均按形如（CLASS，VALUE）的二元式编码。对于变量和常数，CLASS字段为相应的类别码；VALUE字段则是该标识符、常数的具体值或在其符号表中登记项的序号（要求在变量名表登记项中存放该标识符的字符串；常数表登记项中则存放该常数的二进制形式）。对于关键字和运算符，采用一词一类的编码形式；由于采用一词一类的编码方式，所以仅需在二元式的CLASS字段上放置相应的单词的类别码，VALUE字段则为“空”。另外，为便于查看由词法分析程序所输出的单词串，要求在CLASS字段上放置单词类别的助记符。

三、实现方法与环境

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

总的来说，开发一种新语言时，由于它的单词符号在不停地修改，采用LEX等工具生成的词法分析程序比较易于修改和维护。一旦一种语言确定了，则采用手工编写词法分析程序效率更高。

四、实验设计

1）题目1：试用手工编码方式构造识别以下给定单词的某一语言的词法分析程序。语言中具有的单词包括五个有代表性的关键字begin、end、if、then、else；标识符；整型常数；六种关系运算符；一个赋值符和四个算术运算符。参考实现方法简述如下。

单词的分类：构造上述语言中的各类单词符号及其分类码表。

表I 语言中的各类单词符号及其分类码表

单词符号类别编码类别码的助记符单词值 begin end if then else 标识符整常数 < <= = <> > >= := + - * / 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 BEGIN END IF THEN ELSE ID INT LT LE EQ NE GT GE IS PL MI MU DI 字母打头的字母数字串数字串处理过程：在一个程序设计语言中，一般都含有若干类单词符号，为此可首先为每类单词建立一张状态转换图，然后将这些状态转换图合并成一张统一的状态图，即得到了一个有限自动机，再进行必要的确定化和状态数最小化处理，最后据此构造词法分析程序。在此为了使词法分析程序结构比较清晰，且尽量避免某些枝节问题的纠缠，假定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符；在源程序的输入文本中，关键字、标识符、整常数之间，若未出现关系和算术运算符以及赋值符，则至少须用一个空白字符加以分隔。作了这些限制以后，就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期获得一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字表已事先造好），若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为一标识符。采用上述策略后，针对表I中部分单词可以构造一个如图1所示的有限自动机（以状态转换图表示）。在图1中添加了当进行状态转移时，词法分析程序应执行的语义动作。

题目2：将表I单词集中的整常数改为无符号常数，修改题目1中已开发的扫描器。无符号常数的单词分类码助记符：UCON；其值为无符号常数的机内二进制表示。描述无符号数的BNF定义和状态转换图：无符号数的文法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 包含语义处理过程的识别无符号数的状态矩阵

图1 识别表I所列语言中的部分单词的DFA及相关的语义过程

图1及程序一中所出现的语义变量及语义函数的含义和功能说明如下。

函数GETCHAR：每调用一次，就把扫描指示器当前所指示的源程序字符送入字符变量ch，然后把扫描指示器前推一个字符位置。

字符数组TOKEN：用来依次存放一个单词词文中的各个字符。

函数CAT：每调用一次，就把当前ch中的字符拼接于TOKEN中所存字符串的右边。

函数LOOKUP：每调用一次，就以TOKEN中的字符串查保留字表，若查到，就将相应关键字的类别码赋给整型变量c；否则将c置为零。

函数RETRACT：每调用一次，就把扫描指示器回退一个字符位置（即退回多读的那个字符）。函数OUT：一般仅在进入终态时调用此函数，调用的形式为OUT(c，VAL)。其中，实参c为相应单词的类别码或其助记符；当所识别的单词为标识符和整数时，实参VAL为TOKEN（即词文分别为字母数字串和数字串），对于其余种类的单词，VAL均为空串。函数OUT的功能是，在送出一个单词的内部表示之后，返回到调用该词法分析程序的那个程序。

五、源程序

#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 13 char TOKEN[20];

char keyword[5][6]={\char ch;

extern int lookup(char *TOKEN) { int i; for(i=0;i<5;i++) { if(strcmp(keyword[i],TOKEN)==0) return(i+1); } return(0); }

extern void out(int a) { if(a==ID) printf(\ else if(a==INT) printf(\ else if(a==LE) printf(\ else if(a==NE) printf(\ else if(a==LT) printf(\ else if(a==GE) printf(\ else if(a==GT) printf(\ else printf(\}

extern report_error(void) { printf(\}

void scanner_example() { int i,c; if(isalpha(ch)) { TOKEN[0]=ch; ch=getchar();i=1; while(isalnum(ch)) { TOKEN[i]=ch;i++; ch=getchar(); } ungetc(ch,stdin); TOKEN[i]='\\0'; c=lookup(TOKEN); if(c==0) out(ID); else out(c); } else if(isdigit(ch)) { TOKEN[0]=ch; ch=getchar();i=1; while(isdigit(ch)) { TOKEN[i]=ch;i++; ch=getchar(); } TOKEN[i]='\\0'; ungetc(ch,stdin); out(INT); } else switch(ch) { case'<':ch=getchar(); if(ch=='=')out(LE); else if(ch=='>')out(NE); else { ungetc(ch,stdin); out(LT); }

break; case'>':ch=getchar(); if(ch=='=')out(GE); else{ ungetc(ch,stdin); out(GT); } break; default:report_error(); break; } return; }

void main() { printf(\ ch=getchar(); while(ch!='#') { if(ch=='\\n') { ch=getchar(); continue; } else { scanner_example(); ch=getchar(); } } }

六、源程序说明：

字符数组TOKEN：用来依次存放一个单词词文中的各个字符。函数getchar：每调用一次，就把扫描指示器当前所指示的源程序字符送入字符变量ch，然后把扫描指示器前推一个字符位置。

函数lookup：每调用一次，就以TOKEN中的字符串查保留字表，若查到，就将相应关键字的类别码赋给整形变量c；否则将c置为零。

函数ungetc：每调用一次，就把扫描指示器回退一个字符位置（即退回多读的那个字符）。

函数out：一般仅在进入终态时调用此函数，调用的形式为out（c）。其中，实参c为相应单词的类别码。函数根据类别码选择输出形式。

七、输出结果：

实验二语法分析程序实现

一、实验目的与要求

通过设计、编制、调试一个典型的语法分析程序（任选有代表性的语法分析方法，如算符优先法、递归下降法、LL(1)、SLR(1)、LR(1)等，作为编制语法分析程序的依据），对扫描器所提供的单词序列进行语法检查和结构分析，实现并进一步掌握常用的语法分析方法。

二、实验内容

选择对各种常见高级程序设计语言都较为通用的语法结构作为分析对象，给出其文法描述（注意应与所采用的语法分析方法比较贴近），设计并实现一个完整的语法分析程序。

输入：源程序以文件的形式输入。

输出：对于所输入的源程序，如果输入符号串是给定文法定义的合法句子，则输出“RIGHT”，并且给出每一步归约的过程；如果不是句子，即输入串有错误，则输出“ERROR”，并且显示已经归约出的各个文法符号。

三、基本实验题目

以如下文法G1所定义的算术表达式的赋值语句作为分析对象，编写并调试一个语法分析程序。

G1[<赋值语句>]：

<赋值语句> → <变量>:=<算术表达式>

<标识符> → <标识符> <字母> | <标识符> <数字> | <字母> <常数> → <整数> | <浮点数> <整数> → <数字> | <数字> <整数> <浮点数> → ? <整数> | <整数> ? <整数> <字母> → A|B|C|…|X|Y|Z|a|b|c|…|x|y|z <数字> → 0|1|2|…9

四、源程序

#include #include

#include //词法代码 #include #include

#define RIGHT 1 #define ERROR 0 #define MAXINPUT 300 #define MAXSTACK 100

#define STARTSYMBOL 'S' //语法部分

#define ID 6 // 变量标识符

//词法部分

#define UINT 7//用来表示无符号整数代指ICON

#define LT 8 #define LE 9 #define EQ 10 #define NE 11 #define GT 12 #define GE 13 #define IS 14 #define ADD 15 #define SUB 16 #define MUL 17 #define DIV 18 #define LETTER 20 #define DIGIT 21 #define POINT 22 #define OTHER 23 #define POWER 24 #define PLUS 25 #define MINUS 26

#define UFCON 27 //在这用来表示无符号浮点数代指FCON #define ClassF 200 #define EndState -1

/**********************用于无符号数标识***************/ #define LP 28 // ( #define RP 29 // ) #define EOI 30 // #

char TOKEN[20]; struct RetainWord { };

/******************字符串全局变量********************/

int w,n,p,e,d;//w尾数累加器，n十进制小数位数计数器，p指数累加器，e指数符号，d存当前数值 int Class; //Used to indicate class of the word int x=0;

int n; char Word[7]; {1,\}, {2,\}, {3,\}, {4,\}, {5,\},

// + // - // * // /

/**********************用于字符串标识*******************/

}rw[5]={

int l=0; //列标识 int lf=0; //标识符首位置 int r=0; //行标 int ICON; float FCON;

static int CurrentState; //Used to present current state, the initial value:0

int stack[MAXSTACK]; /* a[ ] is input line */ char a[MAXINPUT];

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 table[11][11]={

//语法部分算符优先矩阵，为>,-1为< 0为=;其他为错误类型 //+,-,*,/,(,),ID,UCON,:=,#,N //- //* //,/ //) //ID //UCON

{1,1,-1,-1,-1,1,-1,-1,6,1,1},

{1,1,-1,-1,-1,1,-1,-1,6,1,1}, {1,1,1,1,-1,1,-1,-1,6,1,1}, {1,1,1,1,-1,1,-1,-1,6,1,1}, {1,1,1,1,5,1,5,5,6,1,5}, {1,1,1,1,5,1,5,5,1,1,5},

void coor(char ch1) //词法部分 { }

if(ch1==10){

r++;l=0;} l+=7; l++; else if(ch1==9) else

{1,1,1,1,5,1,5,5,6,1,5},

{-1,-1,-1,-1,-1,0,-1,-1,6,1,-1}, //(

{-1,-1,-1,-1,-1,7,-1,-1,7,1,-1},//:=

{-1,-1,-1,-1,-1,7,-1,-1,-1,-1,-1},//# {1,1,1,1,5,1,5,5,-1,1,0}}; //N

/******************无符号数全局变量********************/ int lookup(char *a) { }

for(int i=0;i<5;i++)

if(strcmp(rw[i].Word,a)==0)

return(rw[i].n); //保留字减去字符数组如果值为就返回保留字类型

return(0);

int report_error(int sk){ }

/******************字符串的函数********************/ int GetChar (FILE *fp) { }

int EXCUTE (int state, int symbol)//state当前状态symbol扫视字符 {

switch (state) { case 0:

switch (symbol) int c; lf=l; c=fgetc(fp); coor(c);

if(isdigit(c)) { }

if (c=='.')

return POINT; return POWER; return PLUS; return MINUS; if (c=='E'||c=='e') if (c=='+') if (c=='-') return OTHER;

d=c-'0'; return DIGIT;

printf(\第%d行，第%d列，出现\,r+1,lf+1); switch (sk) {

case 1:printf(\出现非法无符号浮点数！！词法错误，错误类型%d。\\n\,sk);break; case 2:printf(\出现无法识别符号！！词法错误，错误类型%d。\\n\,sk);break; case 3:printf(\出现无法识别字符！！词法错误，错误类型%d。\\n\,sk);break; case 4:printf(\出现两符号相邻，之间缺少数字或标识符！！语法错误，错误类型%d。case 5:printf(\缺少运算符！！语法错误，错误类型%d。\\n\,sk);break;

case 6:printf(\出现赋值符号前不是标识符的错误！！语法错误，错误类型%d。\\n\,sk);break; case 7:printf(\出现非文法定义的句型！！语法错误，错误类型%d。\\n\,sk);break; case 8:printf(\缺少语句终结符号“#”！！语法错误，错误类型%d。\\n\,sk);break; } return 0;

\\n\,sk);break;

{

case DIGIT: n=0;p=0;e=1;w=d;CurrentState=1;break; case POINT: w=0;n=0;p=0;e=1;CurrentState=3;break; default: report_error(1);Class=0;CurrentState=EndState; }

break; {

case DIGIT: w=w*10+d;break;

//CurrentState=1

case POINT: CurrentState=2;break; case POWER: CurrentState=4;break;

default: ICON=w;Class=UINT;CurrentState=EndState; }

case 1:switch (symbol)

break;

{

case DIGIT: n++;w=w*10+d;break; case POWER: CurrentState=4;x=1;break; default: if(n>0){ }

Class=ClassF;

FCON=(float)w*pow(10,e*p-n); }

CurrentState=EndState;

}

report_error(1);Class=0; else{

case 2:switch (symbol)

break;

{

case DIGIT: n++;w=w*10+d;CurrentState=2;break; default: report_error(2); }

Class=0;CurrentState=EndState;

case 3:switch (symbol)

break;

{

case DIGIT: p=p*10+d;CurrentState=6;break; case MINUS: e=-1;CurrentState=5;break; case PLUS: CurrentState=5;break;

default:report_error(1);Class=0;CurrentState=EndState; }

case 4:switch (symbol)

break;

case 5:switch (symbol)

}

{

case DIGIT: p=p*10+d;CurrentState=6;break; default: report_error(1);Class=0; }

CurrentState=EndState;

break;

{

case DIGIT:p=p*10+d;break;

default: FCON=(float)w*pow(10,e*p-n);Class=ClassF;CurrentState=EndState; }

case 6:switch (symbol)

break;

return CurrentState;

int LEX (FILE *fp) { }

//*****************浮点数部分代码*********

int out(int n,char *p) {

int t=0; switch(n) {

case 1:printf(\,rw[n-1].Word);t=1;break; case 2:printf(\,rw[n-1].Word);t=2;break; case 3:printf(\,rw[n-1].Word);t=3;break; case 4:printf(\,rw[n-1].Word);t=4;break; case 5:printf(\,rw[n-1].Word);t=5;break; case 6:printf(\,p);t=6;break; case 7:printf(\,ICON);t=7;break; case 8:printf(\);t=8;break; case 9:printf(\);t=9;break; case 10:printf(\);t=10;break; case 11:printf(\);t=11;break; int ch;

CurrentState=0;

while (CurrentState!=EndState){ }

return Class;

ch=GetChar(fp);

EXCUTE (CurrentState,ch);

}

case 12:printf(\);t=12;break; case 13:printf(\);t=13;break; case 14:printf(\);t=14;break; case 15:printf(\);t=15;break; case 16:printf(\);t=16;break; case 17:printf(\);t=17;break; case 18:printf(\);t=18;break;

case 27:printf(\,FCON);return 27;break; case 28:printf(\);t=28;break; case 29:printf(\);t=29;break; case 30:printf(\);t=30;break; default : t=report_error(3); } return t;

break;

int scanner_example (FILE *fp) {

char ch; int i, c,t; lf=l;

ch=fgetc(fp); l+=1;

if (isalpha(ch)) /*it must be a identifer!*/ {

TOKEN[0]=ch; ch=fgetc(fp); l+=1; i=1;

while(isalnum(ch)) { }

TOKEN[i]='\\0'; c=lookup (TOKEN); if (c==0)

t=out (ID,TOKEN); t=out (c,\); else

fseek(fp,-1,1);

TOKEN[i]=ch; i++; ch=fgetc(fp); l+=1;

}

l-=1;

else if(isdigit(ch)||ch=='.'){ }

else switch(ch){ l+=1;

if(ch=='=')t=out(LE,\); else if(ch=='>') t=out (NE,\); else{ } break; break; l+=1; if(ch=='=') } break; l+=1; if(ch=='=')

t=out(GE,\); fseek(fp,-1,1); l-=1;

t=out(GT,\); else{

fseek(fp,-1,1); l-=1;

t=out (LT,\); TOKEN[0]=ch; fseek(fp,-1,1); l-=1;

int k=LEX(fp); if(k==ClassF) { }

else if(UINT==k) { }

fseek(fp,-1,1); l-=1;

t=out(UINT,\); t=out(UFCON,\);

case '<': ch=fgetc(fp);

case '=': t=out(EQ, \); case '>': ch=fgetc(fp);

case ':': t=ch=fgetc(fp);

}

t=out(IS,\); fseek(fp,-1,1); t=report_error(2); l-=1; break;

else {

case '+':t=out(ADD,\);break; case '-':t=out(SUB,\);break; case '*':t=out(MUL,\);break; case '/':t=out(DIV,\);break; case '(':t=out(LP,\);break; case ')':t=out(RP,\);break; case '#':t=out(EOI,\);break;

default: t=report_error(3); }

int IsVt(int a) { }

/*存储算符优先关系表，大于为，小于或等于为-1，其它为表示出*/ int changchartoint(FILE *fp) /*将字符转为数字，以得到算符优先值*/ {

int t; char ch; lf=l;

ch=fgetc(fp); coor(ch);

if(ch==EOF) t=20; while(ch!=EOF) {

if(ch==' '||ch==9||ch==10){

ch=fgetc(fp); coor(ch);

if(ch==EOF) return 20;

if(a==0||a==1||a==2||a==3||a==4||a==5||a==6||a==7||a==8||a==9)

return RIGHT; return ERROR; else break; }

return t;

}

} else{ }

fseek(fp,-1,1); l-=1;

switch(scanner_example(fp)){ case ADD:t=0;break; case SUB:t=1;break; case MUL:t=2;break; case DIV:t=3;break; case LP:t=4;break; case RP:t=5;break; case ID:t=6;break; case UINT:t=7;break; case UFCON:t=7;break; case IS:t=8;break; case EOI:t=9;break; case 10:t=10;break; }

break;

return t;

void changinttochar(int t){ }

switch(t){

case 0:printf(\);break; case 1:printf(\);break; case 2:printf(\);break; case 3:printf(\);break; case 4:printf(\);break; case 5:printf(\);break; case 6:printf(\);break; case 7:printf(\);break; case 8:printf(\);break; case 9:printf(\);break; case 10:printf(\);break; }

}

if (IsLowerThan(stack[j],r)||IsEqualTo(stack[j],r)) { } else

return ERROR; stack[++k]=r;

//printf(\新结点入栈，堆栈指针移进k=%d\\n\

//printf(\为：\

// printf(\栈顶节点为：\

}while (r!=9); return RIGHT;

int IsHigherThan(int a,int b) { }

int IsLowerThan(int a,int b) { }

int IsEqualTo(int a,int b) { }

int Reduce(int a,int b,int c) {

char gl='F'; printf(\); for(;a<=b;a++){

changinttochar(stack[a]);

if(stack[a]==1||(stack[a])==0)gl='E'; if(table[a][b]==0)

return RIGHT; return ERROR; else

if(table[a][b]==-1)

return RIGHT; return ERROR; else

if(table[a][b]==1)

return RIGHT;

return report_error(table[a][b]); return ERROR;

else if(table[a][b]!=-1&&table[a][b]!=0) else

}

if(stack[a]==2||(stack[a])==3)gl='T';

printf(\类型为%c,归约为N，\,gl); return 10;

//************************************************语法分析**********

//************************************************语义分析********** char

E( ) /* 识别<算术表达式>*/ {

E1_PLACE=T( ); /* 语法范畴E的一个属性*/ while (SYM='+' || SYM='-') {

ADVANCE; /* 将输入串指针调整至指向下一个输入符号*/ E2_PLACE=T( );

T1=NewTemp( ); /* 分配一个新的临时变量*/

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='标识符') { ADVANCE;

return Entry(i.词文); /* 以标识符的词文为名字查、填符号表*/

} else

if ( SYM='(' ) { ADVANCE; PLACE=E( ); if ( SYM=')' ) { ADVANCE; return PLACE; }

else ERROR; }

//************************************************语义分析********** main() {

//int j=0; FILE *fp; char ch;

if((fp=fopen(\,\))==NULL) //readonly方式打开文件 { }

printf(\文件内容如下:\\n\); ch=fgetc(fp); while(ch!=EOF) { }

printf(\语法分析如下:\\n\); fseek(fp,0,0); int key; ch=fgetc(fp); coor(ch); while(ch!=EOF) {

if(ch==' '||ch==9||ch==10){

ch=fgetc(fp);

coor(ch);}//'\\t'为水平制表符ASCII码为.\\n占两个字节,前一字节无ASCII码为换行格

//坐标移到文档开始位置

putchar(ch); ch=fgetc(fp);

//EOF文档结束标志

printf(\找不到文件!!!\\n\); return(0);

式，后一字节ASCII码为

else

}

{ }

fseek(fp,-1,1); l-=1;

key=parser(fp); if(key==1) { } else { }

//printf(\ch=fgetc(fp); coor(ch);

printf(\出现语法错误！！\\n\\n\);

printf(\成功通过词法分析和语法分析！！\\n\\n\);

//扫描

printf(\); fclose(fp); return(0);

正确输入时结果：

错误输入时结果：

int parser (FILE *fp) {

if (IsLowerThan(stack[j],r)||IsEqualTo(stack[j],r))

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 */ int sj; stack[0]=9; do {

int j;

if (IsVt(stack[k]))

j=k; j=k-1; else

printf(\中内容为(自底向上)：\); for(sj=0;sj<=j;sj++)

changinttochar(stack[sj]); printf(\当前扫描字串为：\); r=changchartoint(fp); //a[i++]=r;

if(r==20&&stack[k]!=9)return report_error(8);

if(r>=0&&r<=3&&stack[k]>=0&&stack[k]<=3)return report_error(4);

//printf(\

while (IsHigherThan(stack[j],r)) {

int q; do {

NewVn=Reduce(j+1,k,r); for(sj=j+1;sj<=k;sj++)

stack[sj]=0;

k=j+1;/* reduce the leftmost prime phrase */

stack[k]=NewVn;/* it is stack[j+1] stack[j+2] ?stack[k] */ printf(\堆栈指针移动到k=%d\\n\,k);

q=stack[j];

if (IsVt(stack[j-1]))

j--; j-=2; else

}while(!IsLowerThan(stack[j],q));

} /*end of while*/

}

{ } else

return ERROR; stack[++k]=r;

//printf(\新结点入栈，堆栈指针移进k=%d\\n\

//printf(\为：\

// printf(\栈顶节点为：\

}while (r!=9); return RIGHT;

int IsHigherThan(int a,int b) { }

int IsLowerThan(int a,int b) { }

int IsEqualTo(int a,int b) { }

int Reduce(int a,int b,int c) {

char gl='F'; printf(\); for(;a<=b;a++){

changinttochar(stack[a]);

if(stack[a]==1||(stack[a])==0)gl='E'; if(stack[a]==2||(stack[a])==3)gl='T'; if(table[a][b]==0)

return RIGHT; return ERROR; else

if(table[a][b]==-1)

return RIGHT; return ERROR; else

if(table[a][b]==1)

return RIGHT;

return report_error(table[a][b]); return ERROR;

else if(table[a][b]!=-1&&table[a][b]!=0) else

}

printf(\类型为%c,归约为N，\,gl); return 10;

main() {

ch=fgetc(fp); coor(ch); while(ch!=EOF) {

if(ch==' '||ch==9||ch==10){

ch=fgetc(fp);

coor(ch);}//'\\t'为水平制表符ASCII码为.\\n占两个字节,前一字节无ASCII码为换行格

//int j=0; FILE *fp; char ch;

if((fp=fopen(\,\))==NULL) //readonly方式打开文件 { }

printf(\文件内容如下:\\n\); ch=fgetc(fp); while(ch!=EOF) { }

printf(\语法分析如下:\\n\); fseek(fp,0,0); int key;

//坐标移到文档开始位置

putchar(ch); ch=fgetc(fp);

//EOF文档结束标志

printf(\找不到文件!!!\\n\); return(0);

式，后一字节ASCII码为

else {

fseek(fp,-1,1); l-=1;

key=parser(fp); if(key==1) { } else {

printf(\出现语法错误！！\\n\\n\);

printf(\成功通过词法分析和语法分析！！\\n\\n\);

}

//printf(\ch=fgetc(fp); coor(ch);

printf(\); fclose(fp); return(0);

五、运行结果：

正确输入时结果：

错误输入时结果：

实验三语义分析程序实现

一、实验目的与要求

在实现词法、语法分析程序的基础上，编写相应的语义子程序，进行语义检查，加深对语法制导翻译原理的理解，进一步掌握将语法分析所识别的语法范畴变换为某种中间代码（四元式）的语义分析方法，完成编译器的前端开发工作。

二、实验内容

语法制导翻译模式是在语法分析的基础上，增加语义操作来实现的。对于给定文法中的每一产生式，编写相应的语义子程序。在语法分析过程中，每当用一产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作之外，还要调用相应的语义子程序，以便完成生成中间代码、查填有关表格、检查并报告源程序中的错误等工作。每个语义子程序需指明相应产生式中各个符号的具体含义，并规定使用该产生式进行分析时所应采取的语义动作。这样，语法制导翻译程序在对源程序从左到右进行的一遍扫描中，既完成语法分析任务，又完成语义分析和中间代码生成方面的工作。

高级语言的语法结构类型很多，例如说明语句、程序流程控制语句、子程序结构语句、格式语句等，可选择其中一类进行语义分析程序的开发。

输入：作为测试用例的源程序文件。

输出：将源程序转换为中间代码形式表示，并将中间代码序列输出到文件中。若源程序中有错误，应指出错误信息。

三、基本实验题目

针对实验一中定义的文法G1[<赋值语句>]，首先根据需进行的语义工作，完成对文法的必要拆分和语义动作的编写，从而为每个产生式都配备相应的语义子程序。然后编写并调试相应的语法制导翻译程序。在此，中间代码以四元式表示，并且对于不同数据类型的运算对象，在进行算术运算前须转换为相同的数据类型。

要求完成词法、语法和语义分析的整体设计，重点通过对实验二中语法分析程序的扩展，将编译程序前端涉及的各个模块组合在一起，形成一个将源程序翻译为四元式序列的编译系统。

四、示例

对实验二中的示例一给出的文法G2[<算术表达式>]，在利用递归下降法进行语法分析的同时，生成四元式形式的中间代码序列。语法制导翻译程序的核心部分（指表达式、项和因式的处理）的算法，可用程序四描述如下：

程序四利用递归下降法生成简单算术表达式的四元式序列

#include #include

#include //词法代码 #include #include

#define RIGHT 1 #define ERROR 0 #define MAXINPUT 300 #define MAXSTACK 100

#define STARTSYMBOL 'S' //语法部分

#define ID 6 // 变量标识符 #define LT 8 #define LE 9 #define EQ 10 #define NE 11 #define GT 12 #define GE 13 #define IS 14 #define ADD 15 #define SUB 16 #define MUL 17 #define DIV 18 #define LETTER 20 #define DIGIT 21 #define POINT 22 #define OTHER 23 #define POWER 24 #define PLUS 25 #define MINUS 26

#define UFCON 27 //在这用来表示无符号浮点数代指FCON #define ClassF 200 #define EndState -1

/**********************用于无符号数标识***************/ #define LP 28 // ( #define RP 29 // ) #define EOI 30 // #

char TOKEN[20]; struct RetainWord { };

int n; char Word[7]; {1,\}, {2,\}, {3,\}, {4,\}, {5,\},

// + // - // * // /

//词法部分

#define UINT 7//用来表示无符号整数代指ICON

/**********************用于字符串标识*******************/

}rw[5]={

/******************字符串全局变量********************/

int w,n,p,e,d;//w尾数累加器，n十进制小数位数计数器，p指数累加器，e指数符号，d存当前数值 int Class; //Used to indicate class of the word int x=0;

int l=0; //列标识 int lf=0; //标识符首位置 int r=0; //行标 int ICON; float FCON;

static int CurrentState; //Used to present current state, the initial value:0

int stack[MAXSTACK]; /* a[ ] is input line */ char a[MAXINPUT];

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 table[11][11]={

//语法部分算符优先矩阵，为>,-1为< 0为=;其他为错误类型 //+,-,*,/,(,),ID,UCON,:=,#,N //- //* //,/ //) //ID //UCON

{1,1,-1,-1,-1,1,-1,-1,6,1,1},

{1,1,-1,-1,-1,1,-1,-1,6,1,1}, {1,1,1,1,-1,1,-1,-1,6,1,1}, {1,1,1,1,-1,1,-1,-1,6,1,1}, {1,1,1,1,5,1,5,5,6,1,5}, {1,1,1,1,5,1,5,5,1,1,5},

void coor(char ch1) //词法部分 { }

if(ch1==10){

r++;l=0;} l+=7; l++; else if(ch1==9) else

{1,1,1,1,5,1,5,5,6,1,5},

{-1,-1,-1,-1,-1,0,-1,-1,6,1,-1}, //(

{-1,-1,-1,-1,-1,7,-1,-1,7,1,-1},//:=

{-1,-1,-1,-1,-1,7,-1,-1,-1,-1,-1},//# {1,1,1,1,5,1,5,5,-1,1,0}}; //N

/******************无符号数全局变量********************/ int lookup(char *a) {

for(int i=0;i<5;i++)

}

if(strcmp(rw[i].Word,a)==0)

return(rw[i].n); //保留字减去字符数组如果值为就返回保留字类型

return(0);

int report_error(int sk){ }

/******************字符串的函数********************/ int GetChar (FILE *fp) { }

int EXCUTE (int state, int symbol)//state当前状态symbol扫视字符 {

int c; lf=l; c=fgetc(fp); coor(c);

if(isdigit(c)) { }

if (c=='.')

return POINT; return POWER; return PLUS; return MINUS; if (c=='E'||c=='e') if (c=='+') if (c=='-') return OTHER;

d=c-'0'; return DIGIT;

printf(\第%d行，第%d列，出现\,r+1,lf+1); switch (sk) {

\\n\,sk);break;

switch (state) { case 0:

switch (symbol) {

case DIGIT: n=0;p=0;e=1;w=d;CurrentState=1;break; case POINT: w=0;n=0;p=0;e=1;CurrentState=3;break; default: report_error(1);Class=0;CurrentState=EndState; }

break; {

case DIGIT: w=w*10+d;break;

//CurrentState=1

case POINT: CurrentState=2;break; case POWER: CurrentState=4;break;

default: ICON=w;Class=UINT;CurrentState=EndState; }

case 1:switch (symbol)

break;

{

case DIGIT: n++;w=w*10+d;break; case POWER: CurrentState=4;x=1;break; default: if(n>0){ }

Class=ClassF;

FCON=(float)w*pow(10,e*p-n); }

CurrentState=EndState;

}

report_error(1);Class=0; else{

case 2:switch (symbol)

break;

{

case DIGIT: n++;w=w*10+d;CurrentState=2;break; default: report_error(2); }

Class=0;CurrentState=EndState;

case 3:switch (symbol)

break;

{

case DIGIT: p=p*10+d;CurrentState=6;break; case MINUS: e=-1;CurrentState=5;break; case PLUS: CurrentState=5;break;

case 4:switch (symbol)

}

default:report_error(1);Class=0;CurrentState=EndState; }

break;

{

case DIGIT: p=p*10+d;CurrentState=6;break; default: report_error(1);Class=0; }

CurrentState=EndState;

case 5:switch (symbol)

break;

{

case DIGIT:p=p*10+d;break;

default: FCON=(float)w*pow(10,e*p-n);Class=ClassF;CurrentState=EndState; }

case 6:switch (symbol)

break;

return CurrentState;

int LEX (FILE *fp) { }

//*****************浮点数部分代码*********

int out(int n,char *p) {

int t=0; switch(n) {

CurrentState=0;

while (CurrentState!=EndState){ }

return Class;

ch=GetChar(fp);

EXCUTE (CurrentState,ch);

}

case 8:printf(\);t=8;break; case 9:printf(\);t=9;break; case 10:printf(\);t=10;break; case 11:printf(\);t=11;break; case 12:printf(\);t=12;break; case 13:printf(\);t=13;break; case 14:printf(\);t=14;break; case 15:printf(\);t=15;break; case 16:printf(\);t=16;break; case 17:printf(\);t=17;break; case 18:printf(\);t=18;break;

case 27:printf(\,FCON);return 27;break; case 28:printf(\);t=28;break; case 29:printf(\);t=29;break; case 30:printf(\);t=30;break; default : t=report_error(3); } return t;

break;

int scanner_example (FILE *fp) {

char ch; int i, c,t; lf=l;

ch=fgetc(fp); l+=1;

if (isalpha(ch)) /*it must be a identifer!*/ {

TOKEN[0]=ch; ch=fgetc(fp); l+=1; i=1;

while(isalnum(ch)) { }

TOKEN[i]='\\0'; c=lookup (TOKEN); if (c==0)

TOKEN[i]=ch; i++; ch=fgetc(fp); l+=1;

}

t=out (ID,TOKEN); t=out (c,\);

else

fseek(fp,-1,1); l-=1;

else if(isdigit(ch)||ch=='.'){ }

else switch(ch){ l+=1;

if(ch=='=')t=out(LE,\); else if(ch=='>') t=out (NE,\); else{ } break; break; l+=1; if(ch=='=') }

t=out(GE,\); fseek(fp,-1,1); l-=1;

t=out(GT,\); else{

fseek(fp,-1,1); l-=1;

t=out (LT,\); TOKEN[0]=ch; fseek(fp,-1,1); l-=1;

int k=LEX(fp); if(k==ClassF) { }

else if(UINT==k) { }

fseek(fp,-1,1); l-=1;

t=out(UINT,\); t=out(UFCON,\);

case '<': ch=fgetc(fp);

case '=': t=out(EQ, \); case '>': ch=fgetc(fp);

break; l+=1; if(ch=='=') }

break;

t=out(IS,\); fseek(fp,-1,1); t=report_error(2); l-=1; else {

case ':': t=ch=fgetc(fp);

default: t=report_error(3); }

//************************************************语义分析**********

int IsVt(int a) { }

/*存储算符优先关系表，大于为，小于或等于为-1，其它为表示出*/ int changchartoint(FILE *fp) /*将字符转为数字，以得到算符优先值*/ {

int t; char ch; lf=l;

ch=fgetc(fp); coor(ch);

if(ch==EOF) t=20;

if(a==0||a==1||a==2||a==3||a==4||a==5||a==6||a==7||a==8||a==9)

return RIGHT; return ERROR; else break; }

return t;

}

while(ch!=EOF) { }

return t;

if(ch==' '||ch==9||ch==10){ } else{ }

fseek(fp,-1,1); l-=1;

ch=fgetc(fp); coor(ch);

if(ch==EOF) return 20;

break;

void changinttochar(int t){

switch(t){

}

int parser (FILE *fp) {

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 */ int sj; stack[0]=9; do {

int j;

if (IsVt(stack[k]))

j=k; j=k-1; else

printf(\中内容为(自底向上)：\); for(sj=0;sj<=j;sj++)

changinttochar(stack[sj]); printf(\当前扫描字串为：\); r=changchartoint(fp); //a[i++]=r;

if(r==20&&stack[k]!=9)return report_error(8);

if(r>=0&&r<=3&&stack[k]>=0&&stack[k]<=3)return report_error(4);

//printf(\

while (IsHigherThan(stack[j],r)) {

int q; do {

NewVn=Reduce(j+1,k,r); for(sj=j+1;sj<=k;sj++)

stack[sj]=0;