Determining the lookahead set of an $\mathrm{LL}(1)$-grammar

54 Views Asked by At

I would like to determine the lookahead set $\newcommand{\LA}[1]{\mathrm{LookAhead}_{#1}}\LA{1}(S)$ for the productions $P$ \begin{align*} \newcommand{\rewrite}{\longrightarrow} S &\rewrite Ab & S &\rewrite Cd & A &\rewrite aA \\ A &\rewrite \epsilon & C &\rewrite cC & C &\rewrite \epsilon\,. \end{align*} of the grammar $\newcommand{\set}[1]{\left\{#1\right\}}G = \newcommand{\perm}[1]{\left\langle#1\right\rangle}\perm{\Sigma, V, P, S} = \perm{\set{a, b, c, d}, \set{S, A,C}, P, S}$. Now in my head this is \begin{align*} \LA{1}(S) &= \LA{1}(A) \cup \LA{1}(C) \\ &= \set{a, \epsilon} \cup \set{c, \epsilon} = \set{\epsilon, a, c}, \end{align*} as the productions where $S$ is on the left side have $A$ and $C$ as the first variable, but once again my plans have been thwarted by an automatic assessment system. According to the submit form, the correct answer does not involve all of the strings $a$, $b$ and $\epsilon$. My guess is that the culprit is $\epsilon$, but I'm not sure why.

The set $\LA k (\alpha)$ is defined as \begin{align}\newcommand{\derive}{\Longrightarrow}\tag{1}\label{eq:LA} \LA k (\alpha) &= \set{ x \in \Sigma^\ast \mid \alpha\derive_G^\ast x, |x| < k } \\ &\cup \set{ x \in\Sigma^\ast \mid \alpha \derive_G^\ast x\beta, |x| = k, \beta \in (\Sigma\cup V)^\ast }, \end{align} but I don't see why this wouldn't allow empty strings $\epsilon$. What am I not getting here?

Edit

After the answer of @CalumGilhooley, I get the following derivations: \begin{alignat*}{3} S &\derive_G Ab &&\derive_G \epsilon b &&\derive_G b \\ S &\derive_G Ab &&\derive_G aAb &&\derive_G \ldots \\ S &\derive_G Cd &&\derive_G \epsilon d &&\derive_G d \\ S &\derive_G Cd &&\derive_G cCd &&\derive_G \ldots \end{alignat*} With one lookahead, we apply the productions until we end up with a single alphabet $\alpha\in\Sigma$ (a string of length one) at the front of the derivation, so if we run into the empty string, we need to go deeper. With a lookahead of length 2, based on the definition \eqref{eq:LA}, we would repeat the process until there were strings of length 2 and less in front of the derived strings, and so on.

With this logic the lookahead set $\LA 1(S) = \set{a, b, c, d}$. No empty strings attached.

1

There are 1 best solutions below

6
On BEST ANSWER

I think your mistake is in the line $\operatorname{LookAhead}_1(S) = \operatorname{LookAhead}_1(A) \cup \operatorname{LookAhead}_1(C).$

This is false because the rules $A \longrightarrow \epsilon$ and $C \longrightarrow \epsilon$ allow $S$ to produce $b$ and $d,$ respectively.

I get $\operatorname{LookAhead}_1(S) = \{a, b, c, d\}.$ Is that correct?