Class: Dhaka::Grammar

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

Overview

This class is subclassed when specifying a grammar. Note that subclasses of this class may not be further subclassed.

The following is a grammar specification for simple arithmetic. Familiarity with Yacc helps, but the short version is that precedences for symbols are specified 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

Class Method Summary collapse

Class Method Details

.closure(kernel) ⇒ Object 



127
128
129
130
131
132
133
134
135
136
137
138
139
 
# File 'lib/grammar/grammar.rb', line 127

def closure(kernel)
  channels = 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|
        channels << spontaneous_channel(item, hash[Item.new(production, 0)])
      end
    end
  end

  [channels, result]
end

.first(given_symbol) ⇒ Object 



145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
 
# File 'lib/grammar/grammar.rb', line 145

def first(given_symbol)
  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 productions for the symbol with name symbol. The block blk is evaluated in the context of a ProductionBuilder.



98
99
100
101
102
 
# File 'lib/grammar/grammar.rb', line 98

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

.non_terminal_symbols ⇒ Object 



170
171
172
 
# File 'lib/grammar/grammar.rb', line 170

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

.passive_channel(start_item, end_item) ⇒ Object 



141
142
143
 
# File 'lib/grammar/grammar.rb', line 141

def passive_channel(start_item, end_item)
  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.



106
107
108
 
# File 'lib/grammar/grammar.rb', line 106

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

.production_named(name) ⇒ Object 



162
163
164
 
# File 'lib/grammar/grammar.rb', line 162

def production_named(name)
  productions_by_name[name]
end

.productions ⇒ Object 



119
120
121
 
# File 'lib/grammar/grammar.rb', line 119

def productions
  productions_by_name.values
end

.productions_for_symbol(symbol) ⇒ Object 



123
124
125
 
# File 'lib/grammar/grammar.rb', line 123

def productions_for_symbol(symbol)
  productions_by_symbol[symbol]
end

.symbol_for_name(name) ⇒ Object

Returns the grammar symbol identified by name



111
112
113
114
115
116
117
 
# File 'lib/grammar/grammar.rb', line 111

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 



166
167
168
 
# File 'lib/grammar/grammar.rb', line 166

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