Parser Combinator ライブラリを使ってみる

数式のところを Java のライブラリで書いてみる。*1

JParsec

http://jparsec.codehaus.org/

@Grab('jparsec:jparsec:2.0')
import org.codehaus.jparsec.Parser
import org.codehaus.jparsec.Parser.Reference
import org.codehaus.jparsec.functors.*
import org.codehaus.jparsec.pattern.CharPredicate

import static org.codehaus.jparsec.Parsers.*
import static org.codehaus.jparsec.Scanners.*

// Parser
Parser<Void> digit  = isChar(Character.&isDigit      as CharPredicate)
Parser<Void> space  = isChar(Character.&isWhitespace as CharPredicate)
// Parser -> Parser
def token  = { Parser parser ->
  sequence(
    space.skipMany(),
    parser,
    space.skipMany(),
    { a, b, c -> b } as Map3)
}
// String -> Parser
def symbol = { String str -> token(string(str)) }
// Parser
Parser<Integer> natural = token(digit.many1().source().map(Maps.TO_INTEGER))
Parser<Integer> integer = token(sequence(string('-'), natural, { a, b -> -b } as Map2)).or(natural)

// Arithmetic Expression
Reference exprRef = Parser.newReference()
Reference termRef = Parser.newReference()
Reference factRef = Parser.newReference()
Parser<Integer> expr = exprRef.lazy() 
Parser<Integer> term = termRef.lazy()
Parser<Integer> fact = factRef.lazy()
exprRef.set(
  term.next({ t ->
    sequence(symbol('+'), expr, { _, e -> t + e } as Map2).or(constant(t))
  } as Map))
termRef.set(
  fact.next({ f ->
    sequence(symbol('*'), term, { _, t -> f * t } as Map2).or(constant(f))
  } as Map))
factRef.set(
  sequence(
    symbol('('),
    expr,
    symbol(')'),
    { lp, x, rp -> x } as Map3).or(natural))
def eval = { String str -> expr.parse(str) } // throws ParserException

// Test
assert eval ("2*3+4")       == 10
assert eval ("2*(3+4)")     == 14
assert eval ("2 * (3 + 4)") == 14

Functional Java

Google Code Archive - Long-term storage for Google Code Project Hosting.
http://groovy.codehaus.org/Functional+Programming+with+Groovy

@Grab('org.functionaljava:fj:3.0')
import fj.F
import fj.F2
import fj.F3
import fj.data.Stream
import fj.parser.Parser

import static fj.Function.curry
import static fj.data.LazyString.fromStream
import static fj.data.List.list
import static fj.data.Option.none
import static fj.data.Option.some_
import static fj.data.Stream.fromString
import static fj.parser.Parser.parser
import static fj.parser.Parser.sequence
import static fj.parser.Parser.value
import static fj.parser.Parser.CharsParser.string
import static fj.parser.Parser.StreamParser.satisfy

// Parser<Character>
Parser digit = satisfy(none(), some_(), { Character.isDigit it } as F)
Parser space = satisfy(none(), some_(), { Character.isWhitespace it } as F)
// Parser -> Parser
def token  = { Parser parser ->
  space.repeat().bind(parser, space.repeat(), curry({ ls, p, rs -> p } as F3))
}
// String -> Parser
def symbol = { String str ->
  token(string(none(), some_(), str))
}

// Parser<Integer>
Parser natural = token(digit.repeat1().map({ fromStream(it).toString().toInteger() } as F))
Parser integer = token(symbol('-').bind(natural, curry({ _, n -> -n } as F2))).or(natural)

// Arithmetic Expression
Parser expr, term, fact
expr = parser({ inp ->
  term.bind({ t ->
    sequence(list(symbol("+"), expr))
      .bind({ value(t + it.index(1)) } as F)
      .or(value(t))
  } as F).parse(inp)
} as F)
term = parser({ inp ->
  fact.bind({ f ->
    sequence(list(symbol("*"), term))
      .bind({ value(f * it.index(1)) } as F)
      .or(value(f))
  } as F).parse(inp)
} as F)
fact = parser({ inp ->
  sequence(list(symbol("("), expr, symbol(")")))
    .bind({ value(it.index(1)) } as F)
    .or(natural).parse(inp)
} as F)
def eval = { String str ->
  expr.parse(fromString(str)).success().value()
}

// Test
assert eval ("2*3+4")       == 10
assert eval ("2*(3+4)")     == 14
assert eval ("2 * (3 + 4)") == 14

*1:エントリを分けた