2,908 views
1. An identifier in a programming language consists of up to six letters and digits of which the first character must be a letter. Derive a regular expression for the identifier.

2. Build an $LL(1)$ parsing table for the language defined by the $LL(1)$ grammar with productions

$\text{Program} \rightarrow \text{ begin } d \text{ semi } X\text{ end}$

$X \rightarrow d \text{ semi } X \mid sY$

$Y \rightarrow \text{ semi } s Y \mid \epsilon$

a.  $(letter)(letter+digit+\epsilon)^5$

b.

1. Program $\rightarrow$ begin d semi $X$ end
2. $X \rightarrow d \ semi X$
3. $X \rightarrow sY$
4. $Y \rightarrow semi \ sY$
5. $Y \rightarrow \epsilon$

$$\begin{array}{|l|l|l|}\hline \textbf{Variable} & \textbf{First} & \textbf{Follow} \\\hline \text{Program} & \text{begin} & \text{\} \\\hline \text{X} & \text{d, s} & \text{end} \\\hline \text{Y} & \text{semi, } \epsilon & \text{end}\\\hline \end{array}$$
Here, First$(Y)$ contains $\epsilon$ so we need to add   $Y \rightarrow \epsilon$ to Follow$(Y)$
$$\begin{array}{|l|l|l|l|l|l|l|}\hline \textbf{Variable} & \textbf{begin} & \textbf{d} & \textbf{semi} & \textbf{s} & \text{end} & \textbf{\} \\\hline \text{Program} & \text{A} & \text{} & \text{}& \text{}& \text{}& \text{}\\\hline \text{X} & \text{} & \text{B} & \text{} & \text{C} & \text{} & \text{} \\\hline \text{Y} & \text{}& \text{} & \text{D} & \text{} & \text{Y} \rightarrow \epsilon \\\hline \end{array}$$

by

for part a) (letter)(letter+digit+epsilon)5

y->epsilon should also be under $. please correct if wrong a.$(letter)(letter + digit + epsilon)^5$b. 1.program ---> begin d semi X end 2. X -----> d semi x 3. | sY 4. Y -----> semi sY 5. | epsilon begin d semi s end$
program       1
X                            2                      3
Y                                       4                                5

How did you decide "semi" is variable or terminal?
terminals are given in small letters.
if any symbol(semi in this case) is a non terminal, then we must have it at the LHS of a production.So semi is a terminal.