Lecture No. 17
Dated: 08-04-2025
Note that productions output are tracing out a leftmost derivation.
The grammar symbols on the stack make up left-sentential forms.
\(LL(1)\) Table Construction
Consider the start
\[S \to *\beta A \gamma\]
with \(b\) being the next token,1 we are trying to match \(\beta b \gamma\).
There are 2 possibilities.
- \(b\) belongs to an expansion of
A.- We can use any \(A \to \alpha\) if \(b \in FIRST(\alpha)\), meaning \(b\) can derive a
string[^2] from \(\alpha\).
- We can use any \(A \to \alpha\) if \(b \in FIRST(\alpha)\), meaning \(b\) can derive a
- \(b\) does not belong to an expansion of
A.- \(A \to \epsilon\) then \(S \to *\beta A b \omega\) which means \(b \in FOLLOW(A)\).
Any \(A \to \alpha\) can be used if \(\alpha\) expands to \(\epsilon\). We say that \(\epsilon \in FIRST(A)\) in this case.
Definition
\[FIRST(X) = \{b | X \to * ba\} \cup \{\epsilon | X \to * \epsilon\}\]