高阶函数的明确语法

Question

我的语法如下所示：

<type> ::= <base_type> <optional_array_size>
<optional_array_size> ::= "[" <INTEGER_LITERAL> "]" | ""

<base_type> ::= <integer_type> | <real_type> | <function_type>

<function_type> ::= "(" <params> ")" "->" <type>

<params> ::= <type> <params_tail> | ""
<params_tail> ::= "," <type> <params_tail> | ""

这样我就可以定义 Integer[42]、Real 或 (Integer, Real) -> Integer 等类型。这一切都很好，但我希望我的职能是第一个 class 公民。鉴于上面的语法，我不能有函数数组，因为它只会将 return 类型转换为数组。 (Integer, Real) -> Integer [42] 不会是一个包含 42 个函数的数组，而是 return 一个包含 42 个整数的数组的函数。

我正在考虑在函数类型周围添加可选的括号 ((Integer, Real) -> Integer)[42]，但这会产生另一个问题（注意：我使用的是自上而下的递归下降解析器，所以我的语法必须是 LL(1)） .:

<function_type> ::= "(" <function_type_tail>

<function_type_tail> ::= <params> ")" "->" <type>
                       | "(" <params> ")" "->" <type> ")"

问题是 first(params) 包含 "("，因为函数类型可以作为函数参数传递：((Integer) -> Real, Real) -> Integer。这个语法在我修改语法之前是有效的，但现在不再有效了。如何修改我的语法以获得我想要的内容？

Answer 1

这绝对是一个挑战。

为该语言制作 LR 文法要容易得多，尽管它仍然有点挑战。首先，有必要消除来自

的歧义

<type> ::= <base_type> <optional_array_size>
<base_type> ::= <function_type>
<function_type> ::= "(" <params> ")" "->" <type>

我相信您知道，歧义是由于不知道 ()->Integer[42] 中的 [42] 是顶级 <type> 的一部分还是封闭的 <function_type>。为了消除歧义，我们需要明确说明什么构造可以采用数组大小。（在这里，我添加了允许 <type> 被括号括起来的所需产品）：

<type>        ::= <atomic_type> <optional_array_size>
              |   <function_type>
<opt_array_size>  ::= ""
              |   <array_size>
<atomic_type> ::= <integer_type>
              |   <real_type>
              |   "(" <type> ")"
<function_type> ::= "(" <opt_params> ")" "->" <type>
<opt_params>  ::= ""
              |   <params>
<params>      ::= <type>
              |   <params> "," <type>

不幸的是，该语法是 LR(2)，而不是 LR(1)。

出现问题

( Integer   ) [ 42 ]
( Integer   ) -> Integer
          ^
          |
          +----------------- Lookahead

在前瞻点，解析器仍然不知道它是在查看（冗余的）带括号的类型还是函数类型中的参数列表。在看到以下符号（除了上面的两个选项之外，它可能是输入的结尾）之前，它不会知道这一点。在这两种情况下，它都需要将 Integer 减少到 <atomic_type>，然后再减少到 <type>。但是，第一种情况下它可以只移动右括号，而第二种情况下它需要继续减少，先到<params>，然后到<opt_params>。这是一个转移减少冲突。当然，它可以通过多看一个未来的标记来轻松解决，但是需要看到两个未来的标记才是语法 LR(2) 的原因。

幸运的是，LR(k) 文法总是可以简化为 LR(1) 文法。（顺便说一句，这对于 LL(k) 文法不是真的。）它只是变得有点混乱，因为有必要引入一些冗余。我们通过避免减少 <type> 的需要来做到这一点，直到我们知道我们有一个参数列表，这意味着我们需要接受 "(" <type> ")" 而不提交一个或另一个解析。这导致以下情况，其中向 <function_type> 添加了一个明显冗余的规则，并且 <opt_params> 被修改为接受 0 个或至少两个参数：

<type>        ::= <atomic_type> <optional_array_size>
              |   <function_type>
<atomic_type> ::= <integer_type>
              |   <real_type>
              |   "(" <type> ")"
<function_type> ::= "(" <opt_params> ")" "->" <type>
              |   "(" <type> ")" "->" <type>
<opt_params>  ::= ""
              |   <params2>
<params2>     ::= <type> "," <type>
              |   <params2> "," <type>

现在，我个人会就此打住。那里有很多 LR 解析器生成器，上面的语法是 LALR(1) 并且仍然相当容易阅读。但是可以将它转换为 LL(1) 文法，需要大量的工作。（我使用语法转换工具进行了其中一些转换。）

删除左递归然后左分解语法是很直接的：

# Not LL(1)
<type>          ::= <atomic_type> <opt_size>
                |   <function_type>
<opt_size>      ::= ""
                |   "[" integer "]"
<atomic_type>   ::= <integer_type>
                |   <real_type>
                |   "(" <type> ")"
<function_type> ::= "(" <fop>
<fop>           ::= <opt_params> ")" to <type>
                |   <type> ")" to <type>
<opt_params>    ::= ""
                |   <params2>
<params2>       ::= <type> "," <type> <params_tail>
<params_tail>   ::= "," <type> <params_tail>
                |   ""

但这还不够，因为<function_type>和<atomic_type>都可以以"(" <type>开头。参数列表的产生式之间也存在类似的问题。为了摆脱这些问题，我们需要另一种技术：就地扩展非终结符，以便将冲突放入同一个非终结符中，以便我们可以对它们进行左分解。对于这个例子，这通常是以一些重复为代价的。

通过展开<atomic_type>、<function_type>和<opt_params>，我们得到：

<type>     ::= <integer_type> <opt_size>
           |   <real_type> <opt_size>
           |   "(" <type> ")" <opt_size>
           |   "(" ")" "->" <type>
           |   "(" <type> ")" "->" <type>
           |   "(" <type> "," <type> <params2> ")" "->" <type>
<opt_size> ::= "" 
           |   "[" INTEGER_LITERAL "]"
<params2>  ::= ""
           |   "," <type> <params2>

然后我们可以左因子产生

<type>     ::= <integer_type> <opt_size>
           |   <real_type> <opt_size>
           |   "(" <fop>
<fop>      ::= <type> <ftype>
           |   ")" "->" <type>
<ftype>    ::= ") <fcp>
           |   "," <type> <params2> ")" "->" <type>
<fcp>      ::= <opt_size>
           |   "->" <type>
<opt_size> ::= ""
           |   "[" INTEGER_LITERAL "]"
<params2>  ::= ""
           |   "," <type> <params2>

这是 LL(1)。我将把它留作练习，将所有适当的动作重新附加到这些作品中。

高阶函数的明确语法

Unambigious grammar for higher order functions

grammar

parsing

language-design

higher-order-functions