Парсер: различает скобки и объявление функций в JavaScript как грамматика - PullRequest
Новая
       19

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

0 голосов
/ 06 июля 2018

Я работаю над компилятором, использующим OCaml и Menhir в качестве парсера и лексера. Когда я пишу JavaScript, такой как Грамматика, с (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) }

в 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 (функция one-arg). Но я все еще не мог понять, почему он все еще вызывает эту ошибку, поскольку для меня совершенно ясно, что скобка, за которой следует жирная стрелка =>, будет функцией ...

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

1 Ответ

0 голосов
/ 06 июля 2018

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

Да, это супер ясно. Грамматика совершенно однозначна. Но вы не ограничены просмотром одного входного токена за раз, тогда как анализатор 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, решают эту проблему, добавляя дополнительный взгляд в анализатор лексеров. Например, вы можете распознать ) => как один токен (включая внутренний пробел), или вы можете выдать другой токен с закрывающей скобкой, если следующий токен был жирной стрелкой.

...