Is QML Grammar LALR(1)?

Question

Here is a QML grammar (extracted from 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'

Is it LALR(1)? My program raises a reduce/reduce conflict for the closure I[n] which contains the conflicting items:

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

Answer 1

Note:

The following answer was written on the basis of the information provided in the question. As it happens, the actual implementation of QML only accepts user declarations for types whose names start with an upper case letter, while names of properties must start with a lower case letter. (Many built-in types have names which start with lower case letters, too. So it's not quite as simple as just dividing identifiers into two categories in the lexical scan based on their first letter. Built-in types and keywords still need to be recognised as such.)

Unfortunately, I haven't been able to find a definitive QML grammar, or even a formal description of the syntax. The comments above were based on Qt's QML Reference.

Thanks to @mishmashru for bringing the above to my attention.

---

The grammar is ambiguous so the parser generator correctly identifies a reduce/reduce conflict.

In particular, consider the following simplified productions extracted from the grammar, where most alternatives have been removed to focus on the conflict:

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

Now, consider the body which starts

{ x {

We'll suppose that the parser has just seen x and is now looking at the second {, to figure out what action(s) to take.

If x is an ordinary identifier (whatever "ordinary" might mean, then it can resolve to item, which is an alternative for attribute_value. Then the second { presumably starts a method_body, which is also an alternative for attribute_value.

If, on the other hand, x is a type, then we're looking at an object, which starts type body. And in that case the second { is the start of the interior body.

So the parser needs to decide whether to make x into an attribute_value directly, or to make it into a type. The decision cannot be made at this point, because the { lookahead token doesn't provide enough information.

So it's clear that the grammar is not LR(1).

Without knowing anything more about the problem domain, it's hard to give good advice. If it is possible to distinguish identifier and type, perhaps by consulting a symbol table, then you could solve this problem by using some kind of lexical feedback.