/
get-started.html
338 lines (312 loc) · 14.9 KB
/
get-started.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
<!DOCTYPE html>
<html>
<head>
<meta content="text/html;charset=UTF-8" http-equiv="Content-type" />
<title>parslet -Get Started</title>
<meta content="Kaspar Schiess (http://absurd.li)" name="author" />
<link href="images/favicon3.ico" rel="shortcut icon" /><link href="/parslet/stylesheets/site.css" media="screen" rel="stylesheet" type="text/css" /><link href="/parslet/stylesheets/sh_whitengrey.css" media="screen" rel="stylesheet" type="text/css" /><script src="/parslet/javascripts/sh_main.min.js" type="text/javascript"></script><script src="/parslet/javascripts/sh_ruby.min.js" type="text/javascript"></script></head>
<body class="code" onload="sh_highlightDocument();">
<div id="everything">
<div class="main_menu"><img alt="Parslet Logo" src="/parslet/images/parsley_logo.png" /><ul>
<li><a href="index.html">about</a></li>
<li><a href="get-started.html">get started</a></li>
<li><a href="install.html">install</a></li>
<li><a href="documentation.html">documentation</a></li>
<li><a href="contribute.html">contribute</a></li>
</ul>
</div>
<div class="content">
<h1>Get Started</h1><p>Let’s develop a small language that allows for simple computation together.
Here’s a valid input file for that language:</p>
<pre class="sh_ruby"><code>
puts(1 + 2)
puts(4 + 2)
</code></pre>
<p>To install the parslet library, please do a</p>
<pre><code>
gem install parslet
</code></pre>
<p>Now let’s write the first part of our parser. For now, we’ll just recognize
simple numbers like ‘1’ or ‘42’.</p>
<pre class="sh_ruby"><code title="mini_parser">
require 'parslet'
class Mini < Parslet::Parser
rule(:integer) { match('[0-9]').repeat(1) }
root(:integer)
end
Mini.new.parse("132432") # => "132432"@0
</code></pre>
<p>Running this example will print “132432@0”. Congratulations! You just have
written your first parser. Running it on the input ‘<code>puts(1)</code>’ will
not work yet. Let’s see what happens in case of a failure:</p>
<pre class="sh_ruby"><code>
Mini.new.parse("puts(1)") # raises Parslet::ParseFailed
</code></pre>
<p>Here’s the error message provided by that exception: “Expected at least 1 of
[0-9] at line 1 char 1.” parslet tries to find a number there, but can’t find
one.</p>
<p>There are just two lines to the definition of this parser, let’s go through
them:</p>
<pre class="sh_ruby"><code>
rule(:integer) { match('[0-9]').repeat(1) }
</code></pre>
<p><code>rule</code> lets you create a new parser rule. Inside the block of that
<code>:integer</code> rule, you find <code>match('[0-9]').repeat(1)</code>.
This says: “match a character that is in the range <code>0-9</code>, then
match any number of those, but at least match one.”</p>
<pre class="sh_ruby"><code>
root(:integer)
</code></pre>
<p>That second line just says: Start parsing at the rule called
<code>:integer</code>.</p>
<h2>Addition</h2>
<p>Let’s go for simple addition. We’ll have to allow for spaces in our input,
since those help make code readable.</p>
<pre class="sh_ruby"><code>
rule(:space) { match('\s').repeat(1) }
rule(:space?) { space.maybe }
</code></pre>
<p>Two things are new here: (and both in the second line)</p>
<ul>
<li>you can use (‘call’) other rules in your rules</li>
<li><code>.maybe</code>, the same as <code>.repeat(0,1)</code><sup class="footnote" id="fnr1"><a href="#fn1">1</a></sup>, indicating
that the thing before it is maybe present once in the input.</li>
</ul>
<p>Essentially, you can think about parslet rules as instructing Ruby to “parse
this” and “parse that”. Calling other rules can be looked at in the same way;
you tell Ruby to go off, parse that subrule and then come back with the
results. This helps when thinking about rule recursion. For example, a
self-recursive rule like this one will of course create an endless loop:</p>
<pre class="sh_ruby"><code>
rule(:infinity) {
infinity >> str(';')
}
</code></pre>
<p>Even though infinity seems to be delimited by ‘;’, in reality, infinity is
very long, especially towards the end. There is no way of knowing for the
parser when to stop processing <code>infinity</code> and start reading
semicolons. Ergo, we need to make sure we talk about concrete items that
consume input first, and then do recursion. This way we ensure that our
grammar terminates, since in a way, it is like a normal program.</p>
<p>Here’s the full parser:</p>
<pre class="sh_ruby"><code title="full_parser">
class Mini < Parslet::Parser
rule(:integer) { match('[0-9]').repeat(1) >> space? }
rule(:space) { match('\s').repeat(1) }
rule(:space?) { space.maybe }
rule(:operator) { match('[+]') >> space? }
rule(:sum) { integer >> operator >> expression }
rule(:expression) { sum | integer }
root :expression
end
def parse(str)
mini = Mini.new
mini.parse(str)
rescue Parslet::ParseFailed => failure
puts failure.cause.ascii_tree
end
parse "1 + 2 + 3" # => "1 + 2 + 3"@0
parse "a + 2" # fails, see below
</code></pre>
<p>As you can see, the parser got decorated with the <code>space?</code> idiom.
Every atom of our language consumes the space right after it. This is a useful
convention that makes top level rules (the important ones) look cleaner.</p>
<p>Note also the addition of <code>:operator</code>, <code>:sum</code> and
<code>:expression</code>. The runner code has been extended a bit, so as to
throw nice explanations of what went wrong when a parse failure is
encountered. Running the code on ‘<code>a + 2</code>’ for example outputs:</p>
<pre class="output">
Expected one of [SUM, INTEGER] at line 1 char 1.
|- Failed to match sequence (INTEGER OPERATOR EXPRESSION) at line 1 char 1.
| `- Failed to match sequence ([0-9]{1, } SPACE?) at line 1 char 1.
| `- Expected at least 1 of [0-9] at line 1 char 1.
| `- Failed to match [0-9] at line 1 char 1.
`- Failed to match sequence ([0-9]{1, } SPACE?) at line 1 char 1.
`- Expected at least 1 of [0-9] at line 1 char 1.
`- Failed to match [0-9] at line 1 char 1.
</pre>
<p>This is what parslet calls an <code>#error_tree</code>. Not only the output of
your parser, but also its grammar is constructed like a tree. When things go
wrong, every branch of the tree has its own reasons for not accepting a given
input. The <code>#cause</code> method returns those reasons.</p>
<p>Our grammar has essentially two branches, <code>SUM</code> and
<code>INTEGER</code>. Can you see why all rules expect a number as the first
character?</p>
<h2>Tree output (and what to do about it)</h2>
<p>But if we leave the negative examples for a second; what happens if the parse
succeeds? It turns out, not much:</p>
<pre class="sh_ruby"><code>
parse "1 + 2 + 3" # => "1 + 2 + 3"@0
</code></pre>
<p>The only notable difference between input and output is that the output has an
extra ‘@0’ appended to it. This is related to line number tracking and will be
explained later on (or you can skip ahead and look up
<code>Parslet::Slice</code>).</p>
<p>The code we now have parses the input successfully, but doesn’t do much else.
Parslet hasn’t got its own opinion on what to do with your input. By default,
it will just play it back to you. But parslet provides also a method of
structuring its output:</p>
<pre class="sh_ruby"><code title="output_samples">
# Without structure: just strings.
str('ooo').parse('ooo') # => "ooo"@0
str('o').repeat.parse('ooo') # => "ooo"@0
# Added structure: .as(...)
str('ooo').as(:ex1).parse('ooo') # => {:ex1=>"ooo"@0}
long = str('o').as(:ex2a).repeat.as(:ex2b).parse('ooo')
long # => {:ex2b=>[{:ex2a=>"o"@0}, {:ex2a=>"o"@1}, {:ex2a=>"o"@2}]}
</code></pre>
<p>You get to name things the way you want! This is also free. Seriously: parslet
requires you to add all the structure to its output. Annotate important parts
of your grammar with <code>.as(:symbol)</code> and get back a tree-like
structure composed of hashes (sequence), arrays (repetition) and strings (like
we had initially).</p>
<p>Once you start naming things, you’ll notice that what you don’t name,
disappears. Parslet assumes that <em>what you don’t name is unimportant</em>.</p>
<pre class="sh_ruby"><code title="inline_parser">
parser = str('a').as(:a) >> str(' ').maybe >>
str('+').as(:o) >> str(' ').maybe >>
str('b').as(:b)
parser.parse('a + b') # => {:a=>"a"@0, :o=>"+"@2, :b=>"b"@4}
</code></pre>
<p>Think of this like using a highlighter on your input: What is there not to
like about neon yellow?</p>
<h2>Making the parser complete</h2>
<p>Let’s look at the complete parser definition that also allows for function
calls:</p>
<pre class="sh_ruby"><code title="full_parser">
class MiniP < Parslet::Parser
# Single character rules
rule(:lparen) { str('(') >> space? }
rule(:rparen) { str(')') >> space? }
rule(:comma) { str(',') >> space? }
rule(:space) { match('\s').repeat(1) }
rule(:space?) { space.maybe }
# Things
rule(:integer) { match('[0-9]').repeat(1).as(:int) >> space? }
rule(:identifier) { match['a-z'].repeat(1) }
rule(:operator) { match('[+]') >> space? }
# Grammar parts
rule(:sum) { integer.as(:left) >> operator.as(:op) >> expression.as(:right) }
rule(:arglist) { expression >> (comma >> expression).repeat }
rule(:funcall) { identifier.as(:funcall) >> lparen >> arglist.as(:arglist) >> rparen }
rule(:expression) { funcall | sum | integer }
root :expression
end
require 'pp'
pp MiniP.new.parse("puts(1 + 2 + 3, 45)")
</code></pre>
<p>That’s really all there is to it — our language is a really simple language.
When fed with a string like ’<code>puts(1 + 2 + 3, 45)</code>, our parser outputs
the following:</p>
<pre class="output">
{:funcall=>"puts"@0,
:arglist=>
[{:left=>{:int=>"1"@5},
:op=>"+ "@7,
:right=>{:left=>{:int=>"2"@9}, :op=>"+ "@11, :right=>{:int=>"3"@13}}},
{:int=>"45"@16}]}
</code></pre>
<p>Parslet calls this the <em>intermediary tree</em>. There are three types of nodes in
this tree:</p>
<ul>
<li><strong>Hashes</strong>: a node that has named subtrees</li>
<li><strong>Arrays</strong>: a node storing a collection of sub-nodes</li>
<li><strong>Strings</strong> are the leaves, containing the <em>accepted source</em></li>
</ul>
<p>The format of this tree is easy to work with and to read. Here’s what the
above tree would look like as a graphic:</p>
<p><img src="images/ast.png" alt="" /></p>
<h2>Where to go from here: An Interpreter</h2>
<p>As nice as the format above is for printing and looking at – it may be
difficult at times to get the information out of it again. Let’s look at how
to transform the tree:</p>
<pre class="sh_ruby"><code>
class SimpleTransform < Parslet::Transform
rule(funcall: 'puts', arglist: sequence(:args)) {
"puts(#{args.inspect})"
}
# ... other rules
end
tree = {funcall: 'puts', arglist: [1,2,3]}
SimpleTransform.new.apply(tree) # => "puts([1, 2, 3])"
</code></pre>
<p>Transformation is an entire topic by itself; this will be covered in detail
<a href="transform.html">later on</a>. To whet your appetite, let me just give you a few
teasers:</p>
<ul>
<li>Transformations match portions of your tree at any depth, replacing them
with whatever you decide.</li>
<li>In addition to <code>sequence(sym)</code>, there is also
<code>simple(sym)</code> and <code>subtree(sym)</code>. Those match simple
strings and entire subtrees respectively. Caution with the latter.</li>
</ul>
<p>Here’s how you would write a somewhat classical interpreter for our little
language by using a transformation. Note that from this point on, there is
not one way to go about this, but thousands; you are really free (and on
your own):</p>
<pre class="sh_ruby"><code title="putting it all together">
class MiniP < Parslet::Parser
# Single character rules
rule(:lparen) { str('(') >> space? }
rule(:rparen) { str(')') >> space? }
rule(:comma) { str(',') >> space? }
rule(:space) { match('\s').repeat(1) }
rule(:space?) { space.maybe }
# Things
rule(:integer) { match('[0-9]').repeat(1).as(:int) >> space? }
rule(:identifier) { match['a-z'].repeat(1) }
rule(:operator) { match('[+]') >> space? }
# Grammar parts
rule(:sum) {
integer.as(:left) >> operator.as(:op) >> expression.as(:right) }
rule(:arglist) { expression >> (comma >> expression).repeat }
rule(:funcall) {
identifier.as(:funcall) >> lparen >> arglist.as(:arglist) >> rparen }
rule(:expression) { funcall | sum | integer }
root :expression
end
class IntLit < Struct.new(:int)
def eval; int.to_i; end
end
class Addition < Struct.new(:left, :right)
def eval; left.eval + right.eval; end
end
class FunCall < Struct.new(:name, :args);
def eval
p args.map { |s| s.eval }
end
end
class MiniT < Parslet::Transform
rule(:int => simple(:int)) { IntLit.new(int) }
rule(
:left => simple(:left),
:right => simple(:right),
:op => '+') { Addition.new(left, right) }
rule(
:funcall => 'puts',
:arglist => subtree(:arglist)) { FunCall.new('puts', arglist) }
end
parser = MiniP.new
transf = MiniT.new
ast = transf.apply(
parser.parse(
'puts(1,2,3, 4+5)'))
ast.eval # => [1, 2, 3, 9]
</code></pre>
<p>That’s a bunch of code for printing <code>[1, 2, 3, 9]</code>. Welcome to the
fantastic world of compiler and interpreter writing!</p>
<p><sup class="footnote" id="fnr1"><a href="#fn1">1</a></sup> As far as parsing goes. There is a subtle difference between
<code>#repeat(0,1)</code> and <code>#maybe</code>. Can you figure it out?</p></div>
<div class="copyright"><p><span class="caps">MIT</span> License, 2010-2012, © <a href="http://absurd.li">Kaspar Schiess</a><br/>
Logo by <a href="http://floere.github.com">Florian Hanke</a>, <a href="http://creativecommons.org/licenses/by/1.0/">CC Attribution</a> license</p></div>
<script type="text/javascript">var _gaq = _gaq || [];
_gaq.push(['_setAccount', 'UA-16365074-2']);
_gaq.push(['_trackPageview']);
(function() {
var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
})();</script>
</div>
</body>
</html>