scala / scala/scala-parser-combinators
Potential bug with indirect left-recursion
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
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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