Talk:Tiki forum archive/Forum 5/6850
Source: 2013 Tiki forum 5, thread #6850. Original authors, UTC times, post IDs, and reply-parent IDs are preserved. This is an archive, not an active article discussion.
left recursion changes
left recursion changes
pdf23ds · 2008-06-22 22:18 UTC · Tiki post #6850
left recursion changes
pdf23ds · 2008-06-22 22:18 UTC · Tiki post #6851 · reply to Tiki post #6850
surprisingly easy. The PEG now checks to see if the first item in the first sequence in the first option is a reference to itself. If so, that production will try to match the other, non-recursing options first, and if it finds a match, will try to match the first option using the match from the other option as the value of the recursive item. It repeats this until it can't eat any more text. The changes I made to the grammar to use this feature follow. They're quite regular--decrement the number in the first item, remove asterisk, and add an option for the next production.
-statement-1 <- statement-2 (I-clause joik-jek statement-2?)* +statement-1 <- statement-1 I-clause joik-jek statement-2? / statement-2
-bridi-tail-1 <- bridi-tail-2 (gihek !(stag? BO-clause) !(stag? KE-clause) free* bridi-tail-2 tail-terms)* +bridi-tail-1 <- bridi-tail-1 gihek !(stag? BO-clause) !(stag? KE-clause) free* bridi-tail-2 tail-terms / bridi-tail-2
-terms-1 <- terms-2 (pehe-sa* PEhE-clause free* joik-jek terms-2)* +terms-1 <- terms-1 pehe-sa* PEhE-clause free* joik-jek terms-2 / terms-2
-sumti-2 <- sumti-3 (joik-ek sumti-3)* +sumti-2 <- sumti-2 joik-ek sumti-3 / sumti-3
-selbri-3 <- selbri-4+ +selbri-3 <- selbri-3 selbri-4 / selbri-4
-selbri-4 <- selbri-5 (joik-jek selbri-5 / joik stag? KE-clause free* selbri-3 KEhE-clause? free*)* +selbri-4 <- selbri-4 (joik-jek selbri-5 / joik stag? KE-clause free* selbri-3 KEhE-clause? free*) / selbri-5
tanru-unit-2 <- blah blah blah blah ... / - NU-clause NAI-clause? free* (joik-jek NU-clause NAI-clause? free*)* subsentence KEI-clause? free* + nu-clauses subsentence KEI-clause? free* + +nu-clauses <- nu-clauses joik-jek nu-nai / nu-nai + +nu-nai <- NU-clause NAI-clause? free*
I'm planning on using this feature, xorxes. i mi ba nelci lo nu je ka jo du'u palci pilno .ui
-tag <- tense-modal (joik-jek tense-modal)* +tag <- tag joik-jek tense-modal / tense-modal
-stag <- simple-tense-modal ((jek / joik) simple-tense-modal)* / tense-modal (joik-jek tense-modal)* +stag <- stag (jek / joik) simple-tense-modal / simple-tense-modal / tag
Now these two I'm not entirely sure about. But I don't think it hurts anything too much. On 'stag', besides the recursion I also changed the last option to just be a reference to 'tag', since the sequences were identical.
I made these changes several days ago and haven't seen any problems yet, though that's not a sure indicator of anything. So I don't think there are any gross errors in here.
Chris Capel -- "What is it like to be a bat? What is it like to bat a bee? What is it like to be a bee being batted? What is it like to be a batted bee?" -- The Mind's I (Hofstadter, Dennet)
To unsubscribe from this list, send mail to [email protected]
with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if
left recursion changes
Anonymous · 2008-06-22 22:52 UTC · Tiki post #6852 · reply to Tiki post #6850
> + > +nu-clauses <- nu-clauses joik-jek nu-nai / nu-nai > + > +nu-nai <- NU-clause NAI-clause? free* > > I'm planning on using this feature, xorxes. i mi ba nelci lo nu je ka > jo du'u palci pilno .ui
If I understand correcty, that means you will like ice-cream, right? Since nothing can be both an event and a property, I take it that {lo nu je ka jo du'u ...} could be something that is neither an event nor a property, and also not a du'u. Ice-cream, for instance.
mu'o mi'e xorxes
To unsubscribe from this list, send mail to [email protected]
with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if
left recursion changes
Anonymous · 2008-06-22 23:12 UTC · Tiki post #6853 · reply to Tiki post #6850
> > -tag <- tense-modal (joik-jek tense-modal)* > +tag <- tag joik-jek tense-modal / tense-modal > > -stag <- simple-tense-modal ((jek / joik) simple-tense-modal)* / > tense-modal (joik-jek tense-modal)* > +stag <- stag (jek / joik) simple-tense-modal / simple-tense-modal / tag > > Now these two I'm not entirely sure about. But I don't think it hurts > anything too much. On 'stag', besides the recursion I also changed the > last option to just be a reference to 'tag', since the sequences were > identical.
In fact, you could just do:
stag <- tag
or just remove "stag" from the grammar and replace everywhere with "tag". The PEG eliminated the distinction that existed between them, as it was a consequence of the LALR(1) restriction.
mu'o mi'e xorxes
To unsubscribe from this list, send mail to [email protected]
with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if
left recursion changes
rlpowell · 2008-06-24 05:24 UTC · Tiki post #6861 · reply to Tiki post #6850
> OK, I caved and implemented a subset of left recursion. It was > surprisingly easy. The PEG now checks to see if the first item in > the first sequence in the first option is a reference to itself. > If so, that production will try to match the other, non-recursing > options first, and if it finds a match, will try to match the > first option using the match from the other option as the value of > the recursive item. It repeats this until it can't eat any more > text. The changes I made to the grammar to use this feature > follow. They're quite regular--decrement the number in the first > item, remove asterisk, and add an option for the next production.
This would be your own PEG parser generator, then? Sorry, I haven't been following the thread.
You might want to look at whatever the Rats! guy did; his stuff also automatically deals with left-recursion, but I think maybe in a slightly more structured fashion? He's pretty approachable, you might want to ask him.
-Robin
-- Lojban Reason #17: http://en.wikipedia.org/wiki/Buffalo_buffalo Proud Supporter of the Singularity Institute - http://singinst.org/ http://www.digitalkingdom.org/~rlpowell/ *** http://www.lojban.org/
To unsubscribe from this list, send mail to [email protected]
with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if
left recursion changes
Anonymous · 2008-06-27 09:48 UTC · Tiki post #6870 · reply to Tiki post #6850
<[email protected]> wrote: > You might want to look at whatever the Rats! guy did; his stuff also > automatically deals with left-recursion, but I think maybe in a > slightly more structured fashion? He's pretty approachable, you > might want to ask him.
This is the paper I followed to implement direct and indirect left recursion support in my own peg grammar implementation:
http://www.vpri.org/pdf/packrat_TR-2007-002.pdf
I think Rats uses a method of grammar transformation iirc and doesn't deal with indirect left recursion. It's been a while since I used it though, so that might have been dealt with.
Chris -- http://www.bluishcoder.co.nz
To unsubscribe from this list, send mail to [email protected]
with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if
