CSCI 3675 practice questions for quiz 11

Computer Science 3675
Fall 2015
Practice Questions for Quiz 11

True or false.
1. A token can only have one associated lexeme. Answer
2. A variable name is typically a single lexeme in a program. Answer
3. Most programming languages have a comment token in their grammars. Answer
4. Most programming languages require two consecutive lexemes to be separated by a space or spaces. Answer
What is Backus-Naur Form, and what is it used for?
Answer
Show a parse tree for string aacacab according to the following grammar, where the start nonterminal is S. In this grammar, upper case letters are nonterminals and lower case letters are tokens.
```
    S -> F a S
      |  b

    F -> a F
      |  c
```
Answer
Show that the following grammar is ambiguous. The start symbol is S. Upper case letters are nonterminals and lower case letters are tokens.
```
    S -> S a
      |  a S
      |  a
```
Answer
Show that the following grammar is ambiguous. The start symbol is S. Upper case letters are nonterminals and lower case letters are tokens.
```
    S -> S a S
      |  S b S
      |  c
```
Answer
Write a grammar that describes sequences of left and right parentheses that are balanced. A sequence of parentheses is balanced if parentheses match and are well nested. For example, (( )(( ))) is balanced, but )( and ( ))( )( are not balanced.
Answer