# IRC log for #marpa, 2014-06-25

All times shown according to UTC.

Time Nick Message
01:10 jeffreykegler joined #marpa
14:54 jeffreykegler joined #marpa
16:01 jeffreykegler joined #marpa
16:03 jeffreykegler hobbs: re http://irclog.perlgeek.de/marpa/2014-06-24#i_8922443 -- following up a bit on yesterday
16:04 jeffreykegler Marpa is linear for an ambiguous grammar if it is the "finite union" of other grammars it can parse linearly (assuming they don't share symbols, or that they use those shared symbols to mean exactly the same thing).
16:05 jeffreykegler That is, if you have a C parser and a Perl parser, and want to write a parser that can deal with either one, the combination will be linear if the two separate pieces are, so long as you take care to avoid the two confusing each others symbols.
16:07 jeffreykegler Second, Marpa is linear for ambiguities which have a finite limit.  That is, if there are exactly C different ways to parse something, Marpa can track them all in linear time.
16:09 jeffreykegler Exceptions can occur if the ambiguity involves BNF with a right recursion, because the code that makes right recursions linear won't stay linear in the face of an ambiguity.
16:12 jeffreykegler An example of an ambiguities for which Marpa is *not* linear: parsing strings of digits into sequences of numbers, where the numbers don't have to be space separated.  For example, "123" can be (1,2,3) or (12,3) or (1,23) or (123).  Things like that can go O(n**3) in the length of the string -- cubic.
16:14 jeffreykegler The number of possibilities is exponential, which makes cubic good by comparison, but perhaps more relevant is that usually cubic != practical.
17:39 Aria Indeed.
20:09 LLamaRider joined #marpa