Consider the following extended BNF grammar for a subset of the Scala programming language, called MicroScala.

CompilationUnit ::= object id { {Def} MainDef }

MainDef ::= def main ( args : Array [ String ] ) { {VarDef} Statement {Statement} }

Def ::= def id ( [id : Type {, id : Type}] ) : Type =

{ {VarDef} {Statement} return ListExpr ; }

| VarDef

VarDef ::= var id : Type = Literal ;

Type ::= Int | List [ Int ]

Statement ::= if ( Expr ) Statement [else Statement]

| while ( Expr ) Statement

| id = ListExpr ;

| println ( ListExpr ) ;

| { Statement {Statement} }

Expr ::= AndExpr {|| AndExpr}

AndExpr ::= RelExpr {&& RelExpr}

RelExpr ::= [!] ListExpr [RelOper ListExpr]

RelOper ::= < | <= | > | >= | == | !=

ListExpr ::= AddExpr | AddExpr :: ListExpr

AddExpr ::= MulExpr {AddOper MulExpr}

AddOper ::= + |

MulExpr ::= PrefixExpr {MulOper PrefixExpr}

MulOper ::= * | /

PrefixExpr ::= [AddOper] SimpleExpr {ListMethodCall}

ListMethodCall ::= . head | . tail | . isEmpty

SimpleExpr ::= Literal | ( Expr ) | id [ ( [ListExpr {, ListExpr}] ) ]

| scala . io . StdIn . readInt ( )

Literal ::= integer | Nil

Syntactic and Semantic Conventions The keywords and the token symbols in MicroScala are in bold. Note that MicroScala, like C, C++ and Java, has symbols {, }, [, and ] which are distinguished from grammar metasymbols {, }, [, and ], respectively, by underlining.

Assume that an id can only contain letters (only alphabetic characters), digits, and underscores ( ) with the restrictions that it must begin with a letter, cannot end with an underscore and cannot have two consecutive underscores. For example, give 2 Joe, tell me and A45Asm3 are valid identifiers, but 6gh, two bad, and no end are not. integer is an unsigned integer. Assume that comments are indicated by being preceded by //.

Design and implement a lexical analyzer procedure to read a source program in the above language and print the next token in the input stream. If the token detected is a valueless token, such as a keyword, then it is sufficient to print only the keyword. If it has a value, then both the token type and lexeme should be printed.

Suggestions:

1. Construct a token class to represent the token data structure, including a method to print a token.

2. Use the lex, flex, or JFlex tool to automatically construct a lexical analyzer in Scala from a set of regular expressions specifying tokens. This can interface with your token class to return a token to the main program which then prints the token.