PCF 有 LL(k) 文法吗？

Question

我们正在研究编译器设计中的自顶向下解析 class。示例都是 java 类语言。我决定尝试一种简单的函数式语言来让它变得有趣，所以我选择了 PCF (see e.g. here)。不过，我似乎无法将其纳入 LL(1) 语法。我认为问题是函数应用（即两个表达式的并置）。关于如何确定这是否只是我缺乏技能，或者这是否是一种没有 LL(1) 语法或 LL(k) 的语言，我没有得到明确的答案。有人可以澄清我是需要更聪明还是根本不存在这样的语法？

基本上，我的 PCF 版本类似于下面的草图（大写是非终端，“//”开始注释）。我说 "something like" 是因为我并不拘泥于此，而且我已经写了很多变体——只想要一个合理的 PCF 变体。

请注意，我已尝试使用中间非终结符进行左因式分解和优先级计算。

Exp -> Const     // integer and boolean literals, normal ops e.g. +
    |  if Exp then Exp else Exp
    |  lambda identifier dot Exp    //lambda (function) abstraction
    |  Exp Exp                      // function application
    |  fix Exp                      // fixpoint operator (recursion)

Answer 1

问题是您的语法是左递归的，它不能很好地与自上而下的解析器一起使用，如 LL(k) 所述。

具体来说，尝试解析 Exp 会导致尝试首先解析函数应用程序的第一部分 Exp Exp... 对于自上而下的解析器，这会形成无限循环.

您的情况可能的解决方案是以右递归样式实现任意长度的函数应用程序：

AppExp -> Exp | Exp AppExp

Exp -> Const | (AppExp) | ...

请注意，此结构消除了语法歧义。不幸的是，它以错误的方向解决了您的问题——并且没有很好的方法来解决它；左关联版本：

AppExp  -> Exp | AppExp Exp

将与原来的一样左递归。

在自上而下的解析器范围内解决这个问题的（不太好的）方法是接受右关联语法，将 AppExp 视为列表，并在解析后反转它以便您的抽象语法树具有您想要的关联性：

 application expression:    f a b c d
   |
   |  LL(1) parse
   v
 right-associative   --->   left-associative
       @             list              @
      / \          reversal           / \
     f   @                           @   d
        / \                         / \
       a   @                       @   c
          / \                     / \
         b   @                   @   b
            / \                 / \
           c   .               .   a
               |               |
               d               f

像 Parsec 这样的组合器解析器库通常具有方便的预打包功能，可以为您完成此操作。

在语言理论术语中，这表明了语法接受的语言和解析器产生的解析之间的区别基于那个语法....

PCF 有 LL(k) 文法吗？

Is There an LL(k) Grammar for PCF?

parsing

functional-programming

lambda-calculus