From 98e54ce388233170cd3a3feb2bcc4449670ccabc Mon Sep 17 00:00:00 2001 From: Sergio Queiroz Date: Wed, 14 Dec 2016 08:16:29 -0300 Subject: Removing files related to the previous version (with labeled ordered choice) --- examples/recoveryRe.lua | 141 ------------ lpeglabel.html | 587 ------------------------------------------------ 2 files changed, 728 deletions(-) delete mode 100644 examples/recoveryRe.lua delete mode 100644 lpeglabel.html diff --git a/examples/recoveryRe.lua b/examples/recoveryRe.lua deleted file mode 100644 index 3b83d88..0000000 --- a/examples/recoveryRe.lua +++ /dev/null @@ -1,141 +0,0 @@ -local re = require"relabel" - --- The `errinfo` table contains the list of labels that we will be using --- as well as the corresponding error message for each label, which will --- be used in our error reporting later on. -local errinfo = { - {"NoExp", "no expression found"}, - {"Extra", "extra characters found after the expression"}, - {"ExpTerm", "expected a term after the operator"}, - {"ExpExp", "expected an expression after the parenthesis"}, - {"MisClose", "missing a closing ')' after the expression"}, -} - --- We split the errinfo table into two tables: `labels` which is a --- mapping from the label names to its integer representation, and --- `errmsgs` which is a mapping from the label names to its --- corresponding error message. -local labels = {} -local errmsgs = {} - -for i, err in ipairs(errinfo) do - labels[err[1]] = i - errmsgs[err[1]] = err[2] -end - --- The `labels` table is especially useful for making our re grammar more --- readable through the use of the `setlabels` function which allows us --- to use the label names directly in the re grammar instead of the integers. -re.setlabels(labels) - --- The `errors` table will hold the list of errors recorded during parsing -local errors = {} - --- The `recorderror` function simply records the label and position of --- the failure (index in input string) into the `errors` table. --- Note: The unused `input` parameter is necessary, as this will be called --- by LPeg's match-time capture. -local function recorderror(input, pos, label) - table.insert(errors, {label, pos}) - return true -end - --- The `compute` function takes an alternating list of numbers and --- operators and computes the result of applying the operations --- to the numbers in a left to right order (no operator precedence). -local function compute(tokens) - local result = tokens[1] - for i = 2, #tokens, 2 do - if tokens[i] == '+' then - result = result + tokens[i+1] - elseif tokens[i] == '-' then - result = result - tokens[i+1] - elseif tokens[i] == '*' then - result = result * tokens[i+1] - elseif tokens[i] == '/' then - result = result / tokens[i+1] - else - error('unknown operation: ' .. tokens[i]) - end - end - return result -end - --- Our grammar is a simple arithmetic expression of integers that --- does not take operator precedence into account but allows grouping --- via parenthesis. We have incorporated some error recovery startegies --- to our grammar so that it may resume parsing even after encountering --- an error, which allows us to report more errors. -local g = re.compile([[ - S <- (Exp / ErrNoExp) (!. / ErrExtra) - Exp <- {| Term (op Operand)* |} -> compute - -- If we encounter a missing term/operand, we return a dummy instead. - Operand <- Term / ErrExpTerm /{ExpTerm} dummy - Term <- num / Group - -- If we encounter a missing closing parenthesis, we ignore it. - Group <- "(" InnerExp (")" / ErrMisClose /{MisClose} "") - -- If we encounter a missing inner expression, we skip to the next - -- closing parenthesis, and return a dummy in its place. - InnerExp <- Exp / ErrExpExp /{ExpExp} [^)]* dummy - - op <- {[-+*/]} - num <- [0-9]+ -> tonumber - - -- Before throwing an error, we make sure to record it first. - ErrNoExp <- ("" -> "NoExp" => recorderror) %{NoExp} - ErrExtra <- ("" -> "Extra" => recorderror) %{Extra} - ErrExpTerm <- ("" -> "ExpTerm" => recorderror) %{ExpTerm} - ErrExpExp <- ("" -> "ExpExp" => recorderror) %{ExpExp} - ErrMisClose <- ("" -> "MisClose" => recorderror) %{MisClose} - - dummy <- "" -> "0" -> tonumber -]], { - compute = compute; - recorderror = recorderror; - tonumber = tonumber; -}) - --- The `eval` function takes an input string to match against the grammar --- we've just defined. If the input string matches, then the result of the --- computation is returned, otherwise we return the error messages and --- positions of all the failures encountered. -local function eval(input) - local result, label, suffix = g:match(input) - if #errors == 0 then - return result - else - local out = {} - for i, err in ipairs(errors) do - local pos = err[2] - local msg = errmsgs[err[1]] - local line, col = re.calcline(input, pos) - table.insert(out, "syntax error: " .. msg .. " (line " .. line .. ", col " .. col .. ")") - end - errors = {} - return nil, table.concat(out, "\n") - end -end - -print(eval "98-76*(54/32)") ---> 37.125 - -print(eval "(1+1-1*2/2") ---> syntax error: missing a closing ')' after the expression (line 1, col 10) - -print(eval "(1+)-1*(2/2)") ---> syntax error: expected a term after the operator (line 1, col 4) - -print(eval "(1+1)-1*(/2)") ---> syntax error: expected an expression after the parenthesis (line 1, col 10) - -print(eval "1+(1-(1*2))/2x") ---> syntax error: extra characters found after the expression (line 1, col 14) - -print(eval "-1+(1-(1*2))/2") ---> syntax error: no expression found (line 1, col 1) - -print(eval "(1+1-1*(2/2+)-():") ---> syntax error: expected a term after the operator (line 1, col 13) ---> syntax error: expected an expression after the parenthesis (line 1, col 16) ---> syntax error: missing a closing ')' after the expression (line 1, col 17) ---> syntax error: extra characters found after the expression (line 1, col 17) diff --git a/lpeglabel.html b/lpeglabel.html deleted file mode 100644 index 59e744a..0000000 --- a/lpeglabel.html +++ /dev/null @@ -1,587 +0,0 @@ - - - - LPegLabLabel - Parsing Expression Grammars For Lua - - - - - -
- -
- -
LPegLabel
-
- Parsing Expression Grammars For Lua with Labels, version 0.1 -
-
- -
- - - -
- - -

Introduction

- -

-LPegLabel is an extension of the -LPeg -library that provides an implementation of Parsing Expression -Grammars (PEGs) with labeled failures. Labels can be -used to signal different kinds of erros and to -specify which alternative in a labeled ordered choice -should handle a given label. Labels can also be combined -with the standard patterns of LPeg. -

- -

-This document describes the new functions available -in LpegLabel and presents some examples of usage. -In LPegLabel, the result of an unsuccessful matching -is a triple nil, lab, sfail, where lab -is the label associated with the failure, and -sfail is the suffix input where -the label was thrown. -

- -

-Below there is a brief summary of the new functions -provided by LpegLabel: -

- - - - - - - - - - - - -
FunctionDescription
lpeglabel.T (l)Throws label l
lpeglabel.Lc (p1, p2, l1, ..., ln)Matches p1 and tries to match p2 - if the matching of p1 gives one of l1, ..., ln -
%{l}Syntax of relabel module. Equivalent to lpeg.T(l) -
p1 /{l1, ..., ln} p2Syntax of relabel module. Equivalent to lpeg.Lc(p1, p2, l1, ..., ln) -
relabel.setlabels (tlabel)Allows to specicify a table with mnemonic labels. -
- -

-For a more detailed and formal discussion about -PEGs with labels please see - -Exception Handling for Error Reporting in Parsing Expression Grammars, -Error Reporting in Parsing Expression Grammars, -and -A parsing machine for parsing expression grammars with labeled failures. -

- - - -

Functions

- - -

lpeglabel.T(l)

-

-Returns a pattern that throws the label l. -A label must be an integer between 0 and 63. - -The label 0 is equivalent to the regular failure of PEGs. - - -

lpeglabel.Lc(p1, p2, l1, ..., ln)

-

-Returns a pattern equivalent to a labeled ordered choice. -If the matching of p1 gives one of the labels l1, ..., ln, -then the matching of p2 is tried from the same position. Otherwise, -the result of the matching of p1 is the pattern's result. -

- -

-The labeled ordered choice lpeg.Lc(p1, p2, 0) is equivalent to the -regular ordered choice p1 / p2. -

- -

-Although PEG's ordered choice is associative, the labeled ordered choice is not. -When using this function, the user should take care to build a left-associative -labeled ordered choice pattern. -

- - -

%{l}

-

-Syntax of relabel module. Equivalent to lpeg.T(l). -

- - -

p1 /{l1, ..., ln} p2

-

-Syntax of relabel module. Equivalent to lpeg.Lc(p1, p2, l1, ..., ln). -

- -

-The /{} operator is left-associative. -

- -

-A grammar can use both choice operators (/ and /{}), -but a single choice can not mix them. That is, the parser -of relabel module will not recognize a pattern as -p1 / p2 /{l1} p3. -

- - -

relabel.setlabels (tlabel)

- -

Allows to specicify a table with labels. They keys of -tlabel must be integers between 0 and 63, -and the associated values should be strings. -

- - - -

Some Examples

- -

Throwing a label

-

-The following example defines a grammar that matches -a list of identifiers separated by commas. A label -is thrown when there is an error matching an identifier -or a comma: -

-
-local m = require'lpeglabel'
-
-local g = m.P{
-  "S",
-  S = m.V"Id" * m.V"List",
-  List = -m.P(1) + ("," + m.T(2)) * m.V"Id" * m.V"List",
-  Id = m.R'az'^1 + m.T(1),
-}
-
-function mymatch (g, s)
-  local r, e = g:match(s)
-  if not r then
-    if e == 1 then
-      return "Error: expecting an identifier"
-    elseif e == 2 then
-      return "Error: expecting ','"
-    else
-      return "Error"
-    end
-  end
-  return r
-end
-	
-print(mymatch(g, "a,b"))
-print(mymatch(g, "a b"))
-print(mymatch(g, ", b"))
-
-

-In this example we could think about writing rule List as follows: -

-List = m.P(("," + m.T(2)) * m.V"Id")^0
-
-but this would give us an expression that when matching -the end of input would result in a failure whose associated -label would be 2. -

- -

-In the previous example we could have also created a table -with the error messages to improve the readbility of the PEG. -Below we rewrite the grammar following this approach: -

- -
-local m = require'lpeglabel'
-
-local errUndef = 0
-local errId = 1
-local errComma = 2
-
-local terror = {
-  [errUndef] = "Error",
-  [errId] = "Error: expecting an identifier",
-  [errComma] = "Error: expecting ','",
-}
-
-local g = m.P{
-  "S",
-  S = m.V"Id" * m.V"List",
-  List = -m.P(1) + ("," + m.T(errComma)) * m.V"Id" * m.V"List",
-  Id = m.R'az'^1 + m.T(errId),
-}
-
-function mymatch (g, s)
-  local r, e = g:match(s)
-  if not r then
-    return terror[e]
-  end
-  return r
-end
-	
-print(mymatch(g, "a,b"))
-print(mymatch(g, "a b"))
-print(mymatch(g, ", b"))
-
- -

Throwing a label using the relabel module

- -

-We can also rewrite the previous example using the relabel module -as follows: -

-
-local re = require 'relabel' 
-
-local g = re.compile[[
-  S    <- Id List
-  List <- !.  /  (',' / %{2}) Id List
-  Id   <- [a-z]  /  %{1}	
-]]
-
-function mymatch (g, s)
-  local r, e = g:match(s)
-  if not r then
-    if e == 1 then
-      return "Error: expecting an identifier"
-    elseif e == 2 then
-      return "Error: expecting ','"
-    else
-      return "Error"
-    end
-  end
-  return r
-end
-	
-print(mymatch(g, "a,b"))
-print(mymatch(g, "a b"))
-print(mymatch(g, ", b"))
-
- -

-Another way to describe the previous example using the relabel module -is by using a table with the description of the errors (terror) and -another table that associates a name to a given label (tlabels): -

-
-local re = require 'relabel' 
-
-local errUndef, errId, errComma = 0, 1, 2
-
-local terror = {
-  [errUndef] = "Error",
-  [errId] = "Error: expecting an identifier",
-  [errComma] = "Error: expecting ','",
-}
-
-local tlabels = { ["errUndef"] = errUndef,
-                  ["errId"]    = errId, 
-                  ["errComma"] = errComma }
-
-re.setlabels(tlabels)
-
-local g = re.compile[[
-  S    <- Id List
-  List <- !.  /  (',' / %{errComma}) Id List
-  Id   <- [a-z]  /  %{errId}	
-]]
-
-function mymatch (g, s)
-  local r, e = g:match(s)
-  if not r then
-    return terror[e]
-  end
-  return r
-end
-	
-print(mymatch(g, "a,b"))
-print(mymatch(g, "a b"))
-print(mymatch(g, ", b"))
-
- - - -

Throwing and catching a label

- -

-When a label is thrown, the grammar itself can handle this label -by using the labeled ordered choice. Below we rewrite the example -of the list of identifiers to show this feature: -

-
-local m = require'lpeglabel'
-
-local errUndef, errId, errComma = 0, 1, 2
-
-local terror = {
-  [errUndef] = "Error",
-  [errId] = "Error: expecting an identifier",
-  [errComma] = "Error: expecting ','",
-}
-
-g = m.P{
-  "S",
-  S = m.Lc(m.Lc(m.V"Id" * m.V"List", m.V"ErrId", errId),
-           m.V"ErrComma", errComma),
-  List = -m.P(1)  +  m.V"Comma" * m.V"Id" * m.V"List",
-  Id = m.R'az'^1  +  m.T(errId),
-  Comma = ","  +  m.T(errComma),
-  ErrId = m.Cc(errId) / terror,
-  ErrComma = m.Cc(errComma) / terror
-}
-
-print(g:match("a,b"))
-print(g:match("a b"))
-print(g:match(",b"))
-
- -

-As was pointed out before, the labeled ordered -choice is not associative, so we should impose a left-associative -order when using function Lc. -

-

-Below we use the re module to throw and catch labels. -As was pointed out before, the /{} -operator is left-associative, so we do not need to manually impose -a left-associative order as we did in the previous example that -used Lc: -

-
-local re = require'relabel'
-
-local terror = {} 
-
-local function newError(l, msg) 
-  table.insert(terror, { l = l, msg = msg } )
-end
-
-newError("errId", "Error: expecting an identifier")
-newError("errComma", "Error: expecting ','")
-
-local labelCode = {}
-local labelMsg = {}
-for k, v in ipairs(terror) do 
-  labelCode[v.l] = k
-  labelMsg[v.l] = v.msg
-end
-
-re.setlabels(labelCode)
-
-local p = re.compile([[
-  S        <- Id List  /{errId}  ErrId  /{errComma}  ErrComma
-  List     <- !.  /  Comma Id List
-  Id       <- [a-z]+  /  %{errId}
-  Comma    <- ','  /  %{errComma}
-  ErrId    <- '' -> errId
-  ErrComma <- '' ->  errComma
-]], labelMsg)
-
-print(p:match("a,b"))
-print(p:match("a b"))
-print(p:match(",b"))
-
- - -

Tiny Language

-

-As a more complex example, below we have the grammar -for the Tiny language, as described in -this paper. -The example below can also show the line where the syntactic -error probably happened. -

-
-local re = require 'relabel'
-
-local terror = {}
-
-local function newError(l, msg)
-  table.insert(terror, { l = l, msg = msg} )
-end
-
-newError("errSemi", "Error: missing ';'")  
-newError("errExpIf", "Error: expected expression after 'if'") 
-newError("errThen", "Error: expected 'then' keyword") 
-newError("errCmdSeq1", "Error: expected at least a command after 'then'") 
-newError("errCmdSeq2", "Error: expected at least a command after 'else'") 
-newError("errEnd", "Error: expected 'end' keyword") 
-newError("errCmdSeqRep", "Error: expected at least a command after 'repeat'") 
-newError("errUntil", "Error: expected 'until' keyword") 
-newError("errExpRep", "Error: expected expression after 'until'") 
-newError("errAssignOp", "Error: expected ':=' in assigment") 
-newError("errExpAssign", "Error: expected expression after ':='") 
-newError("errReadName", "Error: expected an identifier after 'read'") 
-newError("errWriteExp", "Error: expected expression after 'write'") 
-newError("errSimpExp", "Error: expected '(', ID, or number after '<' or '='")
-newError("errTerm", "Error: expected '(', ID, or number after '+' or '-'")
-newError("errFactor", "Error: expected '(', ID, or number after '*' or '/'")
-newError("errExpFac", "Error: expected expression after '('")
-newError("errClosePar", "Error: expected ')' after expression")
-
-local line
-
-local function incLine()
-  line = line + 1
-  return true
-end
-
-local function countLine(s, i)
-  line = 1
-  local p = re.compile([[
-    S <- (%nl -> incLine  / .)*
-  ]], { incLine = incLine}) 
-  p:match(s:sub(1, i))
-  return true
-end
-
-local labelCode = {}
-for k, v in ipairs(terror) do 
-  labelCode[v.l] = k
-end
-
-re.setlabels(labelCode)
-
-local g = re.compile([[
-  Tiny         <- CmdSeq  
-  CmdSeq       <- (Cmd (SEMICOLON / ErrSemi)) (Cmd (SEMICOLON / ErrSemi))*
-  Cmd          <- IfCmd / RepeatCmd / ReadCmd / WriteCmd  / AssignCmd 
-  IfCmd        <- IF (Exp / ErrExpIf)  (THEN / ErrThen)  (CmdSeq / ErrCmdSeq1)  (ELSE (CmdSeq / ErrCmdSeq2)  / '') (END / ErrEnd)
-  RepeatCmd    <- REPEAT  (CmdSeq / ErrCmdSeqRep)  (UNTIL / ErrUntil)  (Exp / ErrExpRep)
-  AssignCmd    <- NAME  (ASSIGNMENT / ErrAssignOp)  (Exp / ErrExpAssign)
-  ReadCmd      <- READ  (NAME / ErrReadName)
-  WriteCmd     <- WRITE  (Exp / ErrWriteExp)
-  Exp          <- SimpleExp  ((LESS / EQUAL) (SimpleExp / ErrSimpExp) / '')
-  SimpleExp    <- Term  ((ADD / SUB)  (Term / ErrTerm))*
-  Term         <- Factor  ((MUL / DIV)  (Factor / ErrFactor))*
-  Factor       <- OPENPAR  (Exp / ErrExpFac)  (CLOSEPAR / ErrClosePar)  / NUMBER  / NAME
-  ErrSemi      <- ErrCount %{errSemi}
-  ErrExpIf     <- ErrCount %{errExpIf}
-  ErrThen      <- ErrCount %{errThen}
-  ErrCmdSeq1   <- ErrCount %{errCmdSeq1}
-  ErrCmdSeq2   <- ErrCount %{errCmdSeq2}
-  ErrEnd       <- ErrCount %{errEnd}
-  ErrCmdSeqRep <- ErrCount %{errCmdSeqRep}
-  ErrUntil     <- ErrCount %{errUntil}
-  ErrExpRep    <- ErrCount %{errExpRep}
-  ErrAssignOp  <- ErrCount %{errAssignOp}
-  ErrExpAssign <- ErrCount %{errExpAssign}
-  ErrReadName  <- ErrCount %{errReadName}
-  ErrWriteExp  <- ErrCount %{errWriteExp}
-  ErrSimpExp   <- ErrCount %{errSimpExp}
-  ErrTerm      <- ErrCount %{errTerm}
-  ErrFactor    <- ErrCount %{errFactor}
-  ErrExpFac    <- ErrCount %{errExpFac}
-  ErrClosePar  <- ErrCount %{errClosePar}
-  ErrCount     <- '' => countLine 
-  ADD          <- Sp '+'
-  ASSIGNMENT   <- Sp ':='
-  CLOSEPAR     <- Sp ')'
-  DIV          <- Sp '/'
-  IF           <- Sp 'if'
-  ELSE         <- Sp 'else'
-  END          <- Sp 'end'
-  EQUAL        <- Sp '='
-  LESS         <- Sp '<'
-  MUL          <- Sp '*'
-  NAME         <- Sp !RESERVED [a-z]+
-  NUMBER       <- Sp [0-9]+
-  OPENPAR      <- Sp '('
-  READ         <- Sp 'read'
-  REPEAT       <- Sp 'repeat'
-  SEMICOLON    <- Sp ';'
-  SUB          <- Sp '-'
-  THEN         <- Sp 'then'
-  UNTIL        <- Sp 'until'
-  WRITE        <- Sp 'write'
-  RESERVED     <- (IF / ELSE / END / READ / REPEAT / THEN / UNTIL / WRITE) ![a-z]+
-  Sp           <- %s*	
-]], { countLine = countLine })
-
- - -

Download

- -

LPegLabel -source code.

- - -

License

- -

-The MIT License (MIT) -

-

-Copyright (c) 2014-2015 Sérgio Medeiros -

-

-Permission is hereby granted, free of charge, to any person obtaining a copy -of this software and associated documentation files (the "Software"), to deal -in the Software without restriction, including without limitation the rights -to use, copy, modify, merge, publish, distribute, sublicense, and/or sell -copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: -

-

-The above copyright notice and this permission notice shall be included in all -copies or substantial portions of the Software. -

-

-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR -IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, -FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE -AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER -LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, -OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE -SOFTWARE. - - - - -

- -
- -
- -
-
- -
- - - -- cgit v1.2.3-55-g6feb