Simplifications �of �Context-Free Grammars

1

Fall 2003

A Substitution Rule

2

Fall 2003

Substitute

​

Equivalent

grammar

A Substitution Rule

3

Fall 2003

Equivalent

grammar

Substitute

​

4

Fall 2003

In general:

Substitute

equivalent

grammar

Nullable Variables

5

Fall 2003

Nullable Variable:

Removing Nullable Variables

6

Fall 2003

Example Grammar:

Nullable variable

7

Fall 2003

Substitute

​

Final Grammar

Unit-Productions

8

Fall 2003

Unit Production:

(a single variable in both sides)

Removing Unit Productions

9

Fall 2003

Observation:

Is removed immediately

10

Fall 2003

Example Grammar:

11

Fall 2003

Substitute

​

12

Fall 2003

Remove

​

13

Fall 2003

Substitute

​

14

Fall 2003

Remove repeated productions

Final grammar

Useless Productions

15

Fall 2003

16

Fall 2003

Another grammar:

Not reachable from S

17

Fall 2003

In general:

if

then variable is useful

otherwise, variable is useless

contains only

terminals

18

Fall 2003

A production is useless

if any of its variables is useless

Removing Useless Productions

19

Fall 2003

Example Grammar:

20

Fall 2003

First:

find all variables that can produce

strings with only terminals

Round 1:

Round 2:

21

Fall 2003

Keep only the variables

that produce terminal symbols:

(the rest variables are useless)

Remove useless productions

22

Fall 2003

Second:

Find all variables

reachable from

Use a Dependency Graph

not

reachable

23

Fall 2003

Keep only the variables

reachable from S

Final Grammar

(the rest variables are useless)

Remove useless productions

Removing All

​

​

Step 1: Remove Nullable Variables

​

Step 2: Remove Unit-Productions

​

Step 3: Remove Useless Variables

24

Fall 2003

Normal Forms�for�Context-free Grammars

25

Fall 2003

Chomsky Normal Form

26

Fall 2003

Each productions has form:

variable

variable

or

terminal

27

Fall 2003

Examples:

Not Chomsky

Normal Form

Chomsky

Normal Form

Convertion to Chomsky Normal Form

​

Example:

28

Fall 2003

Not Chomsky

Normal Form

29

Fall 2003

Introduce variables for terminals:

30

Fall 2003

Introduce intermediate variable:

31

Fall 2003

Introduce intermediate variable:

32

Fall 2003

Final grammar in Chomsky Normal Form:

Initial grammar

33

Fall 2003

From any context-free grammar

(which doesn’t produce )

not in Chomsky Normal Form

we can obtain:

An equivalent grammar

in Chomsky Normal Form

In general:

34

Fall 2003

The Procedure

First remove:

​

Nullable variables

​

Unit productions

35

Fall 2003

Then, for every symbol :

In productions: replace with

Add production

New variable:

36

Fall 2003

Replace any production

with

New intermediate variables:

37

Fall 2003

Theorem:

For any context-free grammar

(which doesn’t produce )

there is an equivalent grammar

in Chomsky Normal Form

38

Fall 2003

Observations

• Chomsky normal forms are good

for parsing and proving theorems

• It is very easy to find the Chomsky normal

form for any context-free grammar

Greinbach Normal Form

39

Fall 2003

All productions have form:

symbol

variables

40

Fall 2003

Examples:

Greinbach

Normal Form

Not Greinbach

Normal Form

41

Fall 2003

Conversion to Greinbach Normal Form:

Greinbach

Normal Form

42

Fall 2003

Theorem:

For any context-free grammar

(which doesn’t produce )

there is an equivalent grammar

in Greinbach Normal Form

43

Fall 2003

Observations

• Greinbach normal forms are very good

for parsing

• It is hard to find the Greinbach normal

form of any context-free grammar

The CYK Parser

44

Fall 2003

45

Fall 2003

The CYK Membership Algorithm

Input:

• Grammar in Chomsky Normal Form

• String

Output:

find if

46

Fall 2003

The Algorithm

• Grammar :

• String :

Input example:

47

Fall 2003

48

Fall 2003

49

Fall 2003

50

Fall 2003

51

Fall 2003

Therefore:

Time Complexity:

The CYK algorithm can be

easily converted to a parser

(bottom up parser)

Observation: