The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+13 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$

asked in Compiler Design by Veteran (59.5k points)
edited by | 733 views

2 Answers

+16 votes
Best answer

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

b. Program $\rightarrow$ begin d semi $X$ end  --------------$A$

$X \rightarrow d \ semi X$  -------$B$

$X \rightarrow sY$--------------$C$

$Y \rightarrow semi \ sY$------------$D$ 

 $Y \rightarrow \epsilon$ ---------------$E$

Variable First Follow
Program begin  $
$X$ $d,s$ end
$Y$ $semi$, $\epsilon$ end

Here First$(Y)$ contains $\epsilon$ so we need to add   $Y \rightarrow \epsilon$ at follow$(Y)$ 

Variable begin $d$ semi $s$ end $
Program $A$          
$X$   $B$   $C$    
$Y$     $D$   $Y \rightarrow \epsilon$  
answered by Boss (25.8k points)
edited by
How did you decide "semi" is variable or terminal?
"semi" cannot be a variable as we do not have any productions from it.

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

please edit part a.
+6 votes

  $(letter)(letter + digit + epsilon)^5$
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

answered by Veteran (55.1k points)
edited by

Given is, Programs →  begin d semi X end

 while u considered program ---> begin s end 



 Programs →  begin d semi X end

then why program ---> begin s end  is considered here

@Digvijay Pandey  entry '5' should be in 'y' row and 'end' column

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.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,939 questions
45,453 answers
48,208 users