Re: regular expressions
lucier wrote:
>
> Howdy all.....:-)
>
> During a chat with a linux developer, he mentioned that OS/2 (plus DOS and
> Windows) didn't support "regular expressions". From what I have been able to
> gather from reading app docs (like the EPM INF file) , *nix ported to OS/2 app
> docs and shareware descriptions, it would appear that OS/2 does indeed support
> regular expressions.
>
> 1) What is the definition of "regular expressions"? (A url to grab a tutorial
> would also be great)
>
> 2) Are there any great differences between the way(s) that Linux supports
> (integrates???) regular expressions and the way OS/2 does?
>
> 3) A couple of messages I ran across on DejaNews seemed to imply that REXX
> supports regular expressions. Would this be an integrated function of REXX or
> just indicative that a person could 'roll their own" with REXX?
>
> Any thoughts on the above would be appreciated.........:-)
Whirlwind lecture follows (feel free to correct me, I lost my textbook):
In computer science, regular expressions are at the heart of formal languages.
Languages can be described by grammars, regular expressions, or recognizers.
Each is equivalent to the other two: if you have a regular expression, you can
construct a grammar or recognizer, etc.
Grammar: a set of rules for generating a string. Eg: if you have an A, you can
replace it with AA.
Regular expression: Eg: A* the `*' is a Kleine star and means you may have zero
or one or more of the preceding regular expressions (in this case A).
Recognizer: this would be a machine (ie, software) that takes any string and
returns a yes or no answer to the question "is this string a member of the
language of all strings of As?"
In each of the three above cases, the language used is the language of all
strings with only As: A, AA, AAA, AAAA... Having three ways to describe that
language is useful.
With study you learn that languages can be grouped into classes depending on
their "power." For instance, simple languages can be recognized by simpler
machines than more complex languages. Regular languages are of course easier to
deal with than non-regular languages.
You can transform common problems into languages, and vice versa. Since they
fall into language classes, that is how we say one problem is "harder" than
another: it requires a fundamentally more powerful machine to solve (recognize)
it. For instance, you can solve more problems with two stacks than with one, but
having two tapes gives you no more power than one.
This notion has been formalized as the language sets NP-HARD and NP-COMPLETE,
and P. We theorize that P=NP but have yet to prove or disprove it. These are
just statements about the theoretical maximum "hardness" of problems. We also
theorize that tape (Turing) machines are the most powerful, and can recognize
the hardest languages to recognize (I forget which... context-sensitive?).
Anyways, the important point is that when you use a regular expression in grep,
it transforms it into a little machine (code) that it runs on every line to see
whether that line is in the "language" of strings you are searching for.
Hope I haven't confused anybody.
--
SEGV It is now safe to uninstall Windows:
http://www.cgocable.net/~mlepage/ http://www.debian.org/
--
To UNSUBSCRIBE, email to debian-user-request@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org
Reply to: