컴파일러 실천 5 의 구조 는 가감 곱셈 을 지원하는 창고 컴퓨터 이다

나의 첫 블로그: 컴파일러 실천 1의 덧셈 창고 컴퓨터
최근 간단한 비슨에 추상적인 문법 트리를 조금 배워서 MOOC가 남긴 숙제를 해봤는데, 요구에 따라 코드를 몇 군데 고치고 추가하면서 많은 것을 배운 것 같다.그러나 난이도를 줄이고 중심을 두드러지게 하기 위해 저는 메모리를 관리하지 않았습니다. 메모리 유출이 좀 심각해서 코드는 참고만 합니다.
기능은 한 줄 또는 여러 줄 산술 표현식을 입력하고 표현식에 대해 추상적 문법 트리를 구축한 다음에 출력(주로 추상적 표현식이 정확하게 만들어졌는지 보기 위해서), 컴파일링, 창고 컴퓨터에 대한 시뮬레이션을 완성하는 것이다. 원래의 코드는 감법, 제법, 괄호 표현식을 지원하지 않고 한 줄의 컴파일링만 완성할 수 있다. 나는 그것을 임의의 줄로 확대했다.
다음은 추상 구문 트리에 대한 정의입니다.

/*ast.h*/
#ifndef AST_H
#define AST_H

enum Exp_Kind_t{
  EXP_INT,
  EXP_ADD,
  EXP_TIMES,
  EXP_DIV,
  EXP_SUB};

/*
   E -> n
      | E + E
      | E * E
*/
typedef struct Exp_t *Exp_t;
struct Exp_t{
  enum Exp_Kind_t kind;
};
// all operations on "Exp"
void Exp_print (Exp_t exp);
int Exp_numNodes (Exp_t exp);

typedef struct Exp_Int *Exp_Int;
struct Exp_Int{
  enum Exp_Kind_t kind;
  int n;
};
Exp_t Exp_Int_new (int n);

typedef struct Exp_Add *Exp_Add;
struct Exp_Add{
  enum Exp_Kind_t kind;
  Exp_t left;
  Exp_t right;
};
Exp_t Exp_Add_new (Exp_t left, Exp_t right);

typedef struct Exp_Times *Exp_Times;
struct Exp_Times{
  enum Exp_Kind_t kind;
  Exp_t left;
  Exp_t right;
};
Exp_t Exp_Times_new (Exp_t left, Exp_t right);

typedef struct Exp_Div *Exp_Div;
struct Exp_Div{
  enum Exp_Kind_t kind;
  Exp_t left;
  Exp_t right;
};
Exp_t Exp_Div_new (Exp_t left, Exp_t right);

typedef struct Exp_Sub *Exp_Sub;
struct Exp_Sub{
  enum Exp_Kind_t kind;
  Exp_t left;
  Exp_t right;
};
Exp_t Exp_Sub_new (Exp_t left, Exp_t right);


#endif

다음은ast.h의 실현:

/*ast.c*/
#include <stdio.h>
#include <stdlib.h>
#include "ast.h"

// "constructors"
Exp_t Exp_Int_new (int n)
{
  Exp_Int p = malloc (sizeof (*p));
  p->kind = EXP_INT;
  p->n = n;
  return (Exp_t)p;
}

Exp_t Exp_Add_new (Exp_t left, Exp_t right)
{
  Exp_Add p = malloc (sizeof (*p));
  p->kind = EXP_ADD;
  p->left = left;
  p->right = right;
  return (Exp_t)p;
}

Exp_t Exp_Times_new (Exp_t left, Exp_t right)
{
  Exp_Add p = malloc (sizeof (*p));
  p->kind = EXP_TIMES;
  p->left = left;
  p->right = right;
  return (Exp_t)p;
}

Exp_t Exp_Div_new (Exp_t left, Exp_t right)
{
  Exp_Div p = malloc (sizeof (*p));
  p->kind = EXP_DIV;
  p->left = left;
  p->right = right;
  return (Exp_t)p;
}

Exp_t Exp_Sub_new (Exp_t left, Exp_t right)
{
  Exp_Sub p = malloc (sizeof (*p));
  p->kind = EXP_SUB;
  p->left = left;
  p->right = right;
  return (Exp_t)p;
}

// all operations on "Exp"
void Exp_print (Exp_t exp)
{
  switch (exp->kind){
  case EXP_INT:{
    Exp_Int p = (Exp_Int)exp;
    printf ("%d", p->n);
    return;
  }
  case EXP_ADD:{
    Exp_Add p = (Exp_Add)exp;
    printf ("(");
    Exp_print (p->left);
    printf (") + (");
    Exp_print (p->right);
    printf (")");
    return;
  }
  case EXP_TIMES:{
    Exp_Times p = (Exp_Times)exp;
    printf ("(");
    Exp_print (p->left);
    printf (") * (");
    Exp_print (p->right);
    printf (")");
    return;
  }
  case EXP_DIV:{
    Exp_Div p = (Exp_Div)exp;
    printf ("(");
    Exp_print (p->left);
    printf (") / (");
    Exp_print (p->right);
    printf (")");
    return;
  }
  case EXP_SUB:{
    Exp_Sub p = (Exp_Sub)exp;
    printf ("(");
    Exp_print (p->left);
    printf (") - (");
    Exp_print (p->right);
    printf (")");
    return;
  }
  default:
    return;
  }
}

다음은 스택의 아날로그이고 다음은 스택의 데이터 구조입니다.

/*stack.h*/
#ifndef _STACK_H_
#define _STACK_H_
#include "ast.h"
enum Stack_Kind_t {STACK_ADD, STACK_SUB,STACK_TIMES,STACK_DIV,STACK_PUSH};
struct Stack_t
{
  enum Stack_Kind_t kind;
};

struct Stack_Add
{
  enum Stack_Kind_t kind;
};
struct Stack_Sub
{
  enum Stack_Kind_t kind;
};
struct Stack_Times
{
  enum Stack_Kind_t kind;
};
struct Stack_Div
{
  enum Stack_Kind_t kind;
};
struct Stack_Push
{
  enum Stack_Kind_t kind;
  int i;
};


struct Stack_t *Stack_Add_new ();
struct Stack_t *Stack_Times_new ();
struct Stack_t *Stack_Div_new ();
struct Stack_t *Stack_Sub_new ();
struct Stack_t *Stack_Push_new (int i);

#endif

다음은 실현이다.

/*stack.c*/
#include "stack.h"
#include <stdlib.h>
// "constructors"
struct Stack_t *Stack_Add_new ()
{
  struct Stack_Add *p = (struct Stack_Add *)malloc (sizeof(struct Stack_Add));
  p->kind = STACK_ADD;
  return (struct Stack_t *)p;
}

struct Stack_t *Stack_Times_new ()
{
  struct Stack_Times *p = (struct Stack_Times *)malloc (sizeof(struct Stack_Times));
  p->kind = STACK_TIMES;
  return (struct Stack_t *)p;
}
struct Stack_t *Stack_Div_new ()
{
  struct Stack_Div *p = (struct Stack_Div *)malloc (sizeof(struct Stack_Div));
  p->kind = STACK_DIV;
  return (struct Stack_t *)p;
}

struct Stack_t *Stack_Sub_new ()
{
  struct Stack_Sub *p = (struct Stack_Sub *)malloc (sizeof(struct Stack_Sub));
  p->kind = STACK_SUB;
  return (struct Stack_t *)p;
}

struct Stack_t *Stack_Push_new (int i)
{
  struct Stack_Push *p = (struct Stack_Push *)malloc (sizeof(struct Stack_Push));
  p->kind = STACK_PUSH;
  p->i = i;
  return (struct Stack_t *)p;
}

다음은 창고 컴퓨터의 모든 명령을 저장하고 컴파일하고 출력하는 것이다.h 파일,:

/*list.h*/
#ifndef _LIST_H_
#define _LIST_H_
#include "stack.h"
#include "ast.h"
struct List_t
{
  struct Stack_t *instr;
  struct List_t *next;
};

struct List_t *List_new (struct Stack_t *instr, struct List_t *next);
void List_reverse_print (struct List_t *list);
void emit (struct Stack_t *instr);
void compile (struct Exp_t *exp) ;

#endif

다음은 실현이다.

/*list.c*/
#include <stdio.h>
#include <stdlib.h>
#include "list.h"

/// instruction list

struct List_t *List_new (struct Stack_t *instr, struct List_t *next)
{
  struct List_t *p = (struct List_t *)malloc (sizeof (struct List_t));
  p->instr = instr;
  p->next = next;
  return p;
}

// "printer"
void List_reverse_print (struct List_t *list)
{
	if(list == NULL)
		return ;
	List_reverse_print(list->next) ;
	switch (list->instr->kind)
	{
		case STACK_PUSH:printf("PUSH %d
",((struct Stack_Push *)(list->instr))->i) ;break ;
		case STACK_ADD:puts("ADD") ;break ;
		case STACK_SUB:puts("Sub") ; break ;
		case STACK_TIMES:puts("Mul") ;break ;
		case STACK_DIV:puts("div") ; break ;
		default : break ;
	}
}


//////////////////////////////////////////////////
// a compiler from Sum to Stack
struct List_t *all = 0;
void emit (struct Stack_t *instr)
{
  all = List_new (instr, all);
}

void compile (struct Exp_t *exp)
{
  switch (exp->kind){
  case EXP_INT:{
    struct Exp_Int *p = (struct Exp_Int *)exp;
    emit (Stack_Push_new (p->n));
    break;
  }
  case EXP_ADD:{

	struct Exp_Add * t = (struct Exp_Add *)exp ;
	compile(t->left) ;
	compile(t->right) ;
	emit(Stack_Add_new()) ;
    break;
  }
  case EXP_TIMES :{
  	struct Exp_Times * t = (struct Exp_Times *)exp ;
	compile(t->left) ;
	compile(t->right) ;
	emit(Stack_Times_new()) ;
	break;
  }
  case EXP_SUB :{
  	struct Exp_Sub * t = (struct Exp_Sub *)exp ;
	compile(t->left) ;
	compile(t->right) ;
	emit(Stack_Sub_new()) ;
	break;
  }
  case EXP_DIV :{
  	struct Exp_Div * t = (struct Exp_Div *)exp ;
	compile(t->left) ;
	compile(t->right) ;
	emit(Stack_Div_new()) ;
	break;
  }
  default:
    break;
  }
}

다음은bison을 이용하여 추상 문법 트리exp.y를 생성하는데 추상 문법 트리를 단독으로 수동으로 구성하는 것은 너무 복잡하다.

%{
#include <stdio.h>
#include "list.h"
#include "stack.h"
#include "ast.h"

  int yylex(); // this function will be called in the parser
  void yyerror(char *);
  extern struct List_t *all;

  %}

%union{
  Exp_t exp;
 }

%type <exp> digit exp program


%left '+' '-'
%left '*' '/'

%start program

%%

program: program exp '
' {Exp_t tree = $2;
  Exp_print (tree);
  puts("
START COMPILE...") ;
  compile(tree) ;
  List_reverse_print (all);
  all = 0 ;
  puts("
END COMPILE...") ;}
| program exp {Exp_t tree = $2;
  Exp_print (tree);
  puts("
START COMPILE...") ;
  compile(tree) ;
  List_reverse_print (all);
  all = 0 ;
  puts("
END COMPILE...") ;}
| /*empty*/
;

exp: digit     {$$ = $1;}
| exp '+' exp  {$$ = Exp_Add_new ($1, $3);}
| exp '*' exp  {$$ = Exp_Times_new ($1, $3);}
| exp '/' exp  {$$ = Exp_Div_new ($1, $3);}
| exp '-' exp  {$$ = Exp_Sub_new ($1, $3);}
| '(' exp ')'  {$$ = $2;}
;

digit: '0'  {$$ = Exp_Int_new (0);}
| '1'       {$$ = Exp_Int_new (1);}
| '2'       {$$ = Exp_Int_new (2);}
| '3'       {$$ = Exp_Int_new (3);}
| '4'       {$$ = Exp_Int_new (4);}
| '5'       {$$ = Exp_Int_new (5);}
| '6'       {$$ = Exp_Int_new (6);}
| '7'       {$$ = Exp_Int_new (7);}
| '8'       {$$ = Exp_Int_new (8);}
| '9'       {$$ = Exp_Int_new (9);}
;

%%

int yylex ()
{
  int c = getchar();
  return c;
}

// bison needs this function to report
// error message
void yyerror(char *err)
{
  fprintf (stderr, "%s
", err);
  return;
}

위의 모든 파일을 폴더에 넣고 bison exp.y를 실행합니다
exp.tab이 생성됩니다.c 파일
그런 다음 gcc main을 실행합니다.c ast.c stack.c list.c exp.tab.c
마지막으로 a.exe참고: 테스트.txt는 테스트 파일입니다. 안에 저장된 것은 산술 표현식입니다.
그대와 함께 격려하다