FUNCTIONAL PROGRAMMING

SIMPLE SENTENCE VALIDATOR IN F# $($AS AN F# SCRIPT $/.$FSX FILE$).$

OVERVIEW

This Program is similar to the Syntax Analyzer developed in "Program $1"$ but uses F# instead of Java. To keep the

code short and simple, it does not generate output for a parse tree; it only functions as a syntax checker for a given

input program $($input string$)$ and outputs whether the input is syntactically correct or incorrect based on the

grammar.

You should prompt the user for an input string as follows:

Enter A Program: The user enters the Program here $($all on one line$)$

The input is entirely space$-$delimited.

This allows the input to be "Tokenized" into a simple List by splitting on spaces only.

While virtually every language has a built$-$in $($standard library$)$ function for this, the conversion of

the input into a list is shown in the sample provided.

The output is an indicator of whether the input sentence is syntactically valid.

See next page for an example.

Programming Guidelines

Use recursive list processing where applicable:

E$.$g$.,$ Use Lists $($not arrays$),$ List Mapping, List Pattern Matching, etc.

AVOID THE USE OF MUTABLE DATA:

E$.$g$.,$ No use of the "mutable" and$/$or "ref" keywords in F#$/$OCaml is permitted.

Use "strong" and proper datatypes where applicable:

For example, much like the Java version, which uses an "Enum Class" to represent each

token type, the reimplementation should use the corresponding features of the chosen

language.

OCaml calls them this would mean "Tagged Unions", F# calls these "Discriminated Unions", and both mean the same thing.

The submission will be a single file: Name the file using your Towson login username.

For example, mine would be aconover.fsx$)$

Using the F# parser example in Blackboard, write a program $-$ in F# $-$ that implements a Recursive Descent

Parser defined by the grammar below.

The Program should:

Accept:

a$.$ A space$-$delimited set of symbols representing a sentence as described by the grammar below.

$($The user should be prompted to enter the input via the keyboard. This Program will NOT be

reading from a file.$)$

Output:

a$.$ For successful parsing: "The Sentence $>is$ incorrect because: $"$

$Of$ course, any should $be$ replaced with the appropriate text.

$BNF$ FOR THE PARSER$>$ follows the grammar."

$b.$ For unsuccessful parsing: "The Sentence $>is$ incorrect because: $"$

$Of$ course, any should $be$ replaced with the appropriate text.

$BNF$ FOR THE PARSER

Examples of valid input:

$($REMEMBER: Various fragments can also be valid; providing examples of every possible valid input string

is impossible as an infinite number exists! Of course, this is what the grammar itself describes!$)$

Some randomly generated VALID input examples:

read x

write x $+1$

write x $*($ y $+$ z $)$

n calculate $($ n $)$

n calculate $($ n $+$ x $)$

n calculate $($ n $+$ x $,$ b $,$ c $*$ d $+$ e $)$

if a $$ b then a $=$ b endif

if a $*$ c $$ b $+$ c then a $=$ b endif

if a $$ b then n calculate $($ n $)$ endif

if a $>$ b then a $=$ b else c $=$ d e $=$ f endif

while x $>$ y do x $=$ x $+1$ done

do x $=$ x $+1$ until x $>0$

if x $>$ y then do x $=$ x $+1$ until x $>0$ n f $($ n $)$ else while x $>$ y do x $=$ x $+1$ done endif