Problem to solve:

Write a parser/interpreter for a simple, imperative string-processing language.

Requirements:

The interpreter must implement the language described below. The interpreter should read input from the standard input (stdin) and write output to the standard output (stdout). The interpreter should read statements from the user one at a time and perform the associated action immediately. If invalid   input is provided, the interpreter should attempt to recover and try to provide a useful error message.

Strings Language:

The EBNF grammar for the strings processing language is given below, note that bold names are used for EBNF tokens and italicsnames are used for tokens from the lexer (defined below).

The (incomplete) regular expressions for the tokens in the language are given below. Please note that if you use a language regular expression library then you may need to adjust the syntax for the

expressions below. E.g. the '+' character is a special character in regular expressions. You may also need to use syntax to only match characters at the start of the input etc.

append = append

exit = exit

list = list

print = print

printlength = printlength

printwords = printwords

printwordcount = printwordcount

reverse =  reverse

set = set

constant = SPACE |TAB|NEWLINE

end = ;

plus = +

id = [a-zA-Z][a-zA-Z0-9]*

literal =

Literals:

The string literals in this language are enclosed with double-quotes ( "...") and may contain:

.    letters - upper-case or lower-case

.    digits

.    whitespace - spaces, tabs or newlines

.    punctuation - all standard punctuation marks (including  ';')

.    special characters - special characters such as double-quotes if escaped with a backslash  '\'

Commands:

The intended behavior of each instruction is given in the following table:

Words:

Some of the commands require words to be identified within a string. For this language, a word consists of any set of letters or digits separated by whitespace (or punctuation characters). The only exceptions to this are words that contain a single-quote or hypen character. For example, "let's" or "runner-up" are considered a single word.

Notes:

Your program should read from the standard input and write to the standard output, your program should not open or close any files.

One of the first things you should do is determine what language you are going to use for your program. The assignment can be completed in most languages, but some may make it easier than others. A good regular expression engine may be helpful.

The first major part of the assignment is to write a parser. You may want to  consider a recursive descent parser to base your code on. This type of parser looks at the next token from the lexer and from this can decide which rule to match. For example, if the statement starts with the print token then the parser should expect to parse an expression followed by an end token.

The other main part of the assignment is writing the interpreter that will execute instructions from the program it reads. To do this, you will need to decide what data structures you will use for your symbol table which will store all the variables in your program (and provide a way to access their contents). This language has only one implicit type (a string), so your symbol table does not need to store any information about the type of the variable.

Decisions:

There are some features that have been left (intentionally) unspecified.

.    The regular expression for string literals has not been defined. How are you going to match string literals that contain punctuation?

.    How is your interpreter going to respond when the user enters invalid input? Your program should try to provide  some type  of error handling  and  should not just  crash. A  common approach is just to read and ignore all input until it reaches the next end token (the  ';' character).

These decisions are left up to you to make but you should document them within your assignment (in the comments is fine).

Sample Behaviour:

Sample input/output from the interpreter - input typed by the user is highlighted in bold (see the Stream Site for more examples).