Left and right recursion with subtraction - lepl

The old Google Groups will be going away soon, but your browser is incompatible with the new version.
lepl
Message from discussion Left and right recursion with subtraction
Received-SPF: neutral (google.com: 74.55.86.74 is neither permitted nor denied by best guess record for domain of and...@acooke.org) client-ip=74.55.86.74;
Date: Thu, 23 Jun 2011 14:53:52 -0400
From: andrew cooke <and...@acooke.org>
To: lepl@googlegroups.com
Subject: Re: [LEPL] Re: Left and right recursion with subtraction
Message-ID: <20110623185352.GI26488@acooke.org>
References: <BANLkTikVwOsK74S-JXjqxqBnzU_r-jB+Og@mail.gmail.com>
 <f2e34ddd-041e-48d2-8e56-3f6219533ffd@w36g2000vbi.googlegroups.com>
 <20110531231344.GA24252@acooke.org>
 <BANLkTinMEU-_MTxpfiPZZwA2NGqOG6f2qg@mail.gmail.com>
 <20110622175629.GD23304@acooke.org>
 <20110622225453.GA11555@acooke.org>
 <BANLkTikC6zh6MMyr-wxYzqapkpwPVocdnQ@mail.gmail.com>
 <20110623184637.GG26488@acooke.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20110623184637.GG26...@acooke.org>
User-Agent: Mutt/1.5.21 (2010-09-15)


do you mean something like:

   1 < x < 2

which might in some crazy example be

   1 < x > 3

if so, then those aren't binary operators.  there some freaky mess.  and what
i would do is slurp them up as a sequence of symbols and then try and make
sense of them elsewhere.

so something like:

   expression[2:,Or(">","<")] > FreakyMess

where expression matches some sub-expression like "x" or "1".

andrew


On Thu, Jun 23, 2011 at 02:46:37PM -0400, Andrew Cooke wrote:
> 
> can you give me an exact example with > and < that shows the problem?  i am
> not sure i follow.  thanks, andrew
> 
> 
> On Thu, Jun 23, 2011 at 02:30:46PM -0400, Andrew Stromme wrote:
> > Thanks, that makes sense and my implementation of it is working.
> > 
> > What should I do about other operations with precedence, such as < and >?
> > They don't have the same easy 'inversion' properties that +,- and *,/ have.
> > 
> > I could get a tree structure but without the top level Compare node knowing
> > about how to evaluate its children on a case by cases I can't see how it
> > would work.
> > 
> > Andrew
> > 
> > On Wed, Jun 22, 2011 at 6:54 PM, andrew cooke <and...@acooke.org> wrote:
> > 
> > >
> > > the code is now at
> > >
> > > http://code.google.com/p/lepl/source/browse/src/lepl/_example/expression2.py?spec=svn455ba3ac227d91a0a3ba6a5963118102bc55f20e&r=455ba3ac227d91a0a3ba6a5963118102bc55f20e#203
> > > (and it includes evaluation)
> > >
> > > i don't think (but haven't proved) that the natural pair grouping you want
> > > is
> > > possible (my argument is that the form implies left-recursion, which
> > > contradicts what you are trying to do).  so i had two alternatives: either
> > > rewrite the result tree to re-arrange nodes, or make nested pairs "flat".
> > >
> > > since i already had code that parsed to give "flat" trees, that's what i
> > > went
> > > with.  it took a few attempts (which you can see in the link above) before
> > > i
> > > understood what to do - to easily make the flat nodes you need to create a
> > > list in a single "line" of the parser, which means matching just one "kind
> > > of
> > > thing".  that led to the idea of summing numbers that might be negative,
> > > and
> > > the same for products.
> > >
> > > hope that all makes sense.  i'll update the manual for the next release
> > > (which
> > > i am working on, but which is still a long way off).
> > >
> > > cheers,
> > > andrew
> > >
> > >
> > > On Wed, Jun 22, 2011 at 01:56:29PM -0400, Andrew Cooke wrote:
> > > >
> > > > hi,
> > > >
> > > > just muddled through to find this during lunch.  posting now in case you
> > > are
> > > > waiting, will explain tonight.  hopefully it's fairly self-explanatory.
> > >  the
> > > > idea is to have sums and products, where sums can contain positive and
> > > > negative values, and products can contain values and their inverses.  i
> > > > haven't implemented the node operations to evaluate, but they have
> > > obvious
> > > > (and reasonably efficient) solutions (i hope!):
> > > >
> > > >     def test_repeat3(self):
> > > >         '''
> > > >         Fix the problem above by folding - and / into the value itself.
> > > >         '''
> > > >         basicConfig(level=DEBUG)
> > > >
> > > >         class Op(List): pass
> > > >         class Sum(Op): pass
> > > >         class Neg(Op): pass
> > > >         class Prd(Op): pass
> > > >         class Inv(Op): pass
> > > >
> > > >         with TraceVariables():
> > > >
> > > >             value = Token(UnsignedReal())
> > > >             symbol = Token('[^0-9a-zA-Z \t\r\n]')
> > > >             number = Optional(symbol('-')) + value >> float
> > > >
> > > >             sum = Delayed()
> > > >             parens = ~symbol('(') & sum & ~symbol(')')
> > > >             val = parens | number
> > > >
> > > >             inv = ~symbol('/') & val > Inv
> > > >             eve = ~symbol('*') & val
> > > >             prd = val & (inv | eve)[0:] > Prd
> > > >
> > > >             neg = ~symbol('-') & prd > Neg
> > > >             pos = ~symbol('+') & prd
> > > >             sum += prd & (neg | pos)[0:] > Sum
> > > >
> > > >         line = sum & Eos()
> > > >
> > > >         self.examples([
> > > >                 (lambda: line.parse('4-3-2')[0],
> > > > """Sum
> > > > +- Prd
> > > > |   `- 4.0
> > > > +- Neg
> > > > |   `- 3.0
> > > > `- Neg
> > > >      `- 2.0"""),
> > > >                 (lambda: line.parse('1+2-3-4+5+6+7-8-9-10-11')[0],
> > > > """Sum
> > > > +- Prd
> > > > |   `- 1.0
> > > > +- 2.0
> > > > +- Neg
> > > > |   `- 3.0
> > > > +- Neg
> > > > |   `- 4.0
> > > > +- 5.0
> > > > +- 6.0
> > > > +- 7.0
> > > > +- Neg
> > > > |   `- 8.0
> > > > +- Neg
> > > > |   `- 9.0
> > > > +- Neg
> > > > |   `- 10.0
> > > > `- Neg
> > > >      `- 11.0"""),
> > > >                 (lambda: line.parse('1+2*(3-4)+5/6+7')[0],
> > > > """Sum
> > > >  +- Prd
> > > >  |   `- 1.0
> > > >  +- Prd
> > > >  |   +- 2.0
> > > >  |   `- Sum
> > > >  |       +- Prd
> > > >  |       |   `- 3.0
> > > >  |       `- Neg
> > > >  |           `- Prd
> > > >  |               `- 4.0
> > > >  +- Prd
> > > >  |   +- 5.0
> > > >  |   `- Inv
> > > >  |       `- 6.0
> > > >  `- Prd
> > > >      `- 7.0""")])
> > > >
> > > >
> > > >
> > > >
> > > > On Tue, Jun 21, 2011 at 09:54:09PM -0400, Andrew Stromme wrote:
> > > > > Hi Andrew,
> > > > >
> > > > > I'm just checking in with regards to the repetition vs recursion and
> > > left
> > > > > recursion/right recursion question I had a while back. The parsing part
> > > of
> > > > > my project was on the back burner but I'm picking it up again and
> > > remembered
> > > > > that I had this issue to look at. I had a look at the expression.py
> > > example
> > > > > but couldn't get it to work myself with Tokens.
> > > > >
> > > > > Thanks,
> > > > >
> > > > > Andrew Stromme
> > > > >
> > > > > On Tue, May 31, 2011 at 7:13 PM, andrew cooke <and...@acooke.org>
> > > wrote:
> > > > >
> > > > > >
> > > > > > Hi,
> > > > > >
> > > > > > I am trying to look at this, but am having some "issues" with running
> > > any
> > > > > > Python code at all, so it may be some time before I can get back.
> > > > > >
> > > > > > FWIW it seems like you are right and that exmple is wrong.  What I
> > > would
> > > > > > like
> > > > > > to do is extend the approach at
> > > > > >
> > > http://code.google.com/p/lepl/source/browse/src/lepl/_example/expression.py
> > > > > > which uses repeptition rather than recursion.  I thnk that could give
> > > a
> > > > > > clean
> > > > > > solution, with some work (eg using "sum(...)")
> > > > > >
> > > > > > Sorry I can't be more help right now - will try and be more useful in
> > > the
> > > > > > new
> > > > > > day or two.
> > > > > >
> > > > > > Andrew
> > > > > >
> > > > > >
> > > > > > On Tue, May 31, 2011 at 02:23:36PM -0700, astromme wrote:
> > > > > > > After consulting the dragon book and some online resources I've
> > > come
> > > > > > > up with
> > > > > > >
> > > > > > > group4end = Delayed()
> > > > > > > add = ~symbol('+') & group3 & group4end > List
> > > > > > > sub = ~symbol('-') & group3 & group4end > List
> > > > > > > group4end += Optional(add | sub)
> > > > > > > group4 += group3 & group4end > List
> > > > > > >
> > > > > > > which should associate things as expected, I think? However, this
> > > > > > > makes it a lot harder to generate nodes on the fly. I still would
> > > like
> > > > > > > to have nodes that look sort of like (subtract (subtract 4 3) 2).
> > > > > > >
> > > > > > > Andrew
> > > > > > >
> > > > > > > On May 31, 3:53 pm, Andrew Stromme <andrew.stro...@gmail.com>
> > > wrote:
> > > > > > > > Hi there,
> > > > > > > >
> > > > > > > > A part of my parser deals with expressions matching. I'm handling
> > > > > > operator
> > > > > > > > precedence as shown onhttp://www.acooke.org/lepl/intro-4.html
> > > > > > > >
> > > > > > > > add = group3 & ~symbol('+') & group4 > Add._make
> > > > > > > > sub = group3 & ~symbol('-') & group4 > Sub._make
> > > > > > > > group4 += add | sub | group3
> > > > > > > >
> > > > > > > > Lets assume that I am trying to parse 4 - 3 - 2 to get -1. The
> > > above
> > > > > > grammar
> > > > > > > > matches expressions incorrectly because ((4 - 3) - 2) is
> > > different from
> > > > > > (4 -
> > > > > > > > (3 - 2)). The parser generates an AST that corresponds to the 2nd
> > > > > > option,
> > > > > > > > which is wrong. I could rewrite the grammar as a left-recursive
> > > > > > grammar, but
> > > > > > > > that isn't good because it's best not to memoize. Any ideas?
> > > > > > > >
> > > > > > > > Thanks,
> > > > > > > >
> > > > > > > > Andrew
> > > > > > >
> > > > > > > --
> > > > > > > You received this message because you are subscribed to the Google
> > > Groups
> > > > > > "lepl" group.
> > > > > > > To post to this group, send email to lepl@googlegroups.com.
> > > > > > > To unsubscribe from this group, send email to
> > > > > > lepl+unsubscribe@googlegroups.com.
> > > > > > > For more options, visit this group at
> > > > > > http://groups.google.com/group/lepl?hl=en.
> > > > > > >
> > > > > >
> > > > > > --
> > > > > > You received this message because you are subscribed to the Google
> > > Groups
> > > > > > "lepl" group.
> > > > > > To post to this group, send email to lepl@googlegroups.com.
> > > > > > To unsubscribe from this group, send email to
> > > > > > lepl+unsubscribe@googlegroups.com.
> > > > > > For more options, visit this group at
> > > > > > http://groups.google.com/group/lepl?hl=en.
> > > > > >
> > > > > >
> > > > >
> > > > > --
> > > > > You received this message because you are subscribed to the Google
> > > Groups "lepl" group.
> > > > > To post to this group, send email to lepl@googlegroups.com.
> > > > > To unsubscribe from this group, send email to
> > > lepl+unsubscribe@googlegroups.com.
> > > > > For more options, visit this group at
> > > http://groups.google.com/group/lepl?hl=en.
> > > > >
> > > >
> > >
> > > --
> > > You received this message because you are subscribed to the Google Groups
> > > "lepl" group.
> > > To post to this group, send email to lepl@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > lepl+unsubscribe@googlegroups.com.
> > > For more options, visit this group at
> > > http://groups.google.com/group/lepl?hl=en.
> > >
> > >
> > 
> > -- 
> > You received this message because you are subscribed to the Google Groups "lepl" group.
> > To post to this group, send email to lepl@googlegroups.com.
> > To unsubscribe from this group, send email to lepl+unsubscribe@googlegroups.com.
> > For more options, visit this group at http://groups.google.com/group/lepl?hl=en.
> > 
>
Create a group - Google Groups - Google Home - Terms of Service - Privacy Policy
Account Options
