Class: Dhaka::Grammar

Inherits:
Object
  • Object
show all
Defined in:
lib/dhaka/grammar/grammar.rb

Overview

Abstract base class for grammar specifications.

The following is a grammar specification for simple arithmetic. Precedences are specified as in Yacc - in ascending order of binding strength, with equal-strength symbols on the same level. Production rules are specified for each symbol by specifying the name of the production (used when encoding the Evaluator) and the expansion for that particular production. For example, the production named addition expands the symbol 'E' to the list of symbols ['E', '+', 'E'].

class ArithmeticPrecedenceGrammar < Dhaka::Grammar
  precedences do
    left ['+', '-']
    left ['*', '/']
    nonassoc ['^']
  end

  for_symbol(Dhaka::START_SYMBOL_NAME) do
    expression ['E']
  end

  for_symbol('E') do
    addition ['E', '+', 'E']
    subtraction ['E', '-', 'E']
    multiplication ['E', '*', 'E']
    division ['E', '/', 'E']
    power ['E', '^', 'E']
    literal ['n']
    parenthetized_expression ['(', 'E', ')']
    negated_expression ['-', 'E'], :prec => '*'
  end
end

In the above grammar, the symbols + and - are declared as being left-associative, meaning that 1 + 2 + 3 is parsed as (1 + 2) + 3 as opposed to 1 + (2 + 3) (right-associativity). The symbol ^ is declared nonassoc which means that expressions such as 2 ^ 3 ^ 4 are not allowed (non-associative). + and - are listed before ^ which means that they bind lower, and an expression such as 2 + 3 ^ 5 will be always be parsed as 2 + (3 ^ 5) and not (2 + 3) ^ 5.

Direct Known Subclasses

LexerSupport::RegexGrammar

Class Method Summary collapse

Class Method Details

.closure(kernel) ⇒ Object

:nodoc:



133
134
135
136
137
138
139
140
141
142
143
144
 
# File 'lib/dhaka/grammar/grammar.rb', line 133

def closure(kernel) #:nodoc:
  channels = Hash.new {|hash, start_item| hash[start_item] = Set.new}
  result = compute_closure(kernel) do |hash, item|    
    if item.next_symbol and item.next_symbol.non_terminal
      productions_by_symbol[item.next_symbol].each do |production|
        new_channel = spontaneous_channel(item, hash[Item.new(production, 0)])
        channels[item] << new_channel
      end
    end
  end
  [result, channels]
end

.first(given_symbol) ⇒ Object

:nodoc:



150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
 
# File 'lib/dhaka/grammar/grammar.rb', line 150

def first(given_symbol) #:nodoc:
  cached_result = __first_cache[given_symbol] 
  return cached_result if cached_result
  result = compute_closure([given_symbol]) do |hash, symbol|
        productions_by_symbol[symbol].each do |production| 
          symbol_index = 0
          while next_symbol = production.expansion[symbol_index]
            hash[next_symbol]
            break unless next_symbol.nullable
            symbol_index += 1
          end
        end if symbol.non_terminal
    end.values.select {|symbol| symbol.terminal}.to_set
  __first_cache[given_symbol] = result
  result
end

.for_symbol(symbol, &blk) ⇒ Object

Used for defining the Production-s for the symbol with name symbol. The block blk is evaluated in the context of a ProductionBuilder.



103
104
105
106
107
 
# File 'lib/dhaka/grammar/grammar.rb', line 103

def for_symbol symbol, &blk
  symbol              = symbols[symbol]
  symbol.non_terminal = true
  ProductionBuilder.new(self, symbol).instance_eval(&blk)
end

.non_terminal_symbols ⇒ Object

Returns the set of non-terminal symbols in the grammar.



178
179
180
 
# File 'lib/dhaka/grammar/grammar.rb', line 178

def non_terminal_symbols
  symbols.values.select {|symbol| symbol.non_terminal}
end

.passive_channel(start_item, end_item) ⇒ Object

:nodoc:



146
147
148
 
# File 'lib/dhaka/grammar/grammar.rb', line 146

def passive_channel(start_item, end_item) #:nodoc:
  PassiveChannel.new(self, start_item, end_item)
end

.precedences(&blk) ⇒ Object

Used for defining the precedences and associativities of symbols. The block blk is evaluated in the context of a PrecedenceBuilder.



111
112
113
 
# File 'lib/dhaka/grammar/grammar.rb', line 111

def precedences &blk
  PrecedenceBuilder.new(self).instance_eval(&blk)
end

.production_named(name) ⇒ Object

Returns the Production identified by name.



168
169
170
 
# File 'lib/dhaka/grammar/grammar.rb', line 168

def production_named(name)
  productions_by_name[name]
end

.productions ⇒ Object

Returns a list of all the Production-s in this grammar.



125
126
127
 
# File 'lib/dhaka/grammar/grammar.rb', line 125

def productions 
  productions_by_name.values
end

.productions_for_symbol(symbol) ⇒ Object

:nodoc:



129
130
131
 
# File 'lib/dhaka/grammar/grammar.rb', line 129

def productions_for_symbol(symbol) #:nodoc:
  productions_by_symbol[symbol]
end

.symbol_for_name(name) ⇒ Object

Returns the grammar symbol identified by name



116
117
118
119
120
121
122
 
# File 'lib/dhaka/grammar/grammar.rb', line 116

def symbol_for_name(name)
  if symbols.has_key? name
    symbols[name]
  else
    raise "No symbol with name #{name} found"
  end
end

.terminal_symbols ⇒ Object

Returns the set of terminal symbols in the grammar.



173
174
175
 
# File 'lib/dhaka/grammar/grammar.rb', line 173

def terminal_symbols
  symbols.values.select {|symbol| symbol.terminal}
end

.to_bnf ⇒ Object

Export the grammar to a BNF-like format



183
184
185
186
187
188
189
190
191
192
193
194
195
 
# File 'lib/dhaka/grammar/grammar.rb', line 183

def to_bnf
  result = []
  last_symbol = nil
  productions.sort.each do |production|
    if production.symbol != last_symbol
      result << ""
      result << "#{production.symbol.name.inspect} :"
      last_symbol = production.symbol
    end
    result << "  | #{production.expansion.collect{|symbol| symbol.name.inspect}.join(' ')}"
  end
  result.join("\n")
end