CS 441 UOK Parser in Racket Programming Code

CS 441Fall 2021
Programming Assignment
For this assignment, you will use Racket, a functional programming language, to write a simple parser.
Note that we’re writing only a parser, not a full interpreter (although interpreters in Racket aren’t that
difficult1). Also, your program only needs to pass a verdict on the syntactical correctness of the
program, not produce a full parse tree.
The standard interpreter for Racket is DrRacket, and is installed on all Flarsheim lab machines as well
as available as a free download from https://racket-lang.org/.
Racket is a functional language, so it requires a different approach than what you may be used to. It’s
expression-oriented; functions take in parameters and return function values, with no side effects. I’d
suggest spending some time getting familiar with it, perhaps working out some common algorithms in
a functional form.
Your code should have a function called parse, which takes one parameter—the name of the file of
source code to be processed:
(parse source.css)
It should return a string: either “Accept”, indicating the program is syntactically correct; or a message
as to which line the first syntax error was found:
So output will be either:
Accept
or something like:
Syntax error found on line 25
In the case of a syntax error, printing the offending line would also be helpful. It is not necessary to
continue scanning for additional syntax errors.
You are given a grammar for Cascading Style Sheets 2.0. Your parser will be tested against other
source code in the same language.
Programming notes:
• You will need other functions besides parse, of course. This will be a top-down recursivedescent parser.
• You’re not limited to printing just a final verdict; progress messages will probably be helpful in
development.
• Submit your source code (.rkt file) and a short document listing any resources you used in
developing your program. (This refers to things where you copied & modified someone else’s
code, used a workaround verbatim, or something like that. General references for Racket don’t
need to be listed.)
1
There’s an online book, Beautiful Racket, that shows how to write an interpreter for the Basic language, along with a
couple of specialized languages.
FIRST
program {id, read, write, $$}
stmt_list {id, read, write}
stmt {id, read, write}
expr {(, id, number
term_tail {+, – }
term {(, id, number}
factor-tail {*, /}
factor {C, id, number}
add_op {+, – }
mult_op {*, /}
7. expr
PREDICT
1. program → stmt_list $$ {id, read, write, $$}
2. stmt_list + stmt stmt_list {id, read, write}
3. stmt_list + € {$$}
4. stmt →id := expr {id}
5. stmt read id {read}
6. stmt + write expr {write}
+ term term_tail {(, id, number}
8. term_tail + add_op term term_tail {+, -}
9. term_tail te{, id, read, write, $$}
10. term factor factor-tail {(, id, number}
11. factor-tail + mult op factor factor-tail {*, /}
12. factor-tail + e{+, -, ), id, read, write, $$}
13. factor ( expr ) {C}
14. factor id {id}
15. factor number {number}
16. add-op ++{+}
17. add-op +-{-}
18. mult-op *{*}
19. mult_op +/{7}
FOLLOW
program
stmt_list {$$}
stmt {id, read, write, $$}
expr {), id, read, write, $$}
term_tail {), id, read, write, $$}
term {+, -, ), id, read, write, $$}
factor-tail {+, -, ), id, read, write, $$}
factor {+, -, *, 7,), id, read, write, $$}
add-op {(, id, number}
mult-op {(, id, number}
For this assignment, you will use Racket, a functional programming language, to write a simple parser.
Note that we’re writing only a parser, not a full interpreter (although interpreters in Racket aren’t that
difficult’). Also, your program only needs to pass a verdict on the syntactical correctness of the
program, not produce a full parse tree.
The standard interpreter for Racket is DrRacket, and is installed on all Flarsheim lab machines as well
as available as a free download from https://racket-lang.org/.
Racket is a functional language, so it requires a different approach than what you may be used to. It’s
expression-oriented; functions take in parameters and return function values, with no side effects. I’d
suggest spending some time getting familiar with it, perhaps working out some common algorithms in
a functional form.
Your code should have a function called parse, which takes one parameter—the name of the file of
source code to be processed:
(parse source.css)
It should return a string: either “Accept”, indicating the program is syntactically correct; or a message
as to which line the first syntax error was found:
So output will be either:
Accept
or something like:
Syntax error found on line 25
In the case of a syntax error, printing the offending line would also be helpful. It is not necessary to
continue scanning for additional syntax errors.
You are given a grammar for Cascading Style Sheets 2.0. Your parser will be tested against other
source code in the same language.
.
Programming notes:
You will need other functions besides parse, of course. This will be a top-down recursive-
descent parser.
You’re not limited to printing just a final verdict; progress messages will probably be helpful in
development.
Submit your source code (.rkt file) and a short document listing any resources you used in
developing your program. (This refers to things where you copied & modified someone else’s
code, used a workaround verbatim, or something like that. General references for Racket don’t
need to be listed.)
.