语法分析实验报告

一、    实验目的：

熟悉并设计一个表达式的语法分析器

二、实验内容：

1． 设计表达式的语法分析器算法

2． 编写代码并上机调试运行通过

要求： 输入-----表达式

       输出-----表达式语法是否正确

三、概要设计：

1、算术表达式文法

       E→E+T|T

       T→T*F|F

       F→(E)|i

2、 进行适当的文法变换

经消去直接左递归后变成：

E→TA

A→+TA|ε

T→*FB

B→*FB|ε

F→(E)|i

3、 选择LL(1)语法分析的方法

其中空白格均指“出错标志”。

4、数据结构设计：

typedef char SElemType;

typedef int Status;

typedef struct

{

       SElemType *base;

       SElemType *top;

       int stacksize;

}SqStack;

5、 根据原理给出相应的算法设计

       BEGIN

              首先把“#”然后把文法开始符号推进STACK栈；

              把第一个输入符号读进a；

              FLAG:=TURE;

              WHILE  FLAG  DO

                     BEGIN

                            把STACK栈顶符号上托出去并放在X中；

                            IF  X∈  THEN

                  IF  X=a  THEN 把下一输入符号读进a

                  ELSE ERROR

              ELSE  IF X=’#’ THEN

                  IF X=a THEN FLAG:=FLASE 

ELSE  ERROR

              ELSE IF M[A,a]={X→X1X2…XK}THEN

                  把XK,，…,X1一一推入STACK栈

              ELSE ERROR

           END  ERROR

       END OF WHILE

    STOP

   END

四、源程序：

#include<iostream>

#include<malloc.h>

using namespace std;

#define STACKSIZE      30

#define STACKINCREMENT 10

#define   OK           1

#define   error        0

#define   OVERFLOW     -1

typedef char SElemType;

typedef int Status;

typedef struct

{

       SElemType *base;

       SElemType *top;

       int stacksize;

}SqStack;

Status InitStack(SqStack &S)//栈的初始化

{

       S.base=(SElemType*)malloc(STACKSIZE*sizeof(SElemType));

       if(!S.base)

              exit(OVERFLOW);

       S.top=S.base;

       S.stacksize=STACKSIZE;

       return OK;

}

Status Push(SqStack &S, SElemType e)//入栈

{

       if(S.top-S.base>=S.stacksize)

       {

              S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT) * sizeof(SElemType));

              if(!S.base)

                     exit(OVERFLOW);

              S.top=S.base+S.stacksize;

              S.stacksize+=STACKINCREMENT;

       }

       (S.top)++;

       *(S.top)=e;

       return OK;

}

Status Pop(SqStack &S, SElemType *e)//出栈

{

       if(S.top==S.base)

              return error;

       *e=*(S.top);

       S.top--;

       return OK;

}

Status GrammerAnalysis(SqStack &S,char *ch, char c)//语法分析函数

{

       SElemType e='a';

       Push(S,'#');//压入“#”符号

       Push(S,'E');

       while((*(S.top)!='#')&&(c!='#'))

       {

              Pop(S,&e);

              if((e=='E')&&(((c>='0')&&(c<='9'))||(c=='(')))

              {

                     Push(S,'A');

                     Push(S,'T');

              }//endif

              else if((e=='T')&&(((c>='0')&&(c<='9'))||(c=='(')))

              {

                     Push(S,'B');

                     Push(S,'F');

              }

              else if((e=='F')&&(c>='0')&&(c<='9'))

              {

                     ch++;

                     c=*ch;

                     while((c>='0')&&(c<='9'))

                     {

                            ch++;

                            c=*ch;

                     }

              }

              else if((e=='F')&&(c=='('))

              {

                     Push(S,'E');

                     ch++;

                     c=*ch;

              }

              else if((e=='B')&&((c=='*')))

              {

                     Push(S,'B');

                     Push(S,'F');

                     ch++;

                     c=*ch;

              }

              else if((e=='B')&&((c=='+')||(c==')')))

              {

              }

              else if((e=='A')&&(c=='+'))

              {

                     Push(S,'A');

                     Push(S,'T');

                     ch++;

                     c=*ch;

              }

              else if((e=='A')&&(c==')'))

              {}

              else return error;

       }

       return OK;

}

int main()

{

       char str[50];

       char c;

       SqStack S;

       InitStack(S);

       printf("请输入表达式：\n");

       scanf("%s",str);

       c=*str;

       if(GrammerAnalysis(S,str,c))

              printf("语法分析通过，表达式正确\n");

       else

              printf("语法分析未通过，表达式不正确\n");

       return 0;

}

五、测试数据及运行结果：

 

第二篇：自顶向下的语法分析(实验报告一)

武汉轻工大学

编译原理实验报告

姓    名          朱春桃            

院 （系）       数学与计算机学院     

班    级         软件工程1203         

学    号         1205110605           

指导教师           李禹生             

              2014  年　11　月　10　日

一、实验目的

完成自顶向下语法分析算法的程序设计。

二、实验内容

设计、调试并测试自顶向下语法分析算法程序。

三、设计思路

根据课堂讲授的自顶向下语法分析方法，可以根据递归下降子程序方法设计语法分析程序，也可以根据LL（1）算法设计语法分析程序，针对文法：

G[E]

E→E+T | T

T→T*F | F

F→( E ) | i

（1）由于文法G[E]不满足LL（1）文法条件，需要进行必要的等价文法变换。变换后的等价文法为：

H[E]

E→TA

A→+TA | ε

T→FB

B→*FB | ε

F→( E ) | i

（2）等价文法H[E]不含左递归，可以证明文法H[E]满足LL（1）文法条件

（3）根据递归下降子程序方法设计语法分析程序

①递归程序清单

②调试过程说明

③测试语句设计

④测试结果列表

⑤测试结论分析

（4）根据LL（1）算法设计语法分析程序

①预测分析表

②预测分析程序清单

③调试过程说明

④测试语句设计

⑤测试结果列表

⑥测试结论分析

四、程序清单

/*

E->TA,

A->+TA|ε,

T->FB,

B->*FB|ε,

F->i|(E).

*/

#include<stdio.h>

void E(char str[80],int &i,int &error);

void A(char str[80],int &i,int &error);

void T(char str[80],int &i,int &error);

void B(char str[80],int &i,int &error);

void F(char str[80],int &i,int &error);

void main()

{

      int i=0,j=0,error=0;

      char str[80];

      printf("请输入字符串（'#'为结束字符）:");

      while ((str[j]=getchar())!='#')

            j++;

      str[j]='#';

      E(str,i,error);

      if(error)

            printf("error\n");

      else

            printf("right\n");

}

void E(char str[80],int &i,int &error)

{

      printf("E->TA\n");

      T(str,i,error);

      A(str,i,error);   

}

void A(char str[80],int &i,int &error)

{

      if(str[i]=='+')

      {

            printf("A->+TA|ε\n");

            i++;

            T(str,i,error);

            A(str,i,error);

      }

      else if (str[i]=='#'||str[i]==')'){}

      else

            error++;

}

void T(char str[80],int &i,int &error)

{

      printf("T->FB\n");

      F(str,i,error);

      B(str,i,error);

}

void B(char str[80],int &i,int &error)

{

      if (str[i]=='*')

      {

            printf("B->*FB|ε\n");

            i++;

            F(str,i,error);

            B(str,i,error);

      }

}

void F(char str[80],int &i,int &error)

{

      if (str[i]=='(')

      {

            printf("F->i|(E)\n");

            i++;

            E(str,i,error);

            if(str[i]==')')

            {   

                  i++;

            }

            else

                  error++;

      }

      else

      {

            if(str[i]=='i')

            {

                  printf("F->i|(E)\n");

                  i++;

            }

            else

                  error++;

      }

}

五、测试结果

六、实验总结

实验在老师提前给出的算法指导下，完成自顶向下语法分析的程序实际上是不困难的。但是老师的目的应该不在程序，而是让我们通过此次实验对课堂的理论知识有个深层次的理解。所以通过本次实验，我对自顶向下的语法分析过程有了更深的了解，结合课堂知识打下了学习其他语法分析方法的基础。