Implement an Interpreter using Bison, Flex, and Automake

04 Sep 2013

This 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 rlwrap

Build system

You need to create the file Makefile.dist with the following content.

all:
	aclocal
	autoheader
	libtoolize --force
	automake -a --foreign
	autoconf

configure:
	./configure

Then 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 m4

This 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];

#endif

Finally 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
make

You can run the calculator as follows.

./calculator

Alternatively you can run the interpreter with rlwrap to get command line history.

rlwrap ./calculator

Here 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
9

The code is also available on Github. You can get a copy using Git:

git clone https://github.com/wedesoft/calculator.git

Enjoy!

See also

Jan Wedekind

Implement an Interpreter using Bison, Flex, and Automake

Dependencies

Build system

Implementation

Compiling and running it