Lecturecise 08: Exercises with Grammars

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

Solutions for problems 3 and 6: pdf

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 $A$ such that $A\stackrel{+}{\Rightarrow}A$ , 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 $n$ non-terminals. Show that if the grammar can generate a word with a derivation having at least $2^n$ 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 $\Sigma = \{\#,!\}$ :

    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 $a$ ranges over arbitrary terminals, $X$ , $Y$ 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.