CS 241 -- Winter 2012 -- Assignment 7

You are to create context-free grammars and derivations represented as CFG files each of which is a textual reprentation of a CFG, optionally followed by a textual representation of several derivations. The student.cs environment provides a tool java cs241.CFGCheck which checks the validity of the CFG and derivations.

Due date: Monday, March 5, 10:00 p.m.

A7P1 - 7 marks (a7p1.cfg)

Create a file representing the CFG with the following production rules:

S → BOF A EOF
A → x
A → A x

A7P2 - 7 marks (a7p2.cfg)

Add derivations for the following strings to the CFG file created for A7P1:

BOF x EOF
BOF x x EOF
BOF x x x EOF

A7P3 - 7 marks (a7p3.cfg)

The following production rules yield an ambiguous CFG:

S → BOF A EOF
A → x
A → A x A

Find a string for which the derivation is ambiguous. Compose a CFG file representing the CFG and two different derivations for your string.

A7P4 - 7 marks (a7p4.cfg)

Add a derivation to this context-free grammar for the following sequence of symbols:

BOF id EOF

A7P5 - 7 marks (a7p5.cfg)

Add a derivation to this context-free grammar for the following sequence of symbols:

BOF ( id - ( id - id ) ) - id EOF

A7P6 - 7 marks (a7p6.cfg)

Add a derivation to this augmented grammar for WLPP for the following (augmented) sequence of WLPP tokens:

BOF INT WAIN LPAREN INT ID COMMA INT ID RPAREN LBRACE RETURN ID PLUS ID STAR ID SEMI RBRACE EOF

A7P7 - 18 marks (Galaxy.java or galaxy.ss or galaxy.cc)

Write a Java, Scheme, or C++ program that reads a CFG file that contains the same grammar as for problems A7P4 and A7P5 with the example derivation replaced by another valid derivation for the same grammar.

Assume that each occurrence of the symbol id represents the value 42, that each occurrence of - represents subtraction, that operations associate from left to right, except where overridden by parentheses. Output a single line giving the value of the derived expression.

The correct output for the sample grammar and derivation is a single line containing -42.

Notes:

The grammar is fixed, so you may, if you wish, simply skip over the grammar part of the .cfg file, and embed assumptions about the syntax directly into your program.

The input will have exactly one derivation following the grammar.
The derivation will be valid.

It is not necessary to build a parse tree or any other data structure to solve this problem.

You may find these programs useful: DerivationPrinter.java derivationprinter.ss derivationprinter.cc. Each reads a .cfg file, skips over the grammar, and prints the rules used in the derivation, with the indentation removed. You will want to replace the part that reads the rules so as to process them in a syntax-directed translation, rather than just printing them out.