如何从函数调用中删除逗号和括号

Question

在使用 happy parser 编写的函数式语言编译器中，这与 yacc/bison 非常相似，我实现了列表并使用列表一些核心函数 map、concat 和 filter，使用以下规则：

Exp:
...
| concat '(' Exp ',' Exp ')'         { Concat   }
| map '(' Exp ',' Exp ')'            { Map   }
| filter '(' Exp ',' Exp ')'         { Filter   }

这很好用，但在大多数函数式语言中没有括号或逗号，所以我宁愿写 map myfun [1,2,3] 而不是 map(myfun, [1,2,3])。语法中明显的修改如下：

Exp:
...
| concat Exp Exp         { Concat   }
| map Exp Exp            { Map   }
| filter Exp Exp         { Filter   }

但是这个修改包含了很多reduce-reduce冲突。如何在没有逗号和括号的情况下实现函数调用的解析？

我能提取的最小冲突语法是这样的：

Exp :
    -- Math
     Exp '+' Exp                         { Op  Add  }
    | Exp '-' Exp                        { Op  Sub  }

    -- Literals
    | num                                { Num  }
    | '-' num %prec NEGATIVE             { Num (-) }

    -- Lists
    | map Exp Exp                        { Map   }

它产生了 4 个 reduce/reduce 冲突。删除任何规则也会导致冲突。如果你有兴趣，这里是full grammar。

Answer 1

问题在于，由于函数应用程序中没有令牌，因此基于令牌的优先级冲突解决方案效果不佳——当它试图决定可能是函数应用程序的转变并减少一些其他表达式，先行标记是参数表达式开头的任何内容；没有可以使用的 'blank space' 令牌。

要解决该问题并使其正常工作，您需要将可能是表达式的每个标记（FIRST(Exp) 中的每个标记）的优先级设置为函数应用程序的优先级。如果这些标记中的任何一个需要一些其他优先级（例如，任何可能是中缀或前缀的标记），这会变得更加棘手并且可能无法工作。

一个可能更好的替代方法是根本不使用优先规则——相反，为每个优先级别使用不同的规则来消除语法歧义：

Exp: Term | Exp '+' Term
Term: Factor | Term '*' Factor
Factor: Primary | Factor Primary
Primary: num | id | '(' Exp ')'

如何从函数调用中删除逗号和括号

How to remove commas and parenthesis from function calls

grammar

bison

yacc

happy