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

asked in Compiler Design by Veteran (59.7k points)
edited by | 836 views

2 Answers

+17 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 (26.1k points)
edited by
0
How did you decide "semi" is variable or terminal?
+1
"semi" cannot be a variable as we do not have any productions from it.
+3

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

0
please edit part a.
+6 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

answered by Veteran (55.6k points)
edited by
+1

Given is, Programs →  begin d semi X end

 while u considered program ---> begin s end 

why?

0
Given

 Programs →  begin d semi X end

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

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

0
How did you decide "semi" is variable or terminal?
+1
terminals are given in small letters.
0
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.

Related questions



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

44,297 questions
49,785 answers
164,367 comments
65,857 users