]> git.wincent.com - walrat.git/blob - spec/grammar_spec.rb
Update to RSpec 3.1.0
[walrat.git] / spec / grammar_spec.rb
1 # Copyright 2007-2014 Greg Hurrell. All rights reserved.
2 # Licensed under the terms of the BSD 2-clause license.
3
4 require 'spec_helper'
5
6 describe Walrat::Grammar do
7   describe '::rules' do
8     it 'complains if either parameter is nil' do
9       expect do
10         class AxeGrammar < Walrat::Grammar
11           rule nil, 'expression'
12         end
13       end.to raise_error(ArgumentError, /nil symbol/)
14
15       expect do
16         class BoneGrammar < Walrat::Grammar
17           rule :my_rule, nil
18         end
19       end.to raise_error(ArgumentError, /nil parseable/)
20
21       expect do
22         class CatGrammar < Walrat::Grammar
23           rule nil, nil
24         end
25       end.to raise_error(ArgumentError, /nil/)
26     end
27
28     it 'complains if an attempt is made to define a rule a second time' do
29       expect do
30         class DogGrammar < Walrat::Grammar
31           rule :my_rule, 'foo'
32           rule :my_rule, 'bar'
33         end
34       end.to raise_error(ArgumentError, /already defined/)
35     end
36   end
37
38   describe 'defining productions in a grammar' do
39     it '"node" method should complain if new class name is nil' do
40       expect do
41         class NodeComplainingGrammar < Walrat::Grammar
42           node nil
43         end
44       end.to raise_error(ArgumentError, /nil new_class_name/)
45     end
46
47     it 'should be able to define a simple Node subclass using the "node" function' do
48       class NodeGrammar1 < Walrat::Grammar
49         node      :my_node_subclass
50         node      :my_subclass_of_a_subclass, :my_node_subclass
51       end
52
53       NodeGrammar1::MyNodeSubclass.superclass.should == Walrat::Node
54       NodeGrammar1::MySubclassOfASubclass.superclass.should == NodeGrammar1::MyNodeSubclass
55     end
56
57     it 'should complain if an attempt is made to create the same production class twice' do
58       expect do
59         class HowToGetControlOfJavaAwayFromSun < Walrat::Grammar
60           rule        :foo, 'foo'
61           node        :foo
62           production  :foo
63           production  :foo
64         end
65       end.to raise_error(ArgumentError, /production already defined/)
66     end
67
68     it 'should complain if an attempt is made to create a production for a rule that does not exist yet' do
69       expect do
70         class GettingControlOfJavaAwayFromSun < Walrat::Grammar
71           node        :foo
72           production  :foo
73         end
74       end.to raise_error(ArgumentError, /non-existent rule/)
75     end
76   end
77
78   describe 'parsing using a grammar' do
79     it 'should complain if asked to parse a nil string' do
80       class BobGrammar < Walrat::Grammar; end
81       expect do
82         BobGrammar.new.parse(nil)
83       end.to raise_error(ArgumentError, /nil string/)
84     end
85
86     it 'should complain if trying to parse without first defining a start symbol' do
87       class RoyalGrammar < Walrat::Grammar; end
88       expect do
89         RoyalGrammar.new.parse('foo')
90       end.to raise_error(RuntimeError, /starting symbol not defined/)
91     end
92
93     it 'should parse starting with the start symbol' do
94       class AliceGrammar < Walrat::Grammar
95         rule            :expr, /\w+/
96         starting_symbol :expr
97       end
98
99       grammar = AliceGrammar.new
100       grammar.parse('foo').should == 'foo'
101       lambda { grammar.parse('') }.should raise_error(Walrat::ParseError)
102     end
103
104     it 'should complain if reference is made to an undefined symbol' do
105       class RoyGrammar < Walrat::Grammar
106         starting_symbol :expr # :expr is not defined
107       end
108
109       expect { RoyGrammar.new.parse('foo') }.to raise_error(/no rule for key/)
110     end
111
112     it 'should be able to parse using a simple grammar (one rule)' do
113       class SimpleGrammar < Walrat::Grammar
114         starting_symbol :foo
115         rule            :foo, 'foo!'
116       end
117
118       grammar = SimpleGrammar.new
119       grammar.parse('foo!').should == 'foo!'
120       lambda { grammar.parse('---') }.should raise_error(Walrat::ParseError)
121     end
122
123     it 'should be able to parse using a simple grammar (two rules)' do
124       class AlmostAsSimpleGrammar < Walrat::Grammar
125         starting_symbol :foo
126         rule            :foo, 'foo!' | :bar
127         rule            :bar, /bar/
128       end
129
130       grammar = AlmostAsSimpleGrammar.new
131       grammar.parse('foo!').should == 'foo!'
132       grammar.parse('bar').should == 'bar'
133       lambda { grammar.parse('---') }.should raise_error(Walrat::ParseError)
134     end
135
136     it 'should be able to parse using a simple grammar (three rules)' do
137       # a basic version written using intermediary parslets
138       # (really two parslets and one rule)
139       class MacGrammar < Walrat::Grammar
140         starting_symbol :comment
141
142         # parslets
143         comment_marker  = '##'
144         comment_body    = /.+/
145
146         # rules
147         rule            :comment,         comment_marker & comment_body.optional
148       end
149
150       grammar = MacGrammar.new
151       grammar.parse('## hello!').should == ['##', ' hello!']
152       grammar.parse('##').should == '##'
153       lambda { grammar.parse('foobar') }.should raise_error(Walrat::ParseError)
154
155       # the same grammar rewritten without intermediary parslets
156       # (three rules, no standalone parslets)
157       class MacAltGrammar < Walrat::Grammar
158         starting_symbol :comment
159         rule            :comment,         :comment_marker & :comment_body.optional
160         rule            :comment_marker,  '##'
161         rule            :comment_body,    /.+/
162       end
163
164       grammar = MacAltGrammar.new
165       grammar.parse('## hello!').should == ['##', ' hello!']
166       grammar.parse('##').should == '##'
167       lambda { grammar.parse('foobar') }.should raise_error(Walrat::ParseError)
168     end
169
170     it 'should be able to parse using recursive rules (nested parentheses)' do
171       # basic example
172       class NestedGrammar < Walrat::Grammar
173         starting_symbol :bracket_expression
174         rule            :left_bracket,        '('
175         rule            :right_bracket,       ')'
176         rule            :bracket_content,     (/[^()]+/ | :bracket_expression).zero_or_more
177         rule            :bracket_expression,  :left_bracket & :bracket_content.optional & :right_bracket
178       end
179
180       grammar = NestedGrammar.new
181       grammar.parse('()').should == ['(', ')']
182       grammar.parse('(content)').should == ['(', 'content', ')']
183       grammar.parse('(content (and more content))').should == ['(', ['content ', ['(', 'and more content', ')']], ')']
184       lambda { grammar.parse('(') }.should raise_error(Walrat::ParseError)
185
186       # same example but automatically skipping the delimiting braces for clearer output
187       class NestedSkippingGrammar < Walrat::Grammar
188         starting_symbol :bracket_expression
189         rule            :bracket_expression,  '('.skip & (/[^()]+/ | :bracket_expression).zero_or_more  & ')'.skip
190       end
191
192       grammar = NestedSkippingGrammar.new
193       grammar.parse('()').should == []
194       grammar.parse('(content)').should == 'content'
195       grammar.parse('(content (and more content))').should == ['content ', 'and more content']
196       grammar.parse('(content (and more content)(and more))').should == ['content ', 'and more content', 'and more']
197       grammar.parse('(content (and more content)(and more)(more still))').should == ['content ', 'and more content', 'and more', 'more still']
198       grammar.parse('(content (and more content)(and more(more still)))').should == ['content ', 'and more content', ['and more', 'more still']]
199       lambda { grammar.parse('(') }.should raise_error(Walrat::ParseError)
200
201       # note that this confusing (possible even misleading) nesting goes away if you use a proper AST
202       class NestedBracketsWithAST < Walrat::Grammar
203         starting_symbol :bracket_expression
204         rule            :text_expression,     /[^()]+/
205         rule            :bracket_expression,
206                         '('.skip &
207                         (:text_expression | :bracket_expression).zero_or_more  &
208                         ')'.skip
209         node            :bracket_expression
210         production      :bracket_expression, :children
211       end
212
213       # simple tests
214       grammar = NestedBracketsWithAST.new
215       grammar.parse('()').children.should == []
216       grammar.parse('(content)').children.to_s.should == 'content'
217
218       # nested test: two expressions at the first level, one of them nested
219       results = grammar.parse('(content (and more content))')
220       results.children[0].should == 'content '
221       results.children[1].children.to_s.should == 'and more content'
222
223       # nested test: three expressions at first level, two of them nested
224       results = grammar.parse('(content (and more content)(and more))')#.should == ['content ', 'and more content', 'and more']
225       results.children[0].should == 'content '
226       results.children[1].children.should == 'and more content'
227       results.children[2].children.should == 'and more'
228
229       # nested test: four expressions at the first level, three of them nested
230       results = grammar.parse('(content (and more content)(and more)(more still))')
231       results.children[0].should == 'content '
232       results.children[1].children.should == 'and more content'
233       results.children[2].children.should == 'and more'
234       results.children[3].children.should == 'more still'
235
236       # nested test: three expressions at the first level, one nested and another not only nested but containing another level of nesting
237       results = grammar.parse('(content (and more content)(and more(more still)))')
238       results.children[0].should == 'content '
239       results.children[1].children.should == 'and more content'
240       results.children[2].children[0].should == 'and more'
241       results.children[2].children[1].children.should == 'more still'
242
243       # bad input case
244       lambda { grammar.parse('(') }.should raise_error(Walrat::ParseError)
245     end
246
247     it 'should be able to parse using recursive rules (nested comments)' do
248       class NestedCommentsGrammar < Walrat::Grammar
249         starting_symbol :comment
250         rule            :comment_start,       '/*'
251         rule            :comment_end,         '*/'
252         rule            :comment_content,     (:comment | /\/+/ | ('*' & '/'.not!) | /[^*\/]+/).zero_or_more
253         rule            :comment,             '/*' & :comment_content.optional & '*/'
254       end
255
256       grammar = NestedCommentsGrammar.new
257       grammar.parse('/**/').should == ['/*', '*/']
258       grammar.parse('/*comment*/').should == ['/*', 'comment', '*/']
259       grammar.parse('/* comment /* nested */*/').should == ['/*', [' comment ', ['/*', ' nested ', '*/']], '*/']
260       lambda { grammar.parse('/*') }.should raise_error(Walrat::ParseError)
261     end
262
263     it 'should be able to write a grammar that produces an AST for a simple language that supports addition and assignment' do
264       class SimpleASTLanguage < Walrat::Grammar
265         starting_symbol :expression
266
267         # terminal tokens
268         rule            :identifier,      /[a-zA-Z_][a-zA-Z0-9_]*/
269         node            :identifier
270         production      :identifier
271         rule            :integer_literal, /[0-9]+/
272         node            :integer_literal
273         production      :integer_literal
274
275         # expressions
276         rule            :expression,      :assignment_expression | :addition_expression | :identifier | :integer_literal
277         node            :expression
278         rule            :assignment_expression, :identifier & '='.skip & :expression
279         node            :assignment_expression, :expression
280         production      :assignment_expression, :target, :value
281         rule            :addition_expression,   (:identifier | :integer_literal) & '+'.skip & :expression
282         node            :addition_expression, :expression
283         production      :addition_expression, :summee, :summor
284       end
285
286       grammar = SimpleASTLanguage.new
287       results = grammar.parse('hello')
288       results.should be_kind_of(SimpleASTLanguage::Identifier)
289       results.lexeme.should == 'hello'
290
291       results = grammar.parse('1234')
292       results.should be_kind_of(SimpleASTLanguage::IntegerLiteral)
293       results.lexeme.should == '1234'
294
295       results = grammar.parse('foo=bar')
296       results.should be_kind_of(SimpleASTLanguage::Expression)
297       results.should be_kind_of(SimpleASTLanguage::AssignmentExpression)
298       results.target.should be_kind_of(SimpleASTLanguage::Identifier)
299       results.target.lexeme.should == 'foo'
300       results.value.should be_kind_of(SimpleASTLanguage::Identifier)
301       results.value.lexeme.should == 'bar'
302
303       results = grammar.parse('baz+123')
304       results.should be_kind_of(SimpleASTLanguage::Expression)
305       results.should be_kind_of(SimpleASTLanguage::AdditionExpression)
306       results.summee.should be_kind_of(SimpleASTLanguage::Identifier)
307       results.summee.lexeme.should == 'baz'
308       results.summor.should be_kind_of(SimpleASTLanguage::IntegerLiteral)
309       results.summor.lexeme.should == '123'
310
311       results = grammar.parse('foo=abc+123')
312       results.should be_kind_of(SimpleASTLanguage::Expression)
313       results.should be_kind_of(SimpleASTLanguage::AssignmentExpression)
314       results.target.should be_kind_of(SimpleASTLanguage::Identifier)
315       results.target.lexeme.should == 'foo'
316       results.value.should be_kind_of(SimpleASTLanguage::AdditionExpression)
317       results.value.summee.should be_kind_of(SimpleASTLanguage::Identifier)
318       results.value.summee.lexeme.should == 'abc'
319       results.value.summor.should be_kind_of(SimpleASTLanguage::IntegerLiteral)
320       results.value.summor.lexeme.should == '123'
321
322       results = grammar.parse('a+b+2')
323       results.should be_kind_of(SimpleASTLanguage::Expression)
324       results.should be_kind_of(SimpleASTLanguage::AdditionExpression)
325       results.summee.should be_kind_of(SimpleASTLanguage::Identifier)
326       results.summee.lexeme.should == 'a'
327       results.summor.should be_kind_of(SimpleASTLanguage::AdditionExpression)
328       results.summor.summee.should be_kind_of(SimpleASTLanguage::Identifier)
329       results.summor.summee.lexeme.should == 'b'
330       results.summor.summor.should be_kind_of(SimpleASTLanguage::IntegerLiteral)
331       results.summor.summor.lexeme.should == '2'
332     end
333
334     it 'should be able to write a grammar that complains if all the input is not consumed' do
335       class ComplainingGrammar < Walrat::Grammar
336         starting_symbol :translation_unit
337         rule            :translation_unit,  :word_list & :end_of_string.and? | :end_of_string
338         rule            :end_of_string,     /\z/
339         rule            :whitespace,        /\s+/
340         rule            :word,              /[a-z]+/
341         rule            :word_list,         :word >> (:whitespace.skip & :word).zero_or_more
342       end
343
344       grammar = ComplainingGrammar.new
345       grammar.parse('').should == ''
346       grammar.parse('foo').should == 'foo'
347       grammar.parse('foo bar').should == ['foo', 'bar']
348       lambda { grammar.parse('...') }.should raise_error(Walrat::ParseError)
349       lambda { grammar.parse('foo...') }.should raise_error(Walrat::ParseError)
350       lambda { grammar.parse('foo bar...') }.should raise_error(Walrat::ParseError)
351     end
352
353     it 'should be able to define a default parslet for intertoken skipping' do
354       # simple example
355       class SkippingGrammar < Walrat::Grammar
356         starting_symbol :translation_unit
357         skipping        :whitespace_and_newlines
358         rule            :whitespace_and_newlines, /[\s\n\r]+/
359         rule            :translation_unit,        :word_list & :end_of_string.and? | :end_of_string
360         rule            :end_of_string,           /\z/
361         rule            :word_list,               :word.zero_or_more
362         rule            :word,                    /[a-z0-9_]+/
363       end
364
365       # not sure if I can justify the difference in behaviour here compared with the previous grammar
366       # if I catch these throws at the grammar level I can return nil
367       # but note that the previous grammar returns an empty array, which to_s is just ""
368       grammar = SkippingGrammar.new
369       lambda { grammar.parse('') }.should throw_symbol(:AndPredicateSuccess)
370
371       grammar.parse('foo').should == 'foo'
372       grammar.parse('foo bar').should == ['foo', 'bar']       # intervening whitespace
373       grammar.parse('foo bar     ').should == ['foo', 'bar']  # trailing whitespace
374       grammar.parse('     foo bar').should == ['foo', 'bar']  # leading whitespace
375
376       # additional example, this time involving the ">>" pseudo-operator
377       class SkippingAndMergingGrammar < Walrat::Grammar
378         starting_symbol :translation_unit
379         skipping        :whitespace_and_newlines
380         rule            :whitespace_and_newlines, /[\s\n\r]+/
381         rule            :translation_unit,        :word_list & :end_of_string.and? | :end_of_string
382         rule            :end_of_string,           /\z/
383         rule            :word_list,               :word >> (','.skip & :word).zero_or_more
384         rule            :word,                    /[a-z0-9_]+/
385       end
386
387       # one word
388       grammar = SkippingAndMergingGrammar.new
389       grammar.parse('foo').should == 'foo'
390
391       # two words
392       grammar.parse('foo,bar').should == ['foo', 'bar']         # no whitespace
393       grammar.parse('foo, bar').should == ['foo', 'bar']        # whitespace after
394       grammar.parse('foo ,bar').should == ['foo', 'bar']        # whitespace before
395       grammar.parse('foo , bar').should == ['foo', 'bar']       # whitespace before and after
396       grammar.parse('foo , bar     ').should == ['foo', 'bar']  # trailing and embedded whitespace
397       grammar.parse('     foo , bar').should == ['foo', 'bar']  # leading and embedded whitespace
398
399       # three or four words
400       grammar.parse('foo , bar, baz').should == ['foo', 'bar', 'baz']
401       grammar.parse(' foo , bar, baz ,bin').should == ['foo', 'bar', 'baz', 'bin']
402     end
403
404     it 'should complain if trying to set default skipping parslet more than once' do
405       expect {
406         class SetSkipperTwice < Walrat::Grammar
407           skipping :first   # fine
408           skipping :again   # should raise here
409         end
410       }.to raise_error(/default skipping parslet already set/)
411     end
412
413     it 'should complain if passed nil' do
414       expect {
415         class PassNilToSkipping < Walrat::Grammar
416           skipping nil
417         end
418       }.to raise_error(ArgumentError, /nil rule_or_parslet/)
419     end
420
421     it 'should be able to override default skipping parslet on a per-rule basis' do
422       # the example grammar parses word lists and number lists
423       class OverrideDefaultSkippingParslet < Walrat::Grammar
424         starting_symbol :translation_unit
425         skipping        :whitespace_and_newlines
426         rule            :whitespace_and_newlines, /\s+/       # any whitespace including newlines
427         rule            :whitespace,              /[ \t\v]+/  # literally only spaces, tabs, not newlines etc
428         rule            :translation_unit,        :component.one_or_more & :end_of_string.and? | :end_of_string
429         rule            :end_of_string,           /\z/
430         rule            :component,               :word_list | :number_list
431         rule            :word_list,               :word.one_or_more
432         rule            :word,                    /[a-z]+/
433         rule            :number,                  /[0-9]+/
434
435         # the interesting bit: we override the skipping rule for number lists
436         rule            :number_list,             :number.one_or_more
437         skipping        :number_list,             :whitespace # only whitespace, no newlines
438       end
439
440       # words in word lists can be separated by whitespace or newlines
441       grammar = OverrideDefaultSkippingParslet.new
442       grammar.parse('hello world').should ==  ['hello', 'world']
443       grammar.parse("hello\nworld").should == ['hello', 'world']
444       grammar.parse("hello world\nworld hello").should == ['hello', 'world', 'world', 'hello']
445
446       # numbers in number lists may be separated only by whitespace, not newlines
447       grammar.parse('123 456').should == ['123', '456']
448       grammar.parse("123\n456").should == ['123', '456'] # this succeeds because parser treats them as two separate number lists
449       grammar.parse("123 456\n456 123").should == [['123', '456'], ['456', '123']]
450
451       # intermixing word lists and number lists
452       grammar.parse("bar\n123").should == ['bar', '123']
453       grammar.parse("123\n456\nbar").should == ['123', '456', 'bar']
454
455       # these were buggy at one point: "123\n456" was getting mashed into "123456" due to misguided use of String#delete! to delete first newline
456       grammar.parse("\n123\n456").should == ['123', '456']
457       grammar.parse("bar\n123\n456").should == ['bar', '123', '456']
458       grammar.parse("baz bar\n123\n456").should == [['baz', 'bar'], '123', '456']
459       grammar.parse("hello world\nfoo\n123 456 baz bar\n123\n456").should == [['hello', 'world', 'foo'], ['123', '456'], ['baz', 'bar'], '123', '456']
460     end
461
462     it 'should complain if trying to override the default for the same rule twice' do
463       expect do
464         class OverrideSameRuleTwice < Walrat::Grammar
465           rule      :the_rule, 'foo'
466           skipping  :the_rule, :the_override  # fine
467           skipping  :the_rule, :the_override  # should raise
468         end
469       end.to raise_error(ArgumentError, /skipping override already set for rule/)
470     end
471
472     it "should complain if trying to set an override for a rule that hasn't been defined yet" do
473       expect do
474         class OverrideUndefinedRule < Walrat::Grammar
475           skipping :non_existent_rule, :the_override
476         end
477       end.to raise_error(ArgumentError, /non-existent rule/)
478     end
479
480     it 'use of the "skipping" directive should play nicely with predicates' do
481       # example 1: word + predicate
482       class NicePlayer < Walrat::Grammar
483         starting_symbol :foo
484         skipping        :whitespace
485         rule            :whitespace,                /[ \t\v]+/
486         rule            :foo,                       'hello' & 'world'.and?
487       end
488
489       grammar = NicePlayer.new
490       grammar.parse('hello world').should == 'hello'
491       grammar.parse('hello      world').should == 'hello'
492       grammar.parse('helloworld').should == 'hello'
493       lambda { grammar.parse('hello') }.should raise_error(Walrat::ParseError)
494       lambda { grammar.parse('hello buddy') }.should raise_error(Walrat::ParseError)
495       lambda { grammar.parse("hello\nbuddy") }.should raise_error(Walrat::ParseError)
496
497       # example 2: word + predicate + other word
498       class NicePlayer2 < Walrat::Grammar
499         starting_symbol :foo
500         skipping        :whitespace
501         rule            :whitespace,                /[ \t\v]+/
502         rule            :foo,                       /hel../ & 'world'.and? & /\w+/
503       end
504
505       grammar = NicePlayer2.new
506       grammar.parse('hello world').should == ['hello', 'world']
507       grammar.parse('hello      world').should == ['hello', 'world']
508       grammar.parse('helloworld').should == ['hello', 'world']
509       lambda { grammar.parse('hello') }.should raise_error(Walrat::ParseError)
510       lambda { grammar.parse('hello buddy') }.should raise_error(Walrat::ParseError)
511       lambda { grammar.parse("hello\nbuddy") }.should raise_error(Walrat::ParseError)
512     end
513   end
514 end