gmane.comp.parsers.peg.general

Size and intersections of the PEG language set

Juancarlo Añez — 2013-06-17T21:40:06

A question that often arises in Web circles like Slashdot is what is the
relation of PEG languages to other well known sets like LL, LR, or even CFG
(and there's LSTAR and ALLSTAR).

I think that a PEG grammar is not a CFG grammar in the strict sense because
of PEG's rule/production ordering.

My question is about the set of languages that can be parsed.

Intuition tells me that the L(PEG) is larger than LL and LR, but I haven't
found a proof for it.

Cheers,

Incremental Parsing for PEG

Francisco Mota — 2013-05-06T13:30:51

Hi everyone. Long time follower but first time poster, here.

Is there an off-the-shelf available incremental parser for PEGs?

Incremental parsing is where a small change in the input string
necessitates only a small amount of additional processing. The idea is that
you parse the string once, and then adding or removing characters from the
string in the middle causes only a small amount of reprocessing.

That is, you have some signature like:

parse : String -> Syntax
insert : Int * String * Syntax -> Syntax
remove : Int * Int * Syntax -> Syntax

where parse(s) is used for the initial parse, insert(i,s,t) will insert the
string s at position i of t, and reparse, and remove(i,k,t) will remove k
characters from position i of t.

The trivial algorithm is to just reparse the whole string. The downside is
that insert and remove operation has complexity linear in the size of the
whole string, not just the inserted part.

The more efficient way is to only modify the parts of the parse tree that
are affected. Packrat parsing can be used to this effect. You keep the
cache around after parsing the string the first time. When the string is
updated, you invalidate only some sections of the cache, and you update the
indices of the rest of the cache, and then you reparse using the same
cache. The vast majority of the string will reparse using the cache, so the
cost of this operation is more dependant on the depth of the syntax tree,
rather than its length. (Top-level nodes will have been invalidated.)

So my question is: has anyone implemented this algorithm?

Take care,
Francisco Mota
_______________________________________________
PEG mailing list
PEG< at >lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg

Touchy-feely

Juancarlo Añez — 2013-05-06T10:51:43


James,

Thanks.

Yet, so far, this list has felt like a colosseum.

Maybe they are thus competitive at MIT?

Cheers,

[ANN] ParseKit

Todd Ditchendorf — 2013-05-02T18:14:33

Hello PEG Mailing List.

I'd like to announce the release of an updated version of my Objective-C
framework, ParseKit.

ParseKit is an Objective-C library that converts PEG-style grammars to
Packrat parsers in the form of Objective-C source code suitable for use on
the iOS or Mac OS X platforms.

ParseKit is heavily inspired by ANTLR, and ParseKit grammars have a very
similar syntax.

Parsekit's home page is http://parsekit.com

I've written a tutorial that describes the new PEG/Packrat features:
http://itod.github.io/ParseKitMiniMathExample/

The parsers produced by ParseKit are recursive descent, deterministic,
packrat (memoizing), and backtracking as I believe would be expected for a
PEG/Packrat tool. ParseKit parsers also have the Semantic Predicate feature
copied directly from ANTLR.

ParseKit also includes an *extremely weak* version of ANTLR's LL(*)
concept: Static grammar analysis will produce simple single-token
prediction branching for any decision which is LL(1), but use full
backtracking speculation for any non-LL(1) decision. However, ParseKit does
not implement anything nearly as sophisticated as ANTLR's full LL(*)/DFA
feature.

Thanks to Terence Parr and Bryan Ford for your contributions to this field.
I have really enjoyed reading your books/papers and have learned a great
deal from you in this process.

Todd Ditchendorf
_______________________________________________
PEG mailing list
PEG< at >lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg

From EBNF to PEG

Roman Redz — 2013-04-10T19:45:53

An improved version of my paper "From EBNF toPEG", due to appear in 
Fundamenta Informaticae, is now available from 
http://www.romanredz.se/pubs.htm.
The paper tries to answer the question " when an EBNF grammar can be 
used as its own PEG parser?".
It is inspired by a result from Medeiros about PEGs for LL(1) grammars.
Some sufficient conditions are presented, leading eventually to the 
notion of "LL(1p)" grammars, where a top-down parser may choose the next 
action by examining the input within the reach of one parsing procedure 
("1p") , rather than by looking at the next letter.
This may have some use for inserting the "cut" operator, but a 
mechanical procedure for doing this does not seem easy.
_______________________________________________
PEG mailing list
PEG< at >lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg

About cut making previous memos irrelevant in Grako

Juancarlo Añez — 2013-03-29T19:36:19

After, the recent experiments, I reviewed the implementation of *cut* in
Grako.

Grako's implementation of *cut *is in the spirit of Prolog, which means
that a *cut* applies only to the nearest choice (optional, closure) in the
runtime stack. That means that memos for positions before that of the last
choice have a non-zero theoretical probability of being reused.

The explanation for the low impact of my optimistic memo pruning on
performance should be that the grammar is for a structured,
largely unambiguous, and quite probably LL(k) programming language, which
makes it unlikely that previous memos are reused after any structured
construct ("IF" *cut*) has been entered.

Cheers,

Cutting memoization

Juancarlo Añez — 2013-03-28T20:25:28

Hello Kota,

I'm reading your paper more carefully now (Packrat Parsers can Handle
Practical Grammars in Mostly Constant Space).

If I understand correctly, if a cut is seen at position P in the input,
then all memoization for positions prior to P can be discarded?

Thanks in advance!

Cheers,

Introduction, and Grako, and cut over PEG

Juancarlo Añez — 2013-03-27T00:08:10

Hello,

I just found about this list!

I'm a software engineer with a good part of my career spent on language
theory and programming language implementation.

I recently wrote the tool Grako[1], basically because I was hired to deal
with Software AG Natural, and COBOL with embedded CICS and SQL, the LLxxx
tools I knew made it too hard (I tried), and the PEG parsers around seemed
not to be up to thousands of lines of unencumbered grammars.

One of the biggest questions I had while building Grako was about how to
implement a "cut" feature, much like the one Prolog-style parsers have. It
is something  I have not seen in other PEG parsers, but that I've tried to
implement to my best because I think it is of value.  The original question
is at SO [2]. I'd be very interested in your opinions.

Cheers!

[1] https://pypi.python.org/pypi/grako
[2] http://goo.gl/AnNbp

PEG C parser generator for non-char input symbols

Mikhail Gusarov — 2012-12-15T22:14:58

Good day.

I am looking for a PEG parser generator for C language that uses input
characters different from 'char': the grammar I am implementing is
specified in UTF-16 16-bit words, so matching using regular 8-bit
chars would not be convenient.

Looks like both peg and pacc can be modified to allow it, so the
question is whether there is anything that works "out of the box".

Best regards,
Mikhail Gusarov.

PEG grammar help

Alexey Shamrin — 2012-10-30T15:12:23

Hello,

I'm trying to write a PEG grammar that would match this input:

  a.a(a).a

And would not match this input:

  a.a(a)

I want my input to always end with ".a".

I tried the following grammar in PEG.js [1] and language.js [2]:

  start = expr !.
  expr = a (dot a / left a right)* dot a
  a = 'a'
  dot = '.'
  left = '('
  right = ')'

But it doesn't work. In PEG.js my first input fails with "Expected "("
or "." but end of input found.".

It seems PEG doesn't try to backtrack at this point. Why doesn't it?
What grammar can work for me?

[1]: http://pegjs.majda.cz/online
[2]: http://languagejs.com/

Alexey

From EBNF to PEG

Roman Redziejowski — 2012-09-30T08:47:01

Just announcing a paper "From EBNF to PEG" that builds on ideas from 
Medeiros.
It is available at http://www.romanredz.se/pubs.htm.
Roman

_______________________________________________
PEG mailing list
PEG< at >lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg

Paper about left recursion in PEGs

Sérgio Medeiros — 2012-07-03T12:56:16

Hi.

My colleagues and I wrote a paper
about left recursion in PEGs. 
The paper is available at arXiv:
http://arxiv.org/abs/1207.0443

This paper presents the same semantics
for left recursion that appears in an early
draft that I wrote, with a better explanation.

Any feedback is welcome.

Sérgio
_______________________________________________
PEG mailing list
PEG< at >lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg

Paper about left recursion in PEGs

Sérgio Medeiros — 2012-07-03T12:56:16

Hi.

My colleagues and I wrote a paper
about left recursion in PEGs. 
The paper is available at arXiv:
http://arxiv.org/abs/1207.0443

This paper presents the same semantics
for left recursion that appears in an early
draft that I wrote, with a better explanation.

Any feedback is welcome.

Sérgio
_______________________________________________
PEG mailing list
PEG< at >lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg

Solving the left recursion problem (once more)

Jean-Luc Delatre — 2012-06-23T15:49:10

Hi Packratters,

Could I have some feedback on this one?
https://forge.ocamlcore.org/projects/lrttparser/
As you can see it's Ocaml/Linux only, sorry...

Cheers,

jld

Announcing pacc-0.0

Toby Goodwin — 2012-06-20T20:29:37

pacc (which stands for "pacc - a compiler-compiler") is a parser-generator
that reads a PEG and emits a packrat (i.e. linear) parser in C.

pacc solves the REPL problem mentioned in Ford's ICFP 2002 paper.

pacc is intended, as it matures, to become the parser-generator of choice
for C for the early- to mid-21st century: widely portable, industrial
strength, blazingly fast, parsimonious, and still elegant.

pacc's first release pacc-0.0 is now available under the GPL. (It doesn't
achieve any of those lofty goals, there are lots of unfinished corners,
and there isn't much documentation. But it does actually work!)

    http://paccrat.org/

pacc was written by me, Toby Goodwin. It would not have been possible
without the prior work of Ian Piumarta and (of course) Bryan Ford, to both
of whom I am hugely grateful.

Toby.

integrating backtracking into peg

Ondřej Bílka — 2012-05-15T16:56:51

Hello

I generalized packrat parsing algorithm to algoritm that runs in linear
time and under natural conditions is equivalent to fully backtracking 
parser.

I devise more flexible formalism REG^REG of relativized regular expressions.


A preprint to submitted paper is available here: http://arxiv.org/abs/1205.1877

peg on suffix tree

Ondřej Bílka — 2012-02-03T11:14:43

Assume that you already have have say java code in memory both as string and as suffix tree.

If rule would look at most 5 characters then we could memoize all its
occurences in single step.

I am wondering if suffix tree actualy gave us some speedup.

another left recursion question

Ondřej Bílka — 2012-01-31T10:31:00

What your parser does on following rule:
a = a* 'a' | 'b'
say on string ababbba

global state

Jon Rafkind — 2011-12-13T21:34:00

I am planning on supporting global state in my peg generator. The way Rats! does it with transactions looks pretty good to me but my question is how to actually implement the state operations in a manner that work with transactions. Specifically the state has to be pure in some sense so that it can be "undone" by an abort operation.

My first naive idea is to have some State class (maybe defined by the user) with a pointer to a child State class. The start() method of a transaction would create a new State object and set parent->next to it. Then the user can modify the new State object. commit() would be a no-op and abort() would reset the parent->next pointer to null.

In psuedo-code

start(){
  state = new State();
  current->next = state;
  return state;
}

abort(){
  current->next = null;
}

commit(){}

# blah = a b c
#            |  d e f
rule_blah(){
   # For each production, do a start/commit/abort sequence
   state = start();
   rule_a(); rule_b(); rule_c();
   commit();
   return
   fail: # if any of the rules failed somehow
   abort();

   state = start();
   rule_d(); rule_e(); rule_f();
   commit();
   return
   fail:
   abort();
}

approaching a PEG for time parsing

James Cox — 2011-10-27T12:12:13

Hey,

I'm trying to come up with a peg for natural language time parsing.

given a string like:

"the sunday before last"

or

"4 fridays hence"

or

"jan 1st last year"

I'd like to parse these and convert to meaningful data.

'the sunday before last' translates to sunday, past, 2
'2 fridays hence' translates to friday, future, 4
'jan 1st last year' translates to jan, 1, past, year-1

(or something like that :))

i've started in building my grammar, but i'm struggling to get my head
around how to approach it - and therefore would appreciate any
feedback as to the best approach.

e.g. i'm not sure that PEG is completely right, and since there are no
tokens separating content (other than a space) it's been tricky to
figure out how to approach it.

so... if anyone is willing to help share some pointers and discuss
approach for this, i'd very much appreciate it!

Thanks,

James Cox

Java APG Version 1.0

2011-10-24T15:38:54

I'd like to announce the release of Java APG Version 1.0.
This is APG - An ABNF(*) Parser Generator, written entirely in the Java
language.
As I have mentioned here before, APG is remarkably similar to PEG,
even though PEG was developed by careful consideration
with mathematical proofs at each step of the way and APG by ad hoc happen
chance.
They share:
1. grammars built from parsing expressions (APG's operators)
2. disambiguation through prioritized-choice and greedy repetitions
3. syntactic predicates.

But it is item 1. that is most intriguing in its flexibility 
the ability to invent new expressions/operators as the problem dictates.
The addition of syntactic predicates to APG (Version 4.0) was in fact just
that,
an invented operator to match a needed but non-CFG phrase.
(After the fact, of course. Parr and Quong, and Bryan Ford beat me to it
by years.)

Java APG Version 1.0 introduces User-Defined Terminals (UDTs) which
essentially allow
the user to roll his own operators (expressions?).
Yes, you have to be careful handwriting phrase recognition
(you can easily lose track of exactly what language it is you are
recognizing)
but they are really no different from the three terminal phrases already
defined in ABNF, namely the character range, the case-insensitive literal
string
and the binary string. APG already provides handwritten recognition of those
phrases and has since Version 1.0. UDTs are also similar to semantic actions,
which most parser generators support. UDTs generalize this concept.
By standardizing their introduction into the grammar,
UDTs can also be thought of as putting semantic actions
on the same footing as the other grammar-defining operators or expressions.

Java APG, Version 1.0 includes a small library of UDTs for simple,
but often time-consuming phrases such as alphanum, white space,
C/C++-style comments and others. A number of examples are provided
which give time comparisions between the UDT and CFG versions
of some simple phrases. The time improvement factor is
sometimes negligible but for lengthy phrases can often
be in the 20s and 30s.

Released under the GPL, Java APG can be found at
www.coasttocoastresearch.com

Thanks,
Lowell Thomas

(*) ABNF - IETF RFC 4234 - is the grammar syntax used to define
most Internet standards and protocols.
Its expressiveness is similar to PEG and EBNF.