Парсер: различайте круглые скобки и объявления функций в JavaScript, как в грамматике.

Я работаю над компилятором, используя OCaml и Menhir в качестве парсера и лексера. Когда я пишу JavaScript, например Grammar, с (a, b) => a + b определением лямбда-функции, а также арифметикой (a + b) * c со скобками, отдающими приоритет подвыражениям, я пишу

expr
: x = ID { EId(x) }
...
| LPAREN; e = expr; RPAREN; { e }
...
| LPAREN; args = separated_list(COMMA, ID); RPAREN; ARROW; body = expr; { EFunction(args, body) }

in parser.mly.

Просто добавив еще несколько контекстов, у меня есть lexer.mll вот так:

let letter = ['a'-'z' 'A'-'Z']
let lud = ['a'-'z' 'A'-'Z' '_' '0'-'9']
let id = letter lud*

rule read = parse
    ...
    | "(" { LPAREN }
    | ")" { RPAREN }
    | "," { COMMA }
    | "=>" { ARROW }
    ...
    | id { ID (Lexing.lexeme lexbuf) }
    ...

Но это приведет к ошибке уменьшения/уменьшения при компиляции:

Error: do not know how to resolve a reduce/reduce conflict between the following two productions:
expr -> ID
separated_nonempty_list(COMMA,ID) -> ID

Я знаю, что проблема, вероятно, вызвана неоднозначностью между этими двумя: (a) и (a) => a (функция с одним аргументом). Но я все еще не мог понять, почему он все еще выдает эту ошибку, поскольку для меня совершенно ясно, что скобка, за которой следует жирная стрелка =>, будет функцией...

Может ли кто-нибудь помочь мне немного в этом?


parsing grammar ocaml menhir
person Liby Lee    schedule 06.07.2018    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Но я все еще не мог понять, почему он все еще выдает эту ошибку, поскольку для меня совершенно ясно, что скобка, за которой следует жирная стрелка =>, будет функцией...

Да, это супер ясно. Грамматика совершенно однозначна. Но вы не ограничены просмотром входных данных по одному токену за раз, в отличие от синтаксического анализатора LR(1). В тот момент, когда синтаксический анализатор пытается решить, что делать с a в (a), он еще не видит жирную стрелку и должен принять решение до того, как это сделает. То есть, прежде чем использовать ), синтаксический анализатор должен решить, является ли то, что предшествует ему, expr или separated_nonempty_list.

Возможно, стоит отметить, что грамматика на самом деле LR(2): еще один токен просмотра вперед, и конфликт может быть разрешен. Это не сильно утешает, поскольку Menhir не предоставляет никакого механизма для расширенного просмотра вперед, но это означает, что решение существует, потому что существование LR(k)-грамматики для языка подразумевает существование LR(1)-грамматики для того же самого языка. язык; существует даже механический алгоритм для создания грамматики LR(1).

Вместо того, чтобы преобразовывать всю грамматику, слегка запутанное решение состоит в том, чтобы изолировать случаи '(a)', что можно сделать с помощью пары явно избыточных правил:

expr: LPAREN ID RPAREN ARROW expr
    | LPAREN ID RPAREN

Второе производство, очевидно, конфликтует с LPAREN expr RPAREN, но это конфликт сдвига/уменьшения, а не конфликт уменьшения/уменьшения, и его можно разрешить, дав RPAREN более высокий приоритет, чем ID, чтобы принудительно решить в пользу сдвига RPAREN.

Это полное искажение объявлений приоритета, и вполне может оказаться проблематичным по мере того, как ваша грамматика усложняется. Более теоретически разумным решением было бы определить expr_other_than_identifier. Вы можете найти пример этого здесь, который является очень похожей грамматикой, и в некоторых других ответах SO на аналогичные вопросы.

В частности, собственная грамматика Yacc — LR(2) (вы не можете сказать, что правило закончилось, пока не увидите : после нетерминала, который запускает следующее правило). Аналогичное решение существует и для этой грамматики, но большинство генераторов синтаксических анализаторов, подобных yacc, решают проблему, добавляя дополнительный просмотр вперед в анализатор лексера. Например, вы можете распознать ) => как одиночный токен (включая внутренние пробелы) или вы можете выдать другой токен закрывающей скобки, если следующим токеном будет толстая стрелка.

person rici    schedule 06.07.2018