Парсер остановка mid-parse - PullRequest
Новая
       31

Парсер остановка mid-parse

0 голосов
/ 07 мая 2011

У меня совершенно нет идей. Я трачу каждую свободную минуту на этот день, но у меня совершенно нет идей.

Это моя Ocamlyacc грамматика: 

input: /* empty */ { }
    | input stmt { }

stmt:
    extern { print_endline "Got an extern import" }
    | func  { print_endline "Got function definition" }
    | call  { print_endline "Got function call" }

extern:
    EXTERN proto { Extern $2 }  

func:
    DEF proto expr { Function ($2, $3) }

proto:
    IDENTIFIER LPAREN id_list RPAREN { print_endline "Got prototype definition"; Prototype ($1, $3) }

id_list:
    /* empty */ { [] }
    | IDENTIFIER { [$1] }
    | id_list COMMA IDENTIFIER { $3 :: $1 }

expr_list:
    /* empty */ { [] }
    | expr { [$1] }
    | expr_list COMMA expr { $3 :: $1 }

expr:
    call { $1 }
    | expr OP expr { Binary ($2, $1, $3) }
    | IDENTIFIER { Variable $1 }
    | NUMBER { Number $1 }
    | LPAREN expr RPAREN { $2 }

call:
    IDENTIFIER LPAREN expr_list RPAREN { Call ($1, $3) }

Когда я начинаю синтаксический анализ def foo(a,b) a+b, он должен сказать, что получил функцию и объявление прототипа, согласно сообщениям отладки. Но вместо этого я получаю сообщение только при разборе правила proto.

Дальнейшие сообщения отладки показывают, что синтаксический анализатор доходит до a выражения a+b и затем останавливается. Нет сообщения об ошибке, ничего больше. Он просто останавливается, как если бы весь текст был полностью разобран без соблюдения каких-либо правил в stmt.

Нет ошибок сдвига / уменьшения или аналогичных. Типы AST также не являются проблемой. Я понятия не имею, может быть, кто-то еще может помочь. Конечно, это что-то очевидное, но я не вижу этого.

РЕДАКТИРОВАТЬ : Lexer по многочисленным просьбам: 

{
    open Parser
}

rule token = parse
    | [' ' '\t' '\n'] { token lexbuf }
    | "def" { DEF }
    | "extern" { EXTERN }
    | "if" { IF }
    | "then" { THEN }
    | "else" { ELSE }
    | ['+' '-' '*' '/'] as c { OP c }
    | ['A'-'Z' 'a'-'z'] ['A'-'Z' 'a'-'z' '0'-'9' '_']* as id { IDENTIFIER id }
    | ['0'-'9']*'.'['0'-'9']+ as num { NUMBER (float_of_string num) }
    | '(' { LPAREN }
    | ')' { RPAREN }
    | ',' { COMMA }
    | '#' { comment lexbuf }
    | _ { raise Parsing.Parse_error }
    | eof { raise End_of_file }
and comment = parse
    | '\n' { token lexbuf }
    | _ { comment lexbuf }

1 Ответ

4 голосов
/ 07 мая 2011

Первое замечание: я вас немного ненавидел за то, что вы не дали скомпилированный исходный код.Мне пришлось заново изобрести типы AST, объявления %token и т. Д., Чтобы проверить ваш код.

Проблема заключается в тонком взаимодействии между правилом лексирования 

| eof { raise End_of_file }

и вашей грамматикой.

Повышение Enf_of_file на EOF в лексере - хорошая идея, если ваша грамматика никогда не достигает конца файла.Например, грамматики, которые естественно \n -определены или ;; -кончаны, прекратят синтаксический анализ в этой точке и никогда не дойдут до токена EOF.

Но ваша грамматика не одна из них.Когда синтаксический анализатор достигает DEF proto expr ., он запрашивает следующий токен, чтобы узнать, не случайно ли он, и OP, поэтому он вызывает лексер, который находит EOF и удаляет.

Вот мое исправление:

В lex.mll: 

    | eof { EOF }

В parse.mly:% токен EOF 

%start stmt_eof
%type <Types.stmt> stmt_eof

[...]

stmt_eof: stmt EOF { $1 }

Наконец, вы должны серьезно рассмотреть Менгир в качестве замены для ocamlyacc.Он делает все, что делает ocamlyacc, только лучше, с более четкими файлами грамматики (например, вам не нужно каждый раз заново изобретать foo_list нетерминал), улучшенными сообщениями об ошибках, функциями отладки ...

...