$//$ Token Type

type Token $=$

$|$ ID of string

$|$ ASSIGN

$|$ SEMICOLON

$|$ EOF

$|$ READ

$|$ WRITE

$|$ IF

$|$ THEN

$|$ ELSE

$|$ ENDIF

$|$ COMMA

$|$ WHILE

$|$ DO

$|$ UNTIL

$|$ LPAREN

$|$ RPAREN

$|$ LT

$|$ GT

$|$ EQ

$|$ PLUS

$|$ MINUS

$|$ TIMES

$|$ DIV

$//$ Lexical analyzer function

let lexer $($input: string$)$ : Token list $=$

$//$ Split input string into tokens

input.Split$([|\text{'}\text{'}$; $\text{'}\backslash$t$\text{'}|],$ System.StringSplitOptions.RemoveEmptyEntries$)$

$|>$ Array.map $($fun token $->$

match token with

$|"$:$"->$ ASSIGN

$|"$;$"->$ SEMICOLON

$|$ "read" $->$ READ

$|$ "write" $->$ WRITE

$|"$if$"->$ IF

$|$ "then" $->$ THEN

$|$ "else" $->$ ELSE

$|$ "endif" $->$ ENDIF

$|","->$ COMMA

$|$ "while" $->$ WHILE

$|"$do$"->$ DO

$|$ "until" $->$ UNTIL

$|"("->$ LPAREN

$|")"->$ RPAREN

$|">"->$ GT

$|"<"->$ LT

$|"=="->$ EQ

$|"+"->$ PLUS

$|"-"->$ MINUS

$|"*"->$ TIMES

$|"/"->$ DIV

$|\_$ as s $->$ ID s

$)$

$|>$ Array.toList

let rec parse $($input: string$)$ : string $=$

let tokens $=$ lexer input

match tokens with

$|[]->""$

$|\_->$ let stmts$,$ remainingTokens $=$ stmt$\_$list tokens

match stmts with

$|[]->$ if List.length remainingTokens $>0$ then

sprintf "Unexpected token: $\%$A$"$ remainingTokens.$[0]$

else

$""$

$|\_->""$

and stmt$\_$list $($tokens: Token list$)$ : Token list $*$ Token list $=$

match tokens with

$|[]->[],[]//$ Empty statement list

$|\_->$ let stmt$1,$ remainingTokens$1=$ stmt tokens

match stmt$1$ with

$|[]->[],[]//$ No statement parsed

$|\_->$ let stmts$2,$ remainingTokens$2=$ stmt$\_$list remainingTokens$1$

stmt$1$ @ stmts$2,$ remainingTokens$2$

and stmt $($tokens: Token list$)$ : Token list $*$ Token list $=$

match tokens with

$|($ID $\_)$ :: tl $->$ id$\_$tail $($ID $""$ :: tl$)//$ Begin with an identifier

$|$ READ :: tl $->$ read$\_$stmt tl

$|$ WRITE :: tl $->$ write$\_$stmt tl

$|$ IF :: tl $->$ if$\_$stmt tl

$|$ DO :: tl $->$ do$\_$stmt tl

$|$ WHILE :: tl $->$ while$\_$stmt tl

$|\_->[],$ tokens

and id$\_$tail $($tokens: Token list$)$ : Token list $*$ Token list $=$

match tokens with

$|($ID $\_)$ :: ASSIGN :: $\_->$ assign$\_$stmt tokens

$|($ID $\_)$ :: LPAREN :: $\_->$ fun$\_$call tokens

$|\_->[],$ tokens

and assign$\_$stmt $($tokens: Token list$)$ : Token list $*$ Token list $=$

match tokens with

$|($ID $\_)$ :: ASSIGN :: $\_->$ let exprTokens, remainingTokens $=$ expr $($List$.$tail $($List$.$tail tokens$))$ in

match exprTokens with

$|$ SEMICOLON :: rest $->[$ASSIGN$]$ @ exprTokens @ $[$SEMICOLON$],$ rest

$|\_->[],$ tokens

$|\_->[],$ tokens

and expr $($tokens: Token list$)$ : Token list $*$ Token list $=$

match tokens with

$|($ID $\_)$ :: tl $->$ List.splitAt $3$ tokens $//$ For simplicity, consider an expression as ID :$=$ ID

$|$ LPAREN :: tl $->$ let subExpr, remainingTokens $=$ expr $($List$.$tail tokens$)$ in

match remainingTokens with

$|$ RPAREN :: rest $->$ LPAREN :: subExpr @ $[$RPAREN$],$ rest

$|\_->[],$ tokens

$|\_->[],$ tokens

and fun$\_$call $($tokens: Token list$)$ : Token list $*$ Token list $=$

match tokens with

$|($ID $\_)$ :: LPAREN :: tl $->$ let paramList, remainingTokens $=$ param$\_$list $($List$.$tail $($List$.$tail tokens$))$ in

match remainingTokens with

$|$ RPAREN :: rest $->[$LPAREN$]$ @ paramList @ $[$RPAREN$],$ rest

$|\_->[],$ tokens

$|\_->[],$ tokens

and param$\_$list $($tokens: Token list$)$ : Token list $*$ Token list $=$

match tokens with

$|[]->[],[]//$ Empty parameter list

$|\_->$ let exprTokens, remainingTokens $=$ expr tokens in

match remainingTokens with

$|$ COMMA :: rest $->$ exprTokens @ $[$COMMA$],$ rest $//$ More parameters

$|\_->$ exprTokens, remainingTokens $//$ Last parameter

and while$\_$stmt $($tokens: Token list$)$ : Token list $*$ Token list $=$

match tokens with

$|$ WHILE :: tl $->$ let condTokens, remainingTokens $=$ cond $($List$.$tail tokens$)$ in

match remainingTokens with

$|$ DO :: rest $->$ WHILE :: condTokens @ $[$DO$],$ rest

$|\_->[],$ tokens

$|\_->[],$ tokens

and do$\_$stmt $($tokens: Token list$)$ : Token list $*$ Token list $=$

match tokens with

$|$ DO :: tl $->$ let stmtList, remainingTokens $=$ stmt$\_$list $($List$.$tail tokens$)$ in

match remainingTokens with

$|$ UNTIL :: tail $->$ DO :: stmtList @ $[$UNTIL$],$ tail

$|\_->[],$ tokens

$|\_->[],$ tokens

and if$\_$stmt $($tokens: Token list$)$ : Token list $*$ Token list $=$

match tokens with

$|$ IF :: tl $->$ let c