Рекурсивный спуск с тем же префиксом

Я изучаю рекурсивный приличный синтаксический анализ и придумываю некоторые сценарии, в которых, я думаю, алгоритм не работает. Один из них, учитывая эту простую грамматику:

S → E;
E → id | id + id

Тогда строка id + id; действует на языке этой грамматики. Однако, если мы выполняем алгоритм рекурсивного спуска, он происходит от S в E затем к id, который является первым соответствующим терминалом. Теперь вход на + и мы вернулись в S пытаясь сопоставить ; который тогда терпит неудачу; но нет другого правила на выбор на уровне S,

Я думаю, что грамматика не является двусмысленной, поскольку в языке есть только 2 строки id; а также id + id;каждый из которых имеет уникальное дерево разбора. Общая проблема здесь состоит в том, что нетерминал имеет продукцию с теми же префиксами и потенциально делает выбор, который соответствует на более глубоком уровне в рекурсии, но создает недопустимые входные данные для более мелких уровней.

Я читал о типичных проблемах с рекурсивным спуском, таких как левая рекурсия, но нигде не нашел проблем, упомянутых выше. Так это действительно проблема или я что-то упустил?

Я нашел авторитетный ответ из книги Parsing Techniques: A Practical Guide p.182-188 которые классифицируют вышеупомянутый подход как наивный рекурсивный приличный и выдвигают на первый план ту же проблему. Есть два решения, которые всегда работают для общего случая без упреждения (поскольку в общем случае требуемая длина упреждения увеличивается с длиной префикса): исчерпывающий рекурсивный спуск, который требует использования продолжений, и рекурсивный спуск в ширину.

Источник

3 ответа

Решение

Это проблема в том смысле, что если вы напишите PEG-грамматику подобным образом, она не будет работать. Это известная проблема, иногда описываемая как проблема с разбором PEG, но я не считаю справедливым обвинять PEG в том, что люди, пишущие грамматики, не могут справиться - другие формализмы синтаксического анализа также не защищены от этого.

Если это не грамматика PEG, а обычный старый CFG, проблем не должно быть, если инструмент, который вы используете, не глупый или не прослушивается. Он должен быть в состоянии преобразовать это в работающий синтаксический анализатор, независимо от того, использует ли он рекурсивный спуск или другой алгоритм. Если он использует рекурсивный спуск, он, вероятно, будет использовать lookahead, и это избавит от этого случая.

Источник

Это не проблема, поскольку можно так грамматически учесть грамматику (где первая альтернатива E' пустой):

S → E ;
E → id E'
E' → | + id

За E'мы предсказываем первый вариант, если следующий токен ; и второй, если следующий токен +,

Источник

Я настолько увлечен этим, что собираюсь публиковать мусор, но разве это не решаемо с предвкушением? Что-то вроде:

func recogniseS
    expect(E)
    expect(semicolon)

fund recogniseE
    expect(id)

    if nextTokenIs(plus) then 
        expect(plus)
        expect(id)
    endif

Или, аналогично, вы могли бы переформулировать как:

S → id [+ id];

т.е. суть просто в том, что + не является обязательным. Таким образом, ситуация может быть разрешена до тех пор, пока может быть разрешено что-либо необязательное.

Источник
Другие вопросы по тегам