aboutsummaryrefslogtreecommitdiff
path: root/lpeglabel.html
diff options
context:
space:
mode:
authorSergio Medeiros <sqmedeiros@gmail.com>2015-03-23 15:09:08 -0300
committerSergio Medeiros <sqmedeiros@gmail.com>2015-03-23 15:09:08 -0300
commitf124b2d4449a13ac21af9581a44b4455d89eaddb (patch)
treee0486555ac811c5f712927f110bb7bcda8569adf /lpeglabel.html
parent0e93d536ba2d312502737cce2ab0cc21393c4842 (diff)
downloadlpeglabel-f124b2d4449a13ac21af9581a44b4455d89eaddb.tar.gz
lpeglabel-f124b2d4449a13ac21af9581a44b4455d89eaddb.tar.bz2
lpeglabel-f124b2d4449a13ac21af9581a44b4455d89eaddb.zip
Renaming "re.lua" to "relabel.lua".
Adding examples, README and lpeglabel.html
Diffstat (limited to '')
-rw-r--r--lpeglabel.html574
1 files changed, 574 insertions, 0 deletions
diff --git a/lpeglabel.html b/lpeglabel.html
new file mode 100644
index 0000000..b38e900
--- /dev/null
+++ b/lpeglabel.html
@@ -0,0 +1,574 @@
1<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
3<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
4<head>
5 <title>LPegLabLabel - Parsing Expression Grammars For Lua</title>
6 <link rel="stylesheet"
7 href="http://www.inf.puc-rio.br/~roberto/lpeg/doc.css"
8 type="text/css"/>
9 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
10</head>
11<body>
12
13<!-- $Id: lpeg.html,v 1.71 2013/04/11 19:17:41 roberto Exp $ -->
14
15<div id="container">
16
17<div id="product">
18 <div id="product_logo">
19 <a href="https://github.com/sqmedeiros/lpeglabel">
20 <img alt="LPeg logo" src="lpeg-128.gif"/></a>
21
22 </div>
23 <div id="product_name"><big><strong>LPegLabel</strong></big></div>
24 <div id="product_description">
25 Parsing Expression Grammars For Lua with Labels, version 0.1
26 </div>
27</div> <!-- id="product" -->
28
29<div id="main">
30
31<div id="navigation">
32<h1>LPeg</h1>
33
34<ul>
35 <li><strong>Home</strong>
36 <ul>
37 <li><a href="#intro">Introduction</a></li>
38 <li><a href="#func">Functions</a></li>
39 <li><a href="#ex">Some Examples</a></li>
40 <li><a href="#download">Download</a></li>
41 <li><a href="#license">License</a></li>
42 </ul>
43 </li>
44</ul>
45</div> <!-- id="navigation" -->
46
47<div id="content">
48
49
50<h2><a name="intro">Introduction</a></h2>
51
52<p>
53<em>LPegLabel</em> is an extension of the
54<a href="http://www.inf.puc-rio.br/~roberto/lpeg/">LPeg</a>
55library that provides an implementation of Parsing Expression
56Grammars (PEGs) with labeled failures. Labels can be
57used to signal different kinds of erros and to
58specify which alternative in a labeled ordered choice
59should handle a given label. Labels can also be combined
60with the standard patterns of LPeg.
61</p>
62
63<p>
64This document describes the new functions available
65in LpegLabel and presents some examples of usage.
66For a more detailed and formal discussion about
67PEGs with labels please see
68<a href="http://www.inf.puc-rio.br/~roberto/docs/sblp2013-1.pdf">
69Exception Handling for Error Reporting in Parsing Expression Grammars
70</a>
71and
72<a href="http://arxiv.org/abs/1405.6646">Error Reporting in Parsing Expression Grammars</a>.
73</p>
74
75
76<p>
77Below there is a brief summary of the new functions
78provided by LpegLabel:
79</p>
80<table border="1">
81<tbody><tr><td><b>Function</b></td><td><b>Description</b></td></tr>
82<tr><td><a href="#f-t"><code>lpeglabel.T (l<sub>1</sub>, ..., l<sub>n</sub>)</code></a></td>
83 <td>Throws labels <code>l<sub>1</sub>, ..., l<sub>n</sub></code></td></tr>
84<tr><td><a href="#f-lc"><code>lpeglabel.Lc (p1, p2, l<sub>1</sub>, ..., l<sub>n</sub>)</code></a></td>
85 <td>Matches <code>p1</code> and tries to match <code>p2</code>
86 if the matching of <code>p1</code> gives one of l<sub>1</sub>, ..., l<sub>n</sub>
87 </td></tr>
88<tr><td><a href="#re-t"><code>%{l<sub>1</sub>, ..., l<sub>n</sub>}</code></a></td>
89 <td>Syntax of <em>re</em> module. Equivalent to <code>lpeg.T(l<sub>1</sub>, ..., l<sub>n</sub>)</code>
90 </td></tr>
91<tr><td><a href="#re-lc"><code>p1 /{l<sub>1</sub>, ..., l<sub>n</sub>} p2</code></a></td>
92 <td>Syntax of <em>re</em> module. Equivalent to <code>lpeg.Lc(p1, p2, l<sub>1</sub>, ..., l<sub>n</sub>)</code>
93 </td></tr>
94<tr><td><a href="#re-setl"><code>re.setlabels (tlabel)</code></a></td>
95 <td>Allows to specicify a table with labels. They keys of
96 <code>tlabel</code> must be integers, and the associated values usually are strings.
97 </td></tr>
98</tbody></table>
99
100<p>
101In case of an unsucessful matching, the <em>match</em> function now returns
102<code>nil</code> plus a list of labels. These labels may be used to build
103a good error message.
104</p>
105
106<h2><a name="func">Functions</a></h2>
107
108
109<h3><a name="f-t"></a><code>lpeglabel.T(l<sub>1</sub>, ..., l<sub>n</sub>)</code></h3>
110<p>
111Returns a pattern that throws the list of labels <code>l<sub>1</sub>, ..., l<sub>n</sub></code>.
112A label must be an integer between <code>0</code> and <code>31</code>.
113
114The label <code>0</code> is equivalent to the regular failure of PEGs.
115
116
117<h3><a name="f-lc"></a><code>lpeglabel.Lc(p1, p2, l<sub>1</sub>, ..., l<sub>n</sub>)</code></h3>
118<p>
119Returns a pattern equivalent to a <em>labeled ordered choice</em>.
120If the matching of <code>p1</code> gives one of the labels <code>l<sub>1</sub>, ..., l<sub>n</sub></code>,
121then the matching of <code>p2</code> is tried from the same position. Otherwise,
122the result of the matching of <code>p1</code> is the pattern's result.
123</p>
124
125<p>
126The labeled ordered choice <code>lpeg.Lc(p1, p2, 0)</code> is equivalent to the
127regular ordered choice <code>p1 / p2</code>.
128</p>
129
130<p>
131Although PEG's ordered choice is associative, the labeled ordered choice is not.
132When using this function, the user should take care to build a left-associative
133labeled ordered choice pattern.
134</p>
135
136
137<h3><a name="re-t"></a><code>%{l<sub>1</sub>, ..., l<sub>n</sub>}</code></h3>
138<p>
139Syntax of <em>re</em> module. Equivalent to <code>lpeg.T(l<sub>1</sub>, ..., l<sub>n</sub>)</code>.
140</p>
141
142
143<h3><a name="re-lc"></a><code>p1 /{l<sub>1</sub>, ..., l<sub>n</sub>} p2</code></h3>
144<p>
145Syntax of <em>re</em> module. Equivalent to <code>lpeg.Lc(p1, p2, l<sub>1</sub>, ..., l<sub>n</sub>)</code>.
146</p>
147
148<p>
149The <code>/{}</code> operator is left-associative.
150</p>
151
152<p>
153A grammar can use both choice operators (<code>/</code> and <code>/{}</code>),
154but a single choice can not mix them. That is, the parser
155of <code>re</code> module will not recognize a pattern as
156<code>p1 / p2 /{l<sub>1</sub>} p3</code>.
157</p>
158
159
160
161<h2><a name="ex">Some Examples</a></h2>
162
163<h3>Throwing a label</h3>
164<p>
165The following example defines a grammar that matches
166a list of identifiers separated by commas. A label
167is thrown when there is an error matching an identifier
168or a comma:
169</p>
170<pre class="example">
171local m = require'lpeglabel'
172
173local g = m.P{
174 "S",
175 S = m.V"Id" * m.V"List",
176 List = -m.P(1) + ("," + m.T(2)) * m.V"Id" * m.V"List",
177 Id = m.R'az'^1 + m.T(1),
178}
179
180function mymatch (g, s)
181 local r, e = g:match(s)
182 if not r then
183 if e == 1 then
184 return r, "Error: expecting an identifier"
185 elseif e == 2 then
186 return r, "Error: expecting ','"
187 else
188 return r, "Error"
189 end
190 end
191 return r
192end
193
194print(mymatch(g, "a,b"))
195print(mymatch(g, "a b"))
196print(mymatch(g, ", b"))
197</pre>
198<p>
199In this example we could think about writing rule <em>List</em> as follows:
200<pre class="example">
201List = m.P(("," + m.T(2)) * m.V"Id")^0
202</pre>
203but this would give us an expression that when matching
204the end of input would result in a failure with a label
205different from 0, that is equivalent to the regular failure,
206and the result of the repetition would be this label.
207</p>
208
209<p>
210In the previous example we could have also created a table
211with the error messages to improve the readbility of the PEG.
212Below we rewrite the grammar following this approach:
213</p>
214
215<pre class="example">
216local m = require'lpeglabel'
217
218local errUndef = 0
219local errId = 1
220local errComma = 2
221
222local terror = {
223 [errUndef] = "Error",
224 [errId] = "Error: expecting an identifier",
225 [errComma] = "Error: expecting ','",
226}
227
228local g = m.P{
229 "S",
230 S = m.V"Id" * m.V"List",
231 List = -m.P(1) + ("," + m.T(errComma)) * m.V"Id" * m.V"List",
232 Id = m.R'az'^1 + m.T(errId),
233}
234
235function mymatch (g, s)
236 local r, e = g:match(s)
237 if not r then
238 return r, terror[e]
239 end
240 return r
241end
242
243print(mymatch(g, "a,b"))
244print(mymatch(g, "a b"))
245print(mymatch(g, ", b"))
246</pre>
247
248<h3>Throwing a label using the <em>re</em> module</h3>
249
250<p>
251We can also rewrite the previous example using the <em>re</em> module
252as follows:
253</p>
254<pre class="example">
255local re = require 're'
256
257local g = re.compile[[
258 S <- Id List
259 List <- !. / (',' / %{2}) Id List
260 Id <- [a-z] / %{1}
261]]
262
263function mymatch (g, s)
264 local r, e = g:match(s)
265 if not r then
266 if e == 1 then
267 return r, "Error: expecting an identifier"
268 elseif e == 2 then
269 return r, "Error: expecting ','"
270 else
271 return r, "Error"
272 end
273 end
274 return r
275end
276
277print(mymatch(g, "a,b"))
278print(mymatch(g, "a b"))
279print(mymatch(g, ", b"))
280</pre>
281
282<p>
283Another way to describe the previous example using the <em>re</em> module
284is by using a table with the description the errors (<em>terror</em>) and
285another table that associates a name to a given label (<em>tlabel</em>):
286</p>
287<pre class="example">
288local re = require 're'
289
290local errUndef, errId, errComma = 0, 1, 2
291
292local terror = {
293 [errUndef] = "Error",
294 [errId] = "Error: expecting an identifier",
295 [errComma] = "Error: expecting ','",
296}
297
298local tlabels = { ["errUndef"] = errUndef,
299 ["errId"] = errId,
300 ["errComma"] = errComma }
301
302re.setlabels(tlabels)
303
304local g = re.compile[[
305 S <- Id List
306 List <- !. / (',' / %{errComma}) Id List
307 Id <- [a-z] / %{errId}
308]]
309
310function mymatch (g, s)
311 local r, e = g:match(s)
312 if not r then
313 return r, terror[e]
314 end
315 return r
316end
317
318print(mymatch(g, "a,b"))
319print(mymatch(g, "a b"))
320print(mymatch(g, ", b"))
321</pre>
322
323
324
325<h3>Throwing and catching a label</h3>
326
327<p>
328When a label is thrown, the grammar itself can handle this label
329by using the labeled ordered choice. Below we rewrite the example
330of the list of identifiers to show this feature:
331</p>
332<pre class="example">
333local m = require'lpeglabel'
334
335local errUndef, errId, errComma = 0, 1, 2
336
337local terror = {
338 [errUndef] = "Error",
339 [errId] = "Error: expecting an identifier",
340 [errComma] = "Error: expecting ','",
341}
342
343g = m.P{
344 "S",
345 S = m.Lc(m.Lc(m.V"Id" * m.V"List", m.V"ErrId", errId),
346 m.V"ErrComma", errComma),
347 List = -m.P(1) + m.V"Comma" * m.V"Id" * m.V"List",
348 Id = m.R'az'^1 + m.T(errId),
349 Comma = "," + m.T(errComma),
350 ErrId = m.Cc(errId) / terror,
351 ErrComma = m.Cc(errComma) / terror
352}
353
354print(g:match("a,b"))
355print(g:match("a b"))
356print(g:match(",b"))
357</pre>
358
359<p>
360As was pointed out <a href="#f-lc">before</a>, the labeled ordered
361choice is not associative, so we should impose a left-associative
362order when using function <code>Lc</code>.
363</p>
364<p>
365Below we use the <em>re</em> module to throw and catch labels.
366As was pointed out <a href="#re-lc">before</a>, the <code>/{}</code>
367operator is left-associative, so we do not need to manually impose
368a left-associative order as we did in the previous example that
369used <code>Lc</code>:
370</p>
371<pre class="example">
372local re = require're'
373
374local terror = {}
375
376local function newError(l, msg)
377 table.insert(terror, { l = l, msg = msg } )
378end
379
380newError("errId", "Error: expecting an identifier")
381newError("errComma", "Error: expecting ','")
382
383local labelCode = {}
384local labelMsg = {}
385for k, v in ipairs(terror) do
386 labelCode[v.l] = k
387 labelMsg[v.l] = v.msg
388end
389
390re.setlabels(labelCode)
391
392local p = re.compile([[
393 S <- Id List /{errId} ErrId /{errComma} ErrComma
394 List <- !. / Comma Id List
395 Id <- [a-z]+ / %{errId}
396 Comma <- ',' / %{errComma}
397 ErrId <- '' -> errId
398 ErrComma <- '' -> errComma
399]], labelMsg)
400
401print(p:match("a,b"))
402print(p:match("a b"))
403print(p:match(",b"))
404</pre>
405
406
407<h3>Tiny Language</h3>
408<p>
409As a more complex example, below we have the grammar
410for the Tiny language, as described in
411<a href="http://arxiv.org/abs/1405.6646">this</a> paper.
412The example below can also how the line where the syntactic
413error probably happened.
414</p>
415<pre class="example">
416local re = require 're'
417
418local terror = {}
419
420local function newError(l, msg)
421 table.insert(terror, { l = l, msg = msg} )
422end
423
424newError("errSemi", "Error: missing ';'")
425newError("errExpIf", "Error: expected expression after 'if'")
426newError("errThen", "Error: expected 'then' keyword")
427newError("errCmdSeq1", "Error: expected at least a command after 'then'")
428newError("errCmdSeq2", "Error: expected at least a command after 'else'")
429newError("errEnd", "Error: expected 'end' keyword")
430newError("errCmdSeqRep", "Error: expected at least a command after 'repeat'")
431newError("errUntil", "Error: expected 'until' keyword")
432newError("errExpRep", "Error: expected expression after 'until'")
433newError("errAssignOp", "Error: expected ':=' in assigment")
434newError("errExpAssign", "Error: expected expression after ':='")
435newError("errReadName", "Error: expected an identifier after 'read'")
436newError("errWriteExp", "Error: expected expression after 'write'")
437newError("errSimpExp", "Error: expected '(', ID, or number after '<' or '='")
438newError("errTerm", "Error: expected '(', ID, or number after '+' or '-'")
439newError("errFactor", "Error: expected '(', ID, or number after '*' or '/'")
440newError("errExpFac", "Error: expected expression after '('")
441newError("errClosePar", "Error: expected ')' after expression")
442
443local line
444
445local function incLine()
446 line = line + 1
447 return true
448end
449
450local function countLine(s, i)
451 line = 1
452 local p = re.compile([[
453 S <- (%nl -> incLine / .)*
454 ]], { incLine = incLine})
455 p:match(s:sub(1, i))
456 return true
457end
458
459local labelCode = {}
460for k, v in ipairs(terror) do
461 labelCode[v.l] = k
462end
463
464re.setlabels(labelCode)
465
466local g = re.compile([[
467 Tiny <- CmdSeq
468 CmdSeq <- (Cmd (SEMICOLON / ErrSemi)) (Cmd (SEMICOLON / ErrSemi))*
469 Cmd <- IfCmd / RepeatCmd / ReadCmd / WriteCmd / AssignCmd
470 IfCmd <- IF (Exp / ErrExpIf) (THEN / ErrThen) (CmdSeq / ErrCmdSeq1) (ELSE (CmdSeq / ErrCmdSeq2) / '') (END / ErrEnd)
471 RepeatCmd <- REPEAT (CmdSeq / ErrCmdSeqRep) (UNTIL / ErrUntil) (Exp / ErrExpRep)
472 AssignCmd <- NAME (ASSIGNMENT / ErrAssignOp) (Exp / ErrExpAssign)
473 ReadCmd <- READ (NAME / ErrReadName)
474 WriteCmd <- WRITE (Exp / ErrWriteExp)
475 Exp <- SimpleExp ((LESS / EQUAL) (SimpleExp / ErrSimpExp) / '')
476 SimpleExp <- Term ((ADD / SUB) (Term / ErrTerm))*
477 Term <- Factor ((MUL / DIV) (Factor / ErrFactor))*
478 Factor <- OPENPAR (Exp / ErrExpFac) (CLOSEPAR / ErrClosePar) / NUMBER / NAME
479 ErrSemi <- ErrCount %{errSemi}
480 ErrExpIf <- ErrCount %{errExpIf}
481 ErrThen <- ErrCount %{errThen}
482 ErrCmdSeq1 <- ErrCount %{errCmdSeq1}
483 ErrCmdSeq2 <- ErrCount %{errCmdSeq2}
484 ErrEnd <- ErrCount %{errEnd}
485 ErrCmdSeqRep <- ErrCount %{errCmdSeqRep}
486 ErrUntil <- ErrCount %{errUntil}
487 ErrExpRep <- ErrCount %{errExpRep}
488 ErrAssignOp <- ErrCount %{errAssignOp}
489 ErrExpAssign <- ErrCount %{errExpAssign}
490 ErrReadName <- ErrCount %{errReadName}
491 ErrWriteExp <- ErrCount %{errWriteExp}
492 ErrSimpExp <- ErrCount %{errSimpExp}
493 ErrTerm <- ErrCount %{errTerm}
494 ErrFactor <- ErrCount %{errFactor}
495 ErrExpFac <- ErrCount %{errExpFac}
496 ErrClosePar <- ErrCount %{errClosePar}
497 ErrCount <- '' => countLine
498 ADD <- Sp '+'
499 ASSIGNMENT <- Sp ':='
500 CLOSEPAR <- Sp ')'
501 DIV <- Sp '/'
502 IF <- Sp 'if'
503 ELSE <- Sp 'else'
504 END <- Sp 'end'
505 EQUAL <- Sp '='
506 LESS <- Sp '<'
507 MUL <- Sp '*'
508 NAME <- Sp !RESERVED [a-z]+
509 NUMBER <- Sp [0-9]+
510 OPENPAR <- Sp '('
511 READ <- Sp 'read'
512 REPEAT <- Sp 'repeat'
513 SEMICOLON <- Sp ';'
514 SUB <- Sp '-'
515 THEN <- Sp 'then'
516 UNTIL <- Sp 'until'
517 WRITE <- Sp 'write'
518 RESERVED <- (IF / ELSE / END / READ / REPEAT / THEN / UNTIL / WRITE) ![a-z]+
519 Sp <- %s*
520]], { countLine = countLine })
521</pre>
522
523
524<h2><a name="download"></a>Download</h2>
525
526<p>LPeg
527<a href="http://www.inf.puc-rio.br/~roberto/lpeg/lpeg-0.12.tar.gz">source code</a>.</p>
528
529
530<h2><a name="license">License</a></h2>
531
532<p>
533The MIT License (MIT)
534</p>
535<p>
536Copyright (c) 2014-2015 Sérgio Medeiros
537</p>
538<p>
539Permission is hereby granted, free of charge, to any person obtaining a copy
540of this software and associated documentation files (the "Software"), to deal
541in the Software without restriction, including without limitation the rights
542to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
543copies of the Software, and to permit persons to whom the Software is
544furnished to do so, subject to the following conditions:
545</p>
546<p>
547The above copyright notice and this permission notice shall be included in all
548copies or substantial portions of the Software.
549</p>
550<p>
551THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
552IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
553FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
554AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
555LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
556OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
557SOFTWARE.
558
559
560
561
562</p>
563
564</div> <!-- id="content" -->
565
566</div> <!-- id="main" -->
567
568<div id="about">
569</div> <!-- id="about" -->
570
571</div> <!-- id="container" -->
572
573</body>
574</html>
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-17 21:39:45 +0000