| blob | 605800c49ef7fa655d7f6b8a85007deecf98a700 |
1 require 'voodoo/validator'
3 module Voodoo
4 # Voodoo parser.
5 # The parser reads Voodoo[http://inglorion.net/documents/designs/voodoo/]
6 # source code and turns it into Ruby[http://www.ruby-lang.org/] objects.
7 #
8 # The public interface to Parser consists of the methods #new and
9 # #parse_top_level
10 #
11 # Example usage:
12 #
13 # require 'voodoo/parser'
14 #
15 # File.open('example.voo') do |infile|
16 # parser = Voodoo::Parser.new infile
17 #
18 # while (element = parser.parse_top_level)
19 # puts element.inspect
20 # end
21 # end
22 class Parser
23 NUMBER_STARTER = /\d|-/
24 STRING_STARTER = '"'
25 SYMBOL_STARTER = /[[:alpha:]]|_|\\/
27 # Creates a parser using the specified object as input.
28 # The input object must support a method +getc+, which must
29 # return the next character of the input, or +nil+ to indicate
30 # the end of the input has been reached.
31 def initialize input
32 @input = input
33 @input_name = input.respond_to?(:path) ? input.path : nil
34 @start_line = @line = 1
35 @start_column = @column = 0
36 @lookahead = nil
37 @text = ''
38 end
40 # Base class for errors reported from the parser.
41 # This provides methods to get the name of the input being processed,
42 # as well as the start_line, start_column, and text of the code
43 # that triggered the error.
44 class Error < StandardError
45 def initialize message, input_name, start_line, start_column, text
46 super message
47 @input_name = input_name
48 @start_line = start_line
49 @start_column = start_column
50 @text = text
51 end
53 attr_reader :input_name, :start_line, :start_column, :text
54 end
56 # Class for parse errors.
57 # A ParseError indicates an error in the code being parsed.
58 # For other errors that the parser may raise, see ParserInternalError.
59 class ParseError < Parser::Error
60 def initialize message, input_name, start_line, start_column, text
61 super message, input_name, start_line, start_column, text
62 end
63 end
65 # Class for parser internal errors.
66 # A ParserInternalError indicates an error in the parser that is not
67 # flagged as an error in the code being parsed. Possible causes
68 # include I/O errors while reading code, as well as bugs in the
69 # parser.
70 #
71 # The +cause+ attribute indicates the initial cause for the error.
72 # The other attributes of ParserInternalError are inherited from
73 # Parser::Error and indicate the input that was being
74 # processed when the error occurred.
75 class ParserInternalError < Parser::Error
76 def initialize cause, input_name, start_line, start_column, text
77 super cause.message, input_name, start_line, start_column, text
78 @cause = cause
79 end
81 attr_reader :cause
82 end
84 # Class wrapping multiple Parser::Errors.
85 class MultipleErrors < Parser::Error
86 def initialize errors
87 @errors = errors
88 super(nil, errors[0].input_name, errors[0].start_line,
89 errors[0].start_column, nil)
90 end
92 attr_reader :errors
94 def message
95 if @message == nil
96 msg = "Multiple errors:\n\n"
97 @errors.each do |error|
98 msg << error.input_name << ":" if error.input_name
99 msg << "#{error.start_line}: " << error.message
100 if error.text != nil
101 msg << "\n\n #{error.text.gsub("\n", "\n ")}"
102 end
103 msg << "\n"
104 end
105 @message = msg
106 end
107 @message
108 end
110 def text
111 if @text == nil
112 texts = @errors.map {|error| error.text}
113 @text = texts.join "\n"
114 end
115 @text
116 end
117 end
119 # Parses a top-level element.
120 # Returns an array containing the parts of the element.
121 #
122 # Some examples (Voodoo code, Ruby return values in comments):
123 #
124 # section functions
125 # # [:section, :functions]
126 #
127 # call foo x 12
128 # # [:call, :foo, :x, 12]
129 #
130 # set x add x 42
131 # # [:set, :x, :add, :x, 42]
132 #
133 # set-byte @x 1 10
134 # # [:"set-byte", [:"@", :x], 1, 10]
135 #
136 # ifeq x y
137 # set z equal
138 # else
139 # set z not-equal
140 # end if
141 # # [:ifeq, [:x, :y], [[:set, :z, :equal]], [[:set, :z, :"not-equal"]]]
142 #
143 # foo:
144 # # [:label, :foo]
145 #
146 # function x y
147 # let z add x y
148 # return z
149 # end function
150 # # [:function, [:x, :y], [:let, :z, :add, :x, :y], [:return, :z]]
151 #
152 def parse_top_level
153 wrap_exceptions do
154 @text = ''
155 # Skip whitespace, comments, and empty lines
156 skip_to_next_top_level
158 validate_top_level do
159 parse_top_level_nonvalidating
160 end
161 end
162 end
164 # Parses statements up to "end X". _kind_ should indicate the type
165 # of body being parsed: :block, :conditional, :function, or :group.
166 # Returns an array of statements.
167 def parse_body kind
168 wrap_exceptions do
169 body = []
170 errors = []
171 case kind
172 when :function
173 kind_text = 'function definition'
174 else
175 kind_text = kind.to_s
176 end
177 # Groups are allowed to contain top-level statements.
178 # All other kinds aren't.
179 top_level = kind == :group
180 done = false
181 until done
182 begin
183 with_position do
184 statement = parse_top_level_nonvalidating
185 if statement == nil
186 done = true
187 parse_error "End of input while inside #{kind_text}", nil
189 elsif statement[0] == :end
190 # Done parsing body
191 done = true
192 elsif kind == :conditional && statement[0] == :else
193 # Done parsing body, but there is another one coming up
194 body << statement
195 done = true
196 else
197 # Should be a normal statement. Validate it, then add it to body
198 begin
199 if top_level
200 Validator.validate_top_level statement
201 else
202 Validator.validate_statement statement
203 end
204 body << statement
205 rescue Validator::ValidationError => e
206 magic_word = statement[0]
207 if !top_level &&
208 Validator::TOP_LEVELS.member?(magic_word) &&
209 !Validator::STATEMENTS.member?(magic_word)
210 parse_error "#{magic_word} is only allowed at top-level"
211 else
212 parse_error e.message
213 end
214 end
215 end
216 end
217 rescue => e
218 # Got some kind of error. Still try to parse the rest of the body.
219 errors << e
220 end
221 end
223 # Raise error if we had just one.
224 # If we had more than one, raise a MultipleErrors instance.
225 if errors.length == 1
226 raise errors[0]
227 elsif errors.length > 1
228 raise MultipleErrors.new errors
229 end
231 body
232 end
233 end
235 # Parses an escape sequence.
236 # This method should be called while the lookahead is the escape
237 # character (backslash). It decodes the escape sequence and returns
238 # the result as a string.
239 def parse_escape
240 wrap_exceptions do
241 result = nil
242 consume
243 case lookahead
244 when :eof
245 parse_error "Unexpected end of input in escape sequence", nil
246 when "\\", "\"", " "
247 result = lookahead
248 consume
249 when "n"
250 # \n is newline
251 consume
252 result = "\n"
253 when "r"
254 # \r is carriage return
255 consume
256 result = "\r"
257 when "x"
258 # \xXX is byte with hex value XX
259 code = @input.read 2
260 @column = @column + 2
261 consume
262 @text << code
263 result = [code].pack('H2')
264 when "\n"
265 # \<newline> is line continuation character
266 consume
267 # Skip indentation of next line
268 while lookahead =~ /\s/
269 consume
270 end
271 result = ''
272 else
273 # Default to just passing on next character
274 result = lookahead
275 consume
276 end
277 result
278 end
279 end
281 # Parses a number.
282 # This method should be called while the lookahead is the first
283 # character of the number.
284 def parse_number
285 wrap_exceptions do
286 text = lookahead
287 consume
288 while lookahead =~ /\d/
289 text << lookahead
290 consume
291 end
292 text.to_i
293 end
294 end
296 # Parses a string.
297 # This method should be called while the lookahead is the opening
298 # double quote.
299 def parse_string
300 wrap_exceptions do
301 consume
302 result = ''
303 while true
304 case lookahead
305 when "\""
306 consume
307 break
308 when "\\"
309 result << parse_escape
310 else
311 result << lookahead
312 consume
313 end
314 end
315 result
316 end
317 end
319 # Parses a symbol.
320 # This method should be called while the lookahead is the first
321 # character of the symbol name.
322 def parse_symbol
323 parse_symbol1 ''
324 end
326 # Continues parsing a symbol.
327 # +name+ the part of the symbol that has already been parsed.
328 def parse_symbol1 name
329 wrap_exceptions do
330 while lookahead != :eof
331 case lookahead
332 when "\\"
333 name << parse_escape
334 when /\w|-/
335 name << lookahead
336 consume
337 when ':'
338 # Colon parsed as last character of the symbol name
339 name << lookahead
340 consume
341 break
342 else
343 break
344 end
345 end
346 name.to_sym
347 end
348 end
350 #
351 # Private methods
352 #
353 private
355 # Consumes the current lookahead character.
356 # The character is appended to @text.
357 def consume
358 old = @lookahead
359 @lookahead = nil
360 if old == "\n"
361 @line = @line.succ
362 @column = 0
363 end
364 @text << old
365 old
366 end
368 # Tests if a symbol is a label
369 def is_label? symbol
370 symbol.to_s[-1] == ?:
371 end
373 # Tests if a symbol is a conditional starter.
374 def is_conditional? symbol
375 [:ifeq, :ifge, :ifgt, :ifle, :iflt, :ifne].member? symbol
376 end
378 # Returns the current lookahead character,
379 # or +:eof+ when the end of the input has been reached.
380 def lookahead
381 if @lookahead == nil
382 @lookahead = @input.getc
383 if @lookahead == nil
384 @lookahead = :eof
385 else
386 @lookahead = @lookahead.chr
387 @column = @column.succ
388 end
389 end
390 @lookahead
391 end
393 # Parses a conditional statement.
394 def parse_conditional1 condition, operands
395 # Parse first clause and condition for next clause
396 consequent, next_condition = split_if_clause parse_body(:conditional)
397 if next_condition == nil
398 # No next clause
399 alternative = []
400 elsif next_condition == :else
401 # Next clause is else without if
402 alternative = parse_body :conditional
403 else
404 # Next clause is else with if
405 alternative = [parse_conditional1(next_condition[0],
406 next_condition[1])]
407 end
408 [condition, operands, consequent, alternative]
409 end
411 # Raises a ParseError at the current input position.
412 def parse_error message, text = @text
413 # Create the error object
414 error = ParseError.new(message, @input_name, @start_line,
415 @start_column, text)
417 # Set a backtrace to the calling method
418 error.set_backtrace caller
420 # If we are not at a new line, skip until the next line
421 while @column > 1 && lookahead != :eof
422 consume
423 end
425 # Raise the error
426 raise error
427 end
429 # Parses a top-level incantation without validating it.
430 def parse_top_level_nonvalidating
431 # Skip whitespace, comments, and empty lines
432 skip_to_next_top_level
434 words = []
435 while true
436 # Parse next token
437 skip_whitespace
438 word = try_parse_token
439 if word == nil
440 # Word is nil; that means we did not get a token
441 case lookahead
442 when :eof
443 # End of input
444 break
445 when "\n"
446 # Newline
447 consume
448 # Exit the loop, but only if the line wasn't empty
449 break unless words.empty?
450 when "#"
451 # Skip comment
452 while lookahead != :eof && lookahead != "\n"
453 consume
454 end
455 else
456 parse_error "Unexpected character (#{lookahead}) in input"
457 end
458 else
459 # Word is not nil - we got a token
460 if words.empty? && word.kind_of?(::Symbol) && word.to_s[-1] == ?:
461 # First word is a label
462 words = [:label, word.to_s[0..-2].to_sym]
463 break
464 end
465 # Add word to statement
466 words << word
467 end
468 words
469 end
471 # We have a line of input. Conditionals and function declarations
472 # must be handled specially, because they consist of more than one
473 # line.
474 if words.empty?
475 # Nothing to parse; return nil
476 nil
477 elsif words[0] == :function
478 # Function declaration. Parse function body
479 body = parse_body :function
480 [:function, words[1..-1]] + body
481 elsif is_conditional?(words[0])
482 parse_conditional1 words[0], words[1..-1]
483 elsif words[0] == :block || words[0] == :group
484 body = parse_body words[0]
485 [words[0]] + body
486 else
487 # Statement or data declaration; simply return it
488 words
489 end
490 end
492 # Skips whitespace, newlines, and comments before a top-level incantation.
493 def skip_to_next_top_level
494 while true
495 case lookahead
496 when /\s/
497 # Skip whitespace
498 consume
499 when "\n"
500 # Newline
501 consume
502 when "#"
503 # Skip comment
504 while lookahead != :eof && lookahead != "\n"
505 consume
506 end
507 else
508 break
509 end
510 end
511 end
513 # Consumes characters until a character other than space or tab is
514 # encountered.
515 def skip_whitespace
516 while lookahead == " " || lookahead == "\t"
517 consume
518 end
519 end
521 # Splits a parsed if-clause into two parts:
522 # 1. The list of statements making up the clause proper
523 # 2. The condition for the next clause:
524 # - If there is no next clause, nil
525 # - If the next clause is introduced by else without a condition, :else
526 # - If the next clause is introduced by else iflt x y, [:iflt [:x, :y]]
527 # - And so on for other if.. instances
528 def split_if_clause clause
529 last = clause[-1]
530 if last.respond_to?(:[]) && last.length > 0 && last[0] == :else
531 clause = clause[0..-2]
532 if last.length > 1
533 # Else if
534 [clause, [last[1], last[2..-1]]]
535 else
536 # Only else
537 [clause, :else]
538 end
539 else
540 # No else
541 [clause, nil]
542 end
543 end
545 # Tries to parse a symbol, number, string, or at-expression. If
546 # such a token starts at the current position, it is parsed and returned.
547 # Else, nil is returned.
548 def try_parse_token
549 case lookahead
550 when :eof
551 nil
552 when NUMBER_STARTER
553 # Digit; parse number
554 parse_number
555 when "\\"
556 # Check if this is the line continuation escape or some other escape.
557 decoded = parse_escape
558 if decoded == ''
559 # Line continuation. Now that we've parsed that, try again.
560 try_parse_token
561 else
562 # Some other escape. That means it's a symbol.
563 parse_symbol1 decoded
564 end
565 when SYMBOL_STARTER
566 # Letter, underscore, or backslash; parse symbol
567 # Note: SYMBOL_STARTER matches digits and backslashes, too, so
568 # keep it after the cases that match those.
569 parse_symbol
570 when STRING_STARTER
571 # Double quote; parse string
572 parse_string
573 when '@'
574 # Parse at-expression.
575 # '@' must be followed by a number or symbol.
576 consume
577 case lookahead
578 when NUMBER_STARTER
579 expr = parse_number
580 when SYMBOL_STARTER
581 expr = parse_symbol
582 else
583 parse_error "Invalid character (#{lookahead}) " +
584 "in at-expression; expecting number or symbol"
585 end
586 [:'@', expr]
587 when '%'
588 consume
589 # Must be followed by a symbol.
590 if lookahead !~ SYMBOL_STARTER
591 parse_error "'%' must be followed by a symbol"
592 end
593 [:'%', parse_symbol]
594 else
595 # No valid starter for a token, return nil
596 nil
597 end
598 end
600 # Evaluates _block_ and checks that the result is a valid top-level
601 # incantation.
602 def validate_top_level &block
603 with_position do
604 result = yield
605 begin
606 if result != nil
607 Validator.validate_top_level result
608 end
609 result
610 rescue Validator::ValidationError => e
611 parse_error e.message
612 end
613 end
614 end
616 # Evaluates block, keeping track of @start_line, @start_column
617 # at the beginning of the block, and @text during the evaluation
618 # of block.
619 def with_position &block
620 # Save old values
621 old_line = @start_line
622 old_column = @start_column
623 old_text = @text
625 # Evaluate block with new values
626 begin
627 @start_line = @line
628 @start_column = @column
629 @text = ''
630 wrap_exceptions do
631 yield
632 end
633 ensure
634 # Restore old values
635 @start_line = old_line
636 @start_column = old_column
637 @text = old_text + @text
638 end
639 end
641 # Ensures that any exceptions that escape from block are instances of
642 # Parser::Error.
643 def wrap_exceptions &block
644 begin
645 yield
646 rescue Parser::Error
647 # Already an instance of Parser::Error; pass it through.
648 raise
649 rescue => e
650 # Some other error; wrap in ParserInternalError.
651 wrapped = ParserInternalError.new(e, @input_name, @line,
652 @column, @text)
653 wrapped.set_backtrace e.backtrace
654 raise wrapped
655 end
656 end
658 end
659 end