Class: PackratParser::Parser

Inherits:
Object
  • Object
show all
Defined in:
lib/packrat_parser/parser.rb

Overview

A parser combinator. Wraps a function (input, pos) -> Success | Failure.

The four monadic operations (+flat_map+, map, filter, pure) are what the for ... then comprehension in the Ruby fork desugars to, so grammar rules can be written with comprehension syntax:

for x in multitive, _ in term("+"), y in additive then x + y end
# => multitive.flat_map { |x| term("+").flat_map { |_| additive.map { |y| x + y } } }

Direct Known Subclasses

Rule

Instance Method Summary collapse

Constructor Details

#initialize(&fn) ⇒ Parser

Returns a new instance of Parser.



11
12
13
 
# File 'lib/packrat_parser/parser.rb', line 11

def initialize(&fn)
  @fn = fn
end

Instance Method Details

#*(other) ⇒ Object

Sequence, keeping both results (Scala's ~). Run this parser, then other, and on success return the pair [left, right]. The result type is the product of the operands' types, so * (product) is the natural spelling -- and it dovetails with | for choice, mirroring how a regular language is a semiring with choice as the sum and sequence as the product.

Like Scala's ~ this is left-associative and nests, so p * q * r yields [[a, b], c]; Ruby's block-parameter destructuring takes them apart the way Scala's case a ~ b ~ c does:

(p * q * r).map { |(a, b), c| ... }


117
118
119
120
121
122
123
124
125
126
127
128
129
130
 
# File 'lib/packrat_parser/parser.rb', line 117

def *(other)
  # Equivalent to flat_map { |x| other.map { |y| [x, y] } }, written directly
  # so only the result pair (and its Success) is allocated per match, not a
  # fresh intermediate `map` parser.
  Parser.new do |input, pos|
    a = call(input, pos)
    if a.success?
      b = other.call(input, a.pos)
      b.success? ? Success.new([a.value, b.value], b.pos) : b
    else
      a
    end
  end
end

#<<(other) ⇒ Object

Sequence, keeping the left result (Scala's <~). Run this parser, then other, and on success return this parser's value, discarding +other+'s.

number << term(";")   # parse a number followed by ";", yield the number


78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
# File 'lib/packrat_parser/parser.rb', line 78

def <<(other)
  # Equivalent to flat_map { |x| other.map { |_| x } }, but written directly
  # so the combinator graph is built once (at bind time) instead of
  # allocating a fresh `map` parser on every successful match.
  Parser.new do |input, pos|
    a = call(input, pos)
    if a.success?
      b = other.call(input, a.pos)
      b.success? ? Success.new(a.value, b.pos) : b
    else
      a
    end
  end
end

#>>(other) ⇒ Object

Sequence, keeping the right result (Scala's ~>). Run this parser, then other, and on success return +other+'s value, discarding this one's.

term("(") >> additive   # skip "(", yield whatever additive produces


97
98
99
100
101
102
103
104
 
# File 'lib/packrat_parser/parser.rb', line 97

def >>(other)
  # Equivalent to flat_map { |_| other }, written directly to avoid the
  # per-call block dispatch.
  Parser.new do |input, pos|
    a = call(input, pos)
    a.success? ? other.call(input, a.pos) : a
  end
end

#call(input, pos) ⇒ Object

Run this parser against input starting at pos.



16
17
18
 
# File 'lib/packrat_parser/parser.rb', line 16

def call(input, pos)
  @fn.call(input, pos)
end

#filter ⇒ Object

Succeed only when the block returns a truthy value for the parsed result; otherwise fail at the position where this parser started. This is what a when guard in a comprehension desugars to.



45
46
47
48
49
50
51
52
53
54
 
# File 'lib/packrat_parser/parser.rb', line 45

def filter
  Parser.new do |input, pos|
    result = call(input, pos)
    if result.success? && yield(result.value)
      result
    else
      Failure.new(pos, "guard failed")
    end
  end
end

#flat_map ⇒ Object

Sequencing / monadic bind. On success, yield the value to obtain the next parser and run it where this one stopped. Failures short-circuit.



22
23
24
25
26
27
28
29
30
31
32
 
# File 'lib/packrat_parser/parser.rb', line 22

def flat_map
  Parser.new do |input, pos|
    result = call(input, pos)
    if result.success?
      next_parser = yield(result.value)
      next_parser.call(input, result.pos)
    else
      result
    end
  end
end

#map ⇒ Object

Transform the successful value without consuming further input.



35
36
37
38
39
40
 
# File 'lib/packrat_parser/parser.rb', line 35

def map
  Parser.new do |input, pos|
    result = call(input, pos)
    result.success? ? Success.new(yield(result.value), result.pos) : result
  end
end

#opt ⇒ Object

Optional (Scala's opt / p.?). Yields the parsed value, or nil (consuming nothing) when this parser does not match.



158
159
160
161
162
163
 
# File 'lib/packrat_parser/parser.rb', line 158

def opt
  Parser.new do |input, pos|
    result = call(input, pos)
    result.success? ? result : Success.new(nil, pos)
  end
end

#rep ⇒ Object

Zero or more repetitions (Scala's rep / p.*). Always succeeds, yielding an array of the collected values (empty when there are no matches). A match that consumes no input stops the loop, so a nullable parser can't spin forever.



136
137
138
139
140
141
142
143
144
145
146
147
148
 
# File 'lib/packrat_parser/parser.rb', line 136

def rep
  Parser.new do |input, pos|
    values = []
    cur = pos
    loop do
      result = call(input, cur)
      break if !result.success? || result.pos == cur
      values << result.value
      cur = result.pos
    end
    Success.new(values, cur)
  end
end

#rep1 ⇒ Object

One or more repetitions (Scala's rep1 / p.+). Fails if the first match fails; otherwise yields a non-empty array of values.



152
153
154
 
# File 'lib/packrat_parser/parser.rb', line 152

def rep1
  flat_map { |first| rep.map { |rest| [first, *rest] } }
end

#|(other) ⇒ Object

Ordered choice (PEG /). Try this parser; if it fails, try other at the same position. Reports whichever failure reached furthest into the input.



58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
# File 'lib/packrat_parser/parser.rb', line 58

def |(other)
  Parser.new do |input, pos|
    result = call(input, pos)
    if result.success?
      result
    else
      alt = other.call(input, pos)
      if alt.success?
        alt
      else
        alt.pos >= result.pos ? alt : result
      end
    end
  end
end