CSCI 5220
Spring 2008
Practice questions for exam 1

1. Suppose that you choose to describe a programming language by a context-free grammar at the character level instead of at the token level. That is, you do not use a lexical analyzer as the front-end of the compiler. Describe two important problems or issues that you think you might encounter.

2. Is the following context-free grammar ambiguous? Explain how you know.

   S	->	S a S
   S	->	b
   S	->	c

3. Is the grammar of the preceding question SLR(1)?

4. Is every unambiguous grammar LL(1)?. Explain briefly.

5. Is every LL(1) grammar unambiguous? Explain briefly.

6. Give an example of a grammar that is SLR(1) but not LL(1).

7. Is the following grammar LL(1)? Explain briefly. The start symbol is S.

   S	->	A B
   A	->	a
   A	->	A B
   B	->	b

8. Suppose that an identifier in a particular language starts with a letter and can contain letters, digits and the underscore symbol. Using Flex (or Lex) notation, write a regular expression that describes identifiers of that form.

9. Let G be the following augmented grammar.

   1. S' -> S $
   2. S -> w
   3. S -> a C b
   4. C ->
   5. C ->S x C

   1. What are the FIRST and FOLLOW sets for S and C in grammar G?

   2. Show the SLR(1) state transition diagram, with the correct set of LR(0)-items in each state, for grammar G. Give a number to each state.

   3. Show the SLR(1) parsing table for grammar G, using your transition diagram from part (b). Are there any conflicts?