使用Happy解析函数应用

Question

我该如何解析类似以下内容的数据：

f x y

进入

APPLY (APPLY f x) y

您是否正在使用Happy？现在我有一个规则，它说：

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

但是这将解析上述内容为：

APPLY f (APPLY x y)

- spacepotato

Answer 1

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

正确解决此问题的方法是：

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

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

即：

• 添加一个名为APP的幽灵优先级标记，不需要使它成为left或right，因为它与之无关，所以可以将其保持为nonassoc，以避免产生错误的直觉

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

• 最重要的是经常被忘记的，您需要为可能出现在Expr产生式开头的所有标记都赋予比APP低的优先级，通常通过在某个地方列出它们来实现，对于不关联的标记使用left、right或nonassoc

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

需要最后一步的原因是，算法在决定是移动下一个标记还是缩小APP规则时，将比较APP规则的优先级和传入标记的优先级。默认情况下，您没有提及的标记具有很高的优先级。因此，当面对以下情况时：

Expr Expr . LPAREN VAR RPAREN

例如，它会比较APP规则（以减少）的优先级与LPAREN（进行移位）的优先级，并且除非您正确设置，否则它将进行移位并执行错误操作。

---

对语法进行分段是很丑陋和不愉快的。

- Ptival

---

这对我非常有帮助。谢谢你。 - undefined

@paulotorrens 如果你想要更深入的解释，我在我的博客文章中写了关于这个问题的内容：https://ptival.github.io/2017/05/16/parser-generators-and-function-application/ - undefined

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 }

- ErikR