Является ли грамматика QML LALR (1)?

Вот грамматика 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'

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

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

qml grammar lr lalr lr1
person Swordow    schedule 12.12.2019    source источник
comment
Я отредактировал ваш вопрос, включив в него грамматику, на которую вы ссылаетесь (или, по крайней мере, ее часть). Мне непонятно, откуда взялись identifier и value, так как они не определены в файле, на который вы ссылаетесь; Я предполагаю, что это жетоны. В SO считается плохим стилем включать основной контент для вопроса в виде ссылки. Если владелец репозитория Github отредактирует файл, что он может сделать в любое время, это может сделать вопрос и любой ответ бессмысленными. Пожалуйста, избегайте таких ссылок в будущем.   -  person rici    schedule 12.12.2019
comment
Спасибо!! identifier почти во многих случаях является токеном. Кроме того, я предположил, что value является токеном.   -  person Swordow    schedule 13.12.2019

Ответы (1)


arrow_upward
1
arrow_downward

Примечание:

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

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

Спасибо @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, возможно, обратившись к таблице символов, то вы могли бы решить эту проблему, используя своего рода лексическую обратную связь.

person rici    schedule 12.12.2019
comment
Спасибо! Как вы сказали, это не LR (1), поэтому я думаю, что это неправильная грамматика QML, используемая в QT, и я был введен в заблуждение qml.bnf в github. Грамматика QML, используемая в QT, является грамматикой LALR. QLALR — это генератор парсеров для LALR-грамматик. Он используется для создания внешних интерфейсов для QML(code.qt.io/ cgit/qt/qlarr.git/tree), но я не нашел правильную грамматику для qml. Возможно, я мог бы удалить method_call method_body javascript method method_attribute value и argument, которые используются для поддержки встроенного javascript и остальных является LR(1). - person Swordow; 13.12.2019
comment
Я переписываю грамматику и удаляю токен value, значение которого не удалось понять, добавляю одно правило lambda ::= 'function' method_body и изменяю attribute_value на attribute_value ::= method_call | lambda | item, и это LR(1). - person Swordow; 13.12.2019
comment
Чтобы уменьшить конфликт «элемент» и «тип», QML использует следующий трюк: все типы начинаются с заглавной буквы. Итак, нам просто нужно переписать правило «типа», например, тип: id_with_capital_latter, и ввести этот нетерминал в грамматику. - person mishmashru; 15.01.2020
comment
@mishmashru: Интересно. Это, конечно, не очевидно ни из вопроса, ни из процитированной грамматики. У вас случайно нет ссылочки? - person rici; 15.01.2020
comment
@mishmashru: Интересно. В соответствии с предоставленным URL-адресом rici обнаружил следующее: обратите внимание, что в обоих случаях имя типа должно начинаться с заглавной буквы, чтобы его можно было объявить как тип объекта QML в файле QML из Типы объектов QML и Определение типов объектов с помощью документов QML - person Swordow; 02.02.2020