# Homework 04

**Due Wednesday, 3 November, 10:10am.** Please hand it in to Hossein before the beginning of the exercise session.

## Problem 1

In bottom up parsing replacing the RHS of a rule with its LHS is called reduction. A reductions is called “useless” if it is actually generated during the parsing but it cannot be used in any valid parse tree.

We denote a reduction by a triple (p, A → u, q). We define the fact that a reduction occurs during parsing depending on the parsing technique, as follows.

**For CYK:** CYK parser, if the non-terminal A belongs to d(p)(q) because of its right-hand side u, that is

- either u is a terminal and is stored at substring from p to q (so q = p+1), or
- u is of the form BC, where B belongs to d(p)(r) and C belongs to d(r+1)(q)

**For Earley parser:** in Earley parser executes a completion step because of the item

Consider the following grammar.

S -> UT | V "Int" | "Int" T -> V "Int" | "Int" U -> S "=>" V -> T ","

In all of the following questions, consider the input to be “Int , Int ⇒ Int”.

- Construct the CYK parsing table.
- Is the grammar ambiguous for the input?
- Determine the useless reductions in CYK parsing.
- Give the Earley parsing for the same input and grammar.
- Determine the useless reductions in Earley parsing.
- Classify the useless reductions in three categories: both Earley and CYK, only CYK, only Earley.

## Problem 2

The Predictor of an Earley parser can be improved by taking into account the look-ahead of the next symbol. As an example if the next symbol of the input is and then it will never predict an item of the form . Describe how this improved Predictor can eliminate some useless reductions in the first problem.

## Problem 3

Consider a productive grammar in Chomsky normal form which does not contain . Assume the input consists of exactly tokens, i.e., the lexical analyzer returns tokens before hitting the EOF.

- Assume there are productions of form A → BC and productions are of form A → a. By considering all the combinations of possible dot positions in the right-hand-side of a production and all different possible values of an item, compute the number of possible items.

Consider the following grammar.

S -> AB A -> BA A -> a B -> b

Determine which of the following items are possible and which are impossible during the parsing of an input.