edited by
3,746 views
22 votes
22 votes
  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$

edited by

2 Answers

Best answer
27 votes
27 votes

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}$$

edited by
7 votes
7 votes

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

edited by

Related questions

46 votes
46 votes
2 answers
1
Kathleen asked Sep 25, 2014
13,763 views
Type checking is normally done duringlexical analysissyntax analysissyntax directed translationcode optimization
24 votes
24 votes
2 answers
2
Kathleen asked Sep 25, 2014
12,607 views
Which of the following statements is true?SLR parser is more powerful than LALRLALR parser is more powerful than Canonical LR parserCanonical LR parser is more powerful t...
12 votes
12 votes
4 answers
4
Kathleen asked Sep 26, 2014
4,328 views
Let $G_1 = (N, T, P, S_1)$ be a CFG where, $N=\{S_1, A, B\},T=\{a, b\}$ and $P$ is given by$$\begin{array}{l|l}S_1 \rightarrow a S_1 b &S_1 \rightarrow a B b \\S_1 \right...