Quiz 3 FIRST FOLLOW PREDICT EPS

$$\begin{array}{rl}\text{Program}& \to \text{Stmts }\$\\ \text{Stmts}& \to \text{Stmts }\text{Stmts\_Tail}\\ \text{Stmt}& \to \text{until }(\text{Stmts };\text{ id})\mid \text{id}\\ \text{Stmts\_Tail}& \to ,\text{ Stmt }\text{Stmts\_Tail}\mid ϵ\end{array}$$

EPS FIRST FOLLOW PREDUCT

• epsilon, $ϵ$ cant be in first, follow, or predict!
• EPS(a), if a = $ϵ$ ? true || false (Boolean operation)
• First(a) all possible first outcomes for some a. Eg. First(stmt) = until | id
• Follow:
  • What can come after $a$ on the right hand side of the expr? Eg. FOLLOW(a) = ; $
  • If a is in possible child, put $or$\epsilon$
  • Set of non terminals
• Predict: (requires some $A\to a$)
  • if a can result in $ϵ$ → $First(a)\cup Follow(A)$
    • Union means all unique elements in both sets (basically no elements shared but combine both)
  • if a = $ϵ$ → just take FIRST(A)

p. 121 of textbook

$$\begin{array}{rl}\text{EPS}(\alpha )& \equiv \text{if }\alpha {⟶}^{\ast }e\text{ then true else false}\\ \text{FIRST}(\alpha )& \equiv \{c:\alpha {⟶}^{\ast }c\beta \}\\ \text{FOLLOW}(A)& \equiv \{c:S{⟶}^{+}\alpha Ac\beta \}\\ \text{PREDICT}(A⟶\alpha )& \equiv \text{FIRST}(\alpha )\cup (\text{if EPS}(\alpha )\text{ then FOLLOW}(A)\text{ else }\varnothing )\end{array}$$

parse stack

What is the content of the parse stack, if we run the table-driven top down parser algorithm on

     until (s1, s2, s3; cond)       and “s1” appears for the first time in the top of the stack?

Using the parse tree at the top, start for the Program, replace program with Stmts, and keep expanding eg. Program, \ \rightarrow Stmts, Stmts_Tail$$, then one would expand Both Stmts and Stmts_tail until s_1 is reached. When until is reached use whatever inside until argument (basically each stack item is just some command to follow with the given grammer)