Last active
August 25, 2022 19:41
-
-
Save bilal-fazlani/948456b5c2cfa3d46ce2a9288d4759cb to your computer and use it in GitHub Desktop.
Eliminating left recursion using zio-parser
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import zio.parser.Syntax._ | |
| import zio.Chunk | |
| import zio.parser.Syntax | |
| sealed trait IntegerExpression | |
| case class IntegerValueExpression(value: Int) extends IntegerExpression { | |
| override def toString: String = value.toString | |
| } | |
| sealed trait IntegerOperator | |
| case object Plus extends IntegerOperator{ | |
| override def toString: String = " + " | |
| } | |
| case object Minus extends IntegerOperator{ | |
| override def toString: String = " - " | |
| } | |
| case class Pair(operator: IntegerOperator, expression: IntegerValueExpression) { | |
| override def toString: String = s"${operator.toString}${expression.toString}" | |
| } | |
| case class Compound( | |
| left: IntegerValueExpression, | |
| right: Chunk[Pair] | |
| ) extends IntegerExpression{ | |
| override def toString: String = s"${left.toString}, [${right.mkString(",")}]" | |
| } | |
| trait IntegerSyntax { | |
| private lazy val plus = string(" + ", Plus).widen[IntegerOperator] | |
| private lazy val minus = string(" - ", Minus).widen[IntegerOperator] | |
| private lazy val int = digit.repeat0.transform[IntegerValueExpression]( | |
| x => IntegerValueExpression(x.mkString.toInt), | |
| x => Chunk.fromIterable(x.toString) | |
| ) | |
| private lazy val operatorSyntax = plus | minus | |
| private lazy val compound: Syntax[String, Char, Char, Compound] = | |
| (int ~ (operatorSyntax ~ int).repeat) | |
| .transform[Compound]( | |
| { case (left, right) => | |
| Compound(left, right.map { case (a, b) => Pair(a, b) }) | |
| }, | |
| complex => | |
| ( | |
| complex.left, | |
| complex.right.map(pair => (pair.operator, pair.expression)) | |
| ) | |
| ) | |
| lazy val syntax = | |
| compound.widen[IntegerExpression] | int.widen[IntegerExpression] | |
| } | |
| sealed trait IntExpression | |
| case class Value(value: Integer) extends IntExpression { | |
| override def toString: String = value.toString | |
| } | |
| case class PlusExpression(left: IntExpression, right: IntExpression) | |
| extends IntExpression | |
| case class MinusExpression(left: IntExpression, right: IntExpression) | |
| extends IntExpression | |
| object Transformer { | |
| def transformLeftToRight(integer: IntegerExpression): IntExpression = | |
| integer match { | |
| case IntegerValueExpression(value) => Value(value) | |
| case Compound(left, right) => | |
| right.foldLeft[IntExpression](Value(left.value)) { | |
| case (left, Pair(Plus, right)) => | |
| PlusExpression(left, Value(right.value)) | |
| case (left, Pair(Minus, right)) => | |
| MinusExpression(left, Value(right.value)) | |
| } | |
| } | |
| } | |
| object RunApp extends App with IntegerSyntax { | |
| val input = "1 + 2 - 3 + 4 - 5" | |
| val parsed = syntax.parseString(input) | |
| println(parsed) | |
| //prints: Right(1, [ + 2, - 3, + 4, - 5]) | |
| println(parsed.map(Transformer.transformLeftToRight)) | |
| //prints: Right(MinusExpression(PlusExpression(MinusExpression(PlusExpression(1,2),3),4),5)) | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment