Implement an Interpreter using Bison, Flex, and Automake
04 Sep 2013This is a small example on how to implement an interpreter using Flex, Bison (formerly known as Yacc), and the Autotools. The example is based on Ben Reichard’s course material.
Dependencies
First you need to install the C compiler, the lexer, and the LALR parser generator for this project. It also helps to install the readline wrapper utility.
sudo aptitude install build-essential bison flex rlwrapBuild system
You need to create the file Makefile.dist with the following content.
all:
aclocal
autoheader
libtoolize --force
automake -a --foreign
autoconf
configure:
./configureThen you create the file configure.ac with the following content.
AC_INIT(aclocal.m4)
AM_INIT_AUTOMAKE([calculator], [1.0.0])
AC_CONFIG_MACRO_DIR([m4])
AC_PROG_CC
AC_PROG_INSTALL
AC_PROG_LN_S
AC_PROG_YACC
AC_PROG_LEX
AM_PROG_LIBTOOL
AM_CONFIG_HEADER(config.h)
AC_CHECK_HEADERS([stdio.h])
AC_OUTPUT(Makefile)Finally you create the file Makefile.am with the following content.
SUFFIXES = .c .h .y .l
ACLOCAL_AMFLAGS = -I m4
AM_YFLAGS = -d
bin_PROGRAMS = calculator
calculator_SOURCES = calculator.c calc_bison.y calc_flex.l
calculator_LDFLAGS =
calculator_LDADD =
noinst_HEADERS = calculator.h
BUILT_SOURCES = calc_bison.h
EXTRA_DIST = Makefile.dist configure.ac
CLEANFILES = *~
MAINTAINERCLEANFILES = aclocal.m4 config.guess config.sub configure \
install-sh ltmain.sh Makefile.in missing mkinstalldirs stamp-h.in \
libtool config.cache config.h config.h.in acinclude.m4 depcomp \
ylwrap
maintainer-clean-local:
-rm -rf m4This completes the setup of the build system.
Implementation
First create the file calc_bison.y with the implementation of the parser.
%{
#include <stdio.h>
void yyerror(char *s) {
fprintf(stderr, "%s\n", s);
}
int sym[26];
%}
%union {
int number;
int var;
};
%type <number> expression
%token <var> VAR
%token <number> NUMBER
%%
start: expression '\n' { printf("%d\n\n", $1); } start
| /* NULL */
;
expression: NUMBER
| VAR { $$ = sym[$1]; }
| '-' expression { $$ = -$2; }
| expression '+' expression { $$ = $1 + $3; }
| expression '-' expression { $$ = $1 - $3; }
| expression '*' expression { $$ = $1 * $3; }
| '(' expression ')' { $$ = $2; }
| VAR '=' expression { sym[$1] = $3; $$ = $3; }
;Then create the file calc_flex.l with the implementation of the lexer (tokenizer).
%{
#include "calc_bison.h"
%}
%option noyywrap
%option always-interactive
%%
[0-9]+ { yylval.number = atoi(yytext); return NUMBER; }
[a-z] { yylval.var = *yytext - 'a'; return VAR; }
[-+()*\n=] { return *yytext; }
[ \t] ;
. yyerror("Unknown character");
%%Then create the header file calculator.h for the parser.
#ifndef CALCULATOR_H
#define CALCULATOR_H
int yyparse(void);
extern int sym[26];
#endifFinally create the file calculator.c with the main program.
#include "calculator.h"
int main(void)
{
int i;
for (i=0; i<26; i++) sym[i] = 0;
yyparse();
return 0;
}Compiling and running it
Above program is built using the following steps.
make -f Makefile.dist
./configure
makeYou can run the calculator as follows.
./calculatorAlternatively you can run the interpreter with rlwrap to get command line history.
rlwrap ./calculatorHere is a sample session using the calculator program.
1
1
1 + 2
3
a = 1 + 2
3
b = a * 3
9
(1 + 2) * 3
9
(x = b) + 1
10
x
9The code is also available on Github. You can get a copy using Git:
git clone https://github.com/wedesoft/calculator.gitEnjoy!
See also
