ANTLR двусмысленность в DeCaf - профессор не уверен, где ошибка - PullRequest
Новая
       5

ANTLR двусмысленность в DeCaf - профессор не уверен, где ошибка

1 голос
/ 20 октября 2010

Я работаю над проектом для школы с преобразованием спецификации Decaf BNF-формы в неконтекстную грамматику и построением ее в ANTLR. Я работал над этим в течение нескольких недель и обращался к профессору, когда застрял, но в конце концов столкнулся с чем-то, что, по его словам, не должно вызывать ошибку. Вот отдельная часть моей грамматики, expr является отправной точкой. Прежде чем я сделаю это, у меня есть один вопрос.

Имеет ли значение, если мои правила лексера появляются перед правилами парсера в моей грамматике или они периодически перемешиваются в моем файле грамматики? 

calloutarg:         expr | STRING;
expr:  multexpr ((PLUS|MINUS) multexpr)* ;
multexpr : atom ((MULT|DIVISION) atom)*
;

atom : OPENPAR expr CLOSEPAR | ID ((OPENBRACKET expr CLOSEBRACKET)? | OPENPAR ((expr (COMMA)* )+)? CLOSEPAR)|
CALLOUT OPENPAR STRING (COMMA (calloutarg)+ COMMA)? CLOSEPAR | constant;
constant: INT | CHAR | boolconstant;
boolconstant: TRUE|FALSE;

Уродливое форматирование связано с тем, что часть его рекомендаций по отладке состояла в том, чтобы взять отдельные правила и разбить их там, где двусмысленность заключается в том, чтобы увидеть, откуда начинаются ошибки. В этом случае говорится, что проблема в длинной части идентификатора, что причина в OPENBRACKET и OPENPAR. Если у вас есть какие-либо идеи, я глубоко признателен. Спасибо и извините за то, насколько неприятно форматирование кода, который я выложил.

1 Ответ

1 голос
/ 20 октября 2010

Имеет ли значение, если мои правила лексера появятся раньше, чем правила синтаксического анализа в моей грамматике ...

Нет, это не имеет значения.

Проблема в том, что в вашем правиле atom ANTLR не может сделать выбор между этими тремя вариантами:

  1. ID ( ...
  2. ID [ ...
  3. ID

не прибегая к (возможно) возврату. Вы можете решить это, используя некоторые синтаксические предикаты (которые выглядят так: (...)=> ...). Синтаксические предикаты - это не что иное, как «взгляд в будущее», и если этот «взгляд в будущее» успешен, он выбирает именно этот путь.

Ваше текущее atom правило может быть переписано следующим образом: 

atom 
  :  OPENPAR expr CLOSEPAR
  |  ID OPENPAR ((expr (COMMA)* )+)? CLOSEPAR 
  |  ID OPENBRACKET expr CLOSEBRACKET
  |  ID
  |  CALLOUT OPENPAR STRING (COMMA (calloutarg)+ COMMA)? CLOSEPAR
  |  constant
  ;

А с предикатами это будет выглядеть так: 

atom 
  :  OPENPAR expr CLOSEPAR
  |  (ID OPENPAR)=>     ID OPENPAR ((expr (COMMA)* )+)? CLOSEPAR 
  |  (ID OPENBRACKET)=> ID OPENBRACKET expr CLOSEBRACKET
  |  ID
  |  CALLOUT OPENPAR STRING (COMMA (calloutarg)+ COMMA)? CLOSEPAR
  |  constant
  ;

что должно сделать трюк.

Примечание: не используйте ANTLRWorks для генерации или тестирования парсера! Он не может обрабатывать предикаты (хорошо). Лучше всего делать это в командной строке.

Также см .: https://wincent.com/wiki/ANTLR_predicates

EDIT

Давайте обозначим шесть различных "ветвей" из вашего atom правила от A до F: 

atom                                                            // branch
  :  OPENPAR expr CLOSEPAR                                      //   A
  |  ID OPENBRACKET expr CLOSEBRACKET                           //   B
  |  ID OPENPAR ((expr COMMA*)+)? CLOSEPAR                      //   C
  |  ID                                                         //   D
  |  CALLOUT OPENPAR STRING (COMMA calloutarg+ COMMA)? CLOSEPAR //   E
  |  constant                                                   //   F
  ;

Теперь, когда (будущий) парсер должен обрабатывать ввод следующим образом: 

ID OPENPAR expr CLOSEPAR

ANTLR не знает, как парсер должен с этим справиться. Его можно проанализировать двумя разными способами:

  1. ветвь D, за которой следует ветвь A
  2. филиал C

Который является источником неоднозначности, на которую жалуется ANTLR. Если вы закомментируете одну из веток A, C или D, ошибка исчезнет.

Надеюсь, это поможет.

...