2009/1/18 Chris Double <chris.dou...@double.co.nz>: > On Sun, Jan 18, 2009 at 11:33 AM, Paul Moore <p.f.mo...@gmail.com> wrote: >> I wrote the following parser in factor: >> >> EBNF: omega >> omega = 'O' 'm' 'e' 'g' 'a' | . omega >> ;EBNF > > I can't test your code since I've only got access to a Windows machine > and Factor doesn't run under Windows for me. When I'm next on a Linux > machine I'll try it out.
Odd, since I'm running on Windows myself. I just downloaded the latest Windows x86 build and ran factor.exe no problem. > This won't make a difference to your example but you can use the > string "Omega" instead of each character individually: Thanks, that's easier. > You can use peg.search to find things as well: > > "...string containing bible text..." <EBNF rule= "Omega" EBNF> search > > This actually converts the query to something like: > > <EBNF rule=("Omega" | .) repeat0 EBNF> Hmm, that took a couple of minutes then crashed factor! > Does the lua peg VM handle left recursive rules? My Factor peg > solution does that uses the algorithm outlined by vpri which does make > Factor's peg's not-quite-peg and has different performance > characteristics. Lua uses a bytecode interpreter (described in http://www.inf.puc-rio.br/%7Eroberto/docs/peg.pdf and http://www.inf.puc-rio.br/%7Eroberto/docs/ry08-4.pdf). Compilation of PEGs into bytecodes includes a number of optimisations, one of which (relevant here) is tail call elimination. But I'm not sure I see the relevance of left recursion - the grammar omega = "Omega" | . omega isn't left recursive, surely? For what it's worth, lpeg compiles the above into the bytecode 00: call -> 2 01: jmp -> 12 02: char 'O'-> 9 03: choice -> 9 (1) 04: char 'm'-> FAIL 05: char 'e'-> FAIL 06: char 'g'-> FAIL 07: char 'a'-> FAIL 08: commit -> 11 09: any * 1-> FAIL 10: jmp -> 2 11: ret 12: end and runs it in 0.14 seconds against the 4,445,260 byte file, finding a result at position 4281708. >> As a side note, there doesn't seem to be much documentation of the peg >> modules (or I'm not finding it somehow). Most of what I've found out, >> I got from reading some of the articles on Chris Double's website. Is >> there anything else I can look at on the subject? I tried reading the >> source, but my head exploded :-) > > I haven't documented it as it's not complete. I wrote it as an > experiment with the syntax and functionality likely to change as I > explore different directions. Not documenting it is a warning that > this is the case. Someone then moved it from extra to basis which has > encouraged usage of it. No problem - although I'd say that usage would increase because it's an extremely useful module :-) Thanks for the comments, Paul. ------------------------------------------------------------------------------ This SF.net email is sponsored by: SourcForge Community SourceForge wants to tell your story. http://p.sf.net/sfu/sf-spreadtheword _______________________________________________ Factor-talk mailing list Factor-talk@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/factor-talk