context free grammarrs

Download
Share  Add to  Flag Embed
Views:
 
Category: Education
     
 
License:   All Rights Reserved

Presentation Description

automata theory

Comments

Presentation Transcript

Context-Free Languages : 

1 Context-Free Languages

Slide 2: 

2 Regular Languages

Slide 3: 

3 Regular Languages Context-Free Languages

Slide 4: 

4 Context-Free Languages Pushdown Automata Context-Free Grammars stack automaton

Context-Free Grammars : 

5 Context-Free Grammars

Example : 

6 Example A context-free grammar : A derivation:

Slide 7: 

7 A context-free grammar : Another derivation:

Slide 8: 

8 (((( ))))

Slide 9: 

9 A context-free grammar : A derivation: Example

Slide 10: 

10 A context-free grammar : Another derivation:

Slide 11: 

11

Slide 12: 

12 A context-free grammar : A derivation: Example

Slide 13: 

13 A context-free grammar : A derivation:

Slide 14: 

14 () ((( ))) (( ))

Definition: Context-Free Grammars : 

15 Definition: Context-Free Grammars Grammar Productions of the form: is string of variables and terminals Variables Terminal symbols Start variables

Definition: Context-Free Languages : 

16 Definition: Context-Free Languages A language is context-free if and only if there is a grammar with

Derivation Order : 

17 Derivation Order

Slide 18: 

18

Derivation Trees : 

19 Derivation Trees

Slide 20: 

20

Slide 21: 

21

Slide 22: 

22

Slide 23: 

23

Slide 24: 

24 Derivation Tree

Slide 25: 

25 yield Derivation Tree

Partial Derivation Trees : 

26 Partial Derivation Trees Partial derivation tree

Slide 27: 

27 Partial derivation tree

Slide 28: 

28 Partial derivation tree sentential form yield

Slide 29: 

29 Same derivation tree Sometimes, derivation order doesn’t matter Leftmost: Rightmost:

Ambiguity : 

30 Ambiguity

Slide 31: 

31 leftmost derivation

Slide 32: 

32 leftmost derivation

Slide 33: 

33

Slide 34: 

34 The grammar is ambiguous: string has two derivation trees

Slide 35: 

35 string has two leftmost derivations The grammar is ambiguous:

Slide 36: 

36 Definition: A context-free grammar is ambiguous if some string has: two or more derivation trees

Slide 37: 

37 In other words: A context-free grammar is ambiguous if some string has: two or more leftmost derivations (or rightmost)

Slide 38: 

38 Why do we care about ambiguity? take

Slide 39: 

39

Slide 40: 

40

Slide 41: 

41 Correct result:

Slide 42: 

42 We want to remove ambiguity Ambiguity is bad for programming languages

Slide 43: 

43 We fix the ambiguous grammar: New non-ambiguous grammar:

Slide 44: 

44

Slide 45: 

45 Unique derivation tree

Slide 46: 

46 The grammar : is non-ambiguous: Every string has a unique derivation tree

Inherent Ambiguity : 

47 Inherent Ambiguity Some context free languages have only ambiguous grammars Example:

Slide 48: 

48 The string has two derivation trees