平衡括号和中括号，其中右括号还关闭所有未完成的左括号（直到前一个左括号）

Question

下面的问题来自书：“C 中的现代编译器实现”，chapter03, 3.3.(d)

为平衡括号和方括号编写明确的语法， 其中右括号也关闭任何未完成的左括号 （直到上一个左括号）。

示例：[([](()[(][])]。

提示：首先，制作平衡括号和中括号的语言， 允许使用额外的左括号；然后确保这一点 非终结符必须出现在括号内。

我已经尝试了很多次，找不到完全解决它的方法，最接近的答案如下（在 Yacc 中）：

S   :   /* empty */
    |   '[' LP ']' S
    |   '(' S ')' S
    ; 

LP  :   B
    |   '(' LP
    ;

B   :   /* empty */
    |   '[' LP ']' B
    |   '(' B ')' B
    ;

此版本可以完美地处理诸如示例之类的字符串，但无法处理如下字符串：

[()(]

，其中

LP

的内部

S

只是“平衡括号和方括号的一个实例，其中允许使用额外的左括号” ”，而是一个列表（这是必需的）。

如果有人能解决这个问题，请给我一个完全正确的解决方案。谢谢！

Answer 1

您尝试中的问题在于

LP

的定义。在

B

之后，您仍然应该允许

(

，然后是

LP

，所以它变成：

LP  :   B
    |   B '(' LP
    ;

请注意，您的

S

和

B

是同义词，因此您可以在那里进行简化。