Sunday, March 18, 2007

EOPL - 3.2 - Front-end for the first interpreter

The previous post showed the code for the interpreter, working on an abstract syntax representation of the interpreted programs. In section 3.2 a front-end is presented to permit working with a concrete syntax. The book uses SLLGEN, a tool developed by the PLT Scheme group, to generate lexers and parsers. I used fslex and fsyacc, the standard tools of F# for such purposes. Here's the lexical specification.

{
// eopl1_lex.fsl
//
// Lexical specification for the first interpreter
// in EOPL (Essentials of Programming Languages)

open System
open Eopl1_par
open Lexing

let record_newline (lexbuf : lexbuf) =
lexbuf.EndPos <- lexbuf.EndPos.AsNewLinePos()

}

// These are some regular expression definitions
let digit = ['0'-'9']
let id = ['a'-'z'] ['a'-'z' '0'-'9']*
let whitespace = [' ' '\t' ]
let newline = ('\n' | '\r' '\n')

rule token = parse
| whitespace { token lexbuf }
| '%' [^ '\n']* { token lexbuf }
| newline { record_newline lexbuf; token lexbuf }
| "+" { PLUS }
| "-" { MINUS }
| "*" { MULT }
| "(" { LPAREN }
| ")" { RPAREN }
| "," { COMMA }
| "add1" { INCR }
| "sub1" { DECR }
| id { ID(lexeme lexbuf) }
| ['-']?digit+ { LIT (Int32.Parse(lexeme lexbuf)) }
| eof { EOF }

And the grammar to use with fsyacc.

// eopl1_par.fsy
// Parser for the first interpreter
// in EOPL (Essentials of Programming Languages)

%{

open Eopl_3

%}

%start start

// terminal symbols
%token ID
%token LIT
%token INCR DECR LPAREN RPAREN PLUS MINUS MULT COMMA EOF

%type < Eopl_3.Program > start

%%

start: Prog { $1 }

Prog: Expr { Exp ($1) }

Expr: ID { VarExp($1) }
| LIT { LitExp($1) }
| Prim LPAREN ArgList RPAREN { PrimAppExp ($1, List.rev $3) }

Prim: PLUS { AddPrim }
| MINUS { SubtractPrim }
| MULT { MultPrim }
| INCR { IncrPrim }
| DECR { DecrPrim }

ArgList: Expr { [$1] }
| ArgList COMMA Expr { $3 :: $1 }

Module Eopl_3 contains all the code from the previous post, including a definition of the abstract syntax. Both specifications above were adapted from an example included in the distribution. Now we only need to run these specifications into fslex and fsyacc, and write a driver for the interpreter, a simple read-eval-print loop. Here it is.

// eopl1_main.fs
//
// Driver for the first interpreter in EOPL
// (Essentials of Programming Languages)

#light

open Eopl_3
open Eopl1_par

open Lexing

let parse str =
let lexbuf = Lexing.from_string str
let prog =
try
Some (Eopl1_par.start Eopl1_lex.token lexbuf)
with e ->
let pos = lexbuf.EndPos
printf "error near line %d, character %d\n%s\n"
pos.pos_cnum
(pos.pos_cnum - pos.pos_bol) (e.ToString());
None
prog

let rec read_eval_print prompt =
let _ = print_string prompt
let line = read_line ()
match line with
"#quit" -> ()
| _ -> match parse line with
None -> read_eval_print prompt
| Some p -> let v = Eopl_3.eval_program p in
(print_endline (string_of_int v);
read_eval_print prompt)

let main() =
read_eval_print "--> "

do main()

No comments: