CS 241 — Fall 2017 — Assignment 7

Assignments for CS 241
← Assignment 6 Assignment 7 Assignment 8 →
Friday, Nov 3, 2017 at 5:00 pm Friday, Nov 10, 2017 at 5:00 pm Friday, Nov 17, 2017 at 5:00 pm
P1P2P3P4P5

For Problems 1 and 2 you are to construct reversed rightmost derivations for two problems from Assignment 6. The format of your solution will be that of a CFG-R file which is identical to that of a CFG file except that derivations in CFG-R files are not indented, and represent reversed rightmost rather than forward leftmost derivations. We supply the source code for a tool (cfgrl.rkt, CFGRL.scala, or cfgrl.cc) that reads a CFG-R file containing a single derivation and outputs the equivalent CFG file. You may use this tool to verify your submissions to Problems 1 and 2, and you may use this tool as a model for your implementations for Problems 3, 4 and 5.

For Problem 4 you are to write an SLR(1) parser which reads a representation of the SLR(1) DFA for a context-free language, along with an input sequence to be parsed. For Problem 5 you are to embed an SLR(1) parser for WLP4 into a Racket, Scala, or C++ program in much the same way that you embedded your scanner for Assignment 6.

Problem 1 — 7 marks of 60 (filename: a7p1.cfg-r)

Prepare a .cfg-r file that solves Assignment 6, Problem 6.

Click here to go back to the top of the page.

Problem 2 — 7 marks of 60 (filename: a7p2.cfg-r)

Prepare a .cfg-r file that solves Assignment 6, Problem 7.

Click here to go back to the top of the page.

Problem 3 — 4 marks out of 60 (filename: lr.rkt or LR.scala or lr.cc)

Write a Racket, Scala, or C++ program that reads in an LR1 File representing a context-free grammar and an LR(1) machine, and is followed by a number of lines formatted like so:

n x

Where n is a number and x is a terminal or nonterminal. Your program should print some of the results of performing the correct LR action from that state and input: on a shift, you should print "shift X" where X is the state to shift, and on a reduce you should print "reduce R", where R is the rule to reduce along. If the transition doesn't exist, print "error". For example, given the sample lr1 file with the last line removed and replaced by:

10 EOF
0 -
8 -

Your program should produce the following output:

shift 5
error
reduce expr expr - term

This is to ensure you are reading the .lr1 file correctly, and it is highly recommended that you pass all tests on this question before attempting Problems 4 and 5.

Click here to go back to the top of the page.

Problem 4 — 26 marks of 60 (filename: lr.rkt or LR.scala or lr.cc)

Write a Racket, Scala, or C++ program that reads an LR1 file representing a context-free grammar, an LR(1) machine, and a sequence to be recognized. If the sequence is in the language, output to standard output the unindented reversed rightmost derivation, as defined in the cfg-r file format. If the input is not recognized, output "ERROR at k", followed by a newline character, to standard error, where k is one greater than the number of tokens in the longest correct prefix.

For the sample lr1 file as input, the correct output is:

term id
expr term
term id
expr term
term ( expr )
expr expr - term
term id
expr expr - term
S BOF expr EOF
If you replace the last line of this file by
BOF id - id ) - id EOF
the correct output (to standard error) is
ERROR at 5
You may also test your program with the WLP4 grammar and parse tables, in .lr1 format after adding a sequence to be recognized.

The core of this problem is simply to implement the bottom-up parsing algorithm that was demonstrated to you in class. Remember the invariant for bottom-up parsing: stack symbols + unread input = step in the rightmost derivation. Be sure to make the connection between this invariant and the required output. If you have not yet checked the invariant on a sample trace of a bottom-up parse, do so now. This will help you understand what your program is supposed to do.

Click here to go back to the top of the page.

Problem 5 — 16 marks of 60 (filename: wlp4parse.rkt or WLP4Parse.scala or wlp4parse.cc)

Write a WLP4 parser encapsulated as a Racket, Scala, or C++ program. The input to your parser is a file representing the sequence of tokens in a WLP4 program, as output by the scanner specified in Assignment 6, Problem 1.

That is, each token is represented by a line containing the name of the token, followed by a space, followed by the string recognized as the token in the WLP4 source program. Note: Unlike the input of Problem 4, the input to your parser in this problem will not have lines containing BOF and EOF at the beginning and end.

If the input represents a syntactically valid WLP4 program, the output from your program (on standard output) should be a .wlp4i file. The format of a .wlp4i represents the derivation and also the recognized token strings.

If the input does not represent a syntactically valid WLP4 program, output "ERROR at k" to standard error where k is one greater the number of tokens in the longest correct prefix of the input (that is, not counting BOF).

The student.cs undergraduate enviroment includes three commands to help you test your parser:

This problem builds on your solution to Problem 4. Problem 4 asks you to implement the stack algorithm for SLR(1) parsing. For this problem, you simply have to change the output format to wlp4i, which is essentially a flattened parse tree (so you may wish to create a parse tree data structure as part of your solution for this problem).

Click here to go back to the top of the page.

Extra fun

Jslr -- a Simple LR(1) [SLR(1)] parser generator is a program that generates the LR(1) DFA for any SLR(1) grammar. You can use it to generate parsers for your own grammars, or to generate additional test inputs for Problem 3. The input to Jslr.java is a .cfg file. If the .cfg file represents an SLR(1) grammar, the corresponding .lr1 file is output; otherwise an error message is produced.