1 of 76

Context-Free Languages

1

Fall 2003

2 of 76

Regular Languages

2

Fall 2003

Regular Languages

3 of 76

Regular Languages

3

Fall 2003

Regular Languages

Context-Free Languages

4 of 76

4

Fall 2003

Context-Free Languages

Pushdown

Automata

Context-Free

Grammars

stack

automaton

5 of 76

Context-Free Grammars

5

Fall 2003

6 of 76

Example

6

Fall 2003

A context-free grammar :

A derivation:

7 of 76

7

Fall 2003

A context-free grammar :

Another derivation:

8 of 76

8

Fall 2003

(((( ))))

Describes parentheses:

9 of 76

9

Fall 2003

A context-free grammar :

A derivation:

Example

10 of 76

10

Fall 2003

A context-free grammar :

Another derivation:

11 of 76

11

Fall 2003

12 of 76

12

Fall 2003

A context-free grammar :

A derivation:

Example

13 of 76

13

Fall 2003

A context-free grammar :

A derivation:

14 of 76

14

Fall 2003

() ((( ))) (( ))

Describes

matched

parentheses:

15 of 76

Definition: Context-Free Grammars

15

Fall 2003

Grammar

Productions of the form:

String of variables

and terminals

Variables

Terminal

symbols

Start

variable

Variable

16 of 76

16

Fall 2003

17 of 76

Definition: Context-Free Languages

A language is context-free

if and only if

there is a context-free grammar

with

17

Fall 2003

18 of 76

Derivation Order

18

Fall 2003

Leftmost derivation:

Rightmost derivation:

19 of 76

19

Fall 2003

Leftmost derivation:

Rightmost derivation:

20 of 76

Derivation Trees

20

Fall 2003

21 of 76

21

Fall 2003

22 of 76

22

Fall 2003

23 of 76

23

Fall 2003

24 of 76

24

Fall 2003

25 of 76

25

Fall 2003

Derivation Tree

26 of 76

26

Fall 2003

yield

Derivation Tree

27 of 76

Partial Derivation Trees

27

Fall 2003

Partial derivation tree

28 of 76

28

Fall 2003

Partial derivation tree

29 of 76

29

Fall 2003

Partial derivation tree

sentential

form

yield

30 of 76

30

Fall 2003

Same derivation tree

Sometimes, derivation order doesn’t matter

Leftmost:

Rightmost:

31 of 76

Ambiguity

31

Fall 2003

32 of 76

32

Fall 2003

leftmost derivation

33 of 76

33

Fall 2003

leftmost derivation

34 of 76

34

Fall 2003

Two derivation trees

35 of 76

35

Fall 2003

The grammar

is ambiguous:

string

has two derivation trees

36 of 76

36

Fall 2003

string

has two leftmost derivations

The grammar

is ambiguous:

37 of 76

37

Fall 2003

Definition:

A context-free grammar is ambiguous

if some string has:

two or more derivation trees

38 of 76

38

Fall 2003

In other words:

A context-free grammar is ambiguous

if some string has:

two or more leftmost derivations

(or rightmost)

39 of 76

39

Fall 2003

Why do we care about ambiguity?

take

40 of 76

40

Fall 2003

41 of 76

41

Fall 2003

42 of 76

42

Fall 2003

Correct result:

43 of 76

43

Fall 2003

We want to remove ambiguity

Ambiguity is bad for programming languages

44 of 76

44

Fall 2003

We fix the ambiguous grammar:

New non-ambiguous grammar:

45 of 76

45

Fall 2003

46 of 76

46

Fall 2003

Unique derivation tree

47 of 76

47

Fall 2003

The grammar :

is non-ambiguous:

Every string has

a unique derivation tree

48 of 76

Another Ambiguous Grammar

48

Fall 2003

IF_STMT

if EXPR then STMT

if EXPR then STMT else STMT

49 of 76

49

Fall 2003

If expr1 then if expr2 then stmt1 else stmt2

IF_STMT

expr1

then

else

if

expr2

then

STMT

stmt1

if

IF_STMT

expr1

then

else

if

expr2

then

STMT

stmt2

if

stmt1

stmt2

50 of 76

Inherent Ambiguity

Some context free languages

have only ambiguous grammars

50

Fall 2003

Example:

51 of 76

51

Fall 2003

The string

has two derivation trees

52 of 76

Compilers

52

Fall 2003

53 of 76

53

Fall 2003

Compiler

Program

v = 5;

if (v>5)

x = 12 + v;

while (x !=3) {

x = x - 3;

v = 10;

}

......

Add v,v,0

cmp v,5

jmplt ELSE

THEN:

add x, 12,v

ELSE:

WHILE:

cmp x,3

...

Machine Code

54 of 76

54

Fall 2003

Lexical

analyzer

parser

Compiler

program

machine

code

input

output

55 of 76

55

Fall 2003

A parser knows the grammar

of the programming language

56 of 76

56

Fall 2003

Parser

PROGRAM STMT_LIST

STMT_LIST STMT; STMT_LIST | STMT;

STMT EXPR | IF_STMT | WHILE_STMT

| { STMT_LIST }

EXPR EXPR + EXPR | EXPR - EXPR | ID

IF_STMT if (EXPR) then STMT

| if (EXPR) then STMT else STMT

WHILE_STMT while (EXPR) do STMT

57 of 76

57

Fall 2003

The parser finds the derivation

of a particular input

10 + 2 * 5

Parser

E -> E + E

| E * E

| INT

E => E + E

=> E + E * E

=> 10 + E*E

=> 10 + 2 * E

=> 10 + 2 * 5

input

derivation

58 of 76

58

Fall 2003

10

E

2

5

E => E + E

=> E + E * E

=> 10 + E*E

=> 10 + 2 * E

=> 10 + 2 * 5

derivation

derivation tree

E

+

*

59 of 76

59

Fall 2003

10

E

2

5

derivation tree

E

+

*

mult a, 2, 5

add b, 10, a

machine code

60 of 76

Parsing

60

Fall 2003

61 of 76

61

Fall 2003

grammar

Parser

input

string

derivation

62 of 76

62

Fall 2003

Example:

Parser

derivation

input

?

63 of 76

63

Fall 2003

Exhaustive Search

Phase 1:

All possible derivations of length 1

Find derivation of

64 of 76

64

Fall 2003

65 of 76

65

Fall 2003

Phase 2

Phase 1

66 of 76

66

Fall 2003

Phase 2

Phase 3

67 of 76

67

Fall 2003

Final result of exhaustive search

Parser

derivation

input

(top-down parsing)

68 of 76

68

Fall 2003

Time complexity of exhaustive search

Suppose there are no productions of the form

Number of phases for string :

69 of 76

69

Fall 2003

Time for phase 1:

possible derivations

For grammar with rules

70 of 76

70

Fall 2003

Time for phase 2:

possible derivations

71 of 76

71

Fall 2003

Time for phase :

possible derivations

72 of 76

72

Fall 2003

Total time needed for string :

Extremely bad!!!

phase 1

phase 2

phase 2|w|

73 of 76

73

Fall 2003

There exist faster algorithms

for specialized grammars

S-grammar:

symbol

string

of variables

appears once

Pair

74 of 76

74

Fall 2003

S-grammar example:

Each string has a unique derivation

75 of 76

75

Fall 2003

In the exhaustive search parsing

there is only one choice in each phase

For S-grammars:

Total time for parsing string :

Time for a phase:

76 of 76

76

Fall 2003

For general context-free grammars:

There exists a parsing algorithm

that parses a string

in time

(we will show it in the next class)