|< << >> >|

Implement an Interpreter using Bison, Flex, and Automake (2013/09/04)

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.

Build system

First you need to create the file Makefile.dist with the folowing 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

blog comments powered by Disqus

Latest News

2014/11/13

Graph coloring with Scheme and Graphviz
More...

2014/03/02

Why I like Object Oriented Programming using GNU Guile and GOOPS
More...

2013/09/04

Creating a calculator with Bison, Flex, and Automake
More...

2012/11/07

The choice of programming language plays a fundamental role in the implementation of machine vision systems ...
More...

2012/08/02

Building a dynamically linked C program for Android
More...

2012/07/21

Running the Racket programming language on an Android phone
More...

2012/06/10

Comparison of the Clojure programming language with Scheme/LISP
More...

2011/10/20

Can we attract good and bad things with our mind?
More...

...