Есть ли другое решение проблемы «висящего другого», кроме «сопоставить ближе»?

Следующая контекстно-свободная грамматика представляет неоднозначность типа «висящее другое» (представьте, что обозначает, а обозначает, а обозначает какой-то другой вид инструкции или блока): Например, может быть проанализирован как или как (это самое простое / самое короткое неоднозначное слово для этой грамматики).б с $a$if expr then$b$else$c$ aacbc(a(acbc))(a(ac)bc

$$\begin{aligned} S &\rightarrow aSbS \;|\; aS \;|\; c\\ \end{aligned}$$ $aacbc$$(a(acbc))$$(a(ac)bc)$

«Стандартный» способ разрешить эту «неопределенную неопределенность» заставляет оператор «else» ( ) соединяться с ближайшим / внутренним «if-then» ( ). Это можно сделать следующим образом: Эта грамматика однозначна. В приведенном выше примере он анализ .а $b$$a$ (a(acbc)

$$\begin{aligned} S &\rightarrow aTbS \;|\; aS \;|\; c\\ T &\rightarrow aTbT \;|\; c\\ \end{aligned}$$ $(a(acbc))$

Вопрос: Есть ли другой естественный способ устранить неоднозначность, которая заставила бы анализировать ? Другими словами, я ищу грамматику, которая генерирует тот же язык, что и два выше, однозначно, и который анализирует как .a a c b c a a c b c ( a ( a c ) b c $(a(ac)bc)$$aacbc$$aacbc$$(a(ac)bc)$

Замечание: Моя первая попытка была следующей: который разрешает неоднозначность мере необходимости - но эта грамматика все еще неоднозначна: может быть проанализирован как или как . aacbcaacbacbc(a(ac)b(acbc))(a(acb(ac))bc

$$\begin{aligned} S &\rightarrow aSbS \;|\; aU \;|\; c\\ U &\rightarrow aU \;|\; c\\ \end{aligned}$$ $aacbc$$aacbacbc$$(a(ac)b(acbc))$$(a(acb(ac))bc)$

$a$$b$$a$$b$$c$$b$

Традиционное «сопоставление ближайшего» висячего разрешения сопоставляет каждое закрытие с самым последним, еще не имеющим аналогов открытием. Это означает, что между совпадающим открытием и его совпадающим закрытием никогда не бывает непревзойденного открытия (или закрытия).

$($$()()$$)$

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

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

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

Итак, вот немного неуклюжая грамматика:

$$\begin{aligned} S&\to U \;|\; M \\ U&\to T \;|\; a U b T \;|\; a U b c \;|\; a M b U \\ M&\to a M b M \;|\; c \\ T&\to a T \;|\; a c \\ \end{aligned}$$

$S$$M$$U$$a$$T$$a$$T$$T$$U$$U$$T$

$U$$U$$S$$M^* U$$S$$M$$U$$M$$U$

Вероятно, есть лучший обходной путь, чем тот, который я выбрал. Но этот, кажется, работает, и он хорошо работает с анализатором GLR Бизона, который я использовал для его тестирования; этот синтаксический анализатор жалуется на неоднозначные разборы, если вы не пишете дополнительный код для обработки неоднозначности, и мне было лень это делать. Я протестировал его со строками до 20 открытых + закрытий, и, похоже, он дал однозначный анализ для каждой правильно вложенной последовательности, без создания анализа для неправильно вложенных последовательностей.

Возьмите a + b + c + d + e и abcde. Есть два очевидных способа, как грамматика может их проанализировать, но есть один способ, который мы используем.

В случае с «болтающимся остальным» это не совсем то, как люди смотрят на это. Вместо этого синтаксис интерпретируется как «если», за которым следует ноль, один или несколько «еще, если», а затем необязательный «еще».