Угловые случаи с GLR, приоритетом и неассоциативностью: предполагаемая семантика?

Question

Да, я один из тех безумных людей, у которых есть проект парсер-генератор. Минимальная LR (1) с операторным приоритетом была довольно простой. Следующей является поддержка GLR, желательно без путаницы угловых случаев вокруг приоритета и ассоциативности (P & A).

Предположим, у вас есть конфликт R / R между правилами с различными уровнями приоритета. Детерминированный синтаксический анализатор может безопасно выбрать (первое) правило с наивысшим приоритетом. Парсер, разработанный для обработки локальной неоднозначности, может быть не уверен, особенно если соответствующие правила сводятся к разным нетерминалам.

Предположим, у вас есть конфликт R / R между правилами с и без характеристик приоритета. Детерминированный парсер может разумно выбрать первое. Если вы спрашиваете о GLR, вы хотите развить и то, и другое, или первое должно явно доминировать над последним? Или этот сценарий достаточно странный, чтобы оправдать отказ от грамматики?

Предположим, у вас конфликт S / R / R, в котором только некоторые из участвующих правил имеют приоритет, и, возможно, маркер предварительного просмотра имеет или не имеет приоритет. Если P & A - это все, что нужно делать перед предвкушением, то токен без прецедента, возможно, должен означать, что все варианты остаются жизнеспособными. Но действительно ли это намеченная семантика здесь?

Предположим, у вас есть неассоциативная декларация на терминале и конфликт S / R / R, когда только ОДНО из участвующих правил производства достигает того же уровня неассоциативного приоритета. Тогда другое правило явно все еще можно уменьшить, но как быть с изменением? Должны ли мы взять это? Что если мы находимся в середине правила таким образом, что это не вызывает той же проблемы неассоциативности? Что если прогнозный токен имеет более высокий приоритет, чем оставшееся уменьшение, или оставшееся уменьшение не имеет приоритета? Как мы можем избежать случайного создания неверного анализа таким образом? Есть ли какая-то хитрость с элементами разбора для создания сдвигового состояния, которое не может пойти не так, или это не относится к сфере анализа GLR?

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

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

Answer 1

Традиционные правила приоритета в стиле yacc нельзя использовать для разрешения конфликтов уменьшения / уменьшения.

Yacc / bison «разрешает» уменьшать / уменьшать конфликты, выбирая первое производство в файле грамматики.Это не имеет ничего общего с приоритетом, и в грамматиках, где вы хотите использовать синтаксический анализатор GLR, это почти наверняка не правильно;вы хотите, чтобы синтаксический анализатор GLR следовал по всем возможным путям.

Для синтаксического анализатора зубров GLR требуется разрешить неоднозначность;то есть грамматика должна быть однозначной.Однако у него есть два «аута»: во-первых, он позволяет вам использовать объявления «динамического приоритета» (что является совершенно другим понятием, хотя в нем используется одно и то же слово);во-вторых, если этого недостаточно, он позволяет вам предоставить собственную функцию разрешения.

Среди других возможностей, функция пользовательского разрешения может принимать оба сокращения, например, путем вставки ветви в AST.Есть некоторые теоретические проблемы с этим подходом для общего синтаксического анализа, но он прекрасно работает с реальными языками программирования, которые, как правило, не являются неоднозначными или, по крайней мере, «не очень неоднозначными».

Типичным случаем для динамического приоритета являетсяреализация (текстового) правила, такого как в C ++ §9.8 / 1:

В грамматике существует неоднозначность, включающая выражения-выражения и объявления : An выражение-выражение с явным преобразованием типа в стиле функции (8.2.3) в качестве крайнего левого подвыражения может быть неотличимо от объявления , где первый декларатор начинается с(.В этих случаях оператор является объявлением .

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

Как следует из его названия, динамический приоритет является динамическим;это правило применяется парсером во время разбора.Алгоритм Бизона GLR применяет эти правила только в случае необходимости;синтаксический анализатор обычно обрабатывает возможные многострочные сокращения (поддерживая их все как возможности).Принудительно применять динамический приоритет только в том случае, когда оба возможных сокращения в конфликте уменьшения / уменьшения сводятся к одному и тому же нетерминалу.

В отличие от этого, алгоритм приоритета yacc, который, как я уже говорил, разрешает только конфликты сдвига / уменьшения, является статическим: он компилируется во время генерации в автомат разбора (по сути, удаляя действия из таблиц переходов), поэтому синтаксический анализатор больше не видит конфликт.

Этот алгоритм был (оправданно) подвергнут критикепо ряду причин, одной из которых является странное поведение неассоциативных объявлений в угловых случаях.Кроме того, правила приоритета плохо сочетаются;поскольку они не ограничены областью действия, они могут в конечном итоге случайно обратиться к продукции, для которой они не были предназначены.Нередко они облегчают грамматические ошибки, скрывая конфликт, который должен был разрешить автор грамматики.

Поэтому рекомендуется избегать угловых случаев :-) Статический приоритет должен быть ограничен первоначально запланированным.варианты использования: простой приоритет операторов и, возможно, документирование эвристики «предпочтение сдвига», которая разрешает висячее разрешение и некоторые сгруппированные операции синтаксического анализа операторов (iirc, хороший пример этого есть в книге о драконах).

Если вы реализуете динамический приоритет, и, если честно, есть веские причины этого не делать, тогда его следует применять к простым, легко выражаемым правилам, таким как правило C ++, упомянутое выше: «если это выглядит как объявление,это декларация ".Еще лучше было бы избегать написания неоднозначных грамматик;Эта особенность C ++ приводит к печально известному «самому неприятному анализу», который, вероятно, в какой-то момент укусил каждого из нас, кто пытался писать программы на C ++.