SI 413 Fall 2021 / Homeworks


This is the archived website of SI 413 from the Fall 2021 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Homework 6: Grammars and Parsing

1 Fixing a grammar

The following grammar defines a language for (opening) HTML tags, like <input checked type="checkbox">

startLA inner RA
innerNAME attrs
attrsattrs single
attrs\(\varepsilon\)
singleNAME EQ VAL
singleNAME

Fix this grammar (without modifying the language it accepts!) to make it LL(1). Write your new, updated grammar below.

2 Top-down parsing

Using your LL(1) grammar from the previous question, show the partial parse tree that would result from reading the following sequence of tokens, in a top-down parser.

LA NAME NAME NAME EQ VAL

Note, this sequence does not parse all the way up to the start symbol. So it will be a partial parse tree, with some items un-expanded or un-matched.

3 Bottom-up parsing

Now use the original grammar from problem 1 to complete a partial parse of the same sequence of tokens, but this time using a bottom-up parsing strategy. Here are the grammar and tokens again:

startLA inner RA
innerNAME attrs
attrsattrs single
attrs\(\varepsilon\)
singleNAME EQ VAL
singleNAME

LA NAME NAME NAME EQ VAL

Again, this will be a partial parse. But for bottom-up parsing, that means we will have a “forest” of multiple trees, that haven’t yet combined all the way to get back to the start symbol.

Assume the next token of look-ahead is RA, in order to combine the partial parse trees (reduce) as much as possible.