@@ -20,6 +20,15 @@ import scala.language.implicitConversions
2020
2121// TODO: better error handling (labelling like parsec's <?>)
2222
23+ /** An enumeration of operator associativity values: `Left`, `Right`, and
24+ * `Non`.
25+ */
26+ object Associativity extends Enumeration {
27+ type Associativity = Value
28+
29+ val Left, Right, Non = Value
30+ }
31+
2332/** `Parsers` is a component that ''provides'' generic parser combinators.
2433 *
2534 * There are two abstract members that must be defined in order to
@@ -223,7 +232,7 @@ trait Parsers {
223232 case s @ Success (result, rest) =>
224233 val failure = selectLastFailure(Some (this ), s.lastFailure)
225234 Success (result, rest, failure)
226- case ns : NoSuccess => if (alt.next.pos < next.pos) this else alt
235+ case _ : NoSuccess => if (alt.next.pos < next.pos) this else alt
227236 }
228237 }
229238 }
@@ -316,7 +325,7 @@ trait Parsers {
316325 * @return a `Parser` that -- on success -- returns the result of `q`.
317326 */
318327 def ~> [U ](q : => Parser [U ]): Parser [U ] = { lazy val p = q // lazy argument
319- (for (a <- this ; b <- p) yield b).named(" ~>"
328+ (for (_ <- this ; b <- p) yield b).named(" ~>"
320329 }
321330
322331 /** A parser combinator for sequential composition which keeps only the left result.
@@ -330,7 +339,7 @@ trait Parsers {
330339 * @return a `Parser` that -- on success -- returns the result of `p`.
331340 */
332341 def <~ [U ](q : => Parser [U ]): Parser [T ] = { lazy val p = q // lazy argument
333- (for (a <- this ; b <- p) yield a).named(" <~"
342+ (for (a <- this ; _ <- p) yield a).named(" <~"
334343 }
335344
336345 /**
@@ -372,7 +381,7 @@ trait Parsers {
372381 * The resulting parser fails if either `p` or `q` fails, this failure is fatal.
373382 */
374383 def ~>! [U ](q : => Parser [U ]): Parser [U ] = { lazy val p = q // lazy argument
375- OnceParser { (for (a <- this ; b <- commit(p)) yield b).named(" ~>!"
384+ OnceParser { (for (_ <- this ; b <- commit(p)) yield b).named(" ~>!"
376385 }
377386
378387 /** A parser combinator for non-back-tracking sequential composition which only keeps the left result.
@@ -385,7 +394,7 @@ trait Parsers {
385394 * The resulting parser fails if either `p` or `q` fails, this failure is fatal.
386395 */
387396 def <~! [U ](q : => Parser [U ]): Parser [T ] = { lazy val p = q // lazy argument
388- OnceParser { (for (a <- this ; b <- commit(p)) yield a).named(" <~!"
397+ OnceParser { (for (a <- this ; _ <- commit(p)) yield a).named(" <~!"
389398 }
390399
391400
@@ -448,7 +457,7 @@ trait Parsers {
448457 */
449458 def ^^^ [U ](v : => U ): Parser [U ] = new Parser [U ] {
450459 lazy val v0 = v // lazy argument
451- def apply (in : Input ) = Parser .this (in) map (x => v0)
460+ def apply (in : Input ) = Parser .this (in) map (_ => v0)
452461 }.named(toString+ " ^^^"
453462
454463 /** A parser combinator for partial function application.
@@ -601,7 +610,7 @@ trait Parsers {
601610 p(in) match {
602611 case s @ Success (_, _) => s
603612 case e @ Error (_, _) => e
604- case f @ Failure (msg, next) => Error (msg, next)
613+ case Failure (msg, next) => Error (msg, next)
605614 }
606615 }
607616
@@ -613,7 +622,7 @@ trait Parsers {
613622 * @param p A predicate that determines which elements match.
614623 * @return
615624 */
616- def elem (kind : String , p : Elem => Boolean ) = acceptIf(p)(inEl => kind+ " expected"
625+ def elem (kind : String , p : Elem => Boolean ) = acceptIf(p)(_ => kind + " expected"
617626
618627 /** A parser that matches only the given element `e`.
619628 *
@@ -995,7 +1004,7 @@ trait Parsers {
9951004 */
9961005 def phrase [T ](p : Parser [T ]) = new Parser [T ] {
9971006 def apply (in : Input ) = p(in) match {
998- case s @ Success (out , in1) =>
1007+ case s @ Success (_ , in1) =>
9991008 if (in1.atEnd) s
10001009 else s.lastFailure match {
10011010 case Some (failure) => failure
@@ -1032,9 +1041,100 @@ trait Parsers {
10321041 = OnceParser { (for (a <- this ; b <- commit(p)) yield new ~ (a,b)).named(" ~"
10331042
10341043 override def ~> [U ](p : => Parser [U ]): Parser [U ]
1035- = OnceParser { (for (a <- this ; b <- commit(p)) yield b).named(" ~>"
1044+ = OnceParser { (for (_ <- this ; b <- commit(p)) yield b).named(" ~>"
10361045
10371046 override def <~ [U ](p : => Parser [U ]): Parser [T ]
1038- = OnceParser { (for (a <- this ; b <- commit(p)) yield a).named(" <~"
1047+ = OnceParser { (for (a <- this ; _ <- commit(p)) yield a).named(" <~"
1048+ }
1049+
1050+ import Associativity ._
1051+
1052+ /** A parser that respects operator the precedence and associativity
1053+ * conventions specified in its constructor.
1054+ *
1055+ * @param primary a parser that matches atomic expressions (the atomicity is
1056+ * from the perspective of binary operators). May include
1057+ * unary operators or parentheses.
1058+ * @param binop a parser that matches binary operators.
1059+ * @param prec_table a list of tuples, each of which encodes a level of
1060+ * precedence. Precedence is encoded highest to lowest.
1061+ * Each precedence level contains an Associativity value
1062+ * and a list of operators.
1063+ * @param makeBinop a function that combines two operands and an operator
1064+ * into a new expression. The result must have the same type
1065+ * as the operands because intermediate results become
1066+ * operands to other operators.
1067+ */
1068+ class PrecedenceParser [Exp ,Op ,E <: Exp ](primary : Parser [E ],
1069+ binop : Parser [Op ],
1070+ prec_table : List [(Associativity , List [Op ])],
1071+ makeBinop : (Exp , Op , Exp ) => Exp ) extends Parser [Exp ] {
1072+ private def decodePrecedence : (Map [Op , Int ], Map [Op , Associativity ]) = {
1073+ var precedence = Map .empty[Op , Int ]
1074+ var associativity = Map .empty[Op , Associativity ]
1075+ var level = prec_table.length
1076+ for ((assoc, ops) <- prec_table) {
1077+ precedence = precedence ++ (for (op <- ops) yield (op, level))
1078+ associativity = associativity ++ (for (op <- ops) yield (op, assoc))
1079+ level -= 1
1080+ }
1081+ (precedence, associativity)
1082+ }
1083+ val (precedence, associativity) = decodePrecedence
1084+ private class ExpandLeftParser (lhs : Exp , minLevel : Int ) extends Parser [Exp ] {
1085+ def apply (input : Input ): ParseResult [Exp ] = {
1086+ (binop ~ primary)(input) match {
1087+ case Success (op ~ rhs, next) if precedence(op) >= minLevel => {
1088+ new ExpandRightParser (rhs, precedence(op), minLevel)(next) match {
1089+ case Success (r, nextInput) => new ExpandLeftParser (makeBinop(lhs, op, r), minLevel)(nextInput);
1090+ case ns => ns // dead code
1091+ }
1092+ }
1093+ case _ => {
1094+ Success (lhs, input);
1095+ }
1096+ }
1097+ }
1098+ }
1099+
1100+ private class ExpandRightParser (rhs : Exp , currentLevel : Int , minLevel : Int ) extends Parser [Exp ] {
1101+ private def nextLevel (nextBinop : Op ): Option [Int ] = {
1102+ if (precedence(nextBinop) > currentLevel) {
1103+ Some (minLevel + 1 )
1104+ } else if (precedence(nextBinop) == currentLevel && associativity(nextBinop) == Associativity .Right ) {
1105+ Some (minLevel)
1106+ } else {
1107+ None
1108+ }
1109+ }
1110+ def apply (input : Input ): ParseResult [Exp ] = {
1111+ def done : ParseResult [Exp ] = Success (rhs, input)
1112+ binop(input) match {
1113+ case Success (nextBinop,_) => {
1114+ nextLevel(nextBinop) match {
1115+ case Some (level) => {
1116+ new ExpandLeftParser (rhs, level)(input) match {
1117+ case Success (r, next) => new ExpandRightParser (r, currentLevel, minLevel)(next)
1118+ case ns => ns // dead code
1119+ }
1120+ }
1121+ case None => done
1122+ }
1123+ }
1124+ case _ => done
1125+ }
1126+ }
1127+ }
1128+
1129+ /** Parse an expression.
1130+ */
1131+ def apply (input : Input ): ParseResult [Exp ] = {
1132+ primary(input) match {
1133+ case Success (lhs, next) => {
1134+ new ExpandLeftParser (lhs,0 )(next)
1135+ }
1136+ case noSuccess => noSuccess
1137+ }
1138+ }
10391139 }
10401140}
0 commit comments