在使用快乐解析器编写的函数式语言编译器中，与yacc / bison非常相似，我使用以下规则实现了列表并列出了一些核心函数 map ， concat 和 filter ：
Exp:
...
| concat '(' Exp ',' Exp ')' { Concat $3 $5 }
| map '(' Exp ',' Exp ')' { Map $3 $5 }
| filter '(' Exp ',' Exp ')' { Filter $3 $5 }
这很好用，但在大多数函数式语言中没有paranthesis或逗号，所以我宁愿写 map myfun [1,2,3] 而不是 map(myfun, [1,2,3]) . 语法中的明显修改如下：
Exp:
...
| concat Exp Exp { Concat $2 $3 }
| map Exp Exp { Map $2 $3 }
| filter Exp Exp { Filter $2 $3 }
但是这种修改包括许多减少 - 减少冲突 . 如何在没有逗号和paranthesis的情况下实现函数调用的解析？
我能提取的最小的冲突语法是这样的：
Exp :
-- Math
Exp '+' Exp { Op $1 Add $3 }
| Exp '-' Exp { Op $1 Sub $3 }
-- Literals
| num { Num $1 }
| '-' num %prec NEGATIVE { Num (-$2) }
-- Lists
| map Exp Exp { Map $2 $3 }
它产生4个减少/减少冲突 . 删除任何规则也会导致冲突 . 如果你有兴趣，这是full grammar .
1 回答
问题在于，由于函数应用程序中没有令牌，基于令牌的优先级冲突解决方案不能很好地工作 - 当它试图决定可能是函数应用程序的转移并减少其他表达式时，先行标记是参数表达式的开头;没有可以使用的“空格”标记 .
要解决该问题并使其工作，您需要将可能是表达式（FIRST（Exp）中的每个标记）的每个标记的优先级设置为函数应用程序的优先级 . 如果这些令牌中的任何一个需要一些其他优先权（例如，任何可能是中缀或前缀的令牌），这会变得更加棘手并且可能无法工作 .
可能更好的替代方法是根本不使用优先级规则 - 而是使用针对每个优先级的不同规则消除语法歧义：