求《现代编译器实现(C语言版)》3.3(d)题的正确无歧义文法
无歧义文法求解:含特殊闭合规则的平衡括号问题
问题出自书籍《Modern compiler implementation in C》(《现代编译器实现(C语言版)》)第3章3.3(d)题:
编写一个无歧义文法,用于描述平衡的圆括号和方括号,其中一个闭合方括号会同时闭合之前所有未闭合的圆括号(直到前一个开方括号)。
示例:[([](()[(][])]。
提示:先定义允许额外开圆括号的平衡圆括号和方括号语言;然后确保该非终结符必须出现在方括号内。
我的尝试与遇到的问题
我多次尝试仍未找到完整解决方案,以下是最接近的Yacc文法:
S : /* empty */ | '[' LP ']' S | '(' S ')' S ; LP : B | '(' LP ; B : /* empty */ | '[' LP ']' B | '(' B ')' B ;
该文法能完美处理上述示例,但无法处理[()(]这类字符串——因为S的内部LP仅为一个“允许额外开圆括号的平衡圆括号和方括号”实例,而非所需的列表结构。
另一个可能正确但存在1个归约/归约冲突的歧义文法如下:
S : /* empty */ | '[' B ']' S | '(' S ')' S ; B : P | '[' B ']' B | '(' B ')' B ; P : /* empty */ | '(' P ;
求解请求
恳请能解决该问题的人士提供完全正确的无歧义文法解决方案,谢谢!
内容的提问来源于stack exchange,提问作者Mark
相关产品推荐
相关产品推荐

