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

Reply via email to