Удаление неоднозначности в грамматике

Question

У меня есть простой грамматики я сконструированный с проблемой, я не знаю, как решить:

start syntax Prog = prog: Type Id; 

syntax Dot = {Id "."}+ ; 

syntax Id = 
    id: [A-Z_a-z] !>> [0-9A-Z_a-z] \ KW 
    | Rv 
    ; 

syntax Rv = rv: "$" [a-z_A-Z][a-z_A-Z0-9]* ; 

syntax Type = 
    Rv 
    | Ref 
    ; 

syntax Ref = 
    Dot 
    | s: "str" 
    ; 

keyword KW = "str" ; 

layout LAYOUTLIST = LAYOUT* !>> [\t-\n\r\ /] ; 

lexical LAYOUT = [\t-\n\r\ ] ; 

Проблема в том, что мы можем решить с rv тремя различными способами (Id ->Rv) и (Type ->Rv) и (Type ->Ref ->Dot ->Id ->Rv). Проблема в том, что мне нужны как Type s, так и Id s, чтобы быть Rv s. Таким образом, учитывая простую программу:

$a x 

Моя мысль была я мог бы использовать приоритеты, чтобы исправить это (но я предполагаю, что я не очень понимаю, что они делают), изменяя правила для Type быть:

syntax Type = 
    Rv 
    > Ref 
    ; 

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

info(
    "Ambiguity cluster with 2 alternatives", 
    |cwd:///grammar.txt|(0,3,<1,0>,<1,3>)), 
    info(
    "Production unique to the one alternative: Type = Rv ;", 
    |cwd:///grammar.txt|(0,3,<1,0>,<1,3>)), 
    info(
    "Production unique to the other alternative: Dot = {Id \".\"}+ ;", 
    |cwd:///grammar.txt|(0,3,<1,0>,<1,3>)), 
    info(
    "Production unique to the other alternative: {Id \".\"}+;", 
    |cwd:///grammar.txt|(0,3,<1,0>,<1,3>)), 
    info(
    "Production unique to the other alternative: Ref = Dot ;", 
    |cwd:///grammar.txt|(0,3,<1,0>,<1,3>)), 
    info(
    "Production unique to the other alternative: Type = Ref ;", 
    |cwd:///grammar.txt|(0,3,<1,0>,<1,3>)), 
    info(
    "Production unique to the other alternative: Id = Rv ;", 
    |cwd:///grammar.txt|(0,3,<1,0>,<1,3>)), 
    info(
    "The alternatives have different productions at the top, one has \n Type = Rv \nwhile the other has\n Type = Ref ", 
    |cwd:///grammar.txt|(0,3,<1,0>,<1,3>)), 
    warning(
    "You should give this production a good label: \n Ref = Dot ]", 
    |cwd:///grammar.txt|(0,3,<1,0>,<1,3>)), 
    error(
    "To fix this issue, you could restrict the nesting of\n Ref = Dot \nunder\n Type = Ref \nusing the ! operator on argument 0: !labelX\nHowever, you should realize that you are introducing a restriction that makes the language smaller", 
    |cwd:///grammar.txt|(0,3,<1,0>,<1,3>)) 

Итак, что мне нужно, это какой-то способ Rv с быть как Type с и Id сек без неоднозначности при разборе , Это возможно?

Спасибо!

Answer 1

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

Пример исправления:

syntax Type 
    = Rv 
    | "&" Ref 
    ; 

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

Вы могли бы попытаться использовать !>> и \ операторы и ! исключить некоторые предложения и выкладки, но если это может быть сделано без потери предложения от языка, то инструмент диагностики дал бы вам предложение. Таким образом, эти хаки могут решить двусмысленность, но они также изменят дизайн языка и затрудняют программисту предсказать, что разрешено и что не разрешено.

Механизм приоритетов не помогает, так как он предназначен только для взаимно рекурсивных правил иметь различный приоритет, как 1 + (2 * 3) против (1 + 2) * 3

Короче: я выбрал бы для одного или двух изменений в языке такого что синтаксис становится недвусмысленным как для общего анализатора, так и для человеческого глаза.