gmane.comp.parsers.peg.general

Re: PEG Non-Context Free

Dinesh Bolkensteyn — 2013-06-19T16:00:36

Hello Fadel,

Yep, and you're not the only one to have reported this ;-)

Have a look at
https://lists.csail.mit.edu/pipermail/peg/2009-May/thread.html

Well spotted!

--
Dinesh Bolkensteyn
www.SonarSource.com <http://www.sonarsource.com/>
twitter.com/DBolkensteyn <http://www.SonarSource.com>


On Wed, Jun 19, 2013 at 5:51 PM, Francisco Mota <fmota91< at >gmail.com> wrote:

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

Re: PEG Non-Context Free

Francisco Mota — 2013-06-19T15:51:19

I think you may be right, Fadel. Alternatively, you could use the following
rules:

D => &(A c* !.) a* B !.
A => aAb / ""
B => bBc / ""

Which also gives you the language a^n b^n c^n.
_______________________________________________
PEG mailing list
PEG< at >lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg

PEG Non-Context Free

Fadel al hassan — 2013-06-19T15:35:48

Dear All,

My name is Fadel Al-Hassan, I'm using PEG grammar for some linguistic
pattern matching tasks.

But, during my work I have noticed that the grammar, mentioned in Dr.Ford
paper, for recognizing  (a^n b^n c^n)

D => &(A !b) a* B !.

A => aAb / ""

B => bBc / ""

will also recognize (a^m b^n c^n where m >= n). Since the first match of A
rule can be an empty string.

So as to avoid this I added another predicate for D rule so it  becomes:

D => &(A !a !b) a* B !.

Is this right? or I misunderstood something here?

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

Re: Size and intersections of the PEG language set

Toby Goodwin — 2013-06-19T08:23:05


No, the parsing won't take exponential time, but neither will it work.

O(N^2) time...

Err, did you try it? You've missed the fundamental feature of PEG parsing:
we always take the first match, even if that causes a failure later on.
Your grammar can correctly match "baabb", but it fails on "baaab" (and any
string where there is an "a" after the middle letter and before the last).

You may have confused yourself by the way you've written E in two
definitions (are there any actual PEG implementations that will accept
that?). Every alternative in a PEG is *ordered*. Here's your grammar as a
working example in pacc format:

  S <- E {0}
  E :: void <- ("a"/"b") E ("a"/"b")
            / "a"

The parser in the "baaab" case successfully matches E at these positions:
"ba[a[a]b]", but then the higher-level matches fail. PEG parsing can't
"back up" once an alternative has fully matched.

More on this in the pacc documentation here:

  http://paccrat.org/article/Alternatives

Hope this helps.

Toby.

Re: Size and intersections of the PEG language set

Juancarlo Añez — 2013-06-19T05:06:25


Toby,

I think that a PEG grammar can tackle that language, but Could the parsing
 take exponential time?

A PEG grammar for the same language could be:

S -> E $
E -> (a/b) E (a/b)
E -> a

Mmmm. That actually seems to produce correct parsing with O(N) space and
O(N^2) time...

Regards,

Re: Size and intersections of the PEG language set

Sérgio Medeiros — 2013-06-18T22:57:12

Hi, Juancarlo.

I studied the relation between PEGs and CFGs (and regular expressions)
during my PhD. I have shown how to convert right-linear and strong-LL(k)
CFGs to PEGs. The article "On the Relation between Context-Free
Grammars and Parsing Expression Grammars"
(http://arxiv.org/abs/1304.3177) discusses this,
and it also shows how to convert LL-regular CFGs into PEGs.

I think the question about LR CFGs and PEGs is more difficult
to answer because these CFGs can have left-recursive rules, while
the LL(k) can't. We have tried to give a clear semantics for PEGs
with left-recursive rules in http://arxiv.org/abs/1207.0443. After this,
a next step would be to study the relation between LR CFGs and PEGs.


In http://arxiv.org/abs/1304.3177, we also show that given a grammar G
(without predicates and left recursion), L(PEG) is a subset of L(CFG).

Roman Redziejowski has also several articles that discusses
the relation between the languages of PEGs and CFGs.


As Francisco said, it is a good challenge to prove

Re: Size and intersections of the PEG language set

Toby Goodwin — 2013-06-18T21:37:14

Chapter 6 of Ford's thesis argues (without proof) that "the set of
context-free languages and the set of languages expressible in TDPL are
incomparable". Francisco already gave a variant of Ford's PEG that cannot
be expressed by any CFG.

Going the other way, he suggests this CFG:

  S -> a S a | a S b | b S a | b S b |a

"This CFG describes a language consisting of odd-length strings of 'a's
and 'b's, in which the middle character is always an 'a'. The problem here
is that in TDPL [i.e. PEGs] there is no way to "find the middle" of a
homogeneous string containing no distinguishable syntactic "signposts",
but the middle character must be found in this case in order to reject
strings that have a 'b' at that position."

(He also points out on the next page that LL and LR parsers are equivalent.)

Hope this helps,

Toby.

Re: Size and intersections of the PEG language set

Francisco Mota — 2013-06-17T22:44:38

Hi Juancarlo,

PEG is not contained in CFG. Consider the language { a^n b^n c^n | n >= 0
}. It is recognized by the PEG:

S <- &A a* B !.
A <- (a A b)?
B <- (b B c)?

So, clearly PEG is stronger than LL or LR, and PEG includes some languages
outside of CFG.

It is technically unknown whether PEGs include all CFGs. However, it is
unlikely, and certainly we don't know how to convert an arbitrary
context-free grammar into a parsing expression grammar. To do so would be a
great discovery!

Why? If you can parse CFGs in linear time, then you can multiply nxn binary
matrices in (nearly) n^2 time. The current best algorithm runs in n^2.373
time. On the other hand, PEGs are parseable in linear time.

In other words: there isn't a way to convert an arbitrary CFG into a PEG,
that we know of, and it is unlikely to be found by chance.

All the best,
Francisco Mota



On Mon, Jun 17, 2013 at 10:40 PM, Juancarlo Añez <apalala< at >gmail.com> wrote:

_______________________________________________
PEG mailing list
PEG< at >lists.cs

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,

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