2021/8/23 CS 315 – Fall 2021 – Project02
Syllabus Schedule Assignments
Project02
Due
1. Due in GitHub by Monday, February 22nd at 11:59 PM
2. Create your repo in the GitHub Classroom Assignment published in Piazza
3. Grading for Project02 will combine autograder with a 1:1 interactive grading meeting during lecture time. That is, no lecture on Tuesday February 23rd, since we will hold grading meetings in that time. Schedule details will be in 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. Must compile and run on your Raspberry Pi.
2. 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.
3. 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
https://cs315.cs.usfca.edu/projects/project02 1/5
1202 llaF – 513 SC
2021/8/23 CS 315 – Fall 2021 – Project02
$ ./project02 -e “10” -b 2
0b00000000000000000000000000001010
Syllabus Schedule Assignment
$ ./project02 -e “10” -b 2 -w 4
0b1010
$ ./project02 -e “0x0A” -b 10
10
$ ./project02 -e “0x0A” -b 2 -w 8
0b00001010
s
$ ./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
4. Valid inputs for the number base are -b 2, -b 10 (default if -b not given), and -b https://cs315.cs.usfca.edu/projects/project02 2/5
1202 llaF – 513 SC
p ,(g),
2021/8/23 CS 315 – Fall 2021 – Project02
16
5. Valid inputs for the width are -w 4, -w 8, -w 16, and -w 32 (default if -w not
given)
6. Print unsigned ints with -u (this only has meaning for -b 10)
7. You will write the scanner and parser yourself, without using C strtok() or scanf() or compiler generators such as lex, yacc, bison, antlr, etc.
8. 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:
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:
Syllabus Schedule Assignments
tokenlist ::= (token)*
token ::= intlit | hexlit | binlit | symbol
symbol ::=’+’|’-‘|’*’|’/’|’>>’|’<<'|'~'|'&'| '|' | '^' | '>-‘
intlit
hexlit
binlit
hexdigit
digit
::= digit (digit)*
::= ‘0x’ | hexdigit (hexdigit)*
::= ‘0b’ [‘0’, ‘1’] ([‘0’, ‘1’])* ::=’a’|…|’f’|’A’|…|’F’|digit ::= ‘0’ | … | ‘9’
# Ignore
whitespace ::= ‘ ‘ | ‘\t’ (‘ ‘ | ‘\t’)*
program ::= expression EOT
expression ::= operand (operator operand)*
operand ::= intlit
| hexlit
| binlit
| ‘ ‘ operand
https://cs315.cs.usfca.edu/projects/project02 3/5
1202 llaF – 513 SC
2021/8/23
| ‘-‘ operand
CS 315 – Fall 2021 – Project02
| ‘~’ operand
| ‘(‘ expression ‘)’
Syllabus Schedule Assignment
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 more work.
3. The width parameter controls how many bits wide the output should be.
Rubric
1. 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
2. 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, editor temp files, autograder, etc.)
3. Automated grading counts for 60% of your project grade
1. We will use the autograder tool to grade correctness of your project.
s
https://cs315.cs.usfca.edu/projects/project02 4/5
1202 llaF - 513 SC
2021/8/23 CS 315 - Fall 2021 - Project02
2. Your project must be generated by a Makefile, and the executable must be
called project02
Syllabus Schedule Assignments
4. 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
https://cs315.cs.usfca.edu/projects/project02
5/5
1202 llaF - 513 SC