Roman Redz | 16 Jul 15:55 2015

Two papers

Just to inform you that my paper "More about converting BNF to PEG" appeared in Fundamenta Informaticae 133, 2-3 (2014), pp. 257-270.
Another paper, "Cut points in PEG" is due to appear later this year.
Both are available from .
PEG mailing list
PEG <at>
Henri Tuhola | 29 Apr 00:04 2015

Is this correct implementation of GLL, or something entirely else?

Before writing this, I studied various papers about GLL, such as GLL Parsing and "Modelling GLL Parser Implementations". Also read the paper that described parser combinators of this kind and took a peek into djspiewak/gll-combinators that was written in scala.

I found the project written in scala very hard to read, and the papers weren't any much better. But I understood something about the description.

I wrote a simple recognizer that appears to work. It prints out state transitions similar to what LR parser might go through with:

For someone who have actually understood the papers better, is my implementation even near of what GLL is? What is it if it's not?
PEG mailing list
PEG <at>
Matthew Goode | 28 Oct 22:47 2014

New version of AustenX (1.1)

A new version of AustenX is now available at This is a Java based PEG generator, 
that supports "advanced" handling of left-recursion (which I still have 
not explained how it works), and optional/selective memorisation,  as 
well as useful extensions to PEGs. It works with a tokenisation step.

New for version 1.1 are extensions that allow for indentation sensitive 
parsing (eg, for languages like Python, etc...), as well as some other 
useful features.

Roman Redz | 27 Oct 17:43 2014

PEG for Java 1.8

Just to inform you that I have posted a preliminary version of PEG for Java 1.8  (Java 8?)
at .
Best regards - Roman
PEG mailing list
PEG <at>
Abdelkader Belloundja | 23 Sep 14:10 2014

integer encoding // computational model

Hi everybody,

Maybe some of you, if not all, have heard of things like Church Numerals that use lambda calculus to model numbers and operators, or Peano Numbers that use axioms. This is more or less related to computational models.

I'm concerned about finding a way to do the same with PEG / Backtracking. I, however, don't have any clue for where to start.

I guess the grammar should play the role of the axioms and therefore the input should be the calculus to be computed / verified, but I can't figure out how it should actually work or even look.

Anyway, I would be glad to have any piece of data on the matter. Feel free to send me anything you think may help.

Thanks !

PEG mailing list
PEG <at>
Vitaly S. Lugovskiy | 6 Sep 14:27 2014

MBase 1.0 released under QPL

MBase is a simple metaprogramming framework for .net platform, featuring, among other compiler building blocks, an extensible Packrat+Pratt parser frontend with a transparent left recursion support.

The PEG-related code is in src/l/lib/parsing/ and src/l/lib/pfront/

See (a somewhat outdated) demo here: 

PEG mailing list
PEG <at>
mathew palsberg | 4 Sep 19:54 2014

random program/string generator for PEG

I recently built a small language with PEG. I now want to test my language with random generated(not necessarily meaningful) programs. Does anybody know a tool that given a PEG grammar, it generates random sequences that satisfy the given grammar?


PEG mailing list
PEG <at>
Mayo Kaze | 14 Aug 03:13 2014

Is there any PEG implementation in ActionScript?

Hi mates:

I'd like to ask is there any PEG implementation in ActionScript? If there isn't I am planing to create it myself.

Kind regards,
cashin.peter | 13 Aug 17:48 2014

Serv ed

Pity sugar makes it useless he added taking a sip and shuddering

you have a new message from me

read your video message
PEG mailing list
PEG <at>
Marcus Brinkmann | 12 Aug 00:22 2014

Re: Breaking the Mizushima(2010) cut operator


I reported this in August 2013 to the grako bug tracker:

I think you will find that your example is similar to mine.

The cut operator in grako was implemented like you describe.  But note 
that this is _not_ the Mizushima cut operator.  The Mizushima paper is 
very careful to limit application of the cut operator to an empty 
backtracking stack, which avoids the problem: "Generally, when the 
backtracking stack of a parser is empty at position n, the parser can 
discard all regions in the memoization table whose column indices are 
less than n."

Later the Mizushima paper gives a negative example: "Because the 
backtracking stack is not empty and the position 0 is pushed to the 
stack, the parser cannot discard space for memoization at this point."

You ignored the condition (empty backtracking stack), and thus your 
example showed non-linear behavior.  It is an easy mistake to make.

When I reported this to Juancarlo, he told me (again, see the 
bugtracker): "When I read Kota's paper I empirically found that deleting 
the memoization cache left speed unchanged, but dramatically decreased 
memory use, so I left it in in the know that swiping the whole cache was 
overdoing it :-"

As I wrote at the time, it seems difficult (at least for me!) to come up 
with a proper example that actually shows non-linear behaviour on 
arbitrary long input (rather than a small example grammer that only 
accepts a finite set of sentences).  If you succeed with that, I'd be 
interested!  I described my difficulties like this: "It's surprisingly 
hard to come up with this example, and I can't find an example that has 
non-linear runtime on the input, as the cutting rules themselves are 
memoized, and thus the memoization deletions are in some sense 
"self-healing."" and "I can not prove that this can break the linear 
time promise of PEG parsing, and at the moment I suspect that due to the 
fact that the number of cuts in any grammar is constant and independent 
of the input length, the linear time promise is still preserved. 
However, I can't prove that either :P"

Roman Redziejowski | 23 Jul 14:09 2014

Breaking cut operator

I believe Ger Hobbelt discovered a problem.

The "cut point", in the sense of a point after which there is no use of backtracking, is the property of a specific selection operator.

Once B in Ger's examples sucessfully consumed A, it indeed does not need to backtrack (as this must fail).
But G in the second example has to backtrack after failing B, even if B passed its cut point. So B has no right to erase the history because it may be used by the containing expression.
So the cut points should somehow be considered in the entire hierarchy of parsing expressions.

I recently wrote a note about cut points, to be presented at the CSP workshop this year. It was inspired by a section in the paper by Maidl et al. about producing error messages; apparently failures in 'no return' areas defined by cut points are those relevant ones.
I missed there the fact that cut points are local.

(My note can be found at Remember: it is preliminary and not peer-reviewed yet.)

PEG mailing list
PEG <at>