help-gnu-emacs
[Top][All Lists]
Advanced

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

Re: multiline regex mode?


From: Harald Hanche-Olsen
Subject: Re: multiline regex mode?
Date: Sat, 25 Nov 2006 15:11:14 +0100
User-agent: Gnus/5.11 (Gnus v5.11) Emacs/23.0.0 (berkeley-unix)

+ Peter Dyballa <address@hidden>:

| I think you can't use one regular expression for a variety of nested
| "*balanced* brackets like { { } }".

You think rightly.  In formal language theory, the regular languages
are precisely the ones that can be defined by regular grammars.  It is
a theorem that they are precisely the languages that can be recognized
by a finite state automaton (FSA).  A regular expression is a way of
specifying a regular grammar, i.e., a regular language, and so they
are not powerful enough to recognize balanced parentheses.  The reason
is that you need to be able to count arbitrarily high, in order to be
able to tell the difference between expressions like
{{{{{{{{{{{{{{{{}}}}}}}}}}}}}}}} and {{{{{{{{{{{{{{{{}}}}}}}}}}}}}}}}}.
A FSA with fifteen states cannot tell the difference between the two
expressions above, since it would need to be able to count to sixteen
in order to do so.

So the paren mathcing algorithms in emacs need to be written in code.
And indeed it is:  At the bottom you'll find the function scan-sexps,
which is written in C (for efficiency, no doubt).

See also:

  http://en.wikipedia.org/wiki/Regular_grammar

-- 
* Harald Hanche-Olsen     <URL:http://www.math.ntnu.no/~hanche/>
- It is undesirable to believe a proposition
  when there is no ground whatsoever for supposing it is true.
  -- Bertrand Russell


reply via email to

[Prev in Thread] Current Thread [Next in Thread]