Understanding LL(1) Grammars and Computing First & Follow Sets

Exploring LL(1) grammars and the computation of First and Follow sets for non-terminals. This involves defining FIRST(.) as the set of tokens that appear as the first token in strings derived from a non-terminal and FOLLOW(A) as the terminals that can appear immediately to the right of A in the sentential form. The process involves iterating through the productions to determine the correct expansions and sets of tokens.

• LL(1) Grammars
• Computing
• First Sets
• Follow Sets
• Recursive Descent Parser

beaut Follow

Uploaded on Oct 08, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. CS314 Section 5 Recitation 5 Long Zhao (lz311@rutgers.edu) LL(1) Grammars Recursive Descent Parser Slides available at http://www.ilab.rutgers.edu/~lz311/CS314

2. LL(1) Grammars For any two productions A ::= | with (T N) and (T N) , we would like a distinct way of choosing the correct production to expand. For (T N) , define FIRST ( ) as the set of tokens that appear as the first token in some string derived from . For a non-terminal A, define FOLLOW (A) as the set of terminals that can appear immediately to the right of A in some sentential form.

3. Computing First Sets Compute First(X): initialize: if T is a terminal symbol then First (T) = {T} if T is non-terminal then First(T) = { } while First(X) changes (for any X) do for all X and all rules (X:= ABC...) do First (X) := First(X) U First (ABC...) where First(ABC...) := F1 U F2 U F3 U ... and F1 := First (A) F2 := First (B), if A is Nullable; emptyset otherwise F3 := First (C), if A is Nullable & B is Nullable; emp... ...

4. Computing Follow Sets Follow(X) is computed iteratively base case: initially, we assume nothing in particular follows X (when computing, Follow (X) is initially { }) inductive case: if (Y := s1 X s2) for any strings s1, s2 then Follow (X) = First (s2) if (Y := s1 X s2) for any strings s1, s2 then Follow (X) = Follow(Y), if s2 is Nullable

5. Computing First & Follow Sets FIRST FOLLOW S ::= ABCDE S A ::= a| A B ::= b| B C ::= c C D ::= d| D E ::= e| E

6. Computing First & Follow Sets FIRST FOLLOW S ::= ABCDE S A ::= a| A { a, } B ::= b| B { b, } C ::= c C { c } D ::= d| D { d, } E ::= e| E { e, }

7. Computing First & Follow Sets FIRST FOLLOW S ::= ABCDE S { a, b, c } A ::= a| A { a, } B ::= b| B { b, } C ::= c C { c } D ::= d| D { d, } E ::= e| E { e, }

8. Computing First & Follow Sets FIRST FOLLOW S ::= ABCDE S { a, b, c } { EOF } A ::= a| A { a, } { b, c } B ::= b| B { b, } { c } C ::= c C { c } { d, e, EOF } D ::= d| D { d, } { e, EOF } E ::= e| E { e, } { EOF }

9. Computing First & Follow Sets FIRST FOLLOW S ::= ACB|CbB|Ba S A ::= da|BC A B ::= g| B C ::= h| C

10. Computing First & Follow Sets FIRST FOLLOW S ::= ACB|CbB|Ba S A ::= da|BC A { d } B ::= g| B { g, } C ::= h| C { h, }

11. Computing First & Follow Sets FIRST FOLLOW S ::= ACB|CbB|Ba S { d, g, h, , b, a } A ::= da|BC A { d, g, h, } B ::= g| B { g, } C ::= h| C { h, }

12. Computing First & Follow Sets FIRST FOLLOW S ::= ACB|CbB|Ba S { d, g, h, , b, a } { EOF } A ::= da|BC A { d, g, h, } { h, g, EOF } B ::= g| B { g, } { EOF, a, h, g } C ::= h| C { h, } { g, EOF, b, h }

13. LL(1) Grammars Define FIRST+( ) for rule A ::= FIRST( ) - { } Follow(A), if FIRST( ) FIRST( ) otherwise A grammar is LL(1) iff (A ::= and A ::= ) implies FIRST+( ) FIRST+( ) =

14. LL(1) Grammars FIRST FOLLOW S ::= ACB|CbB|Ba S { d, g, h, , b, a } { EOF } A ::= da|BC A { d, g, h, } { h, g, EOF } B ::= g| B { g, } { EOF, a, h, g } C ::= h| C { h, } { g, EOF, b, h } FIRST+(ACB) = { d, g, h, EOF } FIRST+(CbB) = { h, b } FIRST+(Ba) = { g, a } FIRST+(ACB) FIRST+(CbB) FIRST+(Ba) , so it s not LL(1)

15. LL(1) Grammars FIRST FOLLOW E ::= iT E { i } { EOF } T ::= +iT| T { +, } { EOF } FIRST+(+iT) = { + } FIRST+( ) = { } { EOF } = { EOF } FIRST+(+iT) FIRST+( ) = , so it s LL(1)

16. Computing First & Follow Sets Given the follow rules, compute the First and Follow Sets of all non-terminal symbols, and are they LL(1)? S ::= Bb|Cd, B ::= aB| , C ::= cC| S ::= aBDh, B ::= cC, C ::= bC| , D ::= EF, E ::= g| , F ::= f|

17. Computing First & Follow Sets FIRST FOLLOW S ::= Bb|Cd S B ::= aB| B { a, } C ::= cC| C { c, }

18. Computing First & Follow Sets FIRST FOLLOW S ::= Bb|Cd S { a, b, c, d } B ::= aB| B { a, } C ::= cC| C { c, }

19. Computing First & Follow Sets FIRST FOLLOW S ::= Bb|Cd S { a, b, c, d } { EOF } B ::= aB| B { a, } { b } C ::= cC| C { c, } { d }

20. LL(1) ? FIRST FOLLOW S ::= Bb|Cd S { a, b, c, d } { EOF } B ::= aB| B { a, } { b } C ::= cC| C { c, } { d } FIRST+(Bb) = { a, b }, FIRST+(Cd) = { c, d }, FIRST+(Bb) FIRST+(Cd) = FIRST+(aB) = { a }, FIRST+( ) = { b }, FIRST+(aB) FIRST+( ) = FIRST+(cC) = { c }, FIRST+( ) = { d }, FIRST+(cC) FIRST+( ) = It s LL(1)

21. Computing First & Follow Sets FIRST FOLLOW S ::= aBDh S { a } B ::= cC B { c } C ::= bC| C { b, } D ::= EF D E ::= g| E { g, } F ::= f| F { f, }

22. Computing First & Follow Sets FIRST FOLLOW S ::= aBDh S { a } B ::= cC B { c } C ::= bC| C { b, } D ::= EF D { g, f, } E ::= g| E { g, } F ::= f| F { f, }

23. Computing First & Follow Sets FIRST FOLLOW S ::= aBDh S { a } { EOF } B ::= cC B { c } { g, f, h } C ::= bC| C { b, } { g, f, h } D ::= EF D { g, f, } { h } E ::= g| E { g, } { f, h } F ::= f| F { f, } { h }

24. LL(1) ? FIRST FOLLOW S ::= aBDh S { a } { EOF } B ::= cC B { c } { g, f, h } C ::= bC| C { b, } { g, f, h } D ::= EF D { g, f, } { h } E ::= g| E { g, } { f, h } F ::= f| F { f, } { h } FIRST+(bc) = { b }, FIRST+( ) = { g, f, h }, FIRST+(bc) FIRST+( ) = FIRST+(g) = { g }, FIRST+( ) = { f, h }, FIRST+(g) FIRST+( ) = FIRST+(f) = { f }, FIRST+( ) = { h }, FIRST+(f) FIRST+( ) = It s LL(1)

25. Construct Parsing Table For each production A ::= do: For each terminal t First( ), do Table[A, t] = If in First( ), for each terminal t Follow(A), do Table[A, t] =

26. Parsing Table FIRST FOLLOW E ::= iT E { i } { EOF } T ::= +iT| T { +, } { EOF } i + EOF E iT T +iT

27. Parsing Table (Not LL(1)) FIRST FOLLOW S ::= ACB|CbB|Ba S { d, g, h, , b, a } { EOF } A ::= da|BC A { d, g, h, } { h, g, EOF } B ::= g| B { g, } { EOF, a, h, g } C ::= h| C { h, } { g, EOF, b, h } a b d g h EOF S Ba CbB ACB ACB|Ba ACB|CbB A da A ::= BC A ::= BC B g| C h|

28. Construct Parsing Table (Exercise) Given the follow rules and FIRST and FOLLOW sets, compute the Parsing Table for them: FIRST FOLLOW S ::= Bb|Cd S { a, b, c, d } { EOF } B ::= aB| B { a, } { b } C ::= cC| C { c, } { d } FIRST FOLLOW S ::= aBDh S { a } { EOF } B ::= cC B { c } { g, f, h } C ::= bC| C { b, } { g, f, h } D ::= EF D { g, f, } { h } E ::= g| E { g, } { f, h } F ::= f| F { f, } { h }

29. Parsing Table FIRST FOLLOW S ::= Bb|Cd S { a, b, c, d } { EOF } B ::= aB| B { a, } { b } C ::= cC| C { c, } { d } a b c d EOF S Bb Bb Cd Cd B aB C cC

30. Parsing Table FIRST FOLLOW S ::= aBDh S { a } { EOF } B ::= cC B { c } { g, f, h } C ::= bC| C { b, } { g, f, h } D ::= EF D { g, f, } { h } E ::= g| E { g, } { f, h } F ::= f| F { f, } { h } a b c g f h EOF aBDh S cC B bC C EF EF D g E f F

31. Recursive Descent Parser Each non terminal has an associated parsing procedure that can recognize any sequence of tokens generated by that non terminal. There is a main routine to initialize all globals (e.g.: token) and call the start symbol. On return, check whether token == eof, and whether errors occurred. Within a parsing procedure, both non terminals and terminals can be matched : non terminal A call parsing procedure for A token t compare t with current input token; if match, consume input, otherwise ERROR

32. Recursive Descent Parser i + EOF Grammar: E ::= iT T ::= +iT| E iT T +iT T() { if (token == + ) main() { E() { match(char t) match( + ); { token = next_token(); { match( i ); if (token == i ) E(); if (token == t) T(); { if (token == EOF) token = next_token(); } match( i ); success(); else else T(); else error(); return; } error(); } } } }

33. Recursive Descent Parser Call Stack: i + i + i m(+) m(i) T() m(i) T() T() T() T() E() E() E() E() E() E() EOF EOF EOF EOF EOF EOF EOF i + i + i i + i + i i + i + i i + i + i i + i + i i + i + i i + i + i m(i) T() m(+) T() T() T() T() T() T() T() T() T() E() E() E() E() E() E() EOF EOF EOF EOF EOF EOF EOF i + i + i i + i + i i + i + i i + i + i i + i + i i + i + i i + i + i