Является ли QML Grammar LALR(1)?

Question

Вот грамматика QML (извлеченная из https://github.com/kropp/intellij-qml/blob/master/grammars/qml.bnf):

/* identifier, value, integer and float are terminals */

qml ::= object  /* Simplified */

object ::= type body
body ::= '{' (property_definition|signal_definition|attribute_assignment|method_attribute)* '}'
type ::= 'double'|'real'|identifier

attribute_assignment ::= (attribute ':')? attribute_value ';'?
item ::= list|object|string|boolean|number|identifier|value
attribute_value ::= method_call|method_body|item|value+

property_definition ::= 'default'? 'readonly'? 'property' ('alias'|'var'|type) property (':' attribute_value)?
signal_definition ::= 'signal' signal ('(' (signal_parameter ',')* signal_parameter? ')')?
signal_parameter ::= ('var'|type) parameter

method_attribute ::= 'function' method '(' (parameter ',')* parameter? ')' method_body

method_call ::= method '(' (argument ',')* argument? ')'

method_body ::= '{' javascript '}'
javascript ::= ('{' javascript '}'|'var'|'['|']'|'('|')'|','|':'|';'|string|identifier|number|value)*

list ::= '[' item? (',' item)* ']'

property ::= identifier
attribute ::= identifier
signal ::= identifier
parameter ::= identifier
method ::= identifier
argument ::= string|boolean|number|identifier|value

number ::= integer|float
boolean ::= 'true'|'false'

Это LALR(1)? Моя программа вызывает конфликт уменьшения / уменьшения для закрытия I[n], которое содержит конфликтующие элементы:

// other items here...
[item ::= identifier . , {]  // -> ACTION[n, {] = reduce to item  
[type ::= identifier . , {]  // -> ACTION[n, {] = reduce to type  
// other items here...

Answer 1

Примечание:

Следующий ответ был написан на основе информации, представленной в вопросе. Как это бывает, фактическая реализация QML принимает объявления пользователей только для типов, имена которых начинаются с буквы верхнего регистра, а имена свойств должны начинаться с буквы нижнего регистра. (Многие встроенные типы также имеют имена, которые начинаются с букв нижнего регистра. Так что это не так просто, как просто разделить идентификаторы на две категории при лексическом сканировании на основе их первой буквы. Встроенные типы и ключевые слова по-прежнему должны быть признан таковым.)

К сожалению, мне не удалось найти точную грамматику QML или даже формальное описание синтаксиса. Комментарии выше были основаны на Qt QML Reference.

Спасибо mishmashru за то, что обратил мое внимание на вышесказанное.

---

Грамматика неоднозначна, поэтому генератор синтаксического анализатора правильно определяет конфликт уменьшения / уменьшения.

В частности, рассмотрите следующие упрощенные конструкции, извлеченные из грамматики, где большинство альтернатив было удалено, чтобы сосредоточиться на конфликте:

body ::= '{' attribute_assignment* '}'
attribute_assignment ::= attribute_value
attribute_value ::= method_body | item
method_body ::= '{' javascript '}'
item ::= object | identifier
object ::= type body
type ::= identifier

Теперь рассмотрим body который начинается

{ x {

Предположим, что парсер только что увидел x и сейчас смотрит на второй {, чтобы выяснить, какие действия следует предпринять.

Если x является обычным идентификатором (что бы ни означало "обычный", тогда он может разрешить item, который является альтернативой attribute_value. Затем второй{ предположительно начинает method_body, который также является альтернативой attribute_value.

Если же, с другой стороны, x это type, то мы смотрим на object, который начинается type body. И в этом случае второй{ это начало интерьера body.

Таким образом, парсеру нужно решить, делать ли x в attribute_value напрямую или превратить его в type. Решение не может быть принято на данном этапе, потому что{ Предварительный токен не предоставляет достаточно информации.

Итак, ясно, что грамматика - это не LR(1).

Не зная больше о проблемной области, трудно дать хороший совет. Если можно отличитьidentifier а также type, возможно, обратившись к таблице символов, тогда вы могли бы решить эту проблему, используя какую-то лексическую обратную связь.