compiler construction notes... the night before. macfheo2@mail.dcu.ie to build FOLLOW(B)... 1. Put $ in FOLLOW(<goal>) 2. If A → αBβ: (a) Put FIRST(β) - {ε} in FOLLOW(B) (b) If β = ε (i.e., A → αB) or ε ∈ FIRST(β) (i.e. β ⇒* ε) then put FOLLOW(A) in FOLLOW(B) Repeat until no more additions can be made. how do we construct an LL(1) parse table? 1. ∀ productions A → α: ∀a ∈ LOOKAHEAD(A → α), add A → α to M[A,a] 2. Set each undefined entry of M to error what condition on the table signifies that a grammar is not LL(1)? ∃M[A,a] with multiple entries what are the steps required to build LOOKAHEAD(A → α)? 1. Put FIRST(α) - {ε} in LOOKAHEAD(A → α) 2. If ε ∈ FIRST(α) then put FOLLOW(A) in LOOKAHEAD(A → α) for a non-terminal B, define the follow set of B? the set of terminals that can appear immediately to the right of B in some sentential form what is the follow set for a terminal symbol? there is none! when building FIRST(X), what's the third (longest) step? if X -> Y1Y2...Yk: (a) put FIRST(Y1)-{ε} in FIRST(X) (b) for(1 < i <= k) if ε ∈ FIRST(Y1)∩...∩FIRST(Yi-1) then put FIRST(Yi) - {ε} in FIRST(X) (c) if ε ∈ FIRST(Y1)∩...∩FIRST(Yk) then put ε in FIRST(X) repeat until no more additions can be made. when building FIRST(X), what's the second step? if there is a rule X -> ε, add ε to FIRST(X) if X is a nonterminal, what is FIRST(X)? { X } during LL(1) parsing, if the symbol on top of the stack is a terminal (including EOF), what does the parser do? it compares the symbol on the stack with the symbol on the input stream and if they are equal they are both removed. If they are not equal the parser reports an error and stops. when is a grammar ambiguous? If a grammar has more than one derivation for a single sentential form then it is ambiguous during LL(1) parsing, if the symbol on the top of the stack is a nonterminal, what does the parser do? it looks up in the parsing table for the rule to apply given this nonterminal and the symbol on the input stream. if it finds a rule, it pops the nonterminal and pushes the production corresponding to that rule (backwards, of course...) onto the stack. If the parsing table indicates that there is no such rule then it reports an error and stops. what is the key property of predictive parsing? when 2 productions A -> α and A -> β appear in the grammar, we want FIRST(α) ∩ FIRST(β) = 0 remove the left-recursion: A -> Aα | β | γ A -> NA' N -> β | γ A' -> αA' | ε transform A ::= Aa | B to remove left-recursion A ::= bA' A' ::= aA' | ε what is a sentential form? For a grammar G with start symbol S, any string a such that s -> *a is a sentential form what is a sentence in L(G)? if a belongs to Vt*, a is a sentence in L(G)