Довольно печатная двусмысленная грамматика - PullRequest
Новая
       66

Довольно печатная двусмысленная грамматика

0 голосов
/ 17 мая 2018

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

Точные операторы неизвестны до времени выполнения и могут изменяться во время выполнения, когда пользователь вводит новый оператор.У меня есть поддержка префиксных, постфиксных и инфиксных (слева, справа и неассоциативных) операторов.Инфиксные левые и постфиксные операторы смешиваются на уровне приоритета одновременно.То же самое относится к инфиксным правым и префиксным операторам.Операторы также могут вставлять полные выражения, таким образом, если if-then-else и if-then могут быть реализованы как префиксный оператор.(хотя это может не быть разумным ходом.)

Вот пример, использующий упомянутые операторы if-then-else и if-then, которые здесь предполагаются на одном и том же уровне приоритета.Очевидно, что выражение if a then if b then c else d неоднозначно, поскольку его можно интерпретировать как if a then (if b then c) else d или if a then (if b then c else d).Во время красивой печати алгоритм должен знать, что нужно использовать круглые скобки, даже если оба оператора имеют одинаковый уровень приоритета и имеют совместимую ассоциативность (справа).

Предупреждающий пример: добавьте еще один префиксный оператор, скажем, inc того же приоритетакак если-то-еще и если-то.Теперь предположим, что произвольное множество P ⊂ H x O, где H - это множество операторных отверстий, а O - это множество операторов.Под набором подразумевается отношение, которое сообщает, когда необходимо добавить скобки.Изучите выражения if a then inc b else c и if a then (inc if b then c) else d.Первый требует, чтобы (if-then-else.2, inc) не входил в P, а второй требует обратного.Это противоречит предположению, что проблема может быть решена с помощью некоторого отношения или порядка.Можно попытаться сказать, что пусть (inc.1, if-then) будет в P, делая последнее выражение if a then inc (if b then c) else d, но тогда inc if a then b становится inc (if a then b), который содержит слишком много скобок.

Насколько мне известно, грамматика является контекстомсвободно.Я немного шаткую по определению.

Синтаксический анализатор свободно основан на статье здесь .Я использую Haskell.

1 Ответ

0 голосов
/ 20 мая 2018

Вы можете построить отношение порядка частичного порядка между всеми операторами на основе их фактической ассоциативности и приоритета, как определено.

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

Скажем, отношение имеет тип rel[Operator parent, int pos, Operator child].

Предполагается, что вы можете сгенерировать это отношение из объявлений приоритета и ассоциативности, так как они применяются во время выполнения, а затем использовать это отношение, добавляя скобки во время красивой печати.легко.Если кортеж [parent, pos, child] находится в отношении, то вы печатаете скобки, в противном случае нет (или наоборот, если отношение инвертировано).

Как получить это отношение?Здесь приведен пример кода для грамматического формализма Раскаля, который генерирует его из относительных приоритетов между операторами: https://github.com/usethesource/rascal/blob/master/src/org/rascalmpl/library/lang/rascal/grammar/definition/Priorities.rsc

Он начинается с таких правил: 

E = left E "*" E  
  > left E "+" E
  ;

и производит что-то вроде: 

{<"*", 0, "+">, <"*", 2, "+"> // priority between * and + 
,<"+", 2, "+">, <"*", 2, "*"> // left associativity of * and +
}

В этой таблице объясняется, для каких вложений в каких позициях требуются дополнительные скобки, поэтому, если + вложен в * в 0-й позиции, вам необходимо напечатать скобки

Предположим, что вместо этого у вас есть таблица приоритетов, которая гласит: 

0 * left
1 + left

или что-то напрасно, тогда можно построить аналогичное отношение.Мы должны сгенерировать кортеж для каждого i, j уровней в таблице, где i < j.Конечно, вам нужно будет найти правило для каждого оператора, чтобы выяснить, каковы правильные позиции.

Для этих таблиц и относительных приоритетов, как в Rascal, важно для транзитивного закрытия отношения, однако некоторые кортежи не должны добавляться, если вы не хотите генерировать слишком много скобок, пока довольнопечать.

А именно, если родительское правило является наиболее правым рекурсивным, а дочернее правило - самым левым рекурсивным, то необходима скобка.Тоже наоборот.Но в противном случае нет.Рассмотрим этот пример: 

E = "if" E "then "E"
  > E "+" E
  ;

В этом случае нам нужны скобки в самом правом отверстии, но не в защищенном отверстии между «если» и «тогда».Подобные примеры для индексирования правил, таких как E "[" E "]" и т. Д.

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

Так что для приведенного выше примера мы сгенерируем это: 

{<"if", 3, "+">, // and not <"if", 1, "+"> because the 1 position is not left-most recursive, even though the "+" is right-most recursive.
}

Статьи по этой теме, но они используютТо же отношение для разбора, а не для разбора:

...