OCaml: как построить AST во время парсинга LL без стека

Question

Я написал прогностический парсер для грамматики LL1. Каждый нетерминал A имеет соответствующий метод parseA, который принимает список токенов и возвращает остаток списка токенов и дерево разбора.

Я не понимаю, какой метод 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 как дерево разбора, которое встряхивает и избавляет себя от ненужных листьев). Пока я только что оставил скобки и точки с запятой. Боюсь, я слишком много оставляю, имея type t, type f, type tprime, type eprime в моем AST. Но если бы я их удалил, я бы не знал, как написать type expr в моем AST.

Answer 1

С учетом 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

Вы можете настроить ваши функции синтаксического анализа так, чтобы они возвращали такой 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, потому что я также исключил случай ExpressionParen из определения AST.

Обратите внимание, что здесь нет необходимости различать легальные и нелегальные токены. Можно просто вернуть 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, и я считаю, что это того стоит.

Answer 2

Кажется верным, что если у вас есть тип для каждого нетерминала, вы получите дерево, которое больше на конкретной стороне (похоже на дерево разбора), чем на абстрактной стороне.

Я неЗнайте, что это так плохо, это все еще хорошее представление о коде.

Один из способов взглянуть на это - ваша грамматика настолько проста и упорядочена, что не нужно оставлять много случайных знаков препинания.чтобы сделать дерево более абстрактным.

Возможно, вы могли бы объединить типы для выражений и терминов.Другими словами, вы можете использовать только один тип внутреннего узла для своих деревьев выражений.После того, как приоритеты были отсортированы при разборе, выражения и термины представляют собой список подвыражений с операторами между ними.