Predict Sets

  • Tells us whether grammar is LL(1) or not. Just compute the predict set for each production and check the disjoint property!
  • Used during parsing to choose a production

Left Recursion

Left recursion makes a grammar non-LL(1). A production of the form

\[A ::= A \sigma \hspace{5pt} | \hspace{5pt} \beta\]

can be replaced in the grammer with

\[\begin{align} A &::= \beta B \nonumber \\ B &::= \sigma B \hspace{5pt} | \hspace{5pt} \epsilon \nonumber \end{align}\]

This is an equivalent grammar without left-recursion. The same sentences can be generated. An example:

ident_list ::= ident | ident_list, ident

becomes

ident_list ::= ident ident_list_tail
ident_list_tail ::= , ident ident_list_tail | $\epsilon$

You can also transform to EBNF:

\[A ::= \beta \sigma *\]

Need to be somewhat careful when applying transformations. Losing the left-recursion via transformations can cause unintended loss of information that changes the intention of the grammar.

More non-LL(1) examples

Consider

\[A ::= \alpha \beta \hspace{5pt} | \hspace{5pt} \alpha \gamma.\]

This can be transformed using left factorization

\[\begin{align} A &::= \alpha \beta \nonumber \\ B &::= \beta \hspace{5pt} | \hspace{5pt} \gamma. \nonumber \end{align}\]

Can write this as

\[A ::= \alpha ( \beta \hspace{5pt} | \hspace{5pt} \gamma ).\]

How can me make a parser?

  • Given an LL(1) grammar, we can systematically construct a recursive descent parser.
  • Our first parser will only recognize whether or not a sentence is legal.
  • Later we’ll construct a syntax tree
  • Compute the predict sets for each production
  • Rewrite the grammar so that each non-terminal is on the left side of exactly one production
  • For each non-terminal A, we will have a method void A() to parse that symbol