Predict Sets

TODO

I need to recorganize this entire note when I study for midterms

Here I call a ‘u’ non-terminal and something like A, a terminal

1. Convert grammar from EBNF to BNF
2. Determine nullable non-terminals (EPS)
   1. Which terminals go to $ϵ$? (evaluates to 0 | 1)
3. Determine First sets
   1. What is the first terminals we see for each non-terminal for our grammar?
   2. What does each sub-inout evaluate to (‘u’, ‘w’, etc)
4. Determine Follow sets
   1. What follows each non-terminal?
   2. Where is a symbol used? The follow of a symbol is the follow of the LHS that uses the symbol
   3. If a non-terminal follows the symbol use, then the follow is just that non-terminal
   4. Once we reach a non-terminal (end-case) back-propagate the result up to where we start
5. Determine predict sets
   1. For a given predict set, we want to know what it will evaluate to, expressed in first and follow sets as well as terminals
   2. Predict sets are used when we inspect, this tells us what production to use in our BNF
   3. If a production can be empty you need to add the empty follow set to the predict set

If the predict sets are disjoint, write a recursive parser → LL(1) If the predict sets intersect, refactor the grammar to be LL(1) → Not LL(1)

Read for once in your life

Probably read the textbook since theoretically this is kind of abstract, in practice I should be able to just pick up the patterns.

EBNF to BNF

• Remove stars and bars (|) and add EOFs
• For an input string $S_4$, we have one or many productions (on the left hand side we coupld have multiple terminals)
  • Note to accommodate for (* / many), use recursion
  • You use the predict set to decide which production to use based on the next token (inputs here)

We can turn this idea into code…