Question 9

Deadline	Friday, November 17, 11:59pm
Name on Marmoset	Q9A, Q9B
To Submit	Q9A: `animal.cfg` Q9B: `program.cfg`
Marking Scheme	Q9A: 50% Q9B: 50%

Two CFGs

In this question, you will create derivations to gain some practice with context-free grammars.

Components

The context-free grammars and derivations you will work with must be represented in a specific format so that Marmoset can check your work. Specifically, the CFG must be represented as a CFG component, and the derivations must be represented as DERIVATION components.

See the components page for a summary of all the component formats used in the questions and projects about context-free grammars and parsing.

Testing

The cs241.cfgcheck course tool can be used to verify if your CFG and derivations are formatted correctly and produce the correct string.

Part A: Ambiguous Animal (50% of question mark)

Below is an ambiguous context-free grammar:

start → ( list )
list → value list
list → ε
value → object
value → number
value → animal
object → KIT
number → TEN
animal → KIT TEN

And here is a representation of this grammar as a CFG component:

.CFG
start  ( list )
list   value list
list   .EMPTY
value  object
value  number
value  animal
object KIT
number TEN
animal KIT TEN

Create a file called animal.cfg containing the above CFG component, followed by two DERIVATION components. The DERIVATION components should represent two different leftmost derivations of the same string (thus proving that the grammar is ambiguous).

Part B: Derivations in the WLP4 Grammar (50% of question mark)

Here is a WLP4 program:

int wain(int* array, int size) {
  *array = 241;
  return (1 + 2) / 3;
}

And here it is as a sequence of WLP4 token kinds:

INT WAIN LPAREN INT STAR ID COMMA INT ID RPAREN LBRACE STAR ID BECOMES NUM SEMI RETURN LPAREN NUM PLUS NUM RPAREN SLASH NUM SEMI RBRACE

Create a file called program.cfg containing a CFG component, followed by a DERIVATION component. The CFG component should be this CFG for the (non-augmented) WLP4 grammar, and the DERIVATION component should be a leftmost derivation of the above sequence of token kinds.

Note: If you are using a browser with an automatic translation feature, such as Google Chrome, it may attempt to "translate" the WLP4 grammar linked above and corrupt it! You should either download the file, or ensure automatic translation is disabled before copying the WLP4 grammar into your solution file.