Ambiguity in Context-Free Grammars, Introduction to Pushdown Automata

(1)

Ambiguity in Context-Free Grammars, Introduction to Pushdown Automata

Martin Fr ¨anzle

Informatics and Mathematical Modelling The Technical University of Denmark

Context-free languages II – p.1/25

(2)

What you’ll learn

1. Context-free grammars:

What’s ambiguity Why it is a problem How to avoid it

How to build useful CFGs 2. Pushdown automata:

Machines recognizing CFLs

Operational approach towards CFLs

Tools for CFLs

(3)

Ambiguity in CFGs

(4)

Pragmatics

The use cases of regular languages and context-free languages are subtly different:

For RLs, one is primarily interested in language membership:

finding strings in a text,

classifying words/phrases in a text,

With CFLs, one is often also interested in the structural information conveyed by a parse tree:

BE then S

if

BE then S

if

S else

S

S else

S

BE then S

if

BE then S

if

(5)

A classical ambiguity

Given

if

then else

if

then

print

true

false

what shall

if false then if false then print true else print false output?

BE then S

if

BE then S

if

S else

S

S else

S

BE then S

if

BE then S

if

(6)

A classical ambiguity

Given

if

then else

if

then

print

true

false

what shall

BE then S

if

BE then S

if

S else

S

S else

S

BE then S

if

BE then S

if

(7)

A classical ambiguity — resolved

Given

if

then

print

if

then else

print

true

false

what shall

S else

S

BE then S if

else S

BE then S

if

BE then S’

if S

BE then S’

if

S’

(8)

Ambiguity

Def: A CFG is called ambiguous iff there is

s.t. has (at least) two different parse trees wrt. .

N.B. It is not the existence of multiple derivations for some string

that renders ambiguous!

(9)

Removing ambiguity

There is no algorithm for resolving ambiguity (in the sense of automatically deriving an unambiguous grammar from a given grammar).

There is not even an algorithm for finding out whether a given CFG is ambiguous.

However, there are standard techniques for writing an unambiguous grammar that help in most cases.

(10)

Removing ambiguity

(11)

Removing ambiguity

(12)

Expression grammars

Ambiguous Unambiguous

(13)

Expression grammars

Ambiguous Unambiguous

(14)

Derivations vs. ambiguity

Let

be a grammar and .

Thm: The following statements are equivalent:

has more than one parse tree

has more than one leftmost derivation

has more than one rightmost derivation.

Prf. Leftmost (rightmost, resp.) derivations can be understood as a canonical way of traversing a parse tree and are thus in one-to-one correspondence to parse trees.

(15)

Inherent ambiguity

Def: A CFL is called inherently ambiguous iff all CFGs with

are ambiguous.

N.B. The mere existence of one ambiguous CFG for is not sufficient to render inherently ambiguous.

(In fact, any non-empty CFL has an ambiguous CFG.)

All the previous examples had an unambiguous CFG and are thus not inherently ambiguous.

(16)

An inherently ambiguous language

The language

is inherently ambiguous.

An example grammar:

(17)

An inherently ambiguous language

The language

is inherently ambiguous.

An example grammar:

(18)

Pushdown Automata

(19)

Idea of pushdown automaton

Take an -NFA and

1. add a stack for unbounded storage, yet with access limited to

“last-in-first-out”;

2. make transitions dependent on input symbol and stack top;

3. add side effect on stack to transitions:

transitions replace stack top by an arbitrary string, thus being able to

“pop” stack (replacement by ),

preserve stack (replace stack top by ),

“push” onto stack (replace stack top by ),

“pop” and then “push” (replace stack top by ).

(20)

Formal definition

A pushdown automaton (PDA) is a seven-tuple

with

being a finite set of states,

being the input alphabet, i.e. the finite set of input symbols,

being the stack alphabet,

fin

being the transition function,

implies that can move from to

when the input symbol is (or arbitrary in case ) and the stack top is . is then replaced by .

being the start state,

being the start symbol on the stack (i.e., execution starts with the stack containing exactely one item, namely ),

being the set of accepting states.

(21)

Instantaneous descriptions (IDs)

An instantaneous description (ID) is a triple

, where

denotes the current state,

denotes the remaining input,

denotes the stack contents (top of the stack

first letter of ).

IDs describe configurations of PDA computations.

is a relation between IDs of PDA formalizing “moves” of : iff

(22)

Instantaneous descriptions (IDs)

An instantaneous description (ID) is a triple

, where

denotes the current state,

denotes the remaining input,

denotes the stack contents (top of the stack

first letter of ).

IDs describe configurations of PDA computations.

is a relation between IDs of PDA formalizing “moves” of :

iff

(23)

Translation invariance

Thm: If

is a PDA and and then

implies

I.e., PDA behaviours are preserved under stack extension and/or input extension.

Prf: It is easy to see from the definition that

implies

The theorem follows by induction on the number of steps.

(24)

Translation invariance

Thm: If

is a PDA and then

implies

I.e., PDA behaviour is independent from trailing input.

N.B. The same is not true wrt. trailing stack contents, as the PDA might well pop off, inspect, and then restore some part of the stack contents.

Prf: It is easy to see from the definition that

implies

The theorem follows by induction on the number of steps.

(25)

Language of a PDA

Def: The language

of a PDA

is

def

This form of language acceptance is often called “acceptance by final state”.

Def: The language of a PDA is

def

This form of language acceptance is often called “acceptance by empty stack”.

N.B. In general, .

(26)

Language of a PDA

of a PDA

is

def

This form of language acceptance is often called “acceptance by final state”.

of a PDA

is

def

This form of language acceptance is often called “acceptance by empty stack”.

N.B. In general,

.

(27)

Expressiveness of the acceptance criteria

Thm: If

for some pushdown automaton then there is a pushdown automaton with

.

(Given , the construction of is completely mechanic.)

Thm: If for some pushdown automaton then there is a pushdown automaton with .

Both forms of acceptance are thus equally “expressive”.

(28)

Expressiveness of the acceptance criteria

Thm: If

.

Thm: If

.

Both forms of acceptance are thus equally “expressive”.

(29)

PDAs vs. CFGs

Accepted by a PDA by empty

stack

Definable by a CFG

Accepted by a PDA

by final state

Claim: PDAs and CFGs define the same languages.

(30)

Proof of the claim

Have already shown equivalence between

being accepted by some PDA by empty stack being accepted by some PDA by final state.

Suffices to show equivalence of being definable by a CFG

to one of the two forms of PDA definability.

We will show equivalence of CFG-definabilty to being accepted by some PDA by empty stack.

(31)

From CFG to PDA

Thm: If

for some contextfree grammar then there is a pushdown automaton with

.

Prf: (Essence of) Given , a corresponding 1-state PDA can be defined by

for for

otherwise.

Then show that for any and any

iff ^lm

(32)

From CFG to PDA

Thm: If

for some contextfree grammar then there is a pushdown automaton with

.

Prf: (Essence of) Given

, a corresponding 1-state PDA can be defined by

for

otherwise.

Then show that for any and any

iff ^lm

(33)

From PDA to CFG

Thm: If

for some pushdown automaton then there is a contextfree grammar with

.

Prf: Given , a corresponding CFG can be defined by

Then show that for any , any , and any iff

(34)

From PDA to CFG

Thm: If

for some pushdown automaton then there is a contextfree grammar with

.

Prf: Given

, a corresponding CFG can be defined by

Then show that for any , any , and any

iff

(35)

Stack symbols can simulate states

Cor: For each PDA there is a PDA

with

such that

.

Prf: 1. Convert to an equivalent CFG using the construction of the previous theorem,

2. convert to a one-state PDA

using the construction of the second-last theorem.

Prize is blowup in the size of the stack alphabet!

(36)

Stack symbols can simulate states

Cor: For each PDA there is a PDA

with

such that

.

Prf: 1. Convert to an equivalent CFG using the construction of the previous theorem,

2. convert to a one-state PDA

using the construction of the second-last theorem.

Prize is blowup in the size of the stack alphabet!