Является ли эта грамматика двусмысленной?

Question

Я пытаюсь определить язык, используя Jison с очень маленькой пунктуацией для делимитации - например, CoffeeScript, но без отступа. Это то, чего я хочу достичь:

# Definition 
object1, object2 
    property1 = value1, 
    property2 = value2 

# Definition 
object3 property = value 

# Statement 
object1 + object2 + object3 

Это определяет три объекта с некоторыми свойствами и добавляет их. Обратите внимание, что первое определение указывает два объекта, используя список имен, а второй показывает, что пробелы не должны быть значительными.

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

definition 
    : name_list property_list 
    ; 

name_list 
    : name 
    | name_list ',' name 
    ; 

property_list 
    : property 
    | property_list ',' property 
    ; 

property 
    : name '=' name 
    ; 

Теперь я добавить правила для выражения части грамматики, в довольно обычным способом, насколько я могу сказать:

expr 
    : expr '+' expr 
    | expr '/' expr 
    | name 
    ; 

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

- reduce by rule: name_list -> name 
- reduce by rule: expr -> name 

Я считаю, что грамматика быть однозначным, но как я могу убедить Jison это? Кажется, что, возможно, нужно смотреть вперед на два токена вместо одного, но это глупое предположение, и документация Jison отмечает, что он (пока?) Не поддерживает LL (k) грамматики.

Answer 1

Вы не показываете всю грамматику, но похоже, что ваша проблема заключается в том, что она не может отличить expr от простого имени и начала объявления с единственным именем в названии список. Рассмотрим входы

A B = C 

и

A B C = D 

первый случай является единственным определение A с одним свойством, в то время как второй является выражением A с последующим определением для B.

Проблема заключается в том, что анализатор должен решить, между этими случаями после того, как увидел A и глядя на упреждающую выборку из B, но она не может - она ​​нуждается в более опережение (чтобы увидеть, что после B)

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

1. Изменение языка. Это может быть так, что утверждение, являющееся только одним именем, не имеет никакого смысла. Таким образом, вы можете изменить язык, чтобы иметь отдельные statement правило, не разрешает простые имена:

   statement: expr '+' expr | expr '/' expr ; 
   expr: statement | name ; 
   

   теперь он может различать между statement и declaration без необходимости дополнительного предпросмотра, как statement должен содержать оператор.

2. Измените инструмент. Вы можете использовать опцию bison %glr-parser или инструмент, такой как btyacc, который может обрабатывать не-LALR (1) грамматики. Однако я не совсем уверен, что поддерживает Джисон.

3. Имитировать дополнительный просмотр в лексере. Вы можете использовать свой лексер для вас. У вас может быть шаблон lexer, который соответствует [a-zA-Z]+[ \t\n]*= (то есть имя, за которым следует знак =), и возвратите специальный токен propname вместо name. Тогда ваш property правило становится:

   property: propname name ;