Прекращение синтаксического анализа парсером

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

Это моя 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 }

ocaml ocamlyacc
person Lanbo    schedule 06.05.2011    source источник
comment
выглядит неплохо. определенно ничего очевидного. lexxer?   -  person nlucaroni    schedule 07.05.2011

Ответы (1)


arrow_upward
4
arrow_downward

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

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

| eof { raise End_of_file }

Правило лексирования и ваша грамматика.

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

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

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

В lex.mll:

    | eof { EOF }

В parse.mly:% token EOF

%start stmt_eof
%type <Types.stmt> stmt_eof

[...]

stmt_eof: stmt EOF { $1 }

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

person gasche    schedule 07.05.2011
comment
Спасибо, перешел на Menhir и заменил правило eof. Кроме того, спасибо за помощь, хотя ты меня ненавидишь. - person Lanbo; 07.05.2011
comment
@ Scán: обратите внимание, что добавление других stmt_eof правил, которые запрашивают EOF после stmt, обычно является хорошей идеей: это гарантирует, что грамматика будет принимать только для синтаксического анализа ввода, если она может анализировать его в целом . Если вы этого не сделаете и в вашей грамматике есть ошибка, он может с радостью вернуть самый длинный префикс, который он может проанализировать, вместо того, чтобы предупреждать вас о проблеме. - person gasche; 07.05.2011
comment
Хорошо, спасибо за совет. Теперь моя единственная проблема - заставить ocamlbuild найти модуль Llvm. - person Lanbo; 07.05.2011