lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On Sun, Apr 23, 2017 at 9:06 AM, Martin <> wrote:
>> Yes, AFAIK it's impossible to match ".*%b()" in linear time. That
>> message was regarding FSA to match "%b()".

So I was wrong. It's possible to match ".*%b()" in linear time.
It is almost equivalent of matching "()". Thank you for showing it!

You can match this particular _expression_ in linear time going from right to left, because the language of the reverse string ("^%b().*$") is a LR(1) language. 

Here's another problem:


This won't match if the number of b's is larger than the sum of the numbers of a's and c's. And "%bab" matches "a-+abb", for instance, whereas "a*" won't match any letters except 'a'.

So of course there's an ad-hoc linear time algorithm to match this, but the point is: can we come up with a matching algorithm that writes that ad-hoc algorithm automatically, i.e. can we solve the general case?