GNU bug report logs - #62483
echo a | grep -E -w '((()|a)|())*' # does not terminate

Previous Next

Full log

Message #44 received at 62483 <at> debbugs.gnu.org (full text, mbox):

From: Carlo Arenas <carenas <at> gmail.com>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 62483 <at> debbugs.gnu.org, dimitry <at> andric.com, arnold <at> skeeve.com,
 koen <at> chalmers.se
Subject: Re: bug#62483: echo a | grep -E -w '((()|a)|())*' # does not terminate
Date: Sun, 2 Apr 2023 13:23:54 -0700

On Sun, Apr 2, 2023 at 11:30 AM Paul Eggert <eggert <at> cs.ucla.edu> wrote:
>
> Also, GNU grep -w passes the following more-complicated regexp to dfaparse:

but AFAIK `-w` is not necessary to trigger it, as the following also
infloops in Fedora Rawhide

  $ echo a | grep -E '((()|a)|())+'

interestingly; the loop is broken if any character is added to any of
the `()` branches which might mean that this is also unlikely to
happen in well formed expressions.

Carlo

PS. -P doesn't loop and neither does `echo a | grep -E '((a|())|())+'`
nor '(()|(a|()))+` nor `(()|(()|a))+'`

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.