编译课程设计

课程设计

（2010 －2011 学年度  第 二 学期）

课程名称         编译原理           

设计题目 算术表达式的语法分析及语义分析程序设计                       

专 业：  计算机                

姓 名：                

学 号：                

班 级：  计算机082             

教 师：                 

地 点：                

一、设计目的

掌握算符优先文法进行语法分析，通过设计、编制、调试一个算术表达式的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。进一步培养编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，完成有一定工作量的程序设计任务，综合使用程序设计语言、数据结构和编译原理的知识。

二、设计内容及步骤

   实验内容：

   (1)可以选择递归下降法、LL（1）、算符优先分析法、LR法完成以上任务，中间代码选用逆波兰式或四元式。

   (2)写出算术表达式的符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。

   (3)编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。

   实验步骤：

选择递归下降法实现，其实现思想是，对每个非终结符按其产生式结构构造相应语法分析子程序，其中终极符产生匹配命令，而非终极符则产生调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的，文法中每个非终结符对应一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符产生式有多个候选式时能够按LL（1）形式可唯一确定选择某个候选式进行推导。

此算法的特点是：

递归下降法是语法分析中最易懂的一种方法。递归下降法要满足的条件：假设A的全部产生式为A->a1/a2/.../an.则必须满足如下条件才能保证可以唯一的选择合适的产生式

  构造递归下降语法分析程序

   采用了递归子程序方法进行语法分析，对文法中的每个非终极符号按其产生式结构产生相应的语法分析子程诹，完成相应的识别任务。其中终结符产生匹配命令，非终结符则产生调用命令。每次进入子程序之前都预先读入一个单词。因为使用了递归下降方法，所以程序结结构和层次清晰明了，易于手工实现，且时空效率很高。实际的语法分析工作，从调用总程序的分析子程序开始，根据产生式进行递归调用各个分析子程序。

中间代码选用四元式

四元式是一种更接近目标代码的中间代码形式。由于这种形式的中间代码便于优化处理，因此，在目前许多编译程序中得到了广泛的应用。 　　

四元式实际上是一种“三地址语句”的等价表示。它的一般形式为： 　　(op,arg1,arg2,result) 　　其中， op为一个二元 (也可是一元或零元)运算符；arg1,arg2分别为它的两个运算 (或操作)对象，它们可以是变量、常数或系统定义的临时变量名；运算的结果将放入result中。

四元式还可写为类似于PASCAL语言赋值语句的形式： 　　

result ∶= arg1 op arg2 　　

需要指出的是，每个四元式只能有一个运算符，所以，一个复杂的表达式须由多个四元式构成的序列来表示。例如，表达式A+B*C可写为序列 

　　T1∶=B*C 　　T2∶=A+T1 　

　其中，T1，T2是编译系统所产生的临时变量名。当op为一元、零元运算符 (如无条件转移)时，arg2甚至arg1应缺省，

即result∶=op arg1或 op result ；

对应的一般形式为： 　

　(op,arg1,,result) 或 　(op,,,result) 

首先应该把用文字表示的文法改写为数学符号。（其中关于无符号整数和标识符，由于可以在词法分析的过程中给以确定，所以就不必抽象其表达式。） 

设： 

 indentifer ：标识符    digit : 无符号整数 

E：    表达式              T：项                 F：因子 

则一个简单的术表达式的文法G1中包含以下产生式：

E -> E+E | E-E | E*E | E/E | (E) | indentifer | digit

为了明确运算符的优先权（括号的优先权高于乘除法，乘除法的优先权高于加减法），可改写文法G1如下： 

改写后的文法G2: 

        E -> E+T | E-T | T

        T -> T*F | T/F | F

     F -> (E) | indentifer | digit

为了避免左递归的发生，可进一步将文法改成： 

文法G[E]： 

（1）E -> [+|-]TG

（2）G -> +TG|—TG

（3）G -> ε

（4）T -> FS

（5）S -> *FS|/FS

（6）S -> ε

（7）F -> (E)

（8）F -> indentifer | digit

 设计若干用例：

           i1*i2+i3#

三、详细的算法描述（流程图或伪代码）程序流程图：

             N         Y

                      Y

            N

 将整个的一个程序分成三个模块，既词法分析，语法分析，语义分析。分别对三个模块进行设计实现。然后达到整体的一个实现。

       词法分析：

       单词种类定义如下：

标识符的种类编码 1 

常数的种类编码 2  

运算的种类编码 3 :+ ,- ,* ,/  

界限符的种类编码 4 : (,),;

四、设计结果（测试案例）

五、设计总结与心得

在这次编译的课程设计中，我通过重温课本，查阅资料，请教同学，并且动手实践，加深了对课堂上所学的理论知识的理解和掌握。

在这次课程设计中我最大的收获就是对LR分析法的整个过程有了非常深刻的认识，也更加深了我对该分析法的理解。同时尽管LR分析法我实现的并不是特别完美，但能够大致的将整个过程实现出来，我觉得这也是对我的编程能力的一个极大的提高。同时也培养了自己严密的逻辑思维能力。

同时，这次的设计还让我明白了，用心才会成功，刚开始搞课程设计的时候，因为无法理清思路，找不到解决问题的突破口,我一再找寻新的题目。但毕竟我花了这么多的时间和精力在这个题目上，终究还是舍不得换题。然而，后来突然一下想着想着就通了。。

做学问既要有耐心又要细心。急躁于事无补，正确的心态应该是平和的，戒骄戒躁的。千里之堤，溃于蚁穴，同样地，哪怕一行代码有差错也会使整个程序不能得到正确的结果。

编写程序应该养成良好的习惯。流程图可以使复杂的问题变得明了，可以帮助理清思路。另外，适当的注释不仅增加了程序的可读性，而且也有助于之后的修改和完善。

六、附：程序完整代码

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

char str[100];    //输入的算术表达式字符串

char ch;

int  nn=0;    //字符串计数器

int  f=0;

char count='0';    //四元式临时变量计数器

//***********************词法分析部分数据结构及函数定义*****************

struct cifa     //词法结构体

{

 int type;    //类型

 char  word[10];    //字符串内容

 cifa *next;

};

cifa *cifa_head,*cifa_end,*cifa_p;    //cifa队列

//***********************语义分析部分数据结构及函数定义*****************

struct yuyi     //语义结构体

{

 char  op;    //操作符

 char  op1[10];    //第一个操作数

 char  op2[10];    //第二个操作数

 char  result[10];   //结果

 yuyi  *next;

};

yuyi *yuyi_head,*yuyi_end,*yuyi_q,*yuyi_vt; //yuyi队列

void yufa_zfc_disp(cifa *p)    //输出字符串

{

 while(p!=NULL)

 {

cout<word ;

p = p->next;

 }

// cout<}

//***********************语法分析部分函数定义*****************

void advance();     //取词法分析产生列表中的结点作语法分析

int E(); // E -> [+|-]TG 子函数

int G();     // G -〉+TG | -TG |ε子函数

int T(); // T -> FS 子函数

int S(); // S -> *FS | /FS |ε 子函数

int F(); // F -> (E) | 标识符 | 无符号整数 子函数

int yufa_main();    //语法分析主函数

cifa *cifa_add(cifa *p);   //在分析结果列表尾添加一个新接点

void cifa_disp(cifa *cifa_head);  //输出词法分析结果

void GetChar();     //取字符

void notock();     //去掉空格

int alph(void);                      //识别标识符

int number(void);    //识别数字 

int test(void);     //识别相关符号

int cifa_main();    //词法分析主函数

char E_name[10],T_name[10],F_name[10],temp_name[10];//在求四元式的时候用来传递信息

yuyi *yuyi_add(yuyi *p);      //在四元式链表末添加一个结点

void yuyi_sys_disp();      //输出四元式链表

int E1(); //E -> T+E | T-E | T

int T1(); //T -> F*T | F/T | F

int F1(); //F -> (E) | 标识符 | 无符号整数

void yuyi_main();    //语义分析主函数

//**********************词法分析部分*********************************

void yuyi_main()   //语义分析主函数

{

 cifa_p = cifa_head;

 yuyi_head = new yuyi;

yuyi_head -> next = NULL;

 yuyi_end = yuyi_head;

cout< yufa_zfc_disp(cifa_head->next);

cout<<"语义分析产生的四元式如下："< cout< advance();

 E1();

 yuyi_sys_disp();

cout<}

int F1() //F -> (E) | 标识符 | 无符号整数

{

if ((strcmp(cifa_p->word,"(") == 0 ) )

 {

  advance();

strcpy(F_name,cifa_p->word);

  strcpy(E_name,F_name); 

  E1();

if ((strcmp(cifa_p->word,")") == 0 ) )

  {

   advance();

   strcpy(F_name,E_name);

   return (1);

  }

  else 

  {

cout<<"ERROR"<   return (0);

  }

 }

else if ( cifa_p->type == 1 || cifa_p->type == 2)

 {

strcpy(F_name,cifa_p->word);

  advance();

  return (1);

 }

 else return 0;

}

int T1() //T -> F*T | F/T | F

{

 yuyi *p = new yuyi;

 F1();

strcpy(p->op1,F_name);

if (strcmp(cifa_p->word,"*") == 0)

 {

  advance();

  T1(); 

p->next =NULL;

p->op = '*';

strcpy(p->op2,T_name);

  T_name[0] = 't';

  T_name[1] = ++count;

  T_name[2] = '\\0';

strcpy(p->result,T_name);

  yuyi_add(p);

  return(1);

 }

else if (strcmp(cifa_p->word,"/") == 0)

 {

  advance();

  T1();

p->next =NULL;

p->op = '/';

strcpy(p->op2,T_name);

  T_name[0] = 't';

  T_name[1] = ++count;

  T_name[2] = '\\0';

strcpy(p->result,T_name);

  yuyi_add(p);

  return(1);

 }

 else

 {

  strcpy(T_name,F_name);

  return(1);

 }

}

int E1() //E -> T+E | T-E | T

{

 yuyi *p = new yuyi;

 T1();  

strcpy(p->op1,T_name);

if (strcmp(cifa_p->word,"+") == 0)

 {

  advance();

  E1();

p->next =NULL;

p->op = '+';

strcpy(p->op2,E_name);

  E_name[0] = 't';

  E_name[1] = ++count;

  E_name[2] = '\\0';

strcpy(p->result,E_name);

  yuyi_add(p);

     return (1);

 }

else if (strcmp(cifa_p->word,"-") == 0)

 {

  advance();

  E1();

p->next =NULL;

p->op = '-';

strcpy(p->op2,E_name);

  E_name[0] = 't';

  E_name[1] = ++count;

  E_name[2] = '\\0';

strcpy(p->result,E_name);

  yuyi_add(p);

  return(1);

 }

 else

 {

  strcpy(E_name,T_name);

  return(1);

 }

}

int yufa_main()      //语法分析主程序

{

 int n;

 cifa *p = new cifa;

strcpy(p -> word ,"#"); //对词法分析产生的结果链表进行处理

p -> type =-1;

p -> next = NULL;

 cifa_add(p);   

 cifa_p = cifa_head;

cout< yufa_zfc_disp(cifa_head->next);

cout<<"的递归分析过程如下："< cout< cout<<'\'<<"步骤\t"<<'\'<<"产生式"< advance();

 n = E();

 if (n == 0) 

 {

cout<<'\'< cout<  return (0);

 }

 else if (n == 1)

 {

cout<<'\'< cout<  return (1);

 }

}

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

yuyi *yuyi_add(yuyi *p)     //在四元式链表末添加一个结点

{

yuyi_end->next = p ;

 yuyi_end = p;

 return yuyi_head;

}

void yuyi_sys_disp()     //输出四元式链表

{ 

 yuyi *p;

p = yuyi_head->next;

 while(p!=NULL)

{ cout<<'('<<'\'<op<<','<<'\'<op1<<','<<'\'<op2<<','<<'\'<result<<'\'<<')'< p = p->next;

 }

cout<}

int F() // F -> (E) | 标识符 | 无符号整数 子函数

{

 int m;

if ((strcmp(cifa_p->word,"(") == 0 ) )

 {

cout<<'\'< (E)"<  advance();

  m =E();

  if (m==0) return (0);

if ((strcmp(cifa_p->word,")") == 0 ) )

  {

   advance();

   return (1);

  }

  else 

  {

cout<<"ERROR"<   return (0);

  }

 }

else if ( cifa_p->type == 1 || cifa_p->type == 2) //数字或是标识符

 {

cout<<'\'< 标识符|无符号整数"<  advance();

  return (1);

 }

 else return 0;

}

int S() // S -> *FS | /FS |ε 子函数

{

 int t,g;

if (strcmp(cifa_p->word,"*") == 0)

 {

cout<<'\'< *FS"<  advance();

  t = F();

  if (t== 0) return 0;

  g = S();

  if (g == 0) return 0;

  return(1);

 }

else if (strcmp(cifa_p->word,"/") == 0)

 {

cout<<'\'< /FS"<  advance();

  t = F();

  if (t== 0) return 0;

  g = S();

  if (g == 0) return 0;

  return(1);

 }

else if (strcmp(cifa_p->word,"+") == 0 ||(strcmp(cifa_p->word,"-") == 0)||(strcmp(cifa_p->word,"#") == 0)||(strcmp(cifa_p->word,")") == 0))

 {

cout<<'\'< ε"<  return(1);

 }

 return (0);

}

int T() // T -> FS 子函数

{

 int t,g;

cout<<'\'< FS"< t = F();

 if (t== 0) return 0;

 g = S();

 if (g == 0) return 0;

 return(1);

}

int G()      // G -〉+TG | -TG |ε子函数

{

 int t,g;

if (strcmp(cifa_p->word,"+") == 0)

 {

cout<<'\'< +TG"<  advance();

  t=T();

  if (t == 0) return(0);

  g=G();

  if ( g== 0) return (0);

     return (1);

 }

else if (strcmp(cifa_p->word,"-") == 0)

 {

cout<<'\'< -TG"<  advance();

  t=T();

  if (t == 0) return(0);

  g=G();

  if (g == 0) return (0);

  return(1);

 }

else if (strcmp(cifa_p->word,")") == 0 || strcmp(cifa_p->word,"#") == 0)

 {

cout<<'\'< ε"<  return(1);

 }

 return (0);

}

int E() // E -> [+|-]TG 子函数

{

 int t,g;

if ((strcmp(cifa_p->word,"+") == 0)|| (strcmp(cifa_p->word,"-") == 0)) advance();

cout<<'\'< [+|-]TG"< t = T();

 if (t == 0) return (0);

 g = G();

 if (g == 0) return (0);

 else return (1);

}

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

void advance()     //取词法分析产生列表中的结点作语法分析

{

cifa_p = cifa_p -> next;

}

int test(void)         //识别相关符号 

{

 char temp[3];

 int i=0;

 int type;

 switch (ch)

 {

 case ';' :    //识别 ';'

  {

   temp[i++] = ch;

   GetChar();

   if (ch ==' ' )  temp[i++] =' ';

   temp[i] = '\\0';

   type = 4;

   break;

  }

 case '+' :    //识别 '+'

  {

   temp[i++] = ch;

   GetChar();

   if (ch ==' ' )  temp[i++] =' '; 

   temp[i] = '\\0';

   type = 3;

   break;

  }

 case '-' :    //识别 '-'

  {

   temp[i++] = ch;

   GetChar();

   if (ch ==' ' )  temp[i++] =' '; 

   temp[i] = '\\0';

   type = 3;

   break;

  }

 case '*' :    //识别 '*'

  {

   temp[i++] = ch;

   GetChar();

   if (ch ==' ' ) 

    temp[i++] =' ';

   temp[i] = '\\0';

   type = 3;

   break;

  }

 case '/' :    //识别 '/'

  {

   temp[i++] = ch;

   GetChar();

   if (ch ==' ' ) 

    temp[i++] =' ';

   temp[i] = '\\0';

   type = 3;

   break;

  }

 case '(' :    //识别 '('

  {

   temp[i++] = ch;       

   GetChar();

   if (ch ==' ' ) 

    temp[i++] =' ';

   temp[i] = '\\0';

   type = 4;

   break;

  }

 case ')' :    // 识别')'

  {

   temp[i++] = ch;       

   GetChar();

   if (ch ==' ' ) 

    temp[i++] =' ';       

      temp[i] = '\\0';

   type = 4;

      break; 

  }

 default :

{ cout< cout<<"无法识别，出错！"<   GetChar();

   if (ch == ' ') notock();

   return (0);

  }

 }

 if (ch == ' ') notock();      // 空格跳过

 cifa *p;

 p = new cifa;

p -> next = NULL;

p -> type = type;

strcpy(p->word,temp);

 cifa_add(p); 

 return (1);

}      

int cifa_main()     //词法分析主函数

{

 int f;

 cifa_head = new cifa;

cifa_head -> type = -1;

cifa_head -> next = NULL;

 cifa_end = cifa_head;

cout<<"单词种类定义如下："< cout<<"标识符的种类编码 1 :"< cout<<"常数的种类编码 2 :"< cout<<"运算的种类编码 3 :+ ,- ,* ,/ "< cout<<"界限符的种类编码 4 : (,),;"< GetChar();

 notock();

cout<<"--------------------------------------------------------"< while ( nn < 100 && ch != '^')

 {

if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') )

    f=alph(); //字母串

else if (ch >= '0' && ch <= '9') f=number(); //数字串

      else f=test();//其他符号

  if (f == 0) return (0);

 } 

 cifa_disp(cifa_head);

cout< return (1);

}

int number(void)       //识别数字 

{

 int type=2;

    int i=0;

 char temp[10];

while('0'<= ch && ch <= '9')

    {

  temp[i] = ch;

  i++;

  GetChar();

    }

 temp[i]='\\0';

 if (ch == ' ') notock();

   else if (ch != '^' && ch != '+'  && ch != '-' && ch != ';' && ch != '*' && ch != '/' && ch != '('&& ch != ')')

   {

cout<    return (0);

   }

   if (ch == ' ') notock();  

 cifa *p;

 p = new cifa;

p -> next = NULL;

p -> type = type;

strcpy(p->word,temp);

 cifa_add(p);

 return (1);

}

int alph(void)                       //识别标识符   

{  

 int      i=0;

 char  temp[10];

 int   type = 1;

 temp[i] = ch;

 i++;

 GetChar();

while ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') ||

(ch >= '0' && ch <= '9'))

 {

  temp[i] = ch;

  i++;

  GetChar();

 }

 temp[i] = '\\0';

 if (ch == ' ') notock();

  else if (ch != '^' && ch != '+'  && ch != '-' && ch != ';' &&

 ch != '*' && ch != '/' && ch != '('&& ch != ')')

   {

cout<    return 0;

   }

 cifa *p;

 p = new cifa;

p -> next = NULL;

p -> type = type;

strcpy(p->word,temp);

 cifa_add(p);

 return (1);

}

cifa *cifa_add(cifa *p)    //在分析结果列表尾添加一个新接点

{

cifa_end -> next = p;

cifa_end = cifa_end -> next;

 return cifa_head;

}

void cifa_disp(cifa *cifa_head)   //输出词法分析结果

{

 cifa *p;

p = cifa_head -> next ;

 while ( p != NULL)

 {

cout<<'('<<'\'<type<<'\'<<','<<'\'<word<<'\'<<')'< p = p ->next;

 }

}

void GetChar()     //取字符

{

 ch = str[nn];

 nn++;

}

void notock()     //去掉空格

{

 if ( ch == ' ' )

  while ( ch == ' ' )

   GetChar();

}

//*********************************主函数************************************

void main()    //主函数

{  

 int len;

 int f=1;

cout< gets(str);

 len = strlen(str);

 str[len] = '^';

cout< system("pause");

cout< cout<<"***********************词法分析开始*****************"< f = cifa_main();

 if ( f == 0 ) return;

cout< system("pause");

cout< cout<<"***********************语法分析开始*****************"< f = yufa_main();

 if (f== 0) return;

cout< system("pause");

cout< cout<<"********************语义分析开始*********************"< yuyi_main();

cout< system("pause");

cout<}