The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Message from discussion Left and right recursion with subtraction

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Jun 23 2011, 5:03 pm
From: andrew cooke <and...@acooke.org>
Date: Thu, 23 Jun 2011 17:03:12 -0400
Local: Thurs, Jun 23 2011 5:03 pm
Subject: Re: [LEPL] Re: Left and right recursion with subtraction

i think you're confused about how this works.

> and < are not (always) binary operators.

1 < 2 < 3  is true because AS A WHOLE the sequence is true.

1 < (2 < 3)  is false because it is equivalent to  1 < True  and in such
comparisons True is taken as 1.

so the two above are not equivalent.  because  1 < 2 < 3  is not formed from
binary operations.  it's a freaky mess.  you cannot decompose  1 < 2 < 3 into
two binary operators.

andrew

On Thu, Jun 23, 2011 at 04:17:49PM -0400, Andrew Stromme wrote:
> hmm, my example is inconsistent, oops. I tried some things out in the python
> interpreter, just to see how python interpreted them.

> >>> 1 > 1 < 3
> False
> >>> 1 > (1 < 3)
> False
> >>> (1 > 1) < 3
> True

> That looks to me like python is grouping from the right towards the left, I
> had assumed the other way. I will think about my problem space some more, I
> think my original issue might not exist. Thanks for your help.

> Andrew

> On Thu, Jun 23, 2011 at 3:18 PM, andrew cooke <and...@acooke.org> wrote:

> > what does 1<2 return?  true?  so what is true > 3?

> > andrew

> > On Thu, Jun 23, 2011 at 03:17:09PM -0400, Andrew Stromme wrote:
> > > What about something like

> > > 1 < 2 > 3?
> > > i.e.
> > > ((1 < 2) > 3).

> > > In c this would result in the value 0 (or false if you stuffed it into a
> > > bool). But the way my code currently works we get

> > > (1 < (2 > 3))

> > > which results in the value 1

> > > On Thu, Jun 23, 2011 at 2:53 PM, andrew cooke <and...@acooke.org> wrote:

> > > > 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

> > > > > > > (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

> > > > > > > > > > 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
> > > > > > > Groups
> > > > > > > > > > "lepl" group.
> > > > > > > > > > > To post to this group, send email to
> > > > > > > > > > > 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
> > > > > > > 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
> > > > > > > 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
> > > > 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
> > > > > > For more options, visit this group at

> > > > --
> > > > 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
> > > > For more options, visit this group at

> > > --
> > > 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
> > > For more options, visit this group at

> > --
> > 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
> > For more options, visit this group at

> --
> 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.