CSCI 5220
Spring 2003
Answers to practice questions for exam 1

1. Give a regular expression using flex notation that descibes the set of strings that start with a, end with c and have zero or more digits between them.

   a[0-9]*c

2. Write a program using flex that copies the standard input to the standard output, except that it replaces each sequence of consecutive blanks and tabs by a single blank.

     %{
     #include <stdio.h>
     %}
     %%
     [ \t]+   {printf(" ");}
     "\n"     {printf("\n");}
     .        {printf("%s", yytext);}
     %%
     int main()
     {
       yylex();
       return 0;
     }
   

3. Show that the following grammar is ambiguous.

   S -> S c S

   S -> d

   It suffices to show two different parser trees for dcdcd.

                    S                         S
                   /|\                       /|\
                  / | \                     / | \
                 S  c  S                   S  c  S
                /|\    |                   |    /|\
               / | \   d                   d   / | \
              S  c  S                         S  c  S
              |     |                         |     |
              d     d                         d     d
   

4. Show a parse tree for string cccdd with respect to grammar

   S -> c S d

   S -> c

                            S
                           /|\
                          / | \
                         c  S  d
                           /|\
                          / | \
                         c  S  d
                            |
                            c
   

5. What are the FIRST and FOLLOW sets for the following grammar? The start nonterminal is E.

   E -> A

   E -> L

   A -> n

   A -> i

   L -> ( S )

   S -> E , S

   S -> E

   FIRST(E)	=	{'n', 'i', '(' }
   FIRST(A)	=	{'n', 'i' }
   FIRST(L)	=	{'(' }
   FIRST(S)	=	{'n', 'i', '(' }
   FOLLOW(E)	=	{',', ')', $ }
   FOLLOW(A)	=	{',', ')', $ }
   FOLLOW(L)	=	{',', ')', $ }
   FOLLOW(S)	=	{')' }

6. Build the finite state machine of LR(0) items for the grammar of the preceding problem, and show the SLR(1) parsing table for that grammar.

   
   
   

   Action							Goto
   	n	i	(	)	,	$	E	A	L	S
   0	s4	s5	s6				1	2	3
   1						acc
   2				r1	r1	r1
   3				r2	r2	r2
   4				r3	r3	r3
   5				r4	r4	r4
   6	s4	s5	s6				7	2	3
   7				r7	s8
   8	s4	s5	s6				7	2	3	9
   9				r6