Class: Dhaka::Grammar
- Inherits:
-
Object
- Object
- Dhaka::Grammar
- Defined in:
- lib/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
Class Method Summary collapse
-
.closure(kernel) ⇒ Object
:nodoc:.
-
.first(given_symbol) ⇒ Object
:nodoc:.
-
.for_symbol(symbol, &blk) ⇒ Object
Used for defining the Production-s for the symbol with name
symbol
. -
.non_terminal_symbols ⇒ Object
Returns the set of non-terminal symbols in the grammar.
-
.passive_channel(start_item, end_item) ⇒ Object
:nodoc:.
-
.precedences(&blk) ⇒ Object
Used for defining the precedences and associativities of symbols.
-
.production_named(name) ⇒ Object
Returns the Production identified by
name
. -
.productions ⇒ Object
Returns a list of all the Production-s in this grammar.
-
.productions_for_symbol(symbol) ⇒ Object
:nodoc:.
-
.symbol_for_name(name) ⇒ Object
Returns the grammar symbol identified by
name
. -
.terminal_symbols ⇒ Object
Returns the set of terminal symbols in the grammar.
-
.to_bnf ⇒ Object
Export the grammar to a BNF-like format.
Class Method Details
.closure(kernel) ⇒ Object
:nodoc:
133 134 135 136 137 138 139 140 141 142 143 144 145 |
# File 'lib/grammar/grammar.rb', line 133 def closure(kernel) #:nodoc: 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
:nodoc:
151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 |
# File 'lib/grammar/grammar.rb', line 151 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/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.
179 180 181 |
# File 'lib/grammar/grammar.rb', line 179 def non_terminal_symbols symbols.values.select {|symbol| symbol.non_terminal} end |
.passive_channel(start_item, end_item) ⇒ Object
:nodoc:
147 148 149 |
# File 'lib/grammar/grammar.rb', line 147 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/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
.
169 170 171 |
# File 'lib/grammar/grammar.rb', line 169 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/grammar/grammar.rb', line 125 def productions productions_by_name.values end |
.productions_for_symbol(symbol) ⇒ Object
:nodoc:
129 130 131 |
# File 'lib/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/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.
174 175 176 |
# File 'lib/grammar/grammar.rb', line 174 def terminal_symbols symbols.values.select {|symbol| symbol.terminal} end |
.to_bnf ⇒ Object
Export the grammar to a BNF-like format
184 185 186 187 188 189 190 191 192 193 194 195 196 |
# File 'lib/grammar/grammar.rb', line 184 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 |