Почему макет вокруг необязательных частей продукции вызывает двусмысленность?

Почему в Rascal, когда на позиции необязательной части продукции находится макет, это вызывает двусмысленность? Например. "{ }" неоднозначен, как Start1, в то время как он отлично анализируется как Start2 из следующей грамматики, которая, как я ожидал, будет точно идентичной.

layout Layout                               = " "?;
start syntax Start1                         = "{" "c"? "}";
start syntax Start2                         = "{" "c" "}"
                                            | "{" "}";

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

Очевидно, что в этом коде нет большого количества дубликатов, и Start2 здесь хороший вариант, но это всего лишь пример. Я работаю с грамматикой со многими продуктами, которые содержат три или четыре необязательные части, и в последнем случае обозначение, отображаемое в Start2, уже требует дублирования необязательных частей продукта 2 ^ 4 = 16 раз, что действительно проблематично в моем случае. мнение.


whitespace ambiguous-grammar rascal
person Olav Trauschke    schedule 06.07.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Ваша грамматика сначала расширяется, прежде чем синтаксический анализатор генерируется примерно так:

layout Layout                         = " "?;
syntax " "?                           =  | " ";
syntax Start1                         = "{" Layout "c"? Layout "}";
syntax "c"?                           =  | "c";
lexical " "                           = [\ ];
lexical "c"                           = [c];
lexical "{"                           = [{];
lexical "}"                           = [}];
syntax Start2                         = "{" Layout "c" Layout "}"
                                      | "{" Layout "}";
syntax start[Start1] = Layout Start1 Layout;
syntax start[Start2] = Layout Start2 Layout;

Таким образом, для ввода, такого как { } (пробел между завитушками), пробел может быть получен первым экземпляром Layout в правой части правила Start1 или вторым экземпляром Layout. Поскольку синтаксический анализатор создает все деревья вывода, в обоих случаях синтаксический анализ является, так сказать, неоднозначным.

Обычно двусмысленность разрешается введением жадности с помощью следующего ограничения:

layout Layout = " "? !>> " "

или (эквивалентно) так:

layout Layout = " "? !>> [\ ]

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

person Jurgen Vinju    schedule 06.07.2016
comment
Спасибо за подробный ответ. Мне действительно стало намного понятнее, когда я увидел, насколько расширена грамматика и как легко понять решение. Мне все еще кажется немного странным, что это необходимо. Разве не было бы полезно иметь вариант вопросительного знака (и звездочки), доступный для тех случаев, когда вас не волнует расположение макета? Я могу себе представить, что это будет использоваться довольно много. - person Olav Trauschke; 06.07.2016
comment
Да, мы тоже думали об этом; а жадный? или * может легко привести к очень неожиданным и трудным для отладки ошибкам синтаксического анализа. В этом отношении легче исправить двусмысленность, чем ошибку синтаксического анализа. Декларативное устранение неоднозначности также может привести к ошибкам синтаксического анализа, но, по крайней мере, это явно видно. Тем не менее, мы думаем о том, чтобы ввести активную семантику на лексическом уровне для подъязыков с обычными токенами, сохраняя при этом контекстно-свободную часть в целом. Будущая работа! - person Jurgen Vinju; 06.07.2016