Reputation: 31
The problem below is from book: "Modern compiler implementation in C", chapter03, 3.3.(d)
Write an unambiguous grammar for balanced parentheses and brackets, where a closing bracket also closes any outstanding open parentheses (up to the previous open bracket).
Example:
[([](()[(][])]
.Hint: First, make the language of balanced parentheses and brackets, where extra open parentheses are allowed; then make sure this nonterminal must appear within brackets.
I have tried many times to find no way to solve it entirely, with a closest answer below(in Yacc):
S : /* empty */
| '[' LP ']' S
| '(' S ')' S
;
LP : B
| '(' LP
;
B : /* empty */
| '[' LP ']' B
| '(' B ')' B
;
This version handles strings such as the example perfectly, but fails to handle strings like: [()(]
, where inner LP
of S
is only one instance of "balanced parentheses and brackets, where extra open parentheses are allowed", rather a list(which is required).
Another ambiguous but totally right(maybe) one, only with 1 reduce/reduce conflicts is:
S : /* empty */
| '[' B ']' S
| '(' S ')' S
;
B : P
| '[' B ']' B
| '(' B ')' B
;
P : /* empty */
| '(' P
;
If any one who can handle this problem, please give me a totally right solution. Thx!
Upvotes: 1
Views: 119