Ocaml: список построения для типа Ast в рекурсивной функции

Question

У меня есть рукописный парсер LL1.Мой AST не так прост, как мог бы быть.Часть для утверждений выглядит следующим образом:

type stmt_opt = StmtExpression of assignment | OptNil
[@@deriving show]
(*stmt_list -> stmt stmt_list | ε *)
type stmtlist =
    | StmtList of stmt * stmtlist
    | StmtlistNil 
[@@deriving show]

and stmt = 
| Assignment of assignment
| Return of stmt_opt 
| Parentheses of stmtlist
| If of assignment * stmt
| For of assignment * assignment * assignment * stmt
| While of assignment * stmt
(*“lparen” formals_opt “rparen” “LBRACE” vdecl_list stmt_list “RBRACE”*)
[@@deriving show]

Как видите, я все еще держу много ненужной информации.Я хотел бы построить свое утверждение следующим образом:

type stmt =
    Block of stmt list
  | Expr of expr
  | Return of expr
  | If of expr * stmt * stmt
  | For of expr * expr * expr * stmt
  | While of expr * stmt

Я немного растерялся, пытаясь это сделать, потому что я действительно создал парсер LL1 по книгам (что, я полагаю, не очень-то предвосхищает)длинные грамматики): у каждого нетерминала есть метод синтаксического анализа, и каждый метод синтаксического анализа возвращает токенлист и аст.

Я думаю, что для создания типа блока, как в моем утверждении цели AST, мне нужно создать списокоператоров внутри моего рекурсивного метода parseStmt.Я сократил свой код синтаксического анализатора до только методов синтаксического анализатора, которые вызывают parseStmtList, и конкретных экземпляров, где они вызывают parseStmtList

(*stmt_list = stmt stmt_list | epsilon*)
let rec parseStmtList tokenlist lst = 
    match tokenlist.head with 
    | Lexer.RightBrace -> (tokenlist, Ast.StmtlistNil )
    | _ -> let (tokenlist_stmt, stmt) = parseStmt tokenlist in 
          let new_lst = lst::stmt in
          let (tokenlist_stmt_list, stmt_list) = tokenlist_stmt new_lst |> parseStmtList in
          (tokenlist_stmt_list, Ast.Block(stmt_lst))

(*stmt -> assignment SEMI 
|  RETURN stmt_opt SEMI
|  LBRACE stmt_list RBRACE 
|  IF LPAREN assignment RPAREN stmt 
|  FOR LPAREN assignment SEMI assignment SEMI assignment RPAREN stmt  
|  WHILE LPAREN assignment RPAREN stmt
*)

and parseStmt tokenlist = 
   begin
   match tokenlist.head with 
   | Lexer.ID identifier -> let (tokenlist_assignment, assignment) = parseAssignment tokenlist in
                begin
                match tokenlist_assignment.head with
                | Lexer.Semicolon -> (next tokenlist_assignment, Ast.Assignment(assignment))
                | _-> let err_msg = __LOC__ ^ "Syntax Error semicolon expected but received" ^ show_token_list tokenlist in
                     raise (Syntax_error err_msg) 
                end
         | Lexer.LeftBrace -> let tokenlist_leftbrace = next tokenlist in 
                        let (tokenlist_expr, expr) = parseStmtList tokenlist_leftbrace [] in
                        begin
                        match tokenlist_expr.head with
                        | Lexer.RightBrace -> (next tokenlist_expr, Ast.Parentheses(expr))
                        | _-> let err_msg = __LOC__ ^ "Syntax Error right brace expected but received" ^ show_token_list tokenlist in
                              raise (Syntax_error err_msg)
                        end
   | _-> let err_msg = __LOC__ ^ "Syntax Error left brace expected but received" ^ show_token_list tokenlist in
                    raise (Syntax_error err_msg)
    end

Однако я получаю сообщение об ошибке:

Error: This expression has type 'a -> token_list * Ast.stmtlist
       but an expression was expected of type 'b * 'c

длялиния let (tokenlist_stmt_list, stmt_list) = tokenlist_stmt new_lst |> parseStmtList in в parseStmtList

Answer 1

tokenlist_stmt new_lst |> parseStmtList

Здесь вы применяете tokenlist_stmt к аргументу new_lst, а затем применяете parseStmtList к результату.Но tokenlist_stmt на самом деле не функция, так что это ошибка типа.

Предположительно, вы намеревались вызвать parseStmtList с tokenlist_stmt и new_lst в качестве двух аргументов.Синтаксис для этого просто:

parseStmtList tokenlist_stmt new_lst

Далее lst::stmt также является ошибкой типа по двум причинам:

1. :: принимает список в качестве правого операнда, а неслева, так что это должно быть stmt::lst
2. lst на самом деле не список, это Ast.Block, потому что это то, что parseStmtList возвращает.

Как только выисправив все это, вы заметите, что список будет неправильным (вероятно, именно поэтому вы сначала попытались lst::stmt, но вы не можете добавить в конец такого списка).Это общая проблема при создании списка с помощью аккумулятора.Решение состоит в том, чтобы либо перевернуть список, как только вы закончили его построение, либо вообще не использовать аккумулятор.

---

Важно отметить, что все эти проблемы будут иметьприменяется также при использовании Ast.stmtlist.То есть, если бы ваш код выглядел так:

let new_lst = Ast.StmtList(lst, stmt) in
let (tokenlist_stmt_list, stmt_list) = tokenlist_stmt new_lst |> parseStmtList in
(tokenlist_stmt_list, Ast.Block(stmt_lst))

Тогда вы получите точно такие же ошибки.Это заставляет меня думать, что вы изменили намного больше кода, чем нужно.Поскольку ваш старый код предположительно работал, я предполагаю, что он выглядел примерно так:

let rec parseStmtList tokenlist = 
    match tokenlist.head with 
    | Lexer.RightBrace -> (tokenlist, Ast.StmtlistNil )
    | _ -> let (tokenlist_stmt, stmt) = parseStmt tokenlist in 
          let (tokenlist_stmt_list, stmt_list) = parseStmtList tokenlist_stmt in
          (tokenlist_stmt_list, Ast.StmtList (stmt, stmt_lst))

, а затем в parseStmt у вас было:

let (tokenlist_stmtlist, stmtlist) = parseStmtList tokenlist_leftbrace in
begin
  match tokenlist_expr.head with
  | Lexer.RightBrace -> (next tokenlist_stmtlist, Ast.Block(stmtlist))

Теперь после удаления Ast.stmtlist все, что вам нужно изменить, это части, где вы фактически использовали его конструкторы, и замените эти части конструкторами списков (:: и []).Таким образом, код в parseStmt остался бы полностью неизменным, и единственные изменения в parseStmtList должны состоять в том, чтобы заменить строку

| Lexer.RightBrace -> (tokenlist, Ast.StmtlistNil )

на

| Lexer.RightBrace -> (tokenlist, [] )

и строку

(tokenlist_stmt_list, Ast.StmtList (stmt, stmt_lst))

с

(tokenlist_stmt_list, stmt :: stmt_lst)

Если ваш старый код выглядел иначе, чем я придумал выше, вам, возможно, придется изменить другие строки, но идея остается прежней: замените Ast.StmtList на:: и Ast.StmtListNil с [].

И все.Это все изменения, которые необходимы.Вы были слишком сложны.