gmane.comp.parsers.peg.general

Re: [ANN] ParseKit

Juancarlo Añez — 2013-05-18T18:56:30

Ter,


 Just a note on why I reluctantly had to opt out of ANTLR and seek PEG for

In ANTLR, one you define a word in the tokenizer, it always behaves as a
keyword.

Alternatives like using:

: WORD {WORD.text == "MY_KEYWORD"}?


Make the language too ambiguous in ANTLR terms.

In PEG, you can do exactly the above, with a semantic action, because
there's no ambiguity by PEG's definition.





It's not just the backtracking which distinguishes PEG prom predicting
parser. It is the ability to have the parser behave differently depending
on context.

PEG easily allows for embedded languages within one grammar (the case for
Natural FORMAT statement, and COBOL's PICTURE statement). In a predictive
parser, one language would interfere with the parsing of the other, unless
you do heavy magic with the lexer to separate the sub-languages, and build
a different grammar for each sub-language.



I actually need a scanner that takes care of white-space, comments,
case-insensitivity, and word boundaries. The grammars wou

Re: [ANN] ParseKit

Terence Parr — 2013-05-15T21:35:26

predicate?

option then ANTLR v3 more or less have to backtrack constantly, leading it
to behave exactly like a PEG.

 this sounds like you need a scannerless parser. v4 would handle this no
problem, if you're willing to treat each character as a token.



 I'm not clear on how a PEG has an advantage here; could you be more
specific?

Thanks,
Ter

Re: Incremental Parsing for PEG

Ondřej Bílka — 2013-05-06T21:02:52

As far as I remember on problem of maintaining parity if you use O(n^(1-e)) memory 
then you need do queries of size n^e . 
You can write parity problem as a grammar so incremental parsing is
special case.

For memory complexity my solution is relatively simple. 
First idea is measure how long call takes and memoize only these that
take say 1000 cycles. 
This has problem that it is platform dependent. You can get similar
results if you memoize calls that call at least 16 other
rules(recursively.)
Or if you do not care about pathological grammars you can memoize only
rules that inspect more than 16 characters.

Re: Incremental Parsing for PEG

Ondřej Bílka — 2013-05-06T20:36:41

Yes I implemented it but not entirely integrated in amethyst. 
See my thesis chapter 3. http://kam.mff.cuni.cz/~ondra/thesis.pdf (I
discovered this independently.)
When you can write repetition in way it is associative you could cut
this to logarithmic factor. You essentialy keep at k-th level parts
consisting from at most 2^k iterations

Ondra.
>

Re: Incremental Parsing for PEG

Juancarlo Añez — 2013-05-06T20:14:09

Francisco,

On Mon, May 6, 2013 at 1:06 PM, Francisco Mota <fmota91< at >gmail.com> wrote:



I thought some about it, and I think you could get away with amending the
memoization table by the amount of characters inserted or deleted. For a
change made at position (p:p+n), only the table entries in which (i:i+len)
 intersect the previous range would have to be modified.

OTOH, just deleting the affected entries would be simpler, and very safe.



You could still introduce manual cuts in the rules in which you know there
will be no rewriting. Grako's memory use over 100's of KLOC of COBOL went
down to 40%, with no impact on performance, just by boldly deleting entries
upon a cut.

Cheers,

Re: [ANN] ParseKit

Juancarlo Añez — 2013-05-06T19:46:15

Hello Ter!

Anyway, just wanted to point out that I find this case rare and like having


Just a note on why I reluctantly had to opt out of ANTLR and seek PEG for
my ongoing projects:

   - Software AG Natural allows relevant language words to be used as
   identifiers. In fact, words are keywords or not depending on context.
   - Natural also makes many of the relevant language words optional. The
   predictive ANTLR *v3* grammar was inundated with lookaheads to resolve
   the ambiguity caused by that.
   - Natural has exactly one statement that is not led by a keyword:
   assignment. And most statements lack terminators, so ANTLR would consume
   the left hand side of an assignment unless a negative lookahead was added
   to most rules.
   - COBOL programs embed subprograms in CICS and SQL, and those must be
   parsed to have a complete translation.

It was time-consuming and difficult to deal with the above with a mandated
tokenizer, and with v3's allergy to apparent ambiguity (I couldn't try v4
because

Re: [ANN] ParseKit

Terence Parr — 2013-05-06T19:05:07

Hi all! Just a quick response about scannerless parsers. These are most
useful for modular grammars and for languages where there is no clear
lexical sentinel that differentiates between islands.

This is not hard to do in antlr v4. I have an example in the extras
directory of the book where I do a mini C + SQL example. Here's some sample
input:

void f(int i) {
        resultset r = select * from users where ID='1999' and state<>'CA';
        int select = 'a';
        int from = 'b';
        int x = select * from;
        int nextID = select ID from users where name='parrt' + 1;
}

PEG folks will recognize it as very PEG like. It's inefficient in v4
because each character must be a token.

Anyway, just wanted to point out that I find this case rare and like having
a separate lexer, but of course I want it all in one specification as if it
were scannerless.

Ter


On Sun, May 5, 2013 at 9:40 AM, Juancarlo Añez <apalala< at >gmail.com> wrote:

Re: Incremental Parsing for PEG

Francisco Mota — 2013-05-06T17:36:54

parser.

Only some parts of the memoization table would be invalidated by an insert
or a remove. You would need to update the rest of the memoization table in
order to support the new indices. (The right data structure for the table
would help keep costs down.) This is precisely why I think Packrat parsing
works well for incremental parsing.

Packrat parsers can be sublinear with the addition of cuts, and that cut
insertion can be automated.

I don't think this would work if one wants to optimize incremental parsing,
as opposed to one-time parsing. You need to keep the old parsing data
around in order to minimize future duplication of effort. I reckon that you
would always need at least a linear amount of information in the
memoization table, otherwise you'll have to reparse the entire string (at
least linearly many bits of it) whenever a change is made. But this is
speculation on my part.

To give an example of the algorithm I laid out above, consider the (overly
simple) PEG:

A <- x B y
B <- C / D / E
C <-

Re: Incremental Parsing for PEG

Juancarlo Añez — 2013-05-06T16:19:45

Hello Dinesh,

Yeah! I was probably not quite on target. Sorry.

I don't see the connection of your answer Juancarlo and Francisco's

The principle is the same. PEG parsers are free to manipulate the input
stream.

PEG doesn't have to be Packrat. But you're right: changing the input stream
would throw off memoization in a Packrat parser.



Mizushima and others on this list have work showing that memory use in
Packrat parsers can be sublinear with the addition of cuts, and that cut
insertion can be automated.

Cheers,

Re: Incremental Parsing for PEG

Dinesh Bolkensteyn — 2013-05-06T15:30:45

I don't see the connection of your answer Juancarlo and Francisco's
question on incremental parsing.

Who is talking about error recovery?

I am not aware of an existing PEG implementation that saves the memoization
table in order to allow efficient re-parsing of a slightly altered version
of the input.
In fact it seems that Packrat is fairly memory hungry, and that attempts
are made to drop this table as soon as possible.

--
Dinesh Bolkensteyn
www.SonarSource.com <http://www.sonarsource.com/>
twitter.com/DBolkensteyn
On Mon, May 6, 2013 at 4:58 PM, Juancarlo Añez <apalala< at >gmail.com> wrote:

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

Re: Incremental Parsing for PEG

Juancarlo Añez — 2013-05-06T14:58:57

Hello Francisco,

On Mon, May 6, 2013 at 9:00 AM, Francisco Mota <fmota91< at >gmail.com> wrote:


This is advice I remember from the ANTLR lists, which you can search
online: http://antlr.1301665.n2.nabble.com/


   - Add additional, catch-all/catch-some rules at the points in which
   you'd like recovery to happen.

PEG parsers are outstanding at skipping over input.

For example, in parsing embedded SQL in COBOL, I have a rule similar to
this one for skipping over uninteresting parts:

skip_uninteresting_sql = {!'END-EXEC ANY} ;

With "*!*END-EXE" being a negative lookahead for the end-of-statement word,
and "ANY" matching any input character.

The above is inefficient, but it gives the idea.  The actual rule for the
compiler generator I'm using (Grako), uses a perl-style regular expression
that's handled by the Python re library (DFAs), so it's cool:

skip_uninteresting_sql = ?/(?:.|\n)*?(?=END-EXEC)/? ;

That regular expression means "match anything until END-EXEC is in sight".

As we've been discussing on a

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. Packr

Re: Touchy-feely

James Pike — 2013-05-06T11:19:44

No I think a few people just needed a bit more sleep :P

Cheers, James

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,

Re: [ANN] ParseKit

James Pike — 2013-05-06T09:48:53

If you mean that respectful disagreement and discussion is not
tolerated, then no, this mailing list is not touchy-feely.

However if you mean that outbursts and impolite/blunt statements are
tolerated, then I think no, these are not welcome on any mailing list
in spite of the fact that many notable open source figures display such
characteristics.

Cheers, James

Re: [ANN] ParseKit

Juancarlo Añez — 2013-05-06T01:15:03

Is this mailing list touchy-feely?

There's no ground for interesting discussions if it is so.

Cheers,


On Sun, May 5, 2013 at 12:30 PM, Todd Ditchendorf <
todd.ditchendorf< at >gmail.com> wrote:

Re: [ANN] ParseKit

Todd Ditchendorf — 2013-05-05T17:00:15

ANTLR is not PEG! It is ALLSTAR (aLL[*]).

Although I'll admit you found an ambiguity in my language (see what I did
there?), I didn't say it was. :)

My meaning would have been better conveyed with:

    I may unify parser/tokenizer recognition (like ANTLR) in the future for
my PEG-based generator.

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

Re: [ANN] ParseKit

Juancarlo Añez — 2013-05-05T16:40:50

Todd,

The tokenizer was a component that already existed in ParseKit. So when I


ANTLR is not PEG! It is ALLSTAR (aLL[*]).

The reason I migrated away from ANTLR is because of the tokenizer, which
cannot be parser-driven (not without a huge amount of "glue" code). Quite
unlike PEG.

My way out of it was this:

https://bitbucket.org/apalala/grako


I can explain further, if you care.

Cheers,

Re: [ANN] ParseKit

Todd Ditchendorf — 2013-05-05T16:15:39

Thanks Juancarlo.

The tokenizer was a component that already existed in ParseKit. So when I
began work on the new PEG-based static packrat generator a few weeks ago, I
took a shortcut. I used the existing tokenizer for token recognition. I may
unify parser/tokenizer recognition in the future for the PEG-based
generator (like ANTLR). But either way, the existing tokenizer will remain
as a useful stand-alone component for other applications.

TD


On Sun, May 5, 2013 at 7:57 AM, Juancarlo Añez <apalala< at >gmail.com> wrote:

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

Re: [ANN] ParseKit

Juancarlo Añez — 2013-05-05T14:57:02

Hello Todd,

Interesting!

Why did you include a tokenizer in a PEG parser?

Cheers,


On Thu, May 2, 2013 at 1:44 PM, Todd Ditchendorf <todd.ditchendorf< at >gmail.com

[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 speculat