www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - OT: CFGs vs PEGs?

reply "Nick Sabalausky" <a a.a> writes:
Any compiler experts out there have opinions on contex-free grammars versus 
parsing expression grammars?
Jun 30 2008
parent reply "Manfred_Nowak" <svv1999 hotmail.com> writes:
Nick Sabalausky wrote:


 opinions on contex-free grammars versus parsing expression grammars? 


I have looked into PEG's---and no, I wouldn't trust my life to any 
machine wherein a PEG-based lexer/parser runs.

This is because their precedence based behaviour will hide ambiguities 
and make them ill-conditioned: tiny changes in the grammar may sum up 
to huge changes in behaviour.

Quick to set up and a nightmare for maintenance. 

-manfred
Jun 30 2008
parent reply "Nick Sabalausky" <a a.a> writes:
"Manfred_Nowak" <svv1999 hotmail.com> wrote in message 
news:g4c6ik$2jdi$1 digitalmars.com...

 Nick Sabalausky wrote:


 opinions on contex-free grammars versus parsing expression grammars?


 I have looked into PEG's---and no, I wouldn't trust my life to any
 machine wherein a PEG-based lexer/parser runs.

 This is because their precedence based behaviour will hide ambiguities
 and make them ill-conditioned: tiny changes in the grammar may sum up
 to huge changes in behaviour.

 Quick to set up and a nightmare for maintenance.

 -manfred


I see. That hadn't occurred to me, but I think I can understand why that's 
the case.

As far as more technical differences, from what I've seen, it sounds like 
the main difference between the two is that a PEG is basically like a CFG 
except that (using a contrived example):

A <- B | C

With a CFG, if both B and C match, then that's considered an ambiguity 
error, whereas with a PEG, if both B and C match, then it's automatically 
disambiguated by automatically using B. As I understand it, that seems to be 
the primary difference and all the other differences are basically just 
consequences of that. Is that right, or is there more to it?

(Also, if that's the case, it sounds like there wouldn't be much of a 
performance difference between equivilent PEG-based and CFG-based 
compilers?)
Jul 01 2008
next sibling parent BCS <ao pathlink.com> writes:
Reply to Nick,


 As far as more technical differences, from what I've seen, it sounds
 like the main difference between the two is that a PEG is basically
 like a CFG except that (using a contrived example):
 
 A <- B | C
 
 With a CFG, if both B and C match, then that's considered an ambiguity
 error, whereas with a PEG, if both B and C match, then it's
 automatically disambiguated by automatically using B. As I understand
 it, that seems to be the primary difference and all the other
 differences are basically just consequences of that. Is that right, or
 is there more to it?
 
 (Also, if that's the case, it sounds like there wouldn't be much of a
 performance difference between equivilent PEG-based and CFG-based
 compilers?)
 


If that is th only differerence, than the only difference is the disambuguation 
rule. (IIRC yacc/Bison does some magic to disambiguate stuff as well)
Jul 01 2008
prev sibling parent "Manfred_Nowak" <svv1999 hotmail.com> writes:
Nick Sabalausky wrote:


 is there more to it?


PEG's are backtracking when the prioritized rules fail. The resulting 
exponential behaviour can be eliminated by memoization (-> packrat). 
The memoization may need lots of RAM in addition to the complete input. 
The latter requirement may inhibit dividing off sufficiently completed 
intermediate results.

-manfred
Jul 01 2008