Неоднозначный не-терминал в GLR

Question

Когда анализатор GLR уменьшает текст до одного и того же нетерминального в двух или более путях, он объединяет поддеревья синтаксического анализа. Для этого Rekers использует для этого «узлы символов».

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

Например, в Техническом отчете Elkhound автор реализовал грамматику C++ для анализатора GLR. Он описывает это:

Грамматика в настоящее время имеет 37 конфликты сдвиг/свёртка, 47 свёртка/свёртка и 8 неоднозначное нетерминальное.

Как я могу отделить двусмысленный и однозначный нетерминал для данного CFG? Где я могу прочитать об этом?

Answer 1

Как узнать, какие нетерминалы могут создавать двусмысленность, упростить конструкцию дерева разбора на практике?

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

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

Наконец, вы не можете вообще (теорему) определить, является ли грамматика неоднозначной. Поскольку нетерминал представляет собой субграмматику, вы не можете вообще определить, является ли какой-либо конкретный нетерминал неоднозначным. Вы можете сделать это для множества особых случаев. (Мой генератор парсера GLR фактически найдет некоторые двусмысленности автоматически в основном путем перечисления возможных расширений нетерминалов).