Re: [LEPL] Issues recognizing argument lists with Tokens
andrew cooke
Hi,
I can't see the answer at quick glance, but will look at this tonight.
In general, if you hit an infinite loop, it's because you're repeating
something that's empty. So my initial guess would be that when you make the
commas explicit (which I didn't fully follow, so may be misunderstanding) you
are somehow ending up with an empty match for arg.
Andrew
On Mon, Apr 18, 2011 at 09:41:25AM -0700, Tyler Laing wrote:
> Hello all,
>
> I'm working on a very terse language, and I am having some issues
> getting argument lists recognized with Tokens.
>
> I converted the args example over to Tokens because thats what I'm
> using, and now it doesn't work. I am clearly missing something.
>
> Code: http://pastebin.com/i5WTyFrx
>
> Specifically, look for arg_expr.
>
> The idea as I understand it is that we match a number of arguments,
> dropping commas as we go, until we reach the end of the string(which
> too is dropped). An argument can be a list, a tuple or an item. A list
> is made up of successive args, starting with [, ending ], and
> separated by commas, which get dropped. A tuple uses () instead. An
> item can be a string, number, none, bool, or an ident.
>
> I think the issue is the commas, which get consumed and dropped by the
> tokens earlier on, and then the arg_expr can't match because there are
> no more comma separators. If I change comma from ~symbol(',') to
> symbol(',') and put in the ~ where needed, then it seems to be stuck
> in an infinite loop on a very simple input.
>
> So how to do this right?
>
> --
> You received this message because you are subscribed to the Google Groups "lepl" group.
> To post to this group, send email to le...@googlegroups.com.
> To unsubscribe from this group, send email to lepl+uns...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/lepl?hl=en.
>
Tyler Laing
Tyler Laing
understand of the args parsing code.
A list or a tuple is a series of items separated by commas, with [] or
(). Tokens consume these commas. Matchers don't. Then the arg_expr is
a series of args separated by commas. With the code in the pastebin,
this just throws an error. If I change
comma = ~symbol(',') to just comma = symbol(',')
Then only have the commas dropped in the arg_expr, then we get an
infinite loop. It does sound like it is matching something empty. I'll
look into it deeper.
andrew cooke
Hi,
OK, nothing exciting here (no bugs, thankfully :o), just a few mistakes (not
that I am downplaying the difficulty in finding these - it's taken me nearly
an hour). Also, an important point (4 below) that might bite you later.
1 - First, there was no need for the parse_all in the test. I suspect you
added that in frustration, but it just complicates things so I removed it.
2 - There was a possibility of an empty match in ident. I don't know if this
was causing the loop you saw, but I wouldn't be surprised. You need to make
that [1:] at the end.
3 - (The main one) Eos() isn't a character, it's a conceptual thing
(basically, it matches the error you get when there's nothing left to read).
So don't put it in a symbol because that makes no sense in this context
(you're asking for a symbol that is empty, which will never succeed because
tokens aren't "used" unless they have something to match).
With those, it works for me. I can post the code, but I suspect that's all
you really need. The extra warning is
4 - It looks like you also want strings. The way you're heading your allchars
token will match huge chunks of input and break everything else (because with
tokens, longest wins). The simplest fix for that is to include the quotation
marks in your token (so it's better to have tokens, one with single and one
with double quotes, than to have a matcher just for the contents where you
handle the quotes separately).
Hope that helps!
Andrew
PS If you got the idea that Eos() is a character from something in the docs,
and you can remember where, please say because things did kind-of sort-of work
like that before Lepl 5 and I may not have fixed up the docs correctly.
Thanks.
On Mon, Apr 18, 2011 at 09:41:25AM -0700, Tyler Laing wrote:
andrew cooke
...
> marks in your token (so it's better to have tokens, one with single and one
> with double quotes, than to have a matcher just for the contents where you
> handle the quotes separately).
That should read:
so it's better to have TWO tokens, one with single and one with double quotes,
than to have a TOKEN just for the contents where you handle the quotes
separately
Sorry, Andrew
Tyler Laing
> Node and removing ~symbol(EOS()). Suddenly it all worked.
Now I'm having issues parsing a quotation mark delimited string, ie:
"hello" inside the parsed string, like 'a, b, "c"'. Any resources I
could be pointed towards?
-Tyler
andrew cooke
I just posted a reply that told you to drop the ~symbol(EOS()) and predicted
you'd have problems with the string :o) It shoud arrive in your inbox soon...
Andrew
Tyler Laing
work:
funccall = ident & ~lparens & arg_expr & ~rparens | ident & ~lparens &
~rparens > "function"
For this input string: "func2(a, b)"
It will return:
List
`- List
+- tuple
| +- 'function'
| `- 'func2'
`- tuple
+- 'function'
`- Node
+- 'a'
`- 'b'
Can you tell me why?
andrew cooke
There's a whole section of the manual on debugging. See
http://www.acooke.org/lepl/debugging.html
Apart from the issue I already mentioned with ident (did you get my emails?) I
would also add parentheses to be sure grouping was correct. See
http://www.acooke.org/lepl/faq.html#when-i-change-from-to-my-function-isn-t-called
Andrew
Tyler Laing
http://pastebin.com/Sb4BSKFJ Might help you improve Lepl and its
speed.
I've added loops, fixed the function call parsing, added function
definitions, code blocks(including an optional ; at the end of a code
block, really proud of that one). The tests do show some speed issues
going on in that the number parsing is quite slow.
-Tyler
On Apr 19, 3:40 am, andrew cooke <and...@acooke.org> wrote:
> There's a whole section of the manual on debugging. Seehttp://www.acooke.org/lepl/debugging.html
> Apart from the issue I already mentioned with ident (did you get my emails?) I
andrew cooke
Yeah, number parsing (and worse; the initial compiling) is a bit of a weak
heel at the moment. The next release of Lepl (which I hope to start in a
month or so) will be addressing that (the problem is, I think, with the
regular expression engine). You may be able to improve things by using a
simpler regexp (for example, define a token only for integers and then define
a loat in the grammar as two numbers with a symbol('.') betwene them - that
would, I suspect, be significantly faster).
But anyway, that sounds like a huge moun of progress. I don't think anyone
else has described such a complete use of Lepl. Are you considering releasing
the code? It would be good to have as a test...
Cheers,
Andrew
PS Don't hold you breath for the next release. It will include a lot of work
(ie time) and I am currently working on soemthing else that doesn't have a
clear end date yet.
Tyler Laing
bot on twitter, hence the terseness. I've successfully added loops and
if/else if/else blocks now. I'll try your number suggestion right now.
-Tyler
On Apr 19, 10:45 am, andrew cooke <and...@acooke.org> wrote:
> Yeah, number parsing (and worse; the initial compiling) is a bit of a weak
> heel at the moment. The next release of Lepl (which I hope to start in a
> month or so) will be addressing that (the problem is, I think, with the
> regular expression engine). You may be able to improve things by using a
> simpler regexp (for example, define a token only for integers and then define
> a loat in the grammar as two numbers with a symbol('.') betwene them - that
> would, I suspect, be significantly faster).
>
> But anyway, that sounds like a huge moun of progress. I don't think anyone
> else has described such a complete use of Lepl. Are you considering releasing
> the code? It would be good to have as a test...
>
> Cheers,
> Andrew
>
> PS Don't hold you breath for the next release. It will include a lot of work
> (ie time) and I am currently working on soemthing else that doesn't have a
> clear end date yet.
>
> On Tue, Apr 19, 2011 at 09:48:43AM -0700, Tyler Laing wrote:
> > I've made some significant progress. Thought I'd share what I have:
andrew cooke
I had a quick look at your code (just finished work). Neat :o)
Unless you're getting warnings about left recursion (in which case I would
*strongly* suggest rewriting to fix that) you might find that
config.no_memoize() improves performance (see
http://acooke.org/lepl/lepl5.0.html#id12)
Andrew
Tyler Laing
float_ = (Optional(symbol('-')) & int_ & symbol('.')[0:1] & int_[0:])
> (lambda x: float("%s" % ''.join(x)))
number = float_
Comparison from the old form of number: number =
Optional(symbol('-')) + value >> float
Old form:
real 0m16.288s
user 0m16.240s
sys 0m0.050s
New Form:
real 0m5.921s
user 0m5.910s
sys 0m0.010s
On:
Processor : 4x AMD Phenom(tm) II X4 925 Processor
Memory : 4056MB (1654MB used)
Operating System : Ubuntu 10.04.2 LTS
On Apr 19, 10:45 am, andrew cooke <and...@acooke.org> wrote:
> Yeah, number parsing (and worse; the initial compiling) is a bit of a weak
> heel at the moment. The next release of Lepl (which I hope to start in a
> month or so) will be addressing that (the problem is, I think, with the
> regular expression engine). You may be able to improve things by using a
> simpler regexp (for example, define a token only for integers and then define
> a loat in the grammar as two numbers with a symbol('.') betwene them - that
> would, I suspect, be significantly faster).
>
> But anyway, that sounds like a huge moun of progress. I don't think anyone
> else has described such a complete use of Lepl. Are you considering releasing
> the code? It would be good to have as a test...
>
> Cheers,
> Andrew
>
> PS Don't hold you breath for the next release. It will include a lot of work
> (ie time) and I am currently working on soemthing else that doesn't have a
> clear end date yet.
>
> On Tue, Apr 19, 2011 at 09:48:43AM -0700, Tyler Laing wrote:
> > I've made some significant progress. Thought I'd share what I have:
andrew cooke
Sorry about that :o(
It's not trivial writing fast regexps in Python itself (Lepl is actually
compiling your regexps to a state machine and executing them).
Andrew
Tyler Laing
A little more complex, but will make new users happier.
How would I rewrite the grammar to avoid left recursion?
-Tyler
andrew cooke
Do you know what's left recursing? If you post the latest version and I'll
have a look. I don't know of a simple rule, you just have to look at how
things are and jiggle it around...
Andrew
Tyler Laing
later.
I signed up to pastebin. The latest code will be at: http://pastebin.com/rGWEUtB0
I managed to expand math evaluation. I haven't found many issues with
the grammar, but give it a try and try to break it.
An informal language definition:
if: ~
else if: #
assignment: =
math: same symbols, including modulo
blocks are delimited by: {}
strings: ""
output: @<username/user_id>(object)
input: $<username/user_id>(query) - sends a direct message with the
given query and and then inserts the response into the script(paused
until the response is given)
loops: [conditional;operation] ie: [var<varB;var++]
end of line: ;
and: &
or: ? (chosen because | is usually not available on many qwerty
keyboards)
function definition: ^<name>: varA, varB,...{<block>}
function call: <name>(varA, varB,...)
to be continued on the next text: *!
I just found an issue with the if blocks and the block definition. I
wanted to make it so the last statement in a block(delimited by {})
didn't need to end with a semi-colon. However, anytime there are more
than one line in a block(for ifs), that block then disappears. Blocks
on their own work with multiple statements. They work properly in
loops. Just not in the if structure.
-Tyler
andrew cooke
Sorry, didn't phrase my previous email very well. When I said "do you know
what is left recursing?" I meant "do you know which rule in the grammar is
causing the left recursion?" - I wasn't asking if you understood the theory!
Anyway, looking at the grammar, one place it's happening is with expr. For
example, one of the things that expr can be is cond. And of the things that
cond can be is eq_expr, and one of the things that can be is "expr & ~EQ ...".
So, when the system tries to match an expr it can follow that series of
definitions and do a loop without matching any data. That is left recursion -
it's a problem because the loop can continue forever. So Lepl can try to
match expr, leading to cond, leading to eq_expr, leading to expr, leading to
cond, ....
The way to avoid this is to do what I did in the example you started with. If
you look there (still in your code) you have
parens += ~symbol('(') & group3 ...
group1 += ... parens
group2 += ... group1
group3 += ... group2
see how, even though things loop, they are arranged so that there *must* be at
least a "(" in each loop? That blocks the chance of spinning in one place.
Lepl will detect this and stop the spinnning for you, but it's relatively
slow. That's why I suggest rewriting this.
Does that make sense?
What I sould try doing is making a difference between expr on the left and
right of an operator. So you have lexpr and rexpr. And then only recurse
with rexpr. Also, I think you need to add ( and ) in somewhere? Basically,
copy the example you started with (as you are already doing), but in more
detail. Once you get the idea it's not so hard, but it will mean rewriting
quite a lot of rules.
Cheers,
Andrew
Tyler Laing
cleaned up the text a bit, laid it out better for readability. I
decided to remove tuples, and only have parens in functions,
conditionals, and math evaluations, because those are all unambiguous.
I also made the test case results easier to read and see if they're
working.
Can you see if you can "break" the grammar?
-Tyler
> > > Do you know what's left recursing? �If you post the latest version and I'll
> > > have a look. �I don't know of a simple rule, you just have to look at how
>
> read more »
andrew cooke
I think my advice about left recursion wasn't very good, sorry, and I think
your fix is possibly broken. For example, what if you want a function
evaluation on the left of a comparison?
Here is what I think would be better (but I have not actually run it - it's
only to give the idea):
group2 = Delayed()
group3 = Delayed()
group4 = Delayed()
parens = ~symbol('(') & group4 & ~symbol(')')
group1 = parens | item | funccall
mul_ = group1 & ~symbol('*') & group2 > Mul
div_ = group1 & ~symbol('/') & group2 > Div
group2 += mul_ | div_ | group1
add_ = group2 & ~symbol('+') & group3 > Add
sub_ = group2 & ~symbol('-') & group3 > Sub
group3 += add_ | sub_ | group2
group4 += Or(
group3,
group3 & ~symbol('&') & group4 > AND,
group3 & ~symbol('?') & group4 > OR,
group3 & ~GT & group4 > GreaterThan,
group3 & ~GE & group4 > GreaterEqual,
group3 & ~LT & group4 > LessThan,
group3 & ~LE & group4 > LessEqual,
group3 & ~EQ & group4 > Eq,
group3 & ~NEQ & group4 > NEq
)
And then replace group3 by group4 in list_tuple_item etc. Also NOTE CHANGE in
"parens" from group3 to group4.
Also, "?" for "or" seems odd?!
(But this is really impressive).
I don't have a good way to break things systematically (I just stared at your
code until something started to worry me and then found the possible problem
with functions above). What I tried to do with my regexp code was write
separate program that generated random regexps, and then check that, say, 1000
of them passed. You could do the same here, but it would be a fair amount
more code...
Cheers,
Andrew
On Wed, Apr 20, 2011 at 11:00:02AM -0700, Tyler Laing wrote:
> I've now updated it to remove the left recursion issues. I also
> cleaned up the text a bit, laid it out better for readability. I
> decided to remove tuples, and only have parens in functions,
> conditionals, and math evaluations, because those are all unambiguous.
> I also made the test case results easier to read and see if they're
> working.
>
> Can you see if you can "break" the grammar?
>
> -Tyler
>
> On Apr 20, 2:35�ｿｽam, andrew cooke <and...@acooke.org> wrote:
> > Sorry, didn't phrase my previous email very well. �ｿｽWhen I said "do you know
> > what is left recursing?" I meant "do you know which rule in the grammar is
> > causing the left recursion?" - I wasn't asking if you understood the theory!
> >
> > Anyway, looking at the grammar, one place it's happening is with expr. �ｿｽFor
> > example, one of the things that expr can be is cond. �ｿｽAnd of the things that
> > cond can be is eq_expr, and one of the things that can be is "expr & ~EQ ...".
> >
> > So, when the system tries to match an expr it can follow that series of
> > definitions and do a loop without matching any data. �ｿｽThat is left recursion -
> > it's a problem because the loop can continue forever. �ｿｽSo Lepl can try to
> > match expr, leading to cond, leading to eq_expr, leading to expr, leading to
> > cond, ....
> >
> > The way to avoid this is to do what I did in the example you started with. �ｿｽIf
> > you look there (still in your code) you have
> >
> > �ｿｽ parens += ~symbol('(') & group3 ...
> > �ｿｽ group1 += ... parens
> > �ｿｽ group2 += ... group1
> > �ｿｽ group3 += ... group2
> >
> > see how, even though things loop, they are arranged so that there *must* be at
> > least a "(" in each loop? �ｿｽThat blocks the chance of spinning in one place.
> >
> > Lepl will detect this and stop the spinnning for you, but it's relatively
> > slow. �ｿｽThat's why I suggest rewriting this.
> >
> > Does that make sense?
> >
> > What I sould try doing is making a difference between expr on the left and
> > right of an operator. �ｿｽSo you have lexpr and rexpr. �ｿｽAnd then only recurse
> > with rexpr. �ｿｽAlso, I think you need to add ( and ) in somewhere? �ｿｽBasically,
> > copy the example you started with (as you are already doing), but in more
> > detail. �ｿｽOnce you get the idea it's not so hard, but it will mean rewriting
> > > On Apr 19, 2:34�ｿｽpm, andrew cooke <and...@acooke.org> wrote:
> > > > Do you know what's left recursing? �ｿｽIf you post the latest version and I'll
> > > > have a look. �ｿｽI don't know of a simple rule, you just have to look at how
> > read more �ｿｽ
andrew cooke
Crap. Ignore all/some of that. You do have funccall down in group1 so it
could be on the left.
Sorry. Andrew
Tyler Laing
How do I traverse my generated abstract syntax tree for processing?
-Tyler
> > > > Sorry, didn't phrase my previous email very well. �When I said "do you know
> > > > causing the left recursion?" - I wasn't asking if you understood the theory!
>
> > > > example, one of the things that expr can be is cond. �And of the things that
>
> > > > So, when the system tries to match an expr it can follow that series of
> > > > it's a problem because the loop can continue forever. �So Lepl can try to
> > > > cond, ....
>
>
> > > > � group1 += ... parens
> > > > � group2 += ... group1
> > > > � group3 += ... group2
> > > > see how, even though things loop, they are arranged so that there *must* be at
> > > > Lepl will detect this and stop the spinnning for you, but it's relatively
> > > > Does that make sense?
>
> > > > What I sould try doing is making a difference between expr on the left and
> > > > with rexpr. �Also, I think you need to add ( and ) in somewhere? �Basically,
> > > > > > Do you know what's left recursing? �If you post the latest version and I'll
> > > > > > have a look. �I don't know of a simple rule, you just have to look at how
>
> > > > > > > > > > > I've added loops, fixed the function call parsing, added function
> > > > > > > > > > > definitions, code blocks(including an optional ; at the end of a code
> > > > > > > > > > > block, really proud
>
>
> read more »
andrew cooke
There are some simple tools in
http://code.google.com/p/lepl/source/browse/src/lepl/support/list.py -
particularly sexpr_fold.
Also, since List extends list, you can just write your own Python code.
Finally, you can subclass List to put code there (like with the operator
example). This is probably what you want - make the "if" node evaluate the
condition and call the correect leaf, etc.
Andrew
> > > > On Apr 20, 2:35�am, andrew cooke <and...@acooke.org> wrote:
> > > > > Sorry, didn't phrase my previous email very well. �When I said "do you know
> > > > > what is left recursing?" I meant "do you know which rule in the grammar is
> > > > > causing the left recursion?" - I wasn't asking if you understood the theory!
> >
> > > > > Anyway, looking at the grammar, one place it's happening is with expr. �For
> > > > > example, one of the things that expr can be is cond. �And of the things that
> > > > > cond can be is eq_expr, and one of the things that can be is "expr & ~EQ ...".
> >
> > > > > So, when the system tries to match an expr it can follow that series of
> > > > > definitions and do a loop without matching any data. �That is left recursion -
> > > > > it's a problem because the loop can continue forever. �So Lepl can try to
> > > > > match expr, leading to cond, leading to eq_expr, leading to expr, leading to
> > > > > cond, ....
> >
> > > > > The way to avoid this is to do what I did in the example you started with. �If
> > > > > you look there (still in your code) you have
> >
> > > > > � parens += ~symbol('(') & group3 ...
> > > > > � group1 += ... parens
> > > > > � group2 += ... group1
> > > > > � group3 += ... group2
> >
> > > > > see how, even though things loop, they are arranged so that there *must* be at
> > > > > least a "(" in each loop? �That blocks the chance of spinning in one place.
> >
> > > > > Lepl will detect this and stop the spinnning for you, but it's relatively
> > > > > slow. �That's why I suggest rewriting this.
> >
> > > > > Does that make sense?
> >
> > > > > What I sould try doing is making a difference between expr on the left and
> > > > > right of an operator. �So you have lexpr and rexpr. �And then only recurse
> > > > > with rexpr. �Also, I think you need to add ( and ) in somewhere? �Basically,
> > > > > copy the example you started with (as you are already doing), but in more
> > > > > detail. �Once you get the idea it's not so hard, but it will mean rewriting
> > > > > > On Apr 19, 2:34�pm, andrew cooke <and...@acooke.org> wrote:
> > > > > > > Do you know what's left recursing? �If you post the latest version and I'll
> > > > > > > have a look. �I don't know of a simple rule, you just have to look at how
> > read more �
andrew cooke
>
> There are some simple tools in
> http://code.google.com/p/lepl/source/browse/src/lepl/support/list.py -
> particularly sexpr_fold.
>
> Also, since List extends list, you can just write your own Python code.
>
> Finally, you can subclass List to put code there (like with the operator
> example). This is probably what you want - make the "if" node evaluate the
> condition and call the correect leaf, etc.
I don't know if you've ever written an interpreter before, but the simplest
approach is to have every node in the AST have an execute(namespace) method.
That takes a namespace and returns (result, namespace). The namespace binds
names to values (at it's simplest, with global variables, just a dict).
Each node's execute() does the work for that node. So Add would call the two
sub-nodes and then calculate and return the sum. While a binding node would
extend the namespace with the appropriate variable name and value. The
hardest part is getting variable scopes working correctly - you need to have
namespaces that nest, etc.
Andrew