1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
$:.unshift File.dirname(__FILE__) + "/../lib"
require "parslet"
require "pp"
# Parses strings like "var1 and (var2 or var3)" respecting operator precedence
# and parentheses. After that transforms the parse tree into an array of
# arrays like this:
#
# [["1", "2"], ["1", "3"]]
#
# The array represents a DNF (disjunctive normal form). Elements of outer
# array are connected with "or" operator, while elements of inner arrays are
# joined with "and".
#
class Parser < Parslet::Parser
rule(:space) { match[" "].repeat(1) }
rule(:space?) { space.maybe }
rule(:lparen) { str("(") >> space? }
rule(:rparen) { str(")") >> space? }
rule(:and_operator) { str("and") >> space? }
rule(:or_operator) { str("or") >> space? }
rule(:var) { str("var") >> match["0-9"].repeat(1).as(:var) >> space? }
# The primary rule deals with parentheses.
rule(:primary) { lparen >> or_operation >> rparen | var }
# Note that following rules are both right-recursive.
rule(:and_operation) {
(primary.as(:left) >> and_operator >>
and_operation.as(:right)).as(:and) |
primary }
rule(:or_operation) {
(and_operation.as(:left) >> or_operator >>
or_operation.as(:right)).as(:or) |
and_operation }
# We start at the lowest precedence rule.
root(:or_operation)
end
class Transformer < Parslet::Transform
rule(:var => simple(:var)) { [[String(var)]] }
rule(:or => { :left => subtree(:left), :right => subtree(:right) }) do
(left + right)
end
rule(:and => { :left => subtree(:left), :right => subtree(:right) }) do
res = []
left.each do |l|
right.each do |r|
res << (l + r)
end
end
res
end
end
pp tree = Parser.new.parse("var1 and (var2 or var3)")
# {:and=>
# {:left=>{:var=>"1"@3},
# :right=>{:or=>{:left=>{:var=>"2"@13}, :right=>{:var=>"3"@21}}}}}
pp Transformer.new.apply(tree)
# [["1", "2"], ["1", "3"]]
|
