Project 1

The lectures have covered enough material to complete both scanners. You need to understand DFAs, the simplified maximal munch algorithm, and the general concepts behind scanning. In terms of the course notes, you need to have read Chapter 3 in its entirety.

• For the MIPS scanner, one of the token types (LABELDEF) is related to a feature (labels) we won't discuss in class until some time after the release of this project. However, you can still implement the scanner without understanding what labels do.
• For the WLP4 scanner, while we have not discussed WLP4 in class yet, the given specification is sufficient to implement the scanner. It is up to you whether you want to implement it now, or wait until we discuss WLP4 so that you have more context.

• Reference implementations of both scanners, called mipsscan and wlp4scan, are available as web tools and on the Linux environment (after running /source/u/cs241/setup). You can use these to confirm what the expected output is for test inputs you create.
• Starter code is provided to help you process the DFA file format, in case you want to use this file format to specify your scanning DFAs. See the Stepping Stones section below for details.
• Marmoset secret tests: Unlike questions, the Marmoset tests for projects include secret tests, which are completely invisible before the project deadline. Secret test results will be made visible a few days after the deadline (once any extensions given for special circumstances have passed).
  • For projects, the majority of the marks are for secret tests.
  • While you cannot see how many marks are allocated to secret tests on Marmoset itself, we will post a mark breakdown on this page once the Marmoset tests are set up.
  • For projects, the public tests and release tests do not constitute a thorough test suite. They are meant to ensure your output follows the correct format, and that you have implemented all the specifications, but they do not test functionality on a deep level.
  • For projects, passing the public and release tests does not mean you are "done". You need to test your program thoroughly so that you are confident it will pass the secret tests.
• Notes for C++ users:
  • Valgrind is used to check for memory errors in your program. This does not only include leaks, but also other memory errors like invalid memory accesses or use of an uninitialized value. You will fail tests if Valgrind detects errors in your program. See this guide for tips on how to deal with Valgrind errors.
  • The exit function does not call destructors for stack-allocated objects, which may cause you to leak memory and fail tests. To exit after printing an error, throw an exception and catch it in main, then exit normally with return. Or if the error happens in main itself, you can just exit directly with return.
• Note for Racket users: Our Marmoset scripts cannot distinguish between an error produced by the error function, and other runtime errors caused by mistakes in your code. To report errors, rather than using error, print to standard error (e.g., with eprintf) and then call exit.

Kind	Description of Associated Lexemes
ID	Identifiers: Strings starting with an alphabetic character (a-z or A-Z), followed by zero or more alphanumeric characters (a-z or A-Z or 0-9).
DOTID	Dot-Identifiers: An . character followed by an ID lexeme.
LABELDEF	Label Definitions: An ID lexeme followed by a : character.
DECINT	Decimal Integers: Strings which optionally start with a - character, followed by one or more decimal digits (0-9).
HEXINT	Hexadecimal Integers: Strings starting with 0x, followed by one or more hexadecimal digits (0-9 or a-f or A-F).
REGISTER	Registers: A $ character followed by one or more decimal digits (0-9). The numeric value of the string of decimal digits cannot exceed 31.
COMMA	Comma: A , character.
LPAREN	Left Parenthesis: A ( character.
RPAREN	Right Parenthesis: A ) character.
NEWLINE	Either a line feed character (ASCII 0x0a), or the two-character sequence carriage return, line feed (ASCII 0x0d, ASCII 0x0a). When printing this token, do not print the lexeme. Print a line containing only the kind.
?WHITESPACE	Whitespace: A sequence of one or more space (ASCII 0x20) or tab (ASCII 0x09) characters.
?COMMENT	Comment: A ; character, followed a sequence of zero or more ASCII characters that does not contain a line feed (ASCII 0x0a) or carriage return (ASCII 0x0d). (In other words, once a ; character is encountered, everything up to the next line feed or carriage return is a ?COMMENT.)

Restrictions:

• In a REGISTER token, the numeric value of the decimal integer following the $ character must not exceed 31.
• In a DECINT token, the numeric value of the decimal integer must lie between -2147483648 and 4294967295, inclusive. (This is the union of the signed and unsigned ranges for 32-bit integers.)
• In a HEXINT token, the numeric value of the hexadecimal integer must not exceed 0xFFFFFFFF.

Kind	Description of Associated Lexemes
ID	Identifiers: Strings starting with an alphabetic character (a-z or A-Z), followed by zero or more alphanumeric characters (a-z or A-Z or 0-9), not equal to any of the following keywords: "int", "wain", "if", "else", "while", "println", "return", "new", "delete", "NULL".
NUM	Numbers: Strings consisting of one or more decimal digits (0-9).
INT	Keyword int: The string "int".
WAIN	Keyword wain: The string "wain".
IF	Keyword if: The string "if".
ELSE	Keyword else: The string "else".
WHILE	Keyword while: The string "while".
PRINTLN	Keyword println: The string "println".
RETURN	Keyword return: The string "return".
NEW	Keyword new: The string "new".
DELETE	Keyword delete: The string "delete".
NULL	Keyword NULL: The string "NULL".
LPAREN	Left Parenthesis: The ( character.
RPAREN	Right Parenthesis: The ) character.
LBRACE	Left Brace: The { character.
RBRACE	Right Brace: The } character.
LBRACK	Left Bracket: The [ character.
RBRACK	Right Bracket: The ] character.
BECOMES	Equals: The = character.
PLUS	Plus: The + character.
MINUS	Minus: The - character.
STAR	Star: The * character.
SLASH	SLASH: The / character.
PCT	Percent: The % character.
AMP	Ampersand: The & character.
COMMA	Comma: The , character.
SEMI	Semicolon: The ; character.
LT	Less Than: The < character.
GT	Greater Than: The > character.
LE	Less Than or Equal To: The string "<=".
GE	Greater Than or Equal To: The string ">=".
EQ	Equal To: The string "==".
NE	Not Equal To: The string "!=".
?WHITESPACE	Whitespace: A sequence of one or more of the following characters: space (ASCII 0x20), tab (ASCII 0x09), line feed (ASCII 0x0a) or carriage return (ASCII 0x0d).
?COMMENT	Comment: The string "//", followed a sequence of zero or more ASCII characters that does not contain a line feed (ASCII 0x0a) or a carriage return (ASCII 0x0d).

Restrictions:

• In a NUM token, the numeric value of the decimal number must not exceed 2147483647 (the maximum 32-bit signed integer).
• Useless leading zeroes are not allowed in NUM tokens. That is, a NUM cannot start with 0 unless the lexeme is simply "0".

Suppose the file program.asm contains the following data:

lis $4
.word 16
lw $3, 0xfffc($4) ; what does this do?
jr $31

./mipsscan < program.asm
ID lis
REGISTER $4
NEWLINE
DOTID .word
DECINT 16
NEWLINE
ID lw
REGISTER $3
COMMA ,
HEXINT 0xfffc
LPAREN (
REGISTER $4
RPAREN )
NEWLINE
ID jr
REGISTER $31
NEWLINE

Suppose the file program.asm contains the following data:

jr $32

./mipsscan < program.asm > /dev/null
ERROR: Invalid register number: $32

Suppose the file program.wlp4 contains the following data:

// Simple program that adds 

int wain(int a, int b) {
  // Just add the numbers together
  return a + b; 
}

./wlp4scan < program.wlp4
INT int
WAIN wain
LPAREN (
INT int
ID a
COMMA ,
INT int
ID b
RPAREN )
LBRACE {
RETURN return
ID a
PLUS +
ID b
SEMI ;
RBRACE }

Suppose the file program.wlp4 contains the following data:

int factorial(int n) {
  return (n!);
}

./wlp4scan < program.wlp4 > /dev/null
ERROR: Simplified maximal munch failed at this point:
int factorial(int n) {
  return (n!)

Create a class or struct representing a DFA. Using the function for printing information about a DFA as a starting point, write a function that reads a DFA file and constructs an instance of the DFA class or struct. You can test it by replacing the string constant in dfa.h / dfa.rkt, or by passing your own files to the function directly.

Using your DFA class or struct, write a "get next state" function which takes a state and a character as parameters. If there is an arrow leading out of the input state that is labelled with the input character, return the state pointed to by the arrow. Otherwise, return a value indicating there is no next state to go to.

Use the "get next state" function to implement a "simplified maximal munch" function, which takes a string (or an input stream/port), tokenizes it with simplified maximal munch, and returns a sequence of strings (token lexemes). Do not worry about token kinds or filtering out tokens at this stage.

You can test your implementation with the DFA provided in the starter code, the MIPS token lexeme DFA, and any other DFA files you have lying around.

Replace the DFA provided in the starter code with the MIPS token lexeme DFA. It is time to write the MIPS scanner.

Create a class or struct for tokens. Modify your "simplified maximal munch" function to return a sequence of tokens instead of a sequence of strings.

• When a lexeme is found, the function should determine the appropriate kind for the lexeme. Often this can be done by looking at the current state of the DFA, but depending on the design of the DFA, it may be easier to examine the lexeme itself.
• If the kind is one that should be filtered out, discard the lexeme and continue without adding the token to the sequence.
• If the kind is one that has restrictions associated with it, check the restrictions and produce an error if they are violated.
• If there are no errors, create a token from the kind and lexeme and add it to the sequence of tokens.

• Remember that for NEWLINE tokens, you should not print the lexeme.

Now it is time to write the WLP4 scanner. Create a DFA for WLP4 tokens and replace the MIPS DFA with this new DFA.

Creating the WLP4 DFA may be a little tricky. If you are stuck, study the provided MIPS DFA and try to understand how it works.

Once you have the WLP4 DFA, modify the part of your "simplified maximal munch" function that checks restrictions on tokens, so that it checks the WLP4 restrictions instead of the MIPS restrictions.

Test your code thoroughly, and you're done!