OCaml：如何在没有堆栈的 LL 解析期间构造 AST

Question

我为 LL1 语法编写了一个预测分析器。每个非终结符 A 都有一个相应的 parseA 方法，它接受一个标记列表，returns 标记列表的其余部分和一个解析树。

我对在我的解析器中调用哪个 AST 方法感到困惑。有解决这个问题的通用方法吗？

这是我的尝试：

以我的语法部分为例：

expr -> t eprime 
eprime -> PLUS t eprime | MINUS t eprime | ε
t -> t tprime
tprime -> TIMES f tprime | DIVIDE f tprime | ε
f -> LPAREN expr RPAREN | LITERAL | TRUE | FALSE | ID

我有四种解析方法，一种用于每个非终结符。

let parseExpr tokenlist =
    match tokenlist.head with 
    | "LPAREN" -> let t_expr tokenlist_t = next tokenlist |> parseExpr in 
                  let e_expr tokenlist_e = parseEPrime tokenlist_t in
                  (tokenlist_e, Ast.Expression(t_expr, e_expr))
    | "LITERAL" -> let t_expr tokenlist_t = next tokenlist |> parseExpr in 
                  let e_expr tokenlist_e = parseEPrime tokenlist_t in
                  (tokenlist_e, Ast.Expression(t_expr, e_expr))
    | "TRUE" -> let t_expr tokenlist_t = next tokenlist |> parseExpr in 
                  let e_expr tokenlist_e = parseEPrime tokenlist_t in
                  (tokenlist_e, Ast.Expression(t_expr, e_expr))
    | "FALSE" -> let t_expr tokenlist_t = next tokenlist |> parseExpr in 
                  let e_expr tokenlist_e = parseEPrime tokenlist_t in
                  (tokenlist_e, Ast.Expression(t_expr, e_expr))
    | "ID" -> let t_expr tokenlist_t = next tokenlist |> parseExpr in 
                  let e_expr tokenlist_e = parseEPrime tokenlist_t in
                  (tokenlist_e, Ast.Expression(t_expr, e_expr))


let parseEPrime tokenlist =
  match tokenlist with
   | "PLUS" -> let expr_t tokenlist_t = next tokenlist |> parseT in
                let expr_eprime tokenlist_e = parseEPrime tokenlist_t in 
                (tokenlist_e, Ast.Add(expr_t, expr_eprime))
   | "MINUS" -> let expr_t tokenlist_t = next tokenlist |> parseT in
                let expr_eprime tokenlist_e = parseEPrime tokenlist_t in 
                (tokenlist_e, Ast.Minus(expr_t, expr_eprime))
   | "SEMI" -> (tokenlist, [])
   | "RPAREN" -> (tokenlist, [])
   | _ -> raise error  


let parseT tokenlist = 
  match tokenlist.lookathead with 
  | "LPAREN" -> let expr_f tokenlist_f = parseF tokenlist in 
                let expr_tprime tokenlist_tprime = parseTprime tokenlist_f in 
                (tokenlist_tprime, Ast.F(expr_f, expr_tprime))
  | "LITERAL" -> let expr_f tokenlist_f = parseF tokenlist in 
                let expr_tprime tokenlist_tprime = parseTprime tokenlist_f in 
                (tokenlist_tprime, Ast.Literal(expr_f, expr_tprime))
  | "TRUE" -> let expr_f tokenlist_f = parseF tokenlist in 
                let expr_tprime tokenlist_tprime = parseTprime tokenlist_f in 
                (tokenlist_tprime, Ast.F(expr_f, expr_tprime))
  | "FALSE" -> let expr_f tokenlist_f = parseF tokenlist in 
                let expr_tprime tokenlist_tprime = parseTprime tokenlist_f in 
                (tokenlist_tprime, Ast.F(expr_f, expr_tprime))
  | "ID" -> let expr_f tokenlist_f = parseF tokenlist in 
                let expr_tprime tokenlist_tprime = parseTprime tokenlist_f in 
                (tokenlist_tprime, Ast.F(expr_f, expr_tprime))
  | _-> raise error

let parseTprime tokenlist = 
  match  tokenlist.lookathead with
  | "TIMES" -> let expr_f tokenlist_f = next tokenlist |> parseF in 
                let expr_tprime tokenlist_tprime = parseTPrime tokenlist_f in 
                (tokenlist_tprime, Ast.Times(expr_f, expr_tprime))
  | "DIVIDE" -> let expr_f tokenlist_f = next tokenlist |> parseF in 
                let expr_tprime tokenlist_tprime = parseTPrime tokenlist_f in 
                (tokenlist_tprime, Ast.Divide(expr_f, expr_tprime))
  | "PLUS" -> (tokenlist, [])
  | "MINUS" -> (tokenlist, [])
  | "SEMI" -> (tokenlist, [])
  | "RPAREN" -> (tokenlist, [])
  | _ -> raise error  

let parseF tokenlist = 
  match tokenlist.lookathead with
  | "LPAREN" -> let expr tokenlist_expr = next tokenlist |> parseE in 
                match next tokenlist_expr with 
                | "RPAREN" -> (next tokenlist_expr, Ast.ExpressionParen(expr))
  | "LITERAL" -> (next tokenlist, Ast.FLiteral)
  | "TRUE" -> (next tokenlist, Ast.BoolLit)
  | "FALSE" -> (next tokenlist, Ast.FBool)
  | "ID" -> (next tokenlist, Ast.Id)
  | _ -> raise error

正如您可能从我的代码中看出的那样，我为每个非终结符编写了一个类型，然后为该非终结符的每个产生式编写了一个方法。

(*expr -> T E* *)
type expr = 
| Expression of t eprime 


(*T -> F T*)
type t = 
| F of f * tprime

(*E* -> + T E* 
E* -> - T E* 
E* -> ε  *)
type eprime = 
| Add of t eprime
| Minus of t eprime
| Eempty


(*T* -> TIMES F T* 
T* -> / F T* 
T* -> ε*)
type tprime = 
| Divide of f * tprime 
| Times of f * tprime
| TEmpty

(*F -> LPAREN E RPAREN 
F -> Literal 
F -> TRUE 
F -> FALSE
F -> ID*)
type f = 
| ExpressionParen of expr
| Literal of int 
| BoolLit of bool 
| Id of string

但我不知道我的方法保留了太多不必要的信息，而不是 AST 通常会抖掉的信息（我想 AST 是一个解析树，它抖动并去除了不必要的叶子）。到目前为止，我只是省略了括号和分号。恐怕我的 AST 中有 type t, type f, type tprime, type eprime 太多了。但是如果我要删除它们，我将不知道如何在我的 AST 中编写 type expr。

Answer 1

这似乎是真的，如果你对每个非终结符都有一个类型，你最终会得到一个更具体的树（类似于解析树）而不是抽象的树。

我不知道这有多糟糕，它仍然是代码的一个很好的表示。

一种看待它的方法是你的语法非常简单和流线型，没有很多偶然的标点符号需要被遗漏以使树更抽象。

您或许可以统一表达式和术语的类型。换句话说，您可以只为表达式树使用一种内部节点类型。一旦在解析中整理出优先级，表达式和术语都是一个子表达式列表，它们之间有运算符。

Answer 2

给出这样定义的 AST：

type expr =
  | Add of expr * expr
  | Minus of expr * expr
  | Times of expr * expr
  | Divide of expr * expr
  | IntLit of int 
  | BoolLit of bool 
  | Id of string

您可以将解析函数调整为 return 这样的 AST，方法是使 Prime 函数将左操作数作为参数，如下所示：

let parseExpr tokens =
  let (lhs, remainingTokens) = parseT tokens in
  parseExprPrime lhs remainingTokens

let parseExprPrime lhs tokens = match tokenlist.lookahead with
| PLUS :: tokens ->
  let (rhs, remainingTokens) = parseT (next tokens) in
  parseExprPrime (Add (lhs, rhs)) remainingTokens
| MINUS :: tokens ->
  let (rhs, remainingTokens) = parseT (next tokens) in
  parseExprPrime (Minus (lhs, rhs)) remainingTokens
| tokens ->
  lhs, tokens

parseT 和 parseTPrime 看起来是一样的（当然除了乘法和除法）并且 parseF 几乎保持原样，除了 Ast.ExpressionParen(expr)只是 expr 因为我还从 AST 定义中删除了 ExpressionParen 案例。

请注意，这里没有必要区分合法和非法令牌。对于像 ; 或 ) 这样的合法标记和非法标记，只要 return lhs, tokens 就可以了。在后一种情况下，非法令牌最终将被调用解析器检测到——不需要在多个地方检测错误。表达式规则也是如此：如果 tokens 以非法标记开头，则 parseF 将检测到该标记，因此无需在此处进行检查。也不需要将相同的代码重复四次，因此您只需调用 parseT 和 parseExprPrime 而无需查看当前标记，这些函数将处理它。

至于像这样简化 AST 是否值得 - 让我们考虑一个函数 eval: expr -> int 作为案例研究（为此我们忽略 BoolLit 和 Id）。使用原始定义，它看起来像这样：

let rec eval = function
| Expression (lhs, eprime) -> evalEPrime (evalT lhs) eprime

and evalEPrime lhsValue = function
| Add (rhs, rest) -> evalEPrime (lhsValue + evalT rhs) rest
| Minus (rhs, rest) -> evalEPrime (lhsValue - evalT rhs) rest
| Eempty -> lhsValue

and evalT = function
| T (lhs, tprime) -> evalTPrime (evalF lhs) tprime

and evalTPrime lhsValue = function
| Times (rhs, rest) -> evalTPrime (lhsValue * evalF rhs) rest
| Divide (rhs, rest) -> evalTPrime (lhsValue / evalF rhs) rest
| TEmpty -> lhsValue

and evalF = function
| ExpressionParen expr -> eval expr
| IntLit i -> i

使用简化的定义，它将改为：

let rec eval = function
| Add (lhs, rhs) -> eval lhs + eval rhs
| Minus (lhs, rhs) -> eval lhs - eval rhs
| Times (lhs, rhs) -> eval lhs * eval rhs
| Divide (lhs, rhs) -> eval lhs / eval rhs
| IntLit i -> i

所以我想说简化版本肯定会改进 AST 的工作，我认为这是值得的。

OCaml：如何在没有堆栈的 LL 解析期间构造 AST

OCaml: How to Construct AST during LL Parsing without stack

parsing

ocaml

abstract-syntax-tree