Sorry I sent a wrong pic, this is right
________________________________
From: "peg-requ...@lists.csail.mit.edu" <peg-requ...@lists.csail.mit.edu>
To: peg@lists.csail.mit.edu
Sent: Tue, April 12, 2011 10:00:11 AM
Subject: PEG Digest, Vol 40, Issue 4
Send PEG mailing list submissions to
peg@lists.csail.mit.edu
To subscribe or unsubscribe via the World Wide Web, visit
https://lists.csail.mit.edu/mailman/listinfo/peg
or, via email, send a message with subject or body 'help' to
peg-requ...@lists.csail.mit.edu
You can reach the person managing the list at
peg-ow...@lists.csail.mit.edu
When replying, please edit your Subject line so it is more specific
than "Re: Contents of PEG digest..."
Today's Topics:
1. ANTLR's left-recursion prototype (Terence Parr)
2. Re: Left recursion considered harmful (Terence Parr)
----------------------------------------------------------------------
Message: 1
Date: Tue, 12 Apr 2011 08:47:42 -0700
From: Terence Parr <pa...@cs.usfca.edu>
Subject: [PEG] ANTLR's left-recursion prototype
To: PEG <peg@lists.csail.mit.edu>
Message-ID: <aae2a357-cc37-4457-90c1-a0ac234b6...@cs.usfca.edu>
Content-Type: text/plain; charset="us-ascii"
BTW, I spent a week recently and got ANTLR to support left-recursion with
linear
algorithm that correctly handles precedence:
http://www.antlr.org/pipermail/antlr-interest/2011-February/040830.html
http://www.antlr.org/wiki/display/~admin/2008/04/10/Still+more+about+expression+parsing
[That stuff is all out of date (I don't use / anymore, for example).]
I use Hanson's expr alg.
http://onlinelibrary.wiley.com/doi/10.1002/spe.4380151206/abstract
Used in LCC compiler. More recently called "precedence climbing".
http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing
Works great. ANTLR recognizes left prefix, suffix, binary, and ternary
operations with pattern matcher and transforms grammar to predicated
non-left-recursive grammar with linear performance. Parse tree is identical to
what left-recur grammar would yield. E.g., here is part of Java grammar that
works:
expression
: parExpression
| 'this'
| 'super'
| literal
| Identifier
| expression '.' Identifier
| expression '.' 'class' // should be type.class but causes backtracking
| expression '.' 'this'
| expression '.' 'super' '(' expressionList? ')'
| expression '.' 'super' '.' Identifier arguments?
| expression '.' 'new' Identifier '(' expressionList? ')'
| expression '.' explicitGenericInvocation
| 'new' creator
| expression '[' expression ']'
| '(' type ')' expression
| expression ('++' | '--')
| expression '(' expressionList? ')'
| ('+'|'-'|'++'|'--') expression
| ('~'|'!') expression
| expression ('*'|'/'|'%') expression
| expression ('+'|'-') expression
...
;
Example from upcoming PLDI paper:
declarator
: declarator '[' expression ']'
| declarator '[' ']'
| declarator '(' ')'
| '*' declarator
| '(' declarator ')'
| ID
;
becomes
declarator : declarator_[0] ;
declarator_[int _p]
: declarator_primary
(
( {_p <= 7}?=> '[' expression ']'
| {_p <= 6}?=> '[' ']'
| {_p <= 5}?=> '(' ')'
)
)*
;
declarator_primary
options {backtrack=true;}
: '*' declarator_[4] {}
| '(' declarator ')'
| ID
;
Only limitation is immediate-left-recur handled only. In my experience, that's
good enough :) No point in some complicated algorithm when this covers any
grammar I'd care about.
Coming soon to a theater near you (ANTLR v4 this year).
Terence
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<https://lists.csail.mit.edu/pipermail/peg/attachments/20110412/a6642b02/attachment-0001.htm>
------------------------------
Message: 2
Date: Tue, 12 Apr 2011 08:52:45 -0700
From: Terence Parr <pa...@cs.usfca.edu>
Subject: Re: [PEG] Left recursion considered harmful
To: PEG <PEG@lists.csail.mit.edu>
Message-ID: <7c49262b-1039-4e8c-99dd-d85f8b3e2...@cs.usfca.edu>
Content-Type: text/plain; charset=us-ascii
On Apr 12, 2011, at 7:01 AM, Dale Schumacher wrote:
> As your paper notes, in modifying PEGs to support left recursion "In
> essence, the parser turns from (recursive) top-down in normal
> operation to (iterative) bottom-up when left-recursion is detected."
> This mixed-model of parsing strategy can lead to very confusing
> behavior. In your conclusion, you pose the question, "are PEGs really
> suited to allowing left-recursion?"
>
> My answer to that question is "NO".
Agreed. Per previous post, I transform left-recur grammars of interest to
straight peg/predicated-LL(*).
> There is probably a theoretical
> argument to be made regarding the composability of PEGs, but I don't
> have the academic inclination to pursue that angle. Rather, I appeal
> to the inherent ability for non-experts to reason about the behavior
> of PEGs.
That is the secret sauce.
Ter
------------------------------
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
End of PEG Digest, Vol 40, Issue 4
**********************************
<<attachment: monomy.jpg>>
<<attachment: monomy2.jpg>>
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
