Download PROCESADORES DE LENGUAJES Curso 2003

PROCESADORES DE LENGUAJES
Curso 2003-2004
Un compilador/intérprete de juguete
Que sirve para ilustrar los bloques básicos y algunas prácticas
mínimas para el desarrollo de compiladores en los que el analiza dor
léxico y sintáctico se programan explícitamente en vez de genera rse
con herramientas
Tomado de:
Grune, Bahl, Jacobs y Langedoen, “Modern Compiler Design”
Sección 1.2
Código:
página web de la asignatura, materiales.
Procesadores de Lenguajes
Octubre 2003
Estructura funcional
Análisis
Léxico
Análisis
Sintáctico
Gestión del
Contexto
Procesadores de Lenguajes
Valentín Cardeñoso Payo
Generación
de código
Código
Intermedio
(AST)
Intérprete
de código
Octubre 2003
1
PROCESADORES DE LENGUAJES
Curso 2003-2004
El lenguaje
Expr -> Digito | ‘(‘ Expr Oper Expr ‘)’
Oper -> ‘+’ | ‘*’
Digito -> ‘0’ | ‘1’ | ... | ‘9’
Procesadores de Lenguajes
#include
#include
#include
“parser.h“
“backend.h"
“error.h”
Octubre 2003
/* tipo AST */
/* define Process() */
/* define Error() */
main.c
int main (void) {
AST_node *icode;
if (!Parse_program (&icode))
Error(“No top-level expression ”);
Process(icode);
return 0;
}
extern void Process(AST_node *);
backend.h
extern void Error(char *);
error.h
void Error(char *msg) {
fprintf(stderr, “ERROR:[%s]\n”, msg);
exit(1);
}
error.c
#include “parser .i”
#include “parserbody.i”
Procesadores de Lenguajes
Valentín Cardeñoso Payo
parser.c
Octubre 2003
2
PROCESADORES DE LENGUAJES
#include
#include
#include
Curso 2003-2004
"lex.h"
"error.h"
"parser.h"
/* for Error() */
/* for self check */
/* PRIVATE */
static Expression *new_expression(void) {
return (Expression *)malloc(sizeof (Expression));
}
static void free_expression(Expression *expr)
{free((void *)expr);}
static int Parse _operator(Operator *oper_p);
static int Parse _expression(Expression **expr_p);
parser.i
/* PUBLIC */
int Parse_program(AST_ node **icode _p) {
Expression *expr;
get_next_token();
/* start the lexical
analyzer */
if (Parse_expression(&expr)) {
if (Token.class != EoF) {
Error("Garbage after end of program");
}
*icode_p = expr;
return 1;
}
return 0;
}
Procesadores de Lenguajes
static int Parse_ expression (Expression ** expr_p) {
Expression *expr = *expr_p = new_ expression();
Octubre 2003
parserbody.i
/ * try to parse a digit : */
i f ( Token .class == DIGIT) {
expr- >type = 'D'; expr-> value = Token. repr '0';
get_next_ token ();
return 1;
}
/ * try to parse a parenthesized expression : */
i f ( Token .class == '(') {
expr- >type = 'P';
get_next_ token ();
if (! Parse_expression (&expr-> left )) {
Error("Missing expression ");
}
if (! Parse_operator (& expr- >oper )) {
Error("Missing operator");
}
if (! Parse_expression (&expr-> right)) {
Error("Missing expression ");
}
if (Token .class != ')') {
Error("Missing )");
}
get_next_ token ();
return 1;
}
static int Parse_ operator (Operator
*oper ) {
i f ( Token .class == '+') {
*oper = '+';
get _next _token(); return 1;
}
i f ( Token .class == '*') {
*oper = '*';
get _next _token(); return 1;
}
return 0;
}
/ * failed on both attempts * /
free_expression( expr) ; return 0;
}
Procesadores de Lenguajes
Valentín Cardeñoso Payo
Octubre 2003
3
PROCESADORES DE LENGUAJES
Curso 2003-2004
#include
"lex.h"
/* for self check */
/* PRIVATE */
static int Layout_char(int ch) {
switch (ch) {
case ' ': case '\t': case '\n': return 1;
default:
return 0;
}
}
/* PUBLIC */
Token_type Token ;
lex.c
void get_next_token(void) {
int ch ;
/* get a non-layout character: */
do {
ch = getchar();
if (ch < 0) {
Token.class = EoF; Token.repr = '#';
return;
}
} while (Layout_char(ch));
/* classify it: */
if ('0' <= ch && ch <= '9') {Token.class = DIGIT;}
else {Token.class = ch;}
Token.repr = ch;
}
Procesadores de Lenguajes
Octubre 2003
/* Define class constants */
/* Values 0-255 are reserved for ASCII characters */
#define
EoF
256
#define
DIGIT
257
lex.h
typedef struct {int class; char repr;} Token_type;
extern Token_type Token ;
extern void get_next_token (void );
parser.h
typedef int Operator;
typedef struct _expression {
char type;
int value ;
struct _expression *left, * right;
Operator oper;
} Expression;
Typedef Expression AST_node;
/*
/*
/*
/*
‘D’
for
for
for
o ‘P’ */
‘D’ */
‘P’ */
‘P’ */
/* Top node of AST */
Extern int Parse _program (AST_node **);
Procesadores de Lenguajes
Valentín Cardeñoso Payo
Octubre 2003
4
PROCESADORES DE LENGUAJES
#include
#include
“parser.h" /* for AST_node y Expression */
“backend.h” /* self check */
/* PRIVATE */
static void Code_gen_expression(Expression *expr) {
switch (expr->type) {
case ‘D':
printf(“PUSH %d\n”, expr->value);
break;
case ‘P':
Code_gen_expression(expr->left);
Code_gen_expression(expr->right);
switch (expr->oper) {
case ‘+’: printf(“ADD\n”); break;
case ‘*’: printf(“MUL\n”); break;
}
break;
}
}
/* PUBLIC */
void Process(AST_node *icode ) {
Code_gen_expression(icode);
printf(“PRINT\n”);
}
Procesadores de Lenguajes
#include
#include
“parser.h" /* for AST_node y Expression */
“backend.h” /* self check */
/* PRIVATE */
static void Interpret_expression(Expression *expr) {
switch (expr->type) {
case ‘D':
return(expr->value);
case ‘P': {
int e_l = Interpret_expression(expr->left);
int e_r = Interpret_expression(expr->right);
switch (expr->oper) {
case ‘+’: return e_l + e_r;
case ‘*’: return e_l * e_r;
} }
break;
}
}
/* PUBLIC */
void Process(AST_node *icode ) {
printf(“%d\n”, Interpret_expression (icode ));
}
Procesadores de Lenguajes
Valentín Cardeñoso Payo
Curso 2003-2004
genera.c
Octubre 2003
interpr.c
Octubre 2003
5