CSCI 3675 practice questions for quiz 5

Computer Science 3675
Fall 2011
Practice Questions for Quiz 5

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
5. Layout is a way of showing structure in a program. 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
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