UP Lecture 18

Compilers
Error Recovery - Follow Set
(202503)

Transcript

1. jgs Compilers Lecture 18: Error Handling – Follow Set Dr. Javier Gonzalez-Sanchez jgonzalezs@up.edu.mx
2. Dr. Javier Gonzalez-Sanchez | Compilers | 2 jgs Parser | Error Recovery Rule FIRST set FOLLOW set PROGRAM { EOF BODY FIRST (PRINT) U FIRST (ASIGNMENT) U FIRST(VARIABLE) U FIRST (WHILE) U FIRST(IF) U FIRST (RETURN) } PRINT print ; ASSIGNMENT identifier ; VARIABLE int, float, boolean, void, char, string ; WHILE while } U FIRST(BODY) IF if } U FIRST(BODY) RETURN return ; EXPRESSION FIRST(X) ), ; X FIRST(Y) | U FOLLOW(EXPRESSION) Y ! U FIRST(R) & U FOLLOW(X) R FIRST(E) FOLLOW(Y) E FIRST (A) !=, ==, >, < U FOLLOW(R) A FIRST (B) -, + U FOLLOW(E) B - U FIRST (C) *, /, U FOLLOW(A) C integer, octal, hexadecimal, binary, true, false, string, char, float, identifier, ( FOLLOW(B)
3. jgs Test Yourselves Calculate FIRST set
4. Dr. Javier Gonzalez-Sanchez | Compilers | 4 jgs FIRST set <S> → <A><B><C> <S> → <F> <A> → <E><F>d <A> → a <B> → a<B>b <B> → ε <C> → c<C> <C> → d <E> → e<E> <E> → <F> <F> → <F>f <F> → ε
5. Dr. Javier Gonzalez-Sanchez | Compilers | 5 jgs FIRST set S → ABC S → F A → EFd A → a B → aBb B → ε C → cC C → d E → eE E → F F → Ff F → ε rule FIRST set - evolution S ø {a, ε} {a, ε, e, f} {a, ε, e, f, d} A ø {a} {a, e} {a, e, f, d} B ø {a, ε} C ø {c, d} E ø {e} {e, ε} {e, ε, f} F ø {ε} {ε, f}
6. Dr. Javier Gonzalez-Sanchez | Compilers | 6 jgs FIRST set | Exercise <X> → <A> | <A> a <A> → <B> | <B> b <B> → <C><D><E> | c d e | <C> c <D> d <E> e <C> → one <D> → two <E> → three
7. Dr. Javier Gonzalez-Sanchez | Compilers | 7 jgs FIRST set | Exercise <X> → <A> <X> → <A> a <A> → <B> <A> → <B> b <B> → <C><D><E> <B> → c d e <B> → <C> c <D> d <E> e <C> → one <D> → two <E> → three OPTION 1: FIRST(X) = {c, one} FIRST(A) = {c, one} FIRST(B) = {c, one} FIRST(C) = {one} FIRST(D) = {two} FIRST(E) = {three} OPTION 2: FIRST(X) = {c, one, ε} FIRST(A) = {b, c, one} FIRST(B) = {c, one} FIRST(C) = {one} FIRST(D) = {two} FIRST(E) = {three}
8. Dr. Javier Gonzalez-Sanchez | Compilers | 8 jgs FIRST set | Exercise <X> → <A> <X> → <A> a <A> → <B> <A> → <B> b <B> → <C><D><E> <B> → c d e <B> → <C> c <D> d <E> e <C> → one <C> → ε <D> → two <D> → ε <E> → three FIRST(X) = {c, one, three, two} FIRST(A) = {c, one, three, two} FIRST(B) = {c, one, three, two} FIRST(C) = {one, ε} FIRST(D) = {two, ε} FIRST(E) = {three}
9. jgs Calculating the Follow Set
10. Dr. Javier Gonzalez-Sanchez | Compilers | 10 jgs FOLLOW set Definition FOLLOW (a) is the set of tokens that can follow the construction a. Example <E> → <A> {+ <A>} <A> → <B> {* <B>} <B> → <C> | <C> <C> → integer FOLLOW(E) = {$} // $ represents end of input, i.e., EOF FOLLOW(A) = {+, $} FOLLOW(B) = {*, +, $} FOLLOW(C) = {*, +, $}
11. Dr. Javier Gonzalez-Sanchez | Compilers | 12 jgs Calculate the FOLLOW set R2 R2 R2 R2
12. Dr. Javier Gonzalez-Sanchez | Compilers | 13 jgs Calculate the FOLLOW set 1.First put $ (the end of input marker) in Follow(S) (S is the start symbol) 2.If there is a production A → aBb, (where a can be a whole string) then everything in FIRST(b) except for ε is placed in FOLLOW(B). (apply the rule 4 in calculate FIRST set) 3.If there is a production A → aB, then add FOLLOW(A) to FOLLOW(B) 4.If there is a production A → aBb, where FIRST(b) contains ε, then add FOLLOW(A) to FOLLOW(B)
13. Dr. Javier Gonzalez-Sanchez | Compilers | 14 jgs FOLLOW set Define FOLLOW (BODY) FIRST(BODY) = }
14. Dr. Javier Gonzalez-Sanchez | Compilers | 15 jgs FOLLOW set Define FOLLOW (C)
15. Dr. Javier Gonzalez-Sanchez | Compilers | 16 jgs FOLLOW set <S> → <A><B><C> <S> → <F> <A> → <E><F>d <A> → a <B> → a<B>b <B> → ε <C> → c<C> <C> → d <E> → e<E> <E> → <F> <F> → <F>f <F> → ε
16. Dr. Javier Gonzalez-Sanchez | Compilers | 17 jgs FOLLOW set S → ABC S → F A → EFd A → a B → aBb B → ε C → cC C → d E → eE E → F F → Ff F → ε rule FOLLOW set - evolution S {eof} A {a} {a, c, d} B {c, d} {c, d, b} C {eof} E {f} {f, d} F {eof} {eof, d} {eof, d, f} FIRST sets: S={a,ε,e,f,d} A={a, e, f, d} B={a, ε} C= {c, d} E={e, ε, f} F={ε,f}
17. Dr. Javier Gonzalez-Sanchez | Compilers | 18 jgs Another Example <E> → <T> {+<T>} <T> → <F> {*<F>} <F> → (<E>) | integer FIRST (E) = {(, integer} FIRST (T) = {(, integer} FIRST (F) = {(, integer} FOLLOW(E) = {$, )} FOLLOW(T) = {$, ),+ } FOLLOW(F) = {$, ),+, * }
18. jgs Prediction Rules
19. Dr. Javier Gonzalez-Sanchez | Compilers | 20 jgs Prediction Rules Rule 1. It should always be possible to choose among several alternatives in a grammar rule. FIRST(R1 ) FIRST(R2 ) FIRST(R3 )... FIRST(Rn ) = Ø BODY
20. Dr. Javier Gonzalez-Sanchez | Compilers | 21 jgs Prediction Rules Rule 2. For any optional part, no token that can begin the optional part should also be able to appear immediately after it. FIRST(RULE) != FOLLOW(RULE) BODY PROGRAM
21. jgs Error Recovery
22. Dr. Javier Gonzalez-Sanchez | Compilers | 24 jgs Error Recovery When parsing A: - The parser expects the current token to be in FIRST(A). Remember FIRST (terminal) = {terminal} - If it’s not, the parser knows that a syntax error has occurred. Report it. To recover: - The parser skips tokens until it finds a token in FOLLOW(A).
23. Dr. Javier Gonzalez-Sanchez | Compilers | 25 jgs Parser | Error Recovery PROGRAM Line N: expected { Line N: expected } currentToken++; Searching for FIRST(BODY) or }
24. Dr. Javier Gonzalez-Sanchez | Compilers | 26 jgs Parser | Error Recovery Line N: expected ; Line N: expected identifier or keyword currentToken++; Searching for FIRST(BODY) or FOLLOW(BODY) BODY
25. Dr. Javier Gonzalez-Sanchez | Compilers | 27 jgs Parser | Error Recovery ASSIGNMENT Line N: expected = currentToken++; Searching for FIRST(EXPRESSION) or FOLLOW(EXPRESSION)
26. Dr. Javier Gonzalez-Sanchez | Compilers | 28 jgs Parser | Error Recovery VARIABLE Line N: expected identifier
27. Dr. Javier Gonzalez-Sanchez | Compilers | 29 jgs Parser | Error Recovery WHILE Line N: expected ( Line N: expected ) currentToken++; Searching for FIRST(EXPRESSION) or ) currentToken++; Searching for FIRST(PROGRAM) or FOLLOW(PROGRAM)
28. Dr. Javier Gonzalez-Sanchez | Compilers | 30 jgs Parser | Error Recovery IF Line N: expected ( Line N: expected ) currentToken++; Searching for FIRST(EXPRESSION) or ) currentToken++; Searching for FIRST(PROGRAM) or FOLLOW(PROGRAM)
29. Dr. Javier Gonzalez-Sanchez | Compilers | 31 jgs Parser | Error Recovery RETURN
30. Dr. Javier Gonzalez-Sanchez | Compilers | 32 jgs Parser | Error Recovery PRINT Line N: expected ( Line N: expected ) currentToken++; Searching for FIRST(EXPRESSION) or )
31. Dr. Javier Gonzalez-Sanchez | Compilers | 33 jgs Parser | Error Recovery EXPRESSION X Y R E A B
32. Dr. Javier Gonzalez-Sanchez | Compilers | 34 jgs Parser | Error Recovery C Line N: expected value, identifier or ( Line N: expected )
33. Dr. Javier Gonzalez-Sanchez | Compilers | 36 jgs Homework Working on your Parser
34. Dr. Javier Gonzalez-Sanchez | Compilers | 37 jgs Questions
35. jgs Compilers Javier Gonzalez-Sanchez, Ph.D. jgonzalezs@up.edu.mx Spring 2025 Copyright. These slides can only be used as study material for the Compilers course at Universidad Panamericana. They cannot be distributed or used for another purpose.