Почему эта грамматика ANTLR4 неоднозначна? - PullRequest
Новая
       83

Почему эта грамматика ANTLR4 неоднозначна?

2 голосов
/ 14 января 2020

Я изо всех сил пытаюсь понять алгоритм ANTLR4 и как он обрабатывает левую рекурсию. Надеюсь, что кто-то может научить меня немного.

Возьмите нижнюю левую рекурсивную грамматику: 

grammar Dummy;

TOK1 : 'foo';
TOKE_OPT : 'bar';
TOK2 : 'baz';
TOKDERP : 'derp';

SPACES
 : [ \u000B\t\r\n] -> channel(HIDDEN)
 ;

rr
    : rr TOK1 rr TOKE_OPT?
    | '(' TOK2 ')'
    | TOKDERP
    ;

И следующую входную строку: 

derp foo derp foo  derp

Когда пробежите TestRig -diagnostics ANTLR считает грамматику неоднозначной, и я не понимаю, почему: 

line 1:5 reportAttemptingFullContext d=2 (rr), input='foo'
line 1:9 reportContextSensitivity d=2 (rr), input='foo derp'
line 1:14 reportAttemptingFullContext d=2 (rr), input='foo'
line 2:0 reportAmbiguity d=2 (rr): ambigAlts={1, 2}, input='foo  derp
'

Было бы очень признательно, если бы кто-то смог объяснить, почему эта грамматика неоднозначна и как можно избавиться от этой неоднозначности. Также возможно, что я не понимаю, почему двусмысленность означает:).

Если я уберу предложение TOKE_OPT?, предупреждения go прочь.

Я использую версию ANTLR 4.7.2

1 Ответ

4 голосов
/ 14 января 2020

Эта грамматика действительно неоднозначна, потому что грамматика допускает две интерпретации derp foo derp foo derp: 

(rr (rr (rr derp) foo (rr derp)) foo (rr derp))
(rr (rr derp) foo (rr (rr derp) foo (rr derp)))

(Лично я думаю, что весь этот вопрос было бы легче прочитать, если бы вместо абстрагирования от выражений вы бы просто использовали правдоподобные токены операторов и операндов. Но я отвлекся.)

Antlr4, тип синтаксического анализатора LL, на самом деле не может обрабатывать левую рекурсию. Это обходится путем перевода леворекурсивных правил в простую эквивалентную форму, эффективно изменяя: 

rule: base
    | rule more
    ;

на 

rule: base (more)* ;

Но этого на самом деле недостаточно для обработки типичного случая левой -рекурсивные правила, являющиеся алгебраическими c выражениями. Здесь типичная грамматика может быть такой: 

expr: expr '*' expr
    | expr '+' expr
    | atom
    ;

А намерение выглядит примерно так: 

expr: atom ('*' atom)* ('+' ('*' atom)*)*

Но это сложное преобразование, которое плохо обобщается, так что в действительности делает Antlr это ввести предикаты в каждое правило, которые обеспечивают порядок приоритетов операторов. С этими предикатами грамматика становится однозначной, а также (обычно) соответствует ожиданиям о том, как грамматики выражений должны быть проанализированы.

Однако Antlr может получить предикаты приоритета только в том случае, если нет «скрытых» левых или правильная рекурсия. («Скрытая правая рекурсия» не означает, что рекурсия скрыта. Что скрыто, так это тот факт, что рекурсия происходит в конце правила.) В частности, добавление дополнительного маркера в конце правила скрывает тот факт, что что нетерминал, предшествующий необязательному токену, может быть праворекурсивным, и поэтому Antlr4 не пытается устранить неоднозначность правила с предикатом приоритета. И это оставляет грамматику неоднозначной.

Вы можете обойти это, избегая скрытой правосторонней рекурсии: 

rr
    : rr  TOK1 rr TOKE_OPT
    | rr  TOK1 rr
    | '(' TOK2 ')'
    | TOKDERP
    ;

Теперь, праворекурсивное правило явное, а другое правило (которое заканчивается TOKE_OPT) не является двусмысленным. (Или, по крайней мере, не так неоднозначно.)

Более точное описание алгоритма, используемого Antlr4 для перезаписи правил, см. В конце этого технического отчета в Приложении. 1031 *

...