I'm reading the book: Formal Syntax and Semantics of Programming Languages. I don't understand this exercise:

Consider the following two grammars, each of which generates strings of correctly balanced parentheses and brackets. Determine if either or both is ambiguous. The Greek letter ε represents an empty string.

<string> ::= <string> <string> | ( <string> ) | [ <string> ] | ε
<string> ::= ( <string> ) <string> | [ <string> ] <string> | ε
  • 3
    $\begingroup$ Note that it's the grammar that may or may not be ambiguous, not the language. Do you understand the definition of an ambiguous grammar? $\endgroup$ – Gilles 'SO- stop being evil' Aug 11 '13 at 19:22
  • 1
    $\begingroup$ What exactly do you not understand? Do you understand the definition of ambiguity? Have you had a look at other questions tagged ambiguity? $\endgroup$ – Raphael Aug 12 '13 at 13:09

Consider this a hint. As I write in my comment, what is the syntax tree of ()()()? Does the first two pairs belong to the leftmost of the <string><string>-part, or does the two latter pairs belong to the rightmost?

$$ \left( \overbrace{ \overbrace{ () }^\text{string} \quad \overbrace{ () }^\text{string}}^\text{string} \quad \overbrace{ () }^\text{string} \right) \text{ vs } \left( \overbrace{ () }^\text{string}\quad \overbrace{ \overbrace{ () }^\text{string}\quad \overbrace{ () }^\text{string}}^\text{string} \right) $$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy