2011/11/8 罗勇刚(Yonggang Luo) <yonggang...@hotmail.com> > I have a question about how to match the following left-recursive rules. > > R=Er > E=Ee/Eb/e > > will R match 'ebr' > will R match 'eebr' > will R match 'eeebr' > > > Yes for the 3, it should match these.
> R=Er > E=Ee/e/Eb > > will R match 'ebr' > will R match 'eebr' > will R match 'eeebr' > > > since / means the first matching option will be returned, no, none of your strings can be matched. You would need to use a "longest match" operator instead of '/', or instaure a special case for left-recursion : if you are in a left-recursive iteration cycle, discard the matches that are shorter or equal to your current match. In practice : String : "ebr" Grammar : R=Er E=Ee/e/Eb first E development gives 'e'. Since we passed left-recursive options, you have to try again with this result as E. 'Ee' => 'ee' dsoesn't match. 'e' => 'e' matches, but is not longer than current match (which is also 'e'). So you try 'Eb', matches 'eb', you start a new iteration with E = 'eb', nothing longer than 'eb' can be matched, so you finally have R parsed as 'ebr'. This is how I implemented my own left-recursion handling, but it can result in surprises with resulting parse trees. Besides, it's inconsistent with the PEG specification of the '/' operator.
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
