← Back to branch summary

~ubuntu-branches/debian/sid/scala/sid

« back to all changes in this revision

Viewing changes to src/library/scala/util/parsing/combinator/PackratParsers.scala

  • Committer: Package Import Robot
  • Author(s): Emmanuel Bourg, Mehdi Dogguy, Lucas Satabin, Frank S. Thomas, Emmanuel Bourg
  • Date: 2015-06-05 23:52:59 UTC
  • mfrom: (1.2.11)
  • Revision ID: package-import@ubuntu.com-20150605235259-wk00vgk83dh8o19g
Tags: 2.10.5-1
http://bugs.debian.org/744278
http://bugs.debian.org/754935
http://bugs.debian.org/724704
* Team upload.

[ Mehdi Dogguy ]
* New upstream release (Closes: #744278).

[ Lucas Satabin ]
* Update patches
* Update the clean target
* Update paths of elements to install
* Update watch file

[ Frank S. Thomas ]
* Remove myself from Uploaders.

[ Emmanuel Bourg ]
* The package has been adopted by the Java Team (Closes: #754935)
* Patched the build to avoid downloading libraries from the Internet
* Replaced the minified JavaScript files with unobfuscated ones
* No longer build scala-partest.jar until diffutils is packaged or replaced
* debian/watch: Fixed the versions matched (x.y.z instead of x.y.z..z)
* debian/rules:
  - Added the missing get-orig-source target (Closes: #724704)
  - Improved the clean target
* debian/control:
  - Build depend on scala (>= 2.10) and bnd
  - Use canonical URLs for the Vcs-* fields
  - Standards-Version updated to 3.9.6 (no changes)
* Switch to debhelper level 9

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/library/scala/util/parsing/combinator/PackratParsers.scala
1
1
/*                     __                                               *\
2
2
**     ________ ___   / /  ___     Scala API                            **
3
 
**    / __/ __// _ | / /  / _ |    (c) 2006-2011, LAMP/EPFL             **
 
3
**    / __/ __// _ | / /  / _ |    (c) 2006-2013, LAMP/EPFL             **
4
4
**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
5
5
** /____/\___/_/ |_/____/_/ | |                                         **
6
6
**                          |/                                          **
7
7
\*                                                                      */
8
8
 
9
 
 
10
9
package scala.util.parsing.combinator
11
10
 
12
11
import scala.util.parsing.combinator._
13
12
import scala.util.parsing.input.{ Reader, Position }
14
13
import scala.collection.mutable
 
14
import scala.language.implicitConversions
15
15
 
16
16
/**
17
 
 *  <p>
18
 
 *    <code>PackratParsers</code> is a component that extends the parser combinators
19
 
 *    provided by <a href="Parsers.html"><code>Parsers</code></a> with a memoization facility
20
 
 *    (``Packrat Parsing'').
21
 
 *  </p>
22
 
 *  <p>
23
 
 *    Packrat Parsing is a technique for implementing backtracking, recursive-descent parsers, with the
24
 
 *    advantage that it guarantees unlimited lookahead and a linear parse time. Using this technique,
25
 
 *    left recursive grammars can also be accepted.
26
 
 *  </p>
27
 
 *  <p>
28
 
 *    Using <code>PackratParsers</code> is very similar to using <code>Parsers</code>:
29
 
 *  <ul>
30
 
 *    <li> any class/trait that extends <code>Parsers</code> (directly or through a subclass) can
31
 
 *         mix in <code>PackratParsers</code>. Example:
32
 
 *         <code>object MyGrammar extends StandardTokenParsers with PackratParsers </code>
33
 
 *    <li> each grammar production previously declared as a <code>def</code> without formal parameters
34
 
 *         becomes a <code>lazy val</code>, and its type is changed from <code>Parser[Elem]</code>
35
 
 *         to <code>PackratParser[Elem]</code>. So, for example, <code>def production: Parser[Int] = {...}</code>
36
 
 *         becomes <code>lazy val production: PackratParser[Int] = {...}</code>
37
 
 *    <li> Important: using <code>PackratParser</code>s is not an ``all or nothing'' decision. They
38
 
 *         can be free mixed with regular <code>Parser</code>s in a single grammar.
39
 
 *  </ul>
40
 
 *  </p>
41
 
 *  <p>
42
 
 *    Cached parse results are attached to the <i>input</i>, not the grammar.
43
 
 *    Therefore, <code>PackratsParser</code>s require a <code>PackratReader</code> as input, which
44
 
 *    adds memoization to an underlying <code>Reader</code>. Programmers can create <code>PackratReader</code>
45
 
 *    objects either manually, as in <code>production(new PackratReader(new lexical.Scanner("input")))</code>,
46
 
 *    but the common way should be to rely on the combinator <code>phrase</code> to wrap a given
47
 
 *    input with a <code>PackratReader</code> if the input is not one itself.
48
 
 *  </p>
 
17
 *  `PackratParsers` is a component that extends the parser combinators
 
18
 *  provided by [[scala.util.parsing.combinator.Parsers]] with a memoization
 
19
 *  facility (''Packrat Parsing'').
 
20
 *
 
21
 *  Packrat Parsing is a technique for implementing backtracking,
 
22
 *  recursive-descent parsers, with the advantage that it guarantees
 
23
 *  unlimited lookahead and a linear parse time. Using this technique,
 
24
 *  left recursive grammars can also be accepted.
 
25
 *
 
26
 *  Using `PackratParsers` is very similar to using `Parsers`:
 
27
 *   - any class/trait that extends `Parsers` (directly or through a subclass)
 
28
 *     can mix in `PackratParsers`.
 
29
 *     Example: `'''object''' MyGrammar '''extends''' StandardTokenParsers '''with''' PackratParsers`
 
30
 *   - each grammar production previously declared as a `def` without formal
 
31
 *     parameters becomes a `lazy val`, and its type is changed from
 
32
 *     `Parser[Elem]` to `PackratParser[Elem]`.
 
33
 *     So, for example, `'''def''' production: Parser[Int] = {...}`
 
34
 *     becomes `'''lazy val''' production: PackratParser[Int] = {...}`
 
35
 *   - Important: using `PackratParser`s is not an ''all or nothing'' decision.
 
36
 *     They can be free mixed with regular `Parser`s in a single grammar.
 
37
 *
 
38
 *  Cached parse results are attached to the ''input'', not the grammar.
 
39
 *  Therefore, `PackratsParser`s require a `PackratReader` as input, which
 
40
 *  adds memoization to an underlying `Reader`. Programmers can create
 
41
 *  `PackratReader` objects either manually, as in
 
42
 *  `production('''new''' PackratReader('''new''' lexical.Scanner("input")))`,
 
43
 *  but the common way should be to rely on the combinator `phrase` to wrap
 
44
 *  a given input with a `PackratReader` if the input is not one itself.
49
45
 *
50
46
 * @see Bryan Ford: "Packrat Parsing: Simple, Powerful, Lazy, Linear Time." ICFP'02
51
47
 * @see Alessandro Warth, James R. Douglass, Todd Millstein: "Packrat Parsers Can Support Left Recursion." PEPM'08
52
48
 *
53
49
 * @since 2.8
54
 
 * @author Manohar Jonnalagedda, Tiark Rompf
 
50
 * @author Manohar Jonnalagedda
 
51
 * @author Tiark Rompf
55
52
 */
56
53
 
57
54
trait PackratParsers extends Parsers {
59
56
  //type Input = PackratReader[Elem]
60
57
 
61
58
  /**
62
 
   * A specialized <code>Reader</code> class that wraps an underlying <code>Reader</code>
 
59
   * A specialized `Reader` class that wraps an underlying `Reader`
63
60
   * and provides memoization of parse results.
64
61
   */
65
 
  class PackratReader[+T](underlying: Reader[T]) extends Reader[T]  { outer =>
 
62
  class PackratReader[+T](underlying: Reader[T]) extends Reader[T] { outer =>
66
63
 
67
64
    /*
68
65
     * caching of intermediate parse results and information about recursion
69
66
     */
70
 
 
71
67
    private[PackratParsers] val cache = mutable.HashMap.empty[(Parser[_], Position), MemoEntry[_]]
72
68
 
73
69
    private[PackratParsers] def getFromCache[T](p: Parser[T]): Option[MemoEntry[T]] = {
100
96
    def atEnd: Boolean = underlying.atEnd
101
97
  }
102
98
 
103
 
 
104
99
  /**
105
 
   *  <p>
106
 
   *    A parser generator delimiting whole phrases (i.e. programs).
107
 
   *  </p>
108
 
   *  <p>
109
 
   *    Overridden to make sure any input passed to the argument parser
110
 
   *    is wrapped in a <code>PackratReader</code>.
111
 
   *  </p>
 
100
   *  A parser generator delimiting whole phrases (i.e. programs).
 
101
   *
 
102
   *  Overridden to make sure any input passed to the argument parser
 
103
   *  is wrapped in a `PackratReader`.
112
104
   */
113
105
  override def phrase[T](p: Parser[T]) = {
114
106
    val q = super.phrase(p)
120
112
    }
121
113
  }
122
114
 
123
 
 
124
115
  private def getPosFromResult(r: ParseResult[_]): Position = r.next.pos
125
116
 
126
117
  // auxiliary data structures
148
139
  /**
149
140
   * Implicitly convert a parser to a packrat parser.
150
141
   * The conversion is triggered by giving the appropriate target type:
151
 
   * val myParser: PackratParser[MyResult] = aParser
152
 
   */
 
142
   * {{{
 
143
   *   val myParser: PackratParser[MyResult] = aParser
 
144
   * }}} */
153
145
  implicit def parser2packrat[T](p: => super.Parser[T]): PackratParser[T] = {
154
146
    lazy val q = p
155
147
    memo(super.Parser {in => q(in)})
156
148
  }
157
149
 
158
 
 
159
150
  /*
160
151
   * An unspecified function that is called when a packrat reader is applied.
161
152
   * It verifies whether we are in the process of growing a parse or not.
162
153
   * In the former case, it makes sure that rules involved in the recursion are evaluated.
163
154
   * It also prevents non-involved rules from getting evaluated further
164
155
   */
165
 
 
166
156
  private def recall(p: super.Parser[_], in: PackratReader[Elem]): Option[MemoEntry[_]] = {
167
157
    val cached = in.getFromCache(p)
168
158
    val head = in.recursionHeads.get(in.pos)
237
227
 
238
228
  /**
239
229
   * Explicitly convert a given parser to a memoizing packrat parser.
240
 
   * In most cases, client code should avoid calling <code>memo</code> directly
 
230
   * In most cases, client code should avoid calling `memo` directly
241
231
   * and rely on implicit conversion instead.
242
232
   */
243
233
  def memo[T](p: super.Parser[T]): PackratParser[T] = {