scala / scala/scala-parser-combinators

Potential bug with indirect left-recursion

Open
#247 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Scala
Stars
679
Forks
131
Avg merge
8h 25m
Merged PRs (30d)
3

Description

I've isolated a 3-rule pattern, where I'd expect the parser to succeed for a given input, but it fails instead. The sample grammar:

RuleA ::= RuleB.
RuleB ::= IDENTIFIER
        | RuleC '.' IDENTIFIER
        .
RuleC ::= RuleB
        | RuleA
        .

The implementation:

import scala.util.parsing.combinator._
import scala.util.parsing.combinator.syntactical.StandardTokenParsers

object SimpleParser extends StandardTokenParsers with PackratParsers {
  lexical.delimiters ++= List(".", "$")

  lazy val ruleA: PackratParser[String] = ruleB <~ "$"
  lazy val ruleB: PackratParser[String] = (ident
                                       ||| ruleC ~> "." ~> ident)
  lazy val ruleC: PackratParser[String] = (ruleB
                                       ||| ruleA)

  def main(args: Array[String]) = {
    println(ruleA(new PackratReader(new lexical.Scanner("x.x$"))))
  }
}

It fails for input x.x$, telling me that it expects a $ instead of the ..

For me, this seems to be a problem with how indirect left-recursion is handled. I'm not sure if the original algorithm is incapable of handling this pattern, or this is an implementation bug.

Edit:
I've accidentally used | (first matching alt.) instead of ||| (longest matching alt.), I've fixed that in the code, but doesn't change the outcome.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Run the provided SimpleParser example with PackratParsers and the input x.x$ to reproduce the failure. Read the indirect left-recursion handling and compare it with the linked packrat algorithm; done means establishing whether this is an implementation bug or a limitation of the algorithm and recording the resulting behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
scala
Domain
compilers
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.