为 parser/lexer 规范提供类型系统？

Question

人们通常认为，与 Python 等动态语言的编码相比，Ocaml 或 F# 等函数式编程语言具有类型系统，可让我们花更多时间编写代码，减少调试时间或 JavaScript.

现在我正在编写与 FsLexYacc（F# Lexer 和 Parser 包）一起使用的解析器规范。解析器规范有类似这样的内容，用于解析整数和标识符名称：

%token <int> CSTINT
%token <string> NAME
...
Expr: 
  NAME {VAR }
 |CSTINT {CSTI }

这种代码不再是用函数式编程语言编写的，因此，它们不再受到类型系统的“保护”。我猜奇怪的错误很容易溜进来（虽然不太确定）。

问题：是否有任何工作（理论或实践）试图通过为 parser/lexer 规范提供一种类型系统来解决这个问题？

Answer 1

您可以使用 FParsec 定义您的解析器。这样，您将获得使用 F# 类型系统的所有好处。上面可以用 F# 中的 FParsec 描述如下：

type Expression = StringExpr of String | NumberExpr of int

     
let alphanumericString = letter .>>. (manyChars (letter <|> digit)) 
                          >>= (fun (c,s)-> preturn (StringExpr(c.ToString()+s)))

let number = manyChars digit 
                 >>= (fun n -> preturn (NumberExpr (Int32.Parse n)))

let expression = alphanumericString <|> number

Answer 2

是的，这方面已经有一定的研究。

需要说明的是，虽然LR解析算法中使用的语义值栈存在异构类型，但算法本身是类型安全的。但是当然在算法的实现中可能会出现错误，所以如果编译器本身能够验证解析器生成器生成的代码的类型是否正确，那将是理想的。事实证明这是可能的，并且已经产生了许多实现。

我手边没有完整的参考书目，但手头有两篇发表于 2006 年的论文，它们似乎相关：

Towards Efficient, Typed LR Parsers 作者：François Pottier 和 Yann Régis-Gianas：

The LR parser generators that are bundled with many functional programming language implementations produce code that is untyped, needlessly inefficient, or both. We show that, using generalized algebraic data types, it is possible to produce parsers that are well-typed (so they cannot unexpectedly crash or fail) and nevertheless efficient.
Derivation of a Typed Functional LR Parser 作者：Ralf Hinze 和 Ross Paterson：

This paper describes a purely functional implementation of LR parsing. We formally derive our parsers in a series of steps starting from the inverse of printing. In contrast to traditional implementations of LR parsing, the resulting parsers are fully typed, stackless and table-free. The parsing functions pursue alternatives in parallel with each alternative represented by a continuation argument. The direct implementation presents many opportunities for optimization and initial measurements show excellent performance in comparison with conventional table-driven parsers.

为 parser/lexer 规范提供类型系统？

Providing a type system for the parser/lexer specification?

f#

parsing

type-systems

functional-programming

lex