Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

added a pure functional implementation of operator precedence parsing#470

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Draft
peteraldous wants to merge5 commits intoscala:main
base:main
Choose a base branch
Loading
frompeteraldous:precedence
Draft
Show file tree
Hide file tree
Changes fromall commits
Commits
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
100 changes: 100 additions & 0 deletionsshared/src/main/scala/scala/util/parsing/combinator/Parsers.scala
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -20,6 +20,15 @@ import scala.language.implicitConversions

// TODO: better error handling (labelling like parsec's <?>)

/** An enumeration of operator associativity values: `Left`, `Right`, and
* `Non`.
*/
object Associativity extends Enumeration {
type Associativity = Value

val Left, Right, Non = Value
}

/** `Parsers` is a component that ''provides'' generic parser combinators.
*
* There are two abstract members that must be defined in order to
Expand DownExpand Up@@ -1037,4 +1046,95 @@ trait Parsers {
override def <~ [U](p: => Parser[U]): Parser[T]
= OnceParser{ (for(a <- this; _ <- commit(p)) yield a).named("<~") }
}

import Associativity._

/** A parser that respects operator the precedence and associativity
* conventions specified in its constructor.
*
* @param primary a parser that matches atomic expressions (the atomicity is
* from the perspective of binary operators). May include
* unary operators or parentheses.
* @param binop a parser that matches binary operators.
* @param prec_table a list of tuples, each of which encodes a level of
* precedence. Precedence is encoded highest to lowest.
* Each precedence level contains an Associativity value
* and a list of operators.
* @param makeBinop a function that combines two operands and an operator
* into a new expression. The result must have the same type
* as the operands because intermediate results become
* operands to other operators.
*/
class PrecedenceParser[Exp,Op,E <: Exp](primary: Parser[E],
binop: Parser[Op],
prec_table: List[(Associativity, List[Op])],
makeBinop: (Exp, Op, Exp) => Exp) extends Parser[Exp] {
private def decodePrecedence: (Map[Op, Int], Map[Op, Associativity]) = {
var precedence = Map.empty[Op, Int]
var associativity = Map.empty[Op, Associativity]
var level = prec_table.length
for ((assoc, ops) <- prec_table) {
precedence = precedence ++ (for (op <- ops) yield (op, level))
associativity = associativity ++ (for (op <- ops) yield (op, assoc))
level -= 1
}
(precedence, associativity)
}
val (precedence, associativity) = decodePrecedence
private class ExpandLeftParser(lhs: Exp, minLevel: Int) extends Parser[Exp] {
def apply(input: Input): ParseResult[Exp] = {
(binop ~ primary)(input) match {
case Success(op ~ rhs, next) if precedence(op) >= minLevel => {
new ExpandRightParser(rhs, precedence(op), minLevel)(next) match {
case Success(r, nextInput) => new ExpandLeftParser(makeBinop(lhs, op, r), minLevel)(nextInput);
case ns => ns // dead code
}
}
case _ => {
Success(lhs, input);
}
}
}
}

private class ExpandRightParser(rhs: Exp, currentLevel: Int, minLevel: Int) extends Parser[Exp] {
private def nextLevel(nextBinop: Op): Option[Int] = {
if (precedence(nextBinop) > currentLevel) {
Some(minLevel + 1)
} else if (precedence(nextBinop) == currentLevel && associativity(nextBinop) == Associativity.Right) {
Some(minLevel)
} else {
None
}
}
def apply(input: Input): ParseResult[Exp] = {
def done: ParseResult[Exp] = Success(rhs, input)
binop(input) match {
case Success(nextBinop,_) => {
nextLevel(nextBinop) match {
case Some(level) => {
new ExpandLeftParser(rhs, level)(input) match {
case Success(r, next) => new ExpandRightParser(r, currentLevel, minLevel)(next)
case ns => ns // dead code
}
}
case None => done
}
}
case _ => done
}
}
}

/** Parse an expression.
*/
def apply(input: Input): ParseResult[Exp] = {
primary(input) match {
case Success(lhs, next) => {
new ExpandLeftParser(lhs,0)(next)
}
case noSuccess => noSuccess
}
}
}
}
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
package scala.util.parsing.combinator

// import scala.language.implicitConversions

import java.io.StringReader
import org.junit.Test
import org.junit.Assert.{ assertEquals, assertTrue, fail }
import scala.util.parsing.input.StreamReader

class PrecedenceParsersTest {

abstract class Op
object Plus extends Op {
override def toString = "+"
}
object Minus extends Op {
override def toString = "-"
}
object Mult extends Op {
override def toString = "*"
}
object Divide extends Op {
override def toString = "/"
}
object Equals extends Op {
override def toString = "="
}

abstract class Node
case class Leaf(v: Int) extends Node {
override def toString = v.toString
}
case class Binop(lhs: Node, op: Op, rhs: Node) extends Node {
override def toString = s"($lhs $op $rhs)"
}

object ArithmeticParser extends RegexParsers {
val prec = List(
(Associativity.Left, List(Mult, Divide)),
(Associativity.Left, List(Plus, Minus)),
(Associativity.Right, List(Equals)))
def integer: Parser[Leaf] = "[0-9]+".r ^^ { (s: String) => Leaf(s.toInt) }
def binop: Parser[Op] = "+" ^^^ Plus | "-" ^^^ Minus | "*" ^^^ Mult | "/" ^^^ Divide | "=" ^^^ Equals
def expression = new PrecedenceParser(integer, binop, prec, Binop.apply)
}

def testExp(expected: Node, input: String): Unit = {
ArithmeticParser.expression(StreamReader(new StringReader(input))) match {
case ArithmeticParser.Success(r, next) => {
assertEquals(expected, r);
assertTrue(next.atEnd);
}
case e => {
fail(s"Error parsing $input: $e");
}
}
}

@Test
def basicExpTests: Unit = {
testExp(Leaf(4), "4")
testExp(Binop(Leaf(1), Plus, Leaf(2)), "1 + 2")
testExp(Binop(Leaf(2), Mult, Leaf(1)), "2 * 1")
}

@Test
def associativityTests: Unit = {
testExp(Binop(Binop(Leaf(1), Minus, Leaf(2)), Plus, Leaf(3)), "1 - 2 + 3")
testExp(Binop(Leaf(1), Equals, Binop(Leaf(2), Equals, Leaf(3))), "1 = 2 = 3")
}

@Test
def precedenceTests: Unit = {
testExp(Binop(Binop(Leaf(0), Mult, Leaf(5)), Minus, Leaf(2)), "0 * 5 - 2")
testExp(Binop(Leaf(3), Plus, Binop(Leaf(9), Divide, Leaf(11))), "3 + 9 / 11")
testExp(Binop(Binop(Leaf(6), Plus, Leaf(8)), Equals, Leaf(1)), "6 + 8 = 1")
testExp(Binop(Leaf(4), Equals, Binop(Leaf(5), Minus, Leaf(3))), "4 = 5 - 3")
}
}
[8]ページ先頭
©2009-2025 Movatter.jp