Pollak D. Beginning Scala
Подождите немного. Документ загружается.
CHAPTER 8 ■ PARSERS—BECAUSE BNF IS NOT JUST FOR ACADEMICS ANYMORE
237
Let’s tighten up the example a little by only accepting rest if it’s fewer than 18 digits so
we don’t overflow the
Long:
lazy val long2: Parser[Long] = positiveDigit ~ rep(digit) ^? {
case first ~ rest if rest.length < 18 => (first :: rest).mkString.toLong
}
In this case, we’ve used the ^? method to connect the predicate to the conversion. In
order for the
Parser to succeed, we need to satisfy the predicate, and the partial function
passed to
^? must be defined for the result of the predicate. In this case, the partial func-
tion will be satisfied if the
length of rest is fewer than 18 characters.
We’ve also changed from a method to a
lazy val. This is because the method does not
do the parsing; rather, the method combines smaller
Parsers into a single Parser. This
building of the
Parser need only happen once, and the resulting Parser can be used over
and over, even simultaneously on multiple threads. With the basics under our belt, let’s
put our parser mojo to use.
The Calculator Parser
In this section, we’re going to using the parser combinator to build a four-function calcu-
lator. Yep, it’s time to swat flies with a Buick. You’ll see how easy it is to describe what we
want to build, create a
Parser for it, and then make sure the Parser returns the correct
things. But first, let’s define a utility trait that will allow us to more easily run the
Parsers
from the Scala REPL. The
RunParser trait can be mixed into any Parser and adds a run
method.
import scala.util.parsing.combinator._
trait RunParser {
this: RegexParsers =>
type RootType
def root: Parser[RootType]
def run(in: String): ParseResult[RootType] = parseAll(root, in)
}
The RunParser trait can be mixed into a class that extends RegexParsers. By mixing
RunParser into your Parser, you can type MyParser.run("Thing to test") and see the result.
It’s a convenience trait.
19897ch08.fm Page 237 Wednesday, April 22, 2009 3:54 PM
238
CHAPTER 8
■ PARSERS—BECAUSE BNF IS NOT JUST FOR ACADEMICS ANYMORE
We’ll define the skeleton of our four-function calculator. Let’s first describe how our
calculator works. A sum expression is a product expression followed by zero or more
+ or –
symbols followed by a product expression. A product expression is a factor followed by
zero or more
* or / symbols followed by another factor. This means that the precedence
of production expressions is higher than the precedence of sum expressions. Finally, we
define a factor as a number or parentheses around a sum expression. In BNF,
3
we’d write
<sumExpr> ::= <prodExpr> [("+" <prodExpr>) | ("-" <prodExpr>)]
<prodExpr> ::= <factor> [("*" <factor>) | ("/" <factor>)]
<factor> ::= <float> | ("(" <sumExpr> ")")
We’ve described our parsing rules in English and BNF. Now let’s see how that trans-
lates to Scala.
object CalcSkel extends JavaTokenParsers with RunParser {
lazy val sumExpr = multExpr ~ rep("+" ~ multExpr | "-" ~ multExpr)
lazy val multExpr = factor ~ rep("*" ~ factor | "/" ~ factor)
lazy val factor: Parser[Any] = floatingPointNumber | "(" ~ sumExpr ~ ")"
type RootType = Any
def root = sumExpr
}
We’ve extended JavaTokenParsers, which gives us access to a bunch of stuff that will
parse tokens as defined by the Java Language Specification.
4
We’re taking advantage of
floatingPointNumber and automatic white space consumption between elements. Cool.
Let’s see how this works in the REPL.
scala> CalcSkel.run("1")
res0: [1.2] parsed: ((1~List())~List())
scala> CalcSkel.run("1 + 1")
3. BNF stands for Backus-Naur Form, a common way to describe grammars. See http://
en.wikipedia.org/wiki/Backus–Naur_form.
4. http://java.sun.com/docs/books/jls/third_edition/html/j3TOC.html
19897ch08.fm Page 238 Wednesday, April 22, 2009 3:54 PM
CHAPTER 8 ■ PARSERS—BECAUSE BNF IS NOT JUST FOR ACADEMICS ANYMORE
239
res1: [1.6] parsed: ((1~List())~List((+~(1~List()))))
scala> CalcSkel.run("1 + 1 / 17")
res2: [1.11] parsed: ((1~List())~List((+~(1~List((/~17))))))
scala> CalcSkel.run("1 + 1 / archer")
res3: CalcSkel.ParseResult[CalcSkel.RootType] =
[1.9] failure: `(' expected but ` ' found
1 + 1 / archer
^
This is pretty encouraging. Our English and BNF descriptions of what we wanted to
parse correspond very closely to our Scala code. Furthermore, our parse correctly parses
valid input and rejects input with errors in it. The results, however, are pretty tough to
read.
Next, let’s turn the results into something that performs the calculations. Our
Parser
doesn’t change, but we add a function to convert the parsed items into a
Double. First
comes Listing 8-1, and then we’ll comb through the code.
Listing 8-1. Calculator Parser
import scala.util.parsing.combinator._
object Calc extends JavaTokenParsers with RunParser {
lazy val sumExpr = prodExpr ~
rep("+" ~> prodExpr ^^ (d => (x: Double) => x + d) |
"-" ~> prodExpr ^^ (d => (x: Double) => x - d)) ^^ {
case seed ~ fs => fs.foldLeft(seed)((a, f) => f(a))
}
19897ch08.fm Page 239 Wednesday, April 22, 2009 3:54 PM
240
CHAPTER 8
■ PARSERS—BECAUSE BNF IS NOT JUST FOR ACADEMICS ANYMORE
lazy val prodExpr = factor ~
rep("*" ~> factor ^^ (d => (x: Double) => x * d) |
"/" ~> factor ^^ (d => (x: Double) => x / d)) ^^ {
case seed ~ fs => fs.foldLeft(seed)((a, f) => f(a))
}
lazy val factor: Parser[Double] =
floatingPointNumber ^^ (_.toDouble) | "(" ~> sumExpr <~ ")"
type RootType = Double
def root = sumExpr
}
First we import the appropriate classes and then get down to business:
import scala.util.parsing.combinator._
object Calc extends JavaTokenParsers with RunParser {
lazy val sumExpr = prodExpr ~
rep("+" ~> prodExpr ^^ (d => (x: Double) => x + d) |
"-" ~> prodExpr ^^ (d => (x: Double) => x - d)) ^^ {
case seed ~ fs => fs.foldLeft(seed)((a, f) => f(a))
}
The rep method results in a List of whatever is parsed by the parameter of rep. When
we match the
+ ~> prodExpr, we convert this into a function that adds the two numbers.
Please note the
~> method. This method matches both items but only passes the stuff on
the right to the converter function. There’s a corresponding
<~ operator. Back to the code.
We’ve got a
prodExpr, which is a Parser[Double] and then a Parser[List[Double => Double]],
and we need to convert this into a
Parser[Double]. The line
case seed ~ fs => fs.foldLeft(seed)((a, f) => f(a))
extracts the seed and the list of functions (add or subtract) and uses foldLeft to perform
the calculation.
We do the same for multiplication and division:
lazy val prodExpr = factor ~
rep("*" ~> factor ^^ (d => (x: Double) => x * d) |
"/" ~> factor ^^ (d => (x: Double) => x / d)) ^^ {
case seed ~ fs => fs.foldLeft(seed)((a, f) => f(a))
}
19897ch08.fm Page 240 Wednesday, April 22, 2009 3:54 PM
CHAPTER 8 ■ PARSERS—BECAUSE BNF IS NOT JUST FOR ACADEMICS ANYMORE
241
Next, we define factor, which is either a number or parentheses around a sumExpr.
Because
sumExpr, prodExpr, and factor reference each other and, thus, are recursive, we
must define the type of at least one of the three
vals so the type inferencer can do its work.
lazy val factor: Parser[Double] =
floatingPointNumber ^^ (_.toDouble) | "(" ~> sumExpr <~ ")"
We convert floatingPointNumber into a Double by passing a function that converts a
String to a Double. Next, we use ~> and <~ to discard the parentheses around sumExpr.
Calc mixes in RunParser, so we have to define the abstract RootType type and the root
method.
type RootType = Double
def root = sumExpr
}
That’s it. We’ve defined the conversions from the Strings and List to Doubles. Let’s see
how well it works.
scala> Calc.run("1")
res0: Calc.ParseResult[Calc.RootType] = [1.2] parsed: 1.0
scala> Calc.run("1 + 1")
res1: Calc.ParseResult[Calc.RootType] = [1.6] parsed: 2.0
scala> Calc.run("1 + 1 / 17")
res2: Calc.ParseResult[Calc.RootType] = [1.11] parsed: 1.0588235294117647
scala> Calc.run("(1 + 1) / 17")
res3: Calc.ParseResult[Calc.RootType] = [1.13] parsed: 0.11764705882352941
19897ch08.fm Page 241 Wednesday, April 22, 2009 3:54 PM
242
CHAPTER 8
■ PARSERS—BECAUSE BNF IS NOT JUST FOR ACADEMICS ANYMORE
In this section, we’ve converted from BNF description of the grammar to a running
application using Scala’s parser combinator library. The example, a four-function calcu-
lator, was very simple. In the next section, we’re going to tackle something more complex.
We’re going to parse JSON.
JSON Parsing
JSON, or JavaScript Object Notation, is a common and lightweight mechanism for exchanging
data over the Internet. JSON is a subset of JavaScript and can be parsed by the fast, stable,
efficient JavaScript parsers that are built into browsers. JSON is as readable as XML, more
compact than XML and corresponds to the types built into most dynamic languages:
strings, numbers, Booleans, arrays, and dictionaries or hash maps.
In this section, we’re going to follow the ECMAScript spec to build our
Parser: we’re
going to copy and paste the spec into our Scala code and literally code our
Parser to the
spec as we go. The only new concept in this
Parser is the regular-expression Parser. The
RegexParsers trait has an implicit conversion from a regular expression to a Parser[String].
If the input matches the regular expression, the matching string will be returned by the
Parser. We use this in the definition of spaces: """\s*""".r.
5
The triple quotes contain a
String that does not support any form of escaping, so \s is the literal \s, rather than escaping
s, and the regular expression \s stands for space. The .r at the end of the String converts
the
String into a regular expression.
The code in Listing 8-2 creates a JSON
Parser.
Listing 8-2. ECMAScript Spec -> JSON Parser
import scala.util.parsing.combinator._
object JSON extends RegexParsers with RunParser {
// translation from ECMAScript spec
// http://www.ecma-international.org/publications/files/ECMA-ST/Ecma-262.pdf
/*
Whitespace
*/
lazy val spaces: Parser[String] = """\s*""".r
5. See the Java RegEx Pattern documentation: http://java.sun.com/javase/6/docs/api/java/util/
regex/Pattern.html.
19897ch08.fm Page 242 Wednesday, April 22, 2009 3:54 PM
CHAPTER 8 ■ PARSERS—BECAUSE BNF IS NOT JUST FOR ACADEMICS ANYMORE
243
/*
Source characters (any valid unicode character)
*/
lazy val sourceCharacter: Parser[Char] = elem("Source Character", c => true)
/*
HexDigit :: one of
0 1 2 3 4 5 6 7 8 9 a b c d e f A B C D E F
*/
lazy val hexDigit: Parser[Char] =
elem("Hex Digit", c => ((c >= '0' && c <= '9') ||
(c >= 'a' && c <= 'f') ||
(c >= 'A' && c <= 'F')))
/*
7.8 Literals
Syntax
Literal ::
NullLiteral
BooleanLiteral
NumericLiteral
StringLiteral
*/
lazy val literal: Parser[Any] =
nullLiteral |
booleanLiteral |
numericLiteral |
stringLiteral
/*
7.8.1 Null Literals
Syntax
NullLiteral ::
null
*/
lazy val nullLiteral: Parser[Any] = spaces ~ "null" ~ spaces ^^^ None
/*
7.8.2 Boolean Literals
Syntax
BooleanLiteral ::
true
19897ch08.fm Page 243 Wednesday, April 22, 2009 3:54 PM
244
CHAPTER 8
■ PARSERS—BECAUSE BNF IS NOT JUST FOR ACADEMICS ANYMORE
false
*/
lazy val booleanLiteral: Parser[Boolean] = spaces ~>
("true" ^^^ true | "false" ^^^ false) <~ spaces
/*
7.8.3 Numeric Literals
Syntax
NumericLiteral ::
DecimalLiteral
HexIntegerLiteral
*/
lazy val numericLiteral: Parser[Double] = spaces ~>
(hexIntegerLiteral | decimalLiteral) <~ spaces
/*
DecimalLiteral ::
DecimalIntegerLiteral . DecimalDigits(opt) ExponentPart(opt)
. DecimalDigits ExponentPart(opt)
DecimalIntegerLiteral ExponentPart(opt)
*/
lazy val decimalLiteral: Parser[Double] =
(decimalIntegerLiteral ~ '.' ~ opt(decimalDigits) ~ opt(exponentPart)) ^^
{case lit ~ _ ~ frac ~ optExp =>
val d: Double = frac.map(f =>
(lit.toString + "." + f.mkString).toDouble) getOrElse lit.toDouble
optExp.map(_(d)) getOrElse d
} |
'.' ~> decimalDigits ~ opt(exponentPart) ^^ {
case dd ~ optExp =>
val d = ("." + dd.mkString).toDouble
optExp.map(_(d)) getOrElse d
} |
decimalIntegerLiteral ~ opt(exponentPart) ^^ {
case dd ~ optExp =>
optExp.map(_(dd)) getOrElse dd
}
19897ch08.fm Page 244 Wednesday, April 22, 2009 3:54 PM
CHAPTER 8 ■ PARSERS—BECAUSE BNF IS NOT JUST FOR ACADEMICS ANYMORE
245
/*
DecimalIntegerLiteral ::
0
NonZeroDigit DecimalDigits(opt)
*/
lazy val decimalIntegerLiteral: Parser[Long] = '0' ^^^ 0L |
nonZeroDigit ~ opt(decimalDigits) ^^ {
case first ~ rest => (first :: (rest getOrElse Nil)).mkString.toLong
}
/*
DecimalDigits ::
DecimalDigit
DecimalDigits DecimalDigit
*/
lazy val decimalDigits: Parser[List[Char]] = rep1(decimalDigit)
/*
DecimalDigit :: one of
0 1 2 3 4 5 6 7 8 9
*/
lazy val decimalDigit = elem("Decimal Digit", c => c >= '0' && c <= '9')
/*
NonZeroDigit :: one of
1 2 3 4 5 6 7 8 9
*/
lazy val nonZeroDigit = elem("Non-zero Digit", c => c >= '1' && c <= '9')
/*
ExponentPart ::
ExponentIndicator SignedInteger
*/
lazy val exponentPart: Parser[Double => Double] =
exponentIndicator ~> signedInteger ^^ {
si => n => n.doubleValue * Math.pow(10.0, si.doubleValue)
}
19897ch08.fm Page 245 Wednesday, April 22, 2009 3:54 PM
246
CHAPTER 8
■ PARSERS—BECAUSE BNF IS NOT JUST FOR ACADEMICS ANYMORE
/*
ExponentIndicator :: one of
e E
*/
lazy val exponentIndicator = elem("exp ind", c => c == 'e' || c == 'E')
/*
SignedInteger ::
DecimalDigits
+ DecimalDigits
- DecimalDigits
*/
lazy val signedInteger: Parser[Long] =
decimalDigits ^^ (_.mkString.toLong) |
'+' ~> decimalDigits ^^ (_.mkString.toLong) |
'-' ~> decimalDigits ^^ (_.mkString.toLong * -1L)
/*
HexIntegerLiteral ::
0x HexDigit
0X HexDigit
HexIntegerLiteral HexDigit
*/
lazy val hexIntegerLiteral: Parser[Double] =
(elem('0') ~ (elem('x') | 'X')) ~> rep1(hexDigit) ^^
(s => java.lang.Long.parseLong(s.mkString, 16).toDouble)
/*
7.8.4 String Literals
A string literal is zero or more characters enclosed in single or double quotes.
Each character may be represented by an escape sequence.
Syntax
StringLiteral ::
" DoubleStringCharacters(opt) "
' SingleStringCharacters(opt) '
*/
lazy val stringLiteral: Parser[String] =
'"' ~> opt(doubleStringCharacters) <~ '"' ^^ (_ getOrElse "") |
'\'' ~> opt(singleStringCharacters) <~ '\'' ^^ (_ getOrElse "")
19897ch08.fm Page 246 Wednesday, April 22, 2009 3:54 PM