Previous Next Contents

7   Examples

See the directory examples for examples of parsers constructed using ML-Yacc. Here is a small sample parser and lexer for an interactive calculator, from the directory examples/calc, along with code for creating a parsing function. The calculator reads one or more expressions from the standard input, evaluates the expressions, and prints their values. Expressions should be separated by semicolons, and may also be ended by using an end-of-file. This shows how to construct an interactive parser which reads a top-level declaration and processes the declaration before reading the next top-level declaration.

7.1   Sample Grammar


(* Sample interactive calculator for ML-Yacc *)

fun lookup "bogus" = 10000
  | lookup s = 0

%%

%eop EOF SEMI

(* %pos declares the type of positions for terminals.
   Each symbol has an associated left and right position. *)

%pos int

%left SUB PLUS
%left TIMES DIV
%right CARAT

%term ID of string | NUM of int | PLUS | TIMES | PRINT |
      SEMI | EOF | CARAT | DIV | SUB
%nonterm EXP of int | START of int option

%name Calc

%subst PRINT for ID
%prefer PLUS TIMES DIV SUB
%keyword PRINT SEMI

%noshift EOF
%value ID ("bogus")
%nodefault
%verbose
%%

(* the parser returns the value associated with the expression *)

  START : PRINT EXP (print EXP;
                     print "\n";
                     flush_out std_out; SOME EXP)
        | EXP (SOME EXP)
        | (NONE)
  EXP : NUM             (NUM)
      | ID              (lookup ID)
      | EXP PLUS EXP    (EXP1+EXP2)
      | EXP TIMES EXP   (EXP1*EXP2)
      | EXP DIV EXP     (EXP1 div EXP2)
      | EXP SUB EXP     (EXP1-EXP2)
      | EXP CARAT EXP   (let fun e (m,0) = 1
                                | e (m,l) = m*e(m,l-1)
                         in e (EXP1,EXP2)       
                         end)

7.2   Sample Lexer


structure Tokens = Tokens

type pos = int
type svalue = Tokens.svalue
type ('a,'b) token = ('a,'b) Tokens.token
type lexresult= (svalue,pos) token

val pos = ref 0
val eof = fn () => Tokens.EOF(!pos,!pos)
val error = fn (e,l : int,_) =>
              output(std_out,"line " ^ (makestring l) ^
                               ": " ^ e ^ "\n")
%%
%header (functor CalcLexFun(structure Tokens: Calc_TOKENS));
alpha=[A-Za-z];
digit=[0-9];
ws = [\ \t];
%%
\n       => (pos := (!pos) + 1; lex());
{ws}+    => (lex());
{digit}+ => (Tokens.NUM
                (revfold (fn (a,r) => ord(a)-ord("0")+10*r)
                         (explode yytext) 0,
                  !pos,!pos));
"+"      => (Tokens.PLUS(!pos,!pos));
"*"      => (Tokens.TIMES(!pos,!pos));
";"      => (Tokens.SEMI(!pos,!pos));
{alpha}+ => (if yytext="print"
                 then Tokens.PRINT(!pos,!pos)
                 else Tokens.ID(yytext,!pos,!pos)
            );
"-"      => (Tokens.SUB(!pos,!pos));
"^"      => (Tokens.CARAT(!pos,!pos));
"/"      => (Tokens.DIV(!pos,!pos));
"."      => (error ("ignoring bad character "^yytext,!pos,!pos);
             lex());

7.3   Top-level code

You must follow the instructions in Section 5 to create the parser and lexer functors and load them. After you have done this, you must then apply the functors to produce the CalcParser structure. The code for doing this is shown below. 
structure CalcLrVals =
  CalcLrValsFun(structure Token = LrParser.Token)

structure CalcLex =
  CalcLexFun(structure Tokens = CalcLrVals.Tokens);

structure CalcParser =
  Join(structure LrParser = LrParser
       structure ParserData = CalcLrVals.ParserData
       structure Lex = CalcLex)
Now we need a function which given a lexer invokes the parser. The function invoke does this.

fun invoke lexstream =
    let fun print_error (s,i:int,_) =
            TextIO.output(TextIO.stdOut,
                          "Error, line " ^ (Int.toString i) ^ ", " ^ s ^ "\n")
     in CalcParser.parse(0,lexstream,print_error,())
    end
Finally, we need a function which can read one or more expressions from the standard input. The function parse, shown below, does this. It runs the calculator on the standard input and terminates when an end-of-file is encountered.

fun parse () = 
    let val lexer = CalcParser.makeLexer
                      (fn _ => TextIO.inputLine TextIO.stdIn)
        val dummyEOF = CalcLrVals.Tokens.EOF(0,0)
        val dummySEMI = CalcLrVals.Tokens.SEMI(0,0)
        fun loop lexer =
            let val (result,lexer) = invoke lexer
                val (nextToken,lexer) = CalcParser.Stream.get lexer
             in case result
                  of SOME r =>
                      TextIO.output(TextIO.stdOut,
                             "result = " ^ (Int.toString r) ^ "\n")
                   | NONE => ();
                if CalcParser.sameToken(nextToken,dummyEOF) then ()
                else loop lexer
            end
     in loop lexer
    end
Previous Next Contents