Skipped possibly matching rule

[mlajtos]

Hello,

I have this rather simple grammar that should parse traditional math expressions such as these:

• 1 + 2
• 1 + 2 * 3
• 2 * (3 + 4)
• sin(2)
• sin(2) + 1
• 1 + sin(2)
• etc.

Test {
  Expression
    = BinaryExpression | UnaryExpression | Atom

  BinaryExpression
    = Expression Atom (UnaryExpression | Atom)
    
  UnaryExpression
    = Atom Group
    
  Group
  	= "(" ListOf<Expression, ","> ")"
    
  Atom
    = symbol | number | Group
    
  symbol
    = letter+ | "+" | "-" | "*" | "/" | "@"
    
  number
  	= digit+
}

It does not follow any operator precedence and is strictly left-to-right (i.e. long left scope).

I see BinaryExpression as faulty since one can't use more complex infix operator, e.g. a (+) b won't be parsed as BinaryExpression even though Atom can be Group, which can be symbol. Rather, Ohm will try to parse it as UnaryExpression even though it could match BinaryExpression just fine. More complex examples will also fail, e.g. a (f@g) b.

I can't wrap my head around why this grammar will skip possibly matching rule. Any ideas please?

[pdubroy]

At position 0, it tries to match Expression → BinaryExpression → Expression. This is left recursive, so the inner Expression fails. But, since BinaryExpression only has one alternative, that means that it also fails.

What you probably want to do is to eliminate the alternation in the body of Expression, and instead create a precedence between the different types of expression. This ensures that the left recursive application of BinaryExpression eventually succeeds. For example, here is a snippet from a Smalltalk grammar that I wrote a while back:

    Expression =
      | variable assign Expression  -- assignment
      | KeywordExpression

    KeywordExpression =
      | KeywordExpression KeywordMessage  -- rec
      | BinaryExpression

    KeywordMessage = (keyword BinaryExpression)+

    BinaryExpression =
      | BinaryExpression BinaryMessage  -- rec
      | UnaryExpression

    BinaryMessage = binarySelector UnaryExpression

    UnaryExpression =
      | UnaryExpression UnaryMessage  -- rec
      | Primary

[mlajtos]

@pdubroy Thank you ❤️, this seems to work nicely. I believe it can still be more elegant, but this works for all examples I could think of.

Test {
  Expression
    = BinaryExpression
    
  BinaryExpression =
    | BinaryExpression UnaryExpression UnaryExpression --one
    | BinaryExpression Atom UnaryExpression --two
    | UnaryExpression

  UnaryExpression  =
    | UnaryExpression #(~space) Group --one // Could not get it to work without excluding the space
    | Atom

  Group
  	= "(" ListOf<Expression, ","> ")"
    
  Atom
    = symbol | number | Group
    
  symbol
    = letter+ | "+" | "-" | "*" | "/" | "@"
    
  number
    = digit+
}

Without BinaryExpression_two, this 1+(1) won't be parsed.