Project02 - NTLang

Due Date

  1. Due in GitHub by Monday, September 21st at 11:59 PM

  2. Create your repo in the GitHub Classroom Assignment published in your section's Piazza

Given

  1. We will give a working reference implementation of the scanner and parser we have worked on in class.

  2. You will expand that implementation to match the EBNF given below, and provide your own bitwise operations and base conversions.

Requirements

  1. You will use the techniques we've learned for scanning, parsing, and number manipulation to build an interpreter for a little language with the EBNF grammars given below.

  2. Your interpreter will take an expression , a number base, and a width on the command line, and print its output to stdout like this:

$ ./project02 -e "1 + 1"
2
$ ./project02 -e "10" -b 16
0x0000000A
$ ./project02 -e "10 + 1"
11
$ ./project02 -e "10 + 1" -b 16
0x0000000B


$ ./project02 -e "10" -b 16 -w 16
0x000A
$ ./project02 -e "10" -b 2
0b00000000000000000000000000001010
$ ./project02 -e "10" -b 2 -w 4
0b1010
$ ./project02 -e "0x0A" -b 10
10
$ ./project02 -e "0x0A" -b 2 -w 8
0b00001010

$ ./project02 -e "((1 + 1) * 1)" -b 16 -w 16
0x0002
$ ./project02 -e "((1 + 1) * 1)" -b 2 -w 8
0b00000010

$ ./project02 -e "(1 << 16)" -b 10 -w 32
65536
$ ./project02 -e "(1 << 16)" -b 10 -w
16
0
$ ./project02 -e "(1 << 16)" -b 16 -w 32
0x00010000

$ ./project02 -b 10 -w 8 -e "(2 * (0b1111 & 0b1010))"
20

$ ./project02 -b 10 -w 8 -e "0b00001000"
8
$ ./project02 -b 10 -w 4 -e "0b00001000"
-8
$ ./project02 -b 10 -u -w 4 -e "0b00001000"
8

$ ./project02 -b 10 -w 4 -e "0b1100"
-4
$ ./project02 -e "(((((~((-(2 * ((1023 + 1) / 4)) >- 2) << 8)) >> 10) ^ 0b01110) & 0x1E) | ~(0b10000))"
-1

  1. Valid inputs for the number base are -b 2, -b 10 (default if -b not given), and -b 16

  2. Valid inputs for the width are -w 4, -w 8, -w 16, and -w 32 (default if -w not given)

  3. Print unsigned ints with -u (this only has meaning for -b 10)

  4. You will write the scanner and parser yourself, without using C strtok() or scanf() or compiler generators such as lex, yacc, bison, antlr, etc.

  5. You will write the base conversion tools yourself without using C printf("%d", i) or printf("%x", i)

Scanner

  1. Your scanner will read the expression from the command line and create a data structure of tokens.

  2. The EBNF grammar for the scanner is:

tokenlist ::= (token)*
token ::= intlit | hexlit | binlit | symbol
symbol ::= '+' | '-' | '*' | '/' | '>>' | '<<' | '~' | '&' | '|' | '^' | '>-'
intlit ::= digit (digit)*
hexlit ::= '0x' | hexdigit (hexdigit)*
binlit ::= '0b' ['0', '1'] (['0', '1'])*
hexdigit ::= 'a' | ... | 'f' | 'A' | ... | 'F' | digit
digit ::= '0' | ... | '9'
# Ignore
whitespace ::= ' ' | '\t' (' ' | '\t')*

Parser

  1. As with lab03, your parser will generate parse tree (AST) which represents the meaning of the tokens generated by the scanner.

  2. The parser adds the following elements to the EBNF grammar:

program ::= expression EOT

expression ::= operand (operator operand)*

operand ::= intlit
| hexlit
| binlit
| '-' operand
| '~' operand
| '(' expression ')'

The bitwise operators do the same thing as their counterparts in C:

>> logical shift right
>- arithmetic shift right
<< logical shift left
~ bitwise not
& bitwise and
| bitwise or
^ bitwise xor

Interpreter

  1. Your interpreter will walk the AST depth-first, evaluating the expressions defined by the nodes, and printing the results.

  2. You may want to store the intermediate results in a C uint32_t (unsigned int), to make conversion to binary or hexadecimal easy. It's possible to use a C character string instead if you prefer, but that may be a little more work.

  3. The width parameter controls how many bits wide the output should be.

Grading

  1. Grading will have two components: automated and interactive.

  2. For interactive grading, we will schedule 1:1 meetings with the instructor or TAs using a Google Sheet published in your section's Piazza. You should be prepared to share your screen and answer questions about your design and implementation.

  3. Interactive grading counts for 40% of the project grade, as follows:

    1. 10% Question 1 (examples given in lecture)

    2. 10% Question 2

    3. 10% Question 3

    4. 10% Code quality

  4. The code quality rubric is:

    1. -2 for inconsistent spacing or indentation

    2. -2 for inconsistent naming or commenting

    3. -2 for commented-out ("dead") code

    4. -2 for redundant or overly complicated code

    5. -2 for messy repo (build products, .actual files, etc.)

  5. Automated grading counts for 60% of your project grade

    1. We will use the maketest tool to grade correctness of your project. You can run it yourself on your local repository to see how your code scores. Instructions are in the README.

    2. Your project must be generated by a Makefile, and the executable must be called project02

  6. There is an extra credit problem, worth one point. It's possible for the expression to overflow the 32 bits in a uint32_t. You can detect this. Examples of correct output:
    pi@raspberrypi:~/project02 $ ./project02 -e "0xffffffff"
    -1
    pi@raspberrypi:~/project02 $ ./project02 -e "0xffffffff1"
    overflows uint32_t: ffffffff1
    pi@raspberrypi:~/project02 $ ./project02 -e "0x000000000ffffffff"
    -1