Perl 6 - the future is here, just unevenly distributed

IRC log for #marpa, 2015-07-16

| Channels | #marpa index | Today | | Search | Google Search | Plain-Text | summary

All times shown according to UTC.

Time Nick Message
01:11 jeffreykegler joined #marpa
01:24 koo7 joined #marpa
01:48 ilbot3 joined #marpa
01:48 Topic for #marpa is now Start here: http://savage.net.au/Marpa.html - Pastebin: http://scsys.co.uk:8002/marpa - Jeffrey's Marpa site: http://jeffreykegler.github.io/Marpa-web-site/ - IRC log: http://irclog.perlgeek.de/marpa/today
03:21 ronsavage joined #marpa
06:00 ronsavage joined #marpa
06:28 CQ joined #marpa
07:51 CQ joined #marpa
07:56 lwa joined #marpa
15:45 jeffreykegler joined #marpa
17:02 RichardMichaels joined #marpa
17:05 RichardMichaels hi
17:05 jeffreykegler good morning!
17:05 RichardMichaels thank you and good morning to you as well
17:14 RichardMichaels I am writing a simple lexer. lets say you have a rule <rule1>::="teststr1" | "teststr2"  . The lexer will create two clones of the lexer state for each of the or-alternatives, the lexer state includes a call stack which is cloned, the rule for "teststr1" is added to the top of the call stack of one clone and the rule for "teststr2" is added to the top of the other. . Each clone is then executed in parallel with each
17:14 RichardMichaels character of input string. if "teststr1" comes in only the clone with that rule is kept.
17:15 jeffreykegler Interesting
17:16 jeffreykegler In essence, simulating a non-deterministic lexer using Marpa's Earley parse engine.
17:16 jeffreykegler Or do I get it wrong?
17:18 RichardMichaels basically with each or conditional branch I create a clone of the lexer and advance each clone in lockstep with each character of inpu string. When the lexer finishing running, only the clone(s) with the successful rules remains standing.
17:18 RichardMichaels Im not really sure how the lexer is classified
17:19 RichardMichaels as far as its type. It uses a call stack. The call stack is cloned every time there is a |
17:19 jeffreykegler If a lexer clones into lexers running in parallel it is said to be a NFA -- non-deterministic finite automaton.
17:19 RichardMichaels the clones are run in parallel to each other, each procesing the same byte of input at the same time
17:21 sivoais joined #marpa
17:21 RichardMichaels yes that must be what it is
17:23 jeffreykegler This is an approach is straight out of the textbooks.
17:23 RichardMichaels the call stack is used for nested rules.
17:23 jeffreykegler s/is straight/that is straight/
17:23 RichardMichaels yes
17:27 RichardMichaels A clone branching happens when an OR ( | ) is reached. When the call stack comes back down to that level, the clone continuous to run independantly from clone it was branched from, it doesnt merge back with the parent.
17:28 RichardMichaels I am sure its a textbook example and its been done before
17:31 RichardMichaels The lexing rules are Perl data structures containing anonymous subroutines
17:32 RichardMichaels any subroutine reference actually
17:33 jeffreykegler Two other approaches you might find interesting:
17:33 jeffreykegler First, any regular expression can be rewritten as BNF fairly easily -- you can transform the regex into BNF and parse with the BNF
17:34 jeffreykegler Second, any NFA can be turned into a DFA -- a Deterministic Finite Automaton ...
17:35 RichardMichaels yes
17:35 jeffreykegler that means you can accomplish the same thing without cloning, although you do have more "states" -- a more complicated FA.
17:36 jeffreykegler Dunno if either of these are at all relevant to your interests.
17:36 RichardMichaels The data structure my lexer executes very closely matches the BNF, it uses a simple translator to translate the BNF into the data structure
17:37 RichardMichaels I was only interested in simplicity, extensibility and versatility, here, rather than to win awards for performance
17:39 jeffreykegler Will this go onto CPAN?
17:40 RichardMichaels absolutely, yes
17:42 RichardMichaels Since it works by manipulating and cloning the call stack, if the language supported that I could have used the languages own call stack. Maybe you can do that in Perl with the B module, but it probably would have been more time consuming than writing my own call stack
17:43 RichardMichaels that is, if the language has call stack introspection. Doing that in perl didnt look easy
17:49 jeffreykegler joined #marpa
17:53 RichardMichaels I will put more about PLEX and a copy of the compiler on sourceforge whenever it goes back online
17:54 RichardMichaels Its a lexer, pardon me
18:31 lwa joined #marpa
18:47 ernimril joined #marpa
22:52 ronsavage joined #marpa
22:54 ronsavage RichardMichaels: Re http://irclog.perlgeek.de/m​arpa/2015-07-16#i_10906750. See also https://metacpan.org/release/Set-FA.

| Channels | #marpa index | Today | | Search | Google Search | Plain-Text | summary