Парсер рекурсивного спуска в Окамле - PullRequest
Новая
       92

Парсер рекурсивного спуска в Окамле

0 голосов
/ 05 ноября 2018

Я пытаюсь написать парсер рекурсивного спуска для урезанного языка c в ocaml. Вот грамматика (левая рекурсия удалена и оставлена ​​с учетом): 

program -> decls EOF
decls -> typ id decls_prime 
decls -> ε
decls_prime -> vdecl decls 
decls_prime -> fdecl decls
fdecl -> LPAREN formals_opt RPAREN LBRACE vdecl_list stmt_list RBRACE
formals_opt -> formal_list 
formals_opt -> ε
formal_list -> typ ID formal_list_prime
formal_list_prime -> COMMA formal_list 
formal_list_prime -> ε
typ -> INT 
typ -> BOOL 
typ -> VOID
vdecl_list -> vdecl vdecl_list 
vdecl_list -> ε
vdecl -> SEMI
stmt_list -> stmt stmt_list 
stmt_list -> ε
stmt -> expr SEMI 
stmt -> RETURN SEMI 
stmt -> RETURN expr SEMI 
stmt -> LBRACE stmt_list RBRACE 
stmt -> IF LPAREN expr RPAREN stmt stmt_prime 
stmt -> FOR LPAREN expr_opt SEMI expr SEMI expr_opt RPAREN stmt 
stmt -> WHILE LPAREN expr RPAREN stmt 
stmt_prime -> NOELSE 
stmt_prime -> ELSE stmt
expr_opt -> expr 
expr_opt -> ε
expr ->  INTLITERAL expr_prime 
expr -> TRUE expr_prime 
expr -> FALSE expr_prime 
expr -> MINUS expr NEG expr_prime 
expr -> NOT expr expr_prime 
expr -> ID expr_prime_prime 
expr -> LPAREN expr RPAREN expr_prime
expr_prime -> PLUS expr expr_prime  
expr_prime ->  MINUS  expr expr_prime 
expr_prime -> TIMES   expr expr_prime 
expr_prime -> DIVIDE  expr expr_prime 
expr_prime -> EQ  expr expr_prime 
expr_prime -> NEQ expr expr_prime 
expr_prime -> LT expr expr_prime  
expr_prime -> LEQ expr expr_prime 
expr_prime -> GT expr expr_prime  
expr_prime -> GEQ expr expr_prime 
expr_prime -> AND expr expr_prime  
expr_prime -> OR expr expr_prime  
expr -> ε
expr_prime_prime -> expr_prime 
expr_prime_prime -> ASSIGN expr expr_prime 
expr_prime_prime -> LPAREN actuals_opt RPAREN expr_prime
actuals_opt  -> actuals_list  
actuals_opt  -> ε
actuals_list -> expr actuals_list_prime
actuals_list_prime -> COMMA expr actuals_list_prime 
actuals_list_prime -> ε

У меня также есть первый и следующий наборы для моей грамматики.

Я смотрел на примеры здесь и здесь . Я думаю, что понимаю основную концепцию разбора рекурсивного спуска:

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

Однако я довольно сильно теряюсь, когда пытаюсь написать рекурсивные функции разбора.

Моя попытка до сих пор: 

let parseProgram toklis = let(r, parseTree) = parseDecl (tl toklis)
                        in (if hd r = EOF then (SOME KIND OF AST THING)
                                          else raise SyntaxError)
and parse_decl toklis =
        let identity toklis =
                match toklis.lookahead with
                        Lexer.ID -> (next toklis, Ast.ID??)
        in
        let(toklis, decl_type) = parse_type toklis in
        let(toklis, decl_id) = identity toklis in
        let(toklis, decl_prime) = parse_decl_prime toklis
        in
        (toklis, Ast.decl(decl_type, decl_id, decl_prime))

and parse_decl_prime toklis = 
                        if toklis.lookahead = Lexer.Semi then 
                                let(toklis, vdecl) = parse_decl next toklis
                                Ast.Semi???
                        else
                        match toklis.lookahead with
                        | Lexer.Semi -> (next toklis, Ast.Semi)
                        | Lexer.Lapren -> 
                                let(toklis, e) = parse_fdecl toklis

В целом я чувствую себя очень растерянным, но вот вопросы, которые я, по крайней мере, могу понять, как сформулировать 1. Когда parseA рекурсивен, а когда нет? Например, возьмите этот синтаксический анализатор для грамматики A -> id | (B) ; B -> int | A

let rec parseA toklis = match (hd toklis) with
IDENT x -> (tl toklis, A1 (IDENT x))
| LPAREN -> let (r,t) = parseB (tl toklis)
in (if hd r = RPAREN then (tl r, A2(LPAREN, t, RPAREN))
else raise SyntaxError)
| _ -> raise SyntaxError
and parseB toklis = match (hd toklis) with
INT i -> (tl toklis, B1 (INT i))
| _ -> parseA toklis ;;

Кроме того, для каждого A в наборе нетерминалов в грамматике, который не является начальным символом, будет ли parseA идти с 'и' (то есть and parseB), учитывая, что каждый нетерминал A выводится из начального символа?

  1. Когда я проверяю заголовок списка токенов по сравнению с тем, когда я вызываю метод синтаксического анализа после ввода parseA?

  2. Как первый и последующие факторы устанавливают здесь? В школе построение таблицы синтаксического анализа LL было неотъемлемой частью синтаксического анализа LL (что, я считаю, рекурсивный спуск по сути является?) Но здесь, кажется, мы просто переписываем правило производства в ocaml ...

...