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/20140624#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 