# Lecturecise 08: Exercises with Grammars

Sketch of solutions for Problems 1, 5, and 8: pptx, pdf

Solutions for problems 3 and 6: pdf

Continued in Lecturecise09

## Problem 1

Consider a grammar for expressions where the multiplication sign is optional.

ex ::= ex + ex | ex * ex | ex ex | ex / ex | ( ex ) | ID | INTLITERAL

- Give evidence why this grammar is not LL(1)
- Find a LL(1) grammar recognizing the same language.
- Using your grammar, draw the parse tree for the following expression: 3 * x - z 2
- Create the LL(1) parsing table.

## Problem 2

The goal in this problem is to construct an LL(1) parser for the following grammar.

S -> ( L ) S -> a L -> L , S L -> S

a) Can the grammar be used with a LL(1) parser as is? If not, modify it accordingly.

b) Compute the First and Follow sets for the new grammar.

c) Construct the parsing table for the LL(1) parser

## Problem 3

We will say that a grammar has a cycle if there is a reachable non-terminal such that , i.e. it is possible to derive the nonterminal A from A by a nonempty sequence of production rules.

Show that if a grammar has a cycle, then it is not LL(1).

## Problem 4

Show that the regular languages can be recognized with LL(1) parsers. Describe a process that, given a regular expression, constructs an LL(1) parser for it.

## Problem 5

Put the following grammar into Chomsky normal form. Show your steps.

S -> A ( S ) B | ε A -> S | S B | x | ε B -> S B | y

## Problem 6

Assume a grammar in Chomsky normal form has non-terminals. Show that if the grammar can generate a word with a derivation having at least steps, then the recognized language should be infinite.

## Problem 7

Consider the following grammar.

S -> S S S -> S '+' S S -> S '*' S -> '(' S ')' S -> 'a' | 'b'

a) How many strings does the grammar generate?

b) Is the language generated by this grammar regular? If it is, give the regular expression, if it is not, explain why.

c) How many distinct parse trees exist for the following string?

(a*b+a)+(a+b*b)

Now consider the following grammar:

T -> R T -> a T c R -> R -> R b R

d) How many strings does the second grammar generate?

e) Is the language generated by this grammar regular? If it is, give the regular expression, if it is not, explain why.

f) How many distinct parse trees exist for the following string?

aaabbbccc

## Problem 8

Consider the following grammar over :

S -> #A | !# | ! A -> ! | #B | ε B -> #B | !

a) Determine how the input string `###!`

is derived.

b) Find a regular expression that accepts the same language as this grammar.

c) Consider a grammar in which each rule follows one of the following patterns:

X -> a X -> aY X -> Ya X -> ε

where ranges over arbitrary terminals, , over arbitrary non-terminals.

Show that every regular language can be represented using a grammar of this form.

Vice versa, can every grammar with these four types of rules be converted into a regular expression?

## Problem 9

The following grammar is motivated by type definitions in Scala.

TypeDefinition := "type" Identifier "=" Type Type := Type "," Type Type := Type "=>" Type Type := "Int" | "Boolean"

a) By giving at least one input which has two different parse trees prove that the grammar is ambiguous.

b) Given the fact that “=>” has a lower precedence than “,” resolve the ambiguity of the grammar. That is, write a new grammar that determines the same language but is not ambiguous, such that the Type “Int ⇒ Int, Int” is parsed as function from Int to Int,Int.

## Problem 10

Let {a, b} be terminals, and {A, B} non-terminals. A production is called linear if each right hand side contains either one or zero non-terminals. Show that there are context free languages for which no linear grammar exists.