Syntax

NOT a LISP course in your FP course!

Expressions are of the form

(mult (add x 5) factor)
(bind ((x. 1) (y . 2) (z . 3)) (add x y z)) 
(defun append (x y) 
        (if (null x) y 
             (cons (head x) (append (tail x) y))))

Lexer

Lexer takes character data and presents a stream of tokens

Parser

Parser takes the token stream and creates a syntax tree

Basic Lexer

A state machine

String to character list

"abcde" -> [ 'a'; 'b'; 'c'; 'd'; 'e' ]

"abcde"
[ 'a' ] "bcde"
[ 'a'; 'b' ] "cde"
 ...
[ 'a'; 'b'; 'c'; 'd'; 'e' ] ""

let rec toList (i : string) = 
    if i.Length > 0 
      then ((i.Chars(0))::(toList (i.Substring(1))))
      else [];;

Digression – Set-up for exercises

We are, in this lecture, working from first principles throughout, rather than going to library code — the availability of mature facilities such as fslex/fsyacc or FParsec would reduce this example into just the incantations to initialise those.

This toList implementation is intended as a reminder of the technique used, without diverting into implementation detail. We can see that the repeated creation of temporary strings, for example, would be a potential performance issue in practice. Indeed, what one might write in practice would be more like

let toList s = (s :> char seq) |> Seq.toList;;

but objects and modules come later in the series.

Lexical classes

type lexical = BRA | KET | DOT | SYMATOM of char list | NUMATOM of int ;;

let stopcases = toList "().\n\t " ;;

Predicates

Test what we have found

let rec mem x l = 
  match l with
  | [] -> false
  | (y::ys) -> if x = y 
                 then true 
                 else mem x ys ;;

let stopcase x =  mem x stopcases ;;

let digits = toList "1234567890" ;;

let digit x = mem  x digits ;;

let alpha x = not(mem  x  (digits @ stopcases)) ;;

Character list to integer

let digitToint i = 
   match i with
   | '0' -> 0
   | '1' -> 1
   | '2' -> 2
   | '3' -> 3
   | '4' -> 4
   | '5' -> 5
   | '6' -> 6
   | '7' -> 7
   | '8' -> 8
   | '9' -> 9
   | _ -> 0 ;;

let mkint s =
 let rec mkint' s a =
   match s with 
   |[] -> a
   | (x::xs) ->  mkint' xs ((a*10) + (digitToint x))
 mkint' s 0;;

Component Lexers

let rec lexSym s l =
  match l with 
  |  [] -> (SYMATOM s, [])
  | (x::xs) -> if stopcase x 
               then (SYMATOM s, x::xs) 
               else lexSym (s@[x]) xs ;;

let rec lexNumOrSym s l =
 match l with
    |[]-> (NUMATOM(mkint s), []) 
    |(x::xs) -> 
        (if (stopcase x) then ( NUMATOM(mkint s), x::xs)
        else if (alpha x) then lexSym (s@[x]) xs
        else lexNumOrSym  (s@[x]) xs ) ;;

The Complete Lexer

Assembling the pieces

let rec lexer l = 
  match l with
  | []       -> []
  | '\n'::xs -> lexer xs
  | ' '::xs  -> lexer xs
  | '\t'::xs -> lexer xs
  | '('::xs  -> BRA::(lexer xs)
  | ')'::xs  -> KET::(lexer xs)
  | '.'::xs  -> DOT::(lexer xs)
  | x::xs    -> 
    let (l,r) = if alpha x 
                then (lexSym [x]  xs)
                else (lexNumOrSym [x] xs)
    l :: lexer r;;

Exercise 2.1

Write a lexer for .ica/.ini files (see also Exercise 2.3 below)

The Language

Define the grammar it obeys

• SEXPR = ATOM | BRA SEXPR DOT SEXPR KET | BRA SEXPR* KET
• ATOM = SYMBOL | NUMBER
• → SEXPR = SYMBOL | NUMBER | ( SEXPR . SEXPR ) | ( SEXPR* )

Our Approach

Translate the grammar directly into a program by

• Creating elementary parsers for bra, ket, dot, symbols, atoms etc.
• Combining by sequence '>>', alternation '||' and iteration 'ITERATE'

let parseAtom  s = ((parseSym >* ATOMACTION) ||  (parseNum >* ATOMACTION)) s ;;

let rec parseSEXPR s = 
  (parseAtom ||   
   (bra >> parseSEXPR >> dot >> parseSEXPR >> ket >* CONSPAIR) ||
   (bra >>  (ITERATE parseSEXPR) >* CONSLIST >> ket)
  ) s;;

Basic Parsers

type 'a Maybe = Return of 'a | Fail;;

let parseSym  s =
 match s with
 | Return((SYMATOM y)::ys, (_)) ->
       Return(ys,[SYMATOM y]) 
 | _ ->  Fail ;;

( [SYMATOM mult ; NUMATOM 1; NUMATOM 2; KET] , ANYTHING) →
  (  [NUMATOM 1; NUMATOM 2]; KET , [SYMATOM mult])

Basic Parsers, continued

let parseNum  s =
 match s with
 | Return((NUMATOM y)::ys, a) ->  Return(ys,[NUMATOM y]) 
 | (_) ->  Fail ;;

let parseConst x s =
  match s with 
  | Return(y::ys, a) -> if x = y then Return(ys, []) else Fail 
  | _ ->  Fail ;;

let bra x = parseConst BRA x;;

let ket x = parseConst KET x;;

let dot x = parseConst DOT x;;

Combining Parser Primitives — Alternation

"Either X or Y"

let OTHERWISE f g  x =
  let result = f x
  if result = Fail then (g x) else result ;;

let (||) = OTHERWISE;;

Combining Parser Primitives — Sequence

"After X then Y"

let THENDO  f g x =
  let u = f x
  match u with
  | Return(rest1, result1) 
               -> let v = g u
                  match v with
                  | Return(rest2, result2) -> 
                    Return(rest2, result1 @ result2)
                  | Fail-> Fail
  | Fail -> Fail ;;

let (>>) = THENDO;;

Combining Parser Primitives — Iteration

"As many X as are available"

let rec ITERATE f x = 
  let u = f x
  match u with 
  | Fail -> x
  | Return(rest2, result2) -> 
           match x with
           | Fail -> Fail
           | Return(rest1, result1) -> 
               ITERATE f (Return(rest2, result1 @ result2));;

Exercise 2.2

Write the operator OPT such that OPT A matches zero or one occurrence of the parser A

Write the parser PLUS such that PLUS A matches one or more occurrences of A

Transforms

This builds the syntax tree

The parsers only check the structure of the expression

We also want them to build an abstract structure corresponding to the string!

SEXPR = ATOM → ATOM-ACTION |
        BRA SEXPR DOT SEXPR KET → PAIR-ACTION |
        BRA SEXPR* KET → LIST-ACTION
ATOM = SYMBOL → SYMBOL-ACTION |
       NUMBER → NUMBER-ACTION

Transforms take a parse state and build a parse state of a different type

(unparsed input, parse items list) -> (unparsed input, LISP Tree list)

LISP trees are built from ATOM, NIL and CONS elements

Our Abstract Syntax Tree

type SEXPR = SYMBOL of char list | NUMBER of int | NIL | CONS of SEXPR * SEXPR ;;

Transforms continued

let TRANSFORM f h s =
  let u = f s
  match u with
  | Return(rest, result) 
               ->  Return(rest, h result)
  | Fail -> Fail ;;

let (>*) = TRANSFORM;;

Grammar with Actions : A refinement

The representation we seek is

SEXPR = ATOM |
        BRA SEXPR DOT SEXPR KET → CONSPAIR |
        BRA SEXPR* → CONSLIST KET
ATOM = SYMBOL → ATOM-ACTION |
       NUMBER → ATOM-ACTION

Actions : From grammar to code

let CONSPAIR [ x; y ] = [CONS(x,y)];;

let CONSLIST l =
 let rec conslist y =
   match y with
   | x::xs -> CONS(x, conslist xs)
   | [] -> NIL 
 [conslist l];;

let ATOMACTION v  =
  match v with
  | [SYMATOM u] ->  [SYMBOL u] 
  | [NUMATOM i] ->  [NUMBER i]
  | _ ->  [];;

The Complete Parser

Recapitulating

let parseAtom  s = ((parseSym >* ATOMACTION) ||  (parseNum >* ATOMACTION)) s ;;

let rec parseSEXPR s = 
  (parseAtom ||   
   (bra >> parseSEXPR >> dot >> parseSEXPR >> ket >* CONSPAIR) ||
   (bra >>  (ITERATE parseSEXPR) >* CONSLIST >> ket)
  ) s;;

Wrapping the Parser

Building a usable API

let parse str = 
  let r = parseSEXPR (Return (lexer (toList str), [])) 
  match r with 
  | Return(_ , result::_) -> result
  | Return(_, []) -> NIL
  | Fail -> NIL ;;

Test Case

parse "( ((ABC)) . (123. 456))";;

Result

val it : SEXPR =
  CONS
    (CONS (CONS (SYMBOL ['A'; 'B'; 'C'],NIL),NIL),CONS (NUMBER 123,NUMBER 456))

Exercise 2.3a

Define a grammar

File = Line*

Line = WHITESPACE | CMD | 'NL'

WHITESPACE = ('NL' | 'TAB' | 'SPACE' )

CMD = SectionHeader | BINDING | COMMENT

SectionHeader = '[' HeaderString ']'

BINDING = BindString '=' BindString

HeaderString = Any but ('[' | ']' | 'NL')

BindString = Quote | Any but ('='| 'NL' )

Quote = '"' (Anything but '"') '"'

COMMENT = ';' (Any but 'NL') 'NL'

Exercise 2.3b

Write a Lexer for the grammar

Write a Parser for it

Extend it, using the full INI file format definition.

What real-world performance implications are there in the use of this sort of parser? Re-implement one of the parsers to avoid the limitations of the strictly evaluated list datatype.

Wrapping up

• Q&A

• The collected code from the slides

つづく