[CWB] [ cwb-Bugs-1492044 ] <s> * </s> gets stuck in infinite loop

[SourceForge.net]

Bugs item #1492044, was opened at 2006-05-20 11:49
Message generated for change (Settings changed) made by andrewhardie
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=722303&aid=1492044&group_id=131809

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: CQP engine
>Group: TODO-3.5
Status: Open
Resolution: None
Priority: 7
Private: No
Submitted By: Stefan Evert (schtepf)
Assigned to: Stefan Evert (schtepf)
Summary: <s> * </s> gets stuck in infinite loop

Initial Comment:
The (meaningless) query "<s> * </s>" (which seems quite
natural to try for people who access CQP through a Web
interface and don't know its query language) gets
caught in an infinite loop, i.e. CQP runs forever with
full CPU power.



----------------------------------------------------------------------

Comment By: Stefan Evert (schtepf)
Date: 2006-08-30 12:31

Message:
Logged In: YES 
user_id=545257

This is especially a problem for Web interfaces, which
should try to catch queries of this type until the problem
is fixed.



----------------------------------------------------------------------

Comment By: Stefan Evert (schtepf)
Date: 2006-08-30 11:00

Message:
Logged In: YES 
user_id=545257

This is especially a problem for Web interfaces, which
should try to catch queries of this type until the problem
is fixed.



----------------------------------------------------------------------

Comment By: Stefan Evert (schtepf)
Date: 2006-05-20 12:17

Message:
Logged In: YES 
user_id=545257

What happens is that in the FSA constructed from the query,
<s> is a transition that does not "consume" a token, so <s>*
(Kleene star over <s>) effectively generates an eps-loop at
the start state of the FSA.  Normally, such errors are
caught because the start state is also a final state (the
query "<s> *" would result in such an error message), but in
this case, the additional constraint </s> (which can never
be satisfied) inserts another transition.

There should probably some test for eps-loops in the FSA
simulation, which can never do anything useful (unless I'm
mistaken).

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=722303&aid=1492044&group_id=131809