继续活动模式与F#的列表匹配

Question

我有一个编译器的模式，在expr解析器中我想做这个

let (|InfixOperator|_|) tokens = ...
let (|UnaryValue|_|) tokens = ...
let infixExpr tokens =
match tokens with
| Value v::Operator op::tokens -> ...
| Value v::tokens -> ...

问题是匹配expr的令牌签名为Token list list，或者模式Value(由于解析一元运算，因此需要接收列表(没有返回剩余的令牌，Operator模式也是如此

它周围丑陋的方式将是类似于这个

let (|InfixOperator|_|) tokens = ...
let (|UnaryValue|_|) tokens = ...
let infixExpr tokens =
match tokens with
| Value (v, Operator (op, tokens)) -> ...
| Value (v, tokens) -> ...

有人知道用模式匹配更干净的方法吗？

Answer 1

我为BASIC的一个子集编写了一个使用模式匹配的解析器(源代码在GitHub上可用(。这并没有大量使用活动模式，但它分为两个步骤——首先将输入标记化(将list<char>转换为list<Token>(，然后解析标记列表(将list<Token>转换为list<Statement>(。

通过这种方式，您基本上可以避免嵌套的问题，因为大多数有趣的东西都只是一个标记。例如，对于运营商来说，标记化看起来像：

let rec tokenize toks = function
(* First character is number, collect all remaining number characters *)
| c::cs when isNumber c -> number toks [c] cs
(* First character is operator, collect all remanining operator characters *)
| c::cs when isOp c -> operator toks [c] cs
(* more cases omitted *)
| [] -> List.rev toks
and number toks acc = function
| c::cs when isNumber c -> number toks (c::acc) cs
| input -> tokenize (Number(float (str acc))::toks) input
and operator toks acc = function
| c::cs when isOp c -> operator toks (c::acc) cs
| input -> tokenize (Operator(List.rev acc)::toks) input

如果您现在有一个令牌列表，那么解析二进制表达式就变成：

let rec parseBinary left = function
| (Operator o)::toks -> 
let right, toks = parseExpr toks
Binary(o, left, right), toks
| toks -> left, toks
and parseExpr = function
| (Number n)::toks -> parseBinary (Const(NumberValue n)) toks
(* more cases omitted *)

在某些地方，我使用了活动模式，例如解析BASIC范围表达式，该表达式可以是N1-N2、-N1或N1-

let (|Range|_|) = function
| (Number lo)::(Operator ['-'])::(Number hi)::[] -> 
Some(Some (int lo), Some (int hi))
| (Operator ['-'])::(Number hi)::[] -> Some(None, Some(int hi))
| (Number lo)::(Operator ['-'])::[] -> Some(Some(int lo), None)
| [] -> Some(None, None)
| _ -> None

因此，我想答案是，如果你想使用模式匹配编写一个简单的解析器(而不需要进入更复杂、更强大的一元解析器库(，那么这是非常可行的，但将标记化与解析分离是个好主意。