Mark
Mark

Reputation: 31

Balanced parentheses and brackets, where a closing bracket also closes any outstanding open parentheses (up to the previous open bracket)

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

Answers (0)

Related Questions