Although a regular expression cannot recognize recursive grammars, regular expressions are involved in parsing algorithms. For instance, in LALR(1), the pattern

Although a regular expression cannot recognize recursive grammars, regular expressions are involved in parsing algorithms. For instance, in LALR(1), the pattern matching is a combination of a regex and the parsing stack. If we have a regex matcher for strings, we can use it iteratively to decimate recursive structures. For instance, suppose we have a string consisting of nested parentheses (perhaps with stuff between them). We can match all the inner-most parenthesis pairs like (foo) and () with a regular expression which matches the longest sequence between ( and ) not containing (. Having identified these, we can edit the string by removing them, and then repeat: