The token type is as follows:

type token $=$ Tok$\_$Int of int $|$ Tok$\_$LParen $|$ Tok$\_$RParen $|$

Tok$\_$Mult $|$ Tok$\_$Plus $|$ Tok$\_$EOF

Lookahead Function

This returns the head of the passed$-$in token list, or throws a failure if the list was empty.

let lookahead toks $=$ match toks with

h::t $->$ h

$|\_->$ raise $($Failure$("$Empty input to lookahead"$))$

string$\_$of$\_$token Helpers

These convert tokens into strings and are used for debugging. You do not need to understand them deeply, but the code is here if you want it$.$

let string$\_$of$\_$token tok $=$ match tok with

$|$ Tok$\_$Int$($i$)->$ string$\_$of$\_$int i

$|$ Tok$\_$Mult $->"*"$

$|$ Tok$\_$Plus $->"+"$

$|$ Tok$\_$LParen $->"("$

$|$ Tok$\_$RParen $->")"$

$|$ Tok$\_$EOF $->""$

let rec string$\_$of$\_$list conv lst $=$

match lst with

$|[]->""$

$|$ h::$[]->$ conv h

$|$ h::t $->($conv h$)^""^($string$\_$of$\_$list conv t$)$

match$\_$token Function

This returns the tail of the passed$-$in token list if the passed$-$in token matches the head of the token list. If it does not match, or an empty list was passed in$,$ a failure is thrown.

let match$\_$token $($toks : token list$)($tok : token$)$ : token list $=$

match toks with

$|[]->$ raise $($Failure$($string$\_$of$\_$token tok$))$

$|$ h::t when h $=$ tok $->$ t

$|$ h::$\_->$ raise $($Failure$($

Printf.sprintf "Expected $\%$s from input $\%$s$,$ got $\%$s$"$

$($string$\_$of$\_$token tok$)$

$($string$\_$of$\_$list string$\_$of$\_$token toks$)$

$($string$\_$of$\_$token h$)$

$))$

Consider the following CFG and AST type:

S $->$ T $*$ S $|$ T $+$ S $|$ T

T $->$ n $|($S$)$

$(*$ n is any int$*)$

type ast $=$ Num of int $|$ Paren of ast $|$ Mult of ast $*$ ast $|$

Add of ast $*$ ast

Which of the following code snippets is correct when parsing non$-$terminal S$?$

Note: This returns the rest of the tokens, and then the tree. That is$,$ the type of these functions is token list $->($token list $*$ ast$).$

See that Tok$\_$EOF exists. Like in the discussion example, all valid token lists passed to the parser will end with Tok$\_$EOF. Since both examples have no explicit handling of this, it should remain in the passed back list. parse$\_$S $[$Tok$\_$Int $5$; Tok$\_$EOF$]$ should return $([$Tok$\_$EOF$],$ Num $5)$ where the first thing in the tuple represents the remaining part of the list after successful parsing and the second thing in the tuple is the AST created by the parser.

A correctly functioning parser will never leave anything in the remaining token list except Tok$\_$EOF.

NOTE: Can be neither or both

A$)$

let rec parse$\_$S toks $=$

let $($token$\_$lst$\_1,$ expression$1)=$ parse$\_$T toks in

match lookahead token$\_$lst$\_1$ with

$|$ Tok$\_$Plus $->$ let token$\_$lst$\_2=$ match$\_$token token$\_$lst$\_1$ Tok$\_$Plus in

let $($token$\_$lst$\_3,$ expression$2)=$ parse$\_$S token$\_$lst$\_2$ in

$($token$\_$lst$\_2,$ Add$($expression$1,$ expression$2))$

$|$ Tok$\_$Mult $->$ let token$\_$lst$\_2=$ match$\_$token token$\_$lst$\_1$ Tok$\_$Mult in

let $($token$\_$lst$\_3,$ expression$2)=$ parse$\_$S token$\_$lst$\_1$ in

$($token$\_$lst$\_3,$ Mult$($expression$1,$ expression$2))$

$|\_->($token$\_$lst$\_1,$ expression$1)$

and parse$\_$T toks $=$

match lookahead toks with

$|$ Tok$\_$Int$($n$)->$ let token$\_$lst $=$ match$\_$token toks $($Tok$\_$Int n$)$ in

$($token$\_$lst$,$ Num n$)$

$|$ Tok$\_$LParen $->$ let token$\_$lst$\_1=$ match$\_$token toks Tok$\_$LParen in

let $($token$\_$lst$\_2,$ expression$)=$ parse$\_$S token$\_$lst$\_1$ in

let final$\_$token$\_$lst $=$ match$\_$token token$\_$lst$\_1$ Tok$\_$RParen in

$($final$\_$token$\_$lst$,$ Paren expression$)$

$|\_->$ failwith "Unexpected token in parse$\_$T$"$

B$)$

let rec parse$\_$S toks $=$

let $($toks$1,$ lhs$)=$ parse$\_$T toks in

match lookahead toks$1$ with

$|$ Tok$\_$Plus $->$

let toks$2=$ match$\_$token toks$1$ Tok$\_$Plus in

let $($toks$3,$ rhs$)=$ parse$\_$S toks$2$ in

$($toks$3,$ Add$($lhs$,$ rhs$))$

$|$ Tok$\_$Mult $->$

let toks$2=$ match$\_$token toks$1$ Tok$\_$Mult in

let $($toks$3,$ rhs$)=$ parse$\_$S toks$2$ in

$($toks$3,$ Mult$($lhs$,$ rhs$))$

$|\_->($toks$1,$ lhs$)$

and parse$\_$T toks $=$ match lookahead toks with

$|$ Tok$\_$Int$($n$)->$

let toks$1=$ match$\_$token toks $($Tok$\_$Int n$)$ in

$($toks$1,$ Num n$)$

$|$ Tok$\_$LParen $->$

let toks$1=$ match$\_$token toks Tok$\_$LParen in

let $($toks$2,$ expr$)=$ parse$\_$S toks$1$ in

$($toks$2,$ Paren expr$)$

$|\_->$ failwith "Expected a number or parentheses"