"Regular expressions" for stack automata?

Marko =?ISO-8859-1?Q?M=E4kel=E4?= <Marko.Makela@HUT.FI>
10 Sep 1999 00:08:39 -0400

          From comp.compilers

Related articles
"Regular expressions" for stack automata? Marko.Makela@HUT.FI (Marko =?ISO-8859-1?Q?M=E4kel=E4?=) (1999-09-10)
Re: "Regular expressions" for stack automata? Marko.Makela@HUT.FI (Marko =?ISO-8859-1?Q?M=E4kel=E4?=) (1999-09-16)
Re: "Regular expressions" for stack automata? world!cfc@uunet.uu.net (Chris F Clark) (1999-09-20)
Re: "Regular expressions" for stack automata? ilya@math.ohio-state.edu (1999-09-24)
Re: "Regular expressions" for stack automata? qjackson@wave.home.com (Quinn Tyler Jackson) (1999-10-04)
| List of all articles for this month |

From: Marko =?ISO-8859-1?Q?M=E4kel=E4?= <Marko.Makela@HUT.FI>
Newsgroups: comp.compilers
Date: 10 Sep 1999 00:08:39 -0400
Organization: Compilers Central
Keywords: lex, question, theory, comment

Sometimes regular expressions do not have enough expressive power to
accomplish an intuitively clear task, such as skipping a substring
enclosed by matching parentheses. For instance, if one wants to
search for a call to function f() followed by a comma, the regular
expression


    f([^()]*),


will not match e.g. the string


    f(1 + (2 * 3)),


since the argument contains parentheses.


Now, my questions: Has this field been researched? Is there any
grep-like tool that uses stack automata instead of finite state
automata? Or would such a stack automaton require too much
backtracking to be useful?


I know that this kind of tasks can be accomplished in flex/bison
rather easily, but I'd like to have something that is faster to play
around with (just input pattern strings to the tool instead of writing
and compiling several lines of parser code). I also think that
writing such a tool could be an interesting project for undergraduate
students.


Marko
[Many implementations of REs such as GNU grep extend the REs in interesting
ways with backreferences. -John]


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.