Module: ScopedSearch::QueryLanguage::Parser

Included in:
Compiler
Defined in:
lib/scoped_search/query_language/parser.rb

Overview

The Parser module adss methods to the query language compiler that transform a string into an abstract syntax tree, which can be used for query generation.

This module depends on the tokeinzer module to transform the string into a stream of tokens, which is more appropriate for parsing. The parser itself is a LL(1) recursive descent parser.

Constant Summary collapse

DEFAULT_SEQUENCE_OPERATOR = 
:and
LOGICAL_INFIX_OPERATORS = 
[:and, :or]
LOGICAL_PREFIX_OPERATORS = 
[:not]
NULL_PREFIX_OPERATORS = 
[:null, :notnull]
COMPARISON_OPERATORS = 
[:eq, :ne, :gt, :gte, :lt, :lte, :like, :unlike, :in, :notin]
ALL_INFIX_OPERATORS = 
LOGICAL_INFIX_OPERATORS + COMPARISON_OPERATORS
ALL_PREFIX_OPERATORS = 
LOGICAL_PREFIX_OPERATORS + COMPARISON_OPERATORS + NULL_PREFIX_OPERATORS

Instance Method Summary collapse

Instance Method Details

#parse ⇒ Object

Start the parsing process by parsing an expression sequence



19
20
21
22
23
24
25
 
# File 'lib/scoped_search/query_language/parser.rb', line 19

def parse
  @tokens = tokenize
  while @tokens.last.is_a?(Symbol) do
    @tokens.delete_at(@tokens.size - 1)
  end
  parse_expression_sequence(true).simplify
end

#parse_comparison ⇒ Object

Parses a comparison



81
82
83
84
 
# File 'lib/scoped_search/query_language/parser.rb', line 81

def parse_comparison
  next_token if peek_token == :comma # skip comma
  return (String === peek_token) ? parse_infix_comparison : parse_prefix_comparison
end

#parse_expression_sequence(root_node = false) ⇒ Object

Parses a sequence of expressions



28
29
30
31
32
33
34
35
36
 
# File 'lib/scoped_search/query_language/parser.rb', line 28

def parse_expression_sequence(root_node = false)
  expressions = []

  next_token if !root_node && peek_token == :lparen # skip starting :lparen
  expressions << parse_logical_expression until peek_token.nil? || peek_token == :rparen
  next_token if !root_node && peek_token == :rparen # skip final :rparen

  return ScopedSearch::QueryLanguage::AST::LogicalOperatorNode.new(DEFAULT_SEQUENCE_OPERATOR, expressions, root_node)
end

#parse_infix_comparison ⇒ Object

Parses an infix expression, i.e. 



109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
 
# File 'lib/scoped_search/query_language/parser.rb', line 109

def parse_infix_comparison
  lhs = parse_value
  return case peek_token
    when nil
      lhs
    when :comma
      next_token # skip comma
      lhs
    else
      if COMPARISON_OPERATORS.include?(peek_token)
        comparison_operator = next_token
        rhs = parse_value
        ScopedSearch::QueryLanguage::AST::OperatorNode.new(comparison_operator, [lhs, rhs])
      else
        lhs
      end
  end
end

#parse_logical_expression ⇒ Object

Parses a logical expression.



39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
# File 'lib/scoped_search/query_language/parser.rb', line 39

def parse_logical_expression
  lhs = case peek_token
    when nil;             nil
    when :lparen;         parse_expression_sequence
    when :not;            parse_logical_not_expression
    when :null, :notnull; parse_null_expression
    when *LOGICAL_INFIX_OPERATORS; parse_logical_infix_expression
    else;                 parse_comparison
  end

  if LOGICAL_INFIX_OPERATORS.include?(peek_token)
    parse_logical_infix_expression([lhs])
  else
    lhs
  end
end

#parse_logical_infix_expression(previous = []) ⇒ Object 



56
57
58
59
60
 
# File 'lib/scoped_search/query_language/parser.rb', line 56

def parse_logical_infix_expression(previous = [])
  operator = next_token
  rhs = parse_logical_expression
  ScopedSearch::QueryLanguage::AST::LogicalOperatorNode.new(operator, previous + [rhs])
end

#parse_logical_not_expression ⇒ Object

Parses a NOT expression

Raises:



63
64
65
66
67
68
69
70
71
72
73
 
# File 'lib/scoped_search/query_language/parser.rb', line 63

def parse_logical_not_expression
  next_token # = skip NOT operator
  negated_expression = case peek_token
    when :not;    parse_logical_not_expression
    when :lparen; parse_expression_sequence
    else          parse_comparison
  end

  raise ScopedSearch::QueryNotSupported, "No operands found" if negated_expression.empty?
  return ScopedSearch::QueryLanguage::AST::OperatorNode.new(:not, [negated_expression])
end

#parse_multiple_values ⇒ Object

Parse values in the format (val, val, val)



129
130
131
132
133
134
135
 
# File 'lib/scoped_search/query_language/parser.rb', line 129

def parse_multiple_values
  next_token if  peek_token == :lparen #skip :lparen
  value = []
  value << current_token if String === next_token until peek_token.nil? || peek_token == :rparen
  next_token if peek_token == :rparen  # consume the :rparen
  value
end

#parse_null_expression ⇒ Object

Parses a set? or null? expression



76
77
78
 
# File 'lib/scoped_search/query_language/parser.rb', line 76

def parse_null_expression
  return ScopedSearch::QueryLanguage::AST::OperatorNode.new(next_token, [parse_value])
end

#parse_prefix_comparison ⇒ Object

Parses a prefix comparison, i.e. without an explicit field: 



87
88
89
90
91
92
93
94
95
96
97
 
# File 'lib/scoped_search/query_language/parser.rb', line 87

def parse_prefix_comparison
  token = next_token
  case token
  when :in
    parse_prefix_in(true)
  when :notin
    parse_prefix_in(false)
  else
    ScopedSearch::QueryLanguage::AST::OperatorNode.new(token, [parse_value])
  end
end

#parse_prefix_in(inclusion) ⇒ Object 



99
100
101
102
103
104
105
106
 
# File 'lib/scoped_search/query_language/parser.rb', line 99

def parse_prefix_in(inclusion)
  cmp, log = inclusion ? [:eq, :or] : [:ne, :and]
  leaves = parse_multiple_values.map do |x|
    leaf = ScopedSearch::QueryLanguage::AST::LeafNode.new(x)
    ScopedSearch::QueryLanguage::AST::OperatorNode.new(cmp, [leaf])
  end
  ScopedSearch::QueryLanguage::AST::LogicalOperatorNode.new(log, leaves)
end

#parse_value ⇒ Object

This can either be a constant value or a field name.



138
139
140
141
142
143
144
145
146
147
 
# File 'lib/scoped_search/query_language/parser.rb', line 138

def parse_value
  if String === peek_token
    ScopedSearch::QueryLanguage::AST::LeafNode.new(next_token)
  elsif ([:in, :notin].include? current_token)
    value = parse_multiple_values().join(',')
    ScopedSearch::QueryLanguage::AST::LeafNode.new(value)
  else
    raise ScopedSearch::QueryNotSupported, "Value expected but found #{peek_token.inspect}"
  end
end