Устранение неоднозначной грамматики без обращения к GLR-парсеру - PullRequest
Новая
       13

Устранение неоднозначной грамматики без обращения к GLR-парсеру

3 голосов
/ 01 декабря 2010

У меня есть грамматика, которая имеет две разные возможности при разборе 'if' expr 'then'.Есть простое «назначение», такое как if foo then bar=1; else bar=0;, и вот что я называю «if_block» кода, который может содержать одно или несколько «назначений»: 

if foo then
{
    bar = 1;
    if xyz then abc = -1;
}
else
{
    bar = 0;
    if xyz then
    {
       abc = 0;
    }
}

Я обрабатываю вложенные if_blocksпосредством висящего остального сопоставленного / несопоставленного блока.

Моя ( очень упрощенная) грамматика в основном: 

program : if_blocks
if_blocks : if_block | if_block if_blocks
if_block : assignments
assignments : assignment | assignment assignments
assignment : simple_assignment | if_assignment

Так что мое затруднительное положениес назначением, за которым следует if_block.Например: 

foo = bar;
if foo then
{
   foo = foo + 1;
}

foo = bar; - это присвоение, которое в этом случае должно быть уменьшено до if_block.if foo then { ... } сам по себе является if_block.Таким образом, весь этот код - if_block + if_block (сокращен до if_blocks).Но после того, как foo = bar; сведено к назначению, не хватает предварительного просмотра, чтобы узнать, является ли if foo then другим назначением (в пределах foo = bar; if_block) или это отдельный if_block.

Я добавил %glr-parser, что, кажется, решает эту проблему, но я сталкиваюсь с другими ситуациями, когда выживают несколько ветвей синтаксического анализа, и я не могу примирить различные ветви S / R.Что является общепринятой практикой для такого рода ситуаций, когда отсутствует переключение на совершенно другой сканер / анализатор (для меня было бы много работы по изучению и переписыванию кода) или изменение языка (что я не могу сделать)?Есть ли простое разрешение (как-то определяемое с помощью %dprec?) С использованием GLR или настройки грамматики?

1 Ответ

1 голос
/ 01 декабря 2010

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

Большинство генераторов синтаксических анализаторов (включая YACC и Bison) имеют некоторый способ сказать, что, когда для токена существует конфликт shift-vs-Reduce, предпочитайте «shift», который можно использовать для достижения именно этого эффекта для * 1007. * else ключевое слово. Я не знаю, что такое идиома для YACC или Bison, но это должно быть легко найти в информации описания грамматики.

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

...