parsing - 用 Happy 解析函数应用

Question

我将如何解析类似

f x y

进入

APPLY (APPLY f x) y

使用快乐？现在我有一条规则说

%left APP
Expr : Expr Expr %prec APP { APPLY $1 $2 }

但这会将上述内容解析为

APPLY f (APPLY x y)

Answer 1

接受的答案并不令人满意。

解决这个问题的正确方法是：

%nonassoc VAR LPAREN -- etc...
%nonassoc APP

Expr : Expr Expr %prec APP { APPLY $1 $2 }

那是：

• 添加一个名为 的幽灵优先级标记APP，不需要创建它，left或者right因为它不相关，所以你可以保持它nonassoc不会得到重要的错误直觉

• 像你一样标记你的Expr规则%prec APP

• 最重要且经常被遗忘的是，您需要为所有可能作为生产的第一个标记出现的标记赋予Expr低于 of 的优先级APP，通常通过在上面的某个地方列出它们来实现，或者用left,right或nonassoc没有的那些联系

您的试用失败的原因可能是您错过了最后一步。

之所以需要最后一步，是因为算法在决定是移动下一个令牌还是减少APP规则时，会将APP规则的优先级与传入令牌的优先级进行比较。默认情况下，您未提及的标记具有高优先级。所以当遇到：

Expr Expr . LPAREN VAR RPAREN

例如，它会将APP规则的优先级（减少）与LPAREN（转移）的优先级进行比较，除非您正确设置它，否则它将转移并做错事。

---

分级你的语法是丑陋和不愉快的。

Answer 2

您可以使用语法规则对左/右关联性进行编码。

例如，看看这个基本的 lambda 演算解析器：

https://github.com/ghulette/haskell-parser-examples/blob/master/src/HappyParser.y

有效的产品是：

Expr : let VAR '=' Expr in Expr    { App (Abs $2 $6) $4 }
     | '\\' VAR '->' Expr          { Abs $2 $4 }
     | Form                        { $1 }

Form : Form '+' Form               { Binop Add $1 $3 }
     | Juxt                        { $1 }

Juxt : Juxt Atom                   { App $1 $2 }
     | Atom                        { $1 }

Atom : '(' Expr ')'                { $2 }
     | NUM                         { Num $1 }
     | VAR                         { Var $1 }