You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

求《现代编译器实现(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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.06.28 07:27:16