! Aware to Perl: Are Perl regexps DFAs or NFAs? Are they POSIX compliant?

RocketAware > Perl >

Are Perl regexps DFAs or NFAs? Are they POSIX compliant?

Tips: Browse or Search all pages for efficient awareness of Perl functions, operators, and FAQs.

Home

Search Perl pages

Subjects

By activity
Professions, Sciences, Humanities, Business, ...

User Interface
Text-based, GUI, Audio, Video, Keyboards, Mouse, Images,...

Text Strings
Conversions, tests, processing, manipulation,...

Math
Integer, Floating point, Matrix, Statistics, Boolean, ...

Processing
Algorithms, Memory, Process control, Debugging, ...

Stored Data
Data storage, Integrity, Encryption, Compression, ...

Communications
Networks, protocols, Interprocess, Remote, Client Server, ...

Hard World
Timing, Calendar and Clock, Audio, Video, Printer, Controls...

File System
Management, Filtering, File & Directory access, Viewers, ...

Are Perl regexps DFAs or NFAs? Are they POSIX compliant?

While it's true that Perl's regular expressions resemble the DFAs (deterministic finite automata) of the egrep(1) program, they are in fact implemented as NFAs (non-deterministic finite automata) to allow backtracking and backreferencing. And they aren't POSIX-style either, because those guarantee worst-case behavior for all cases. (It seems that some people prefer guarantees of consistency, even when what's guaranteed is slowness.) See the book ``Mastering Regular Expressions'' (from O'Reilly) by Jeffrey Friedl for all the details you could ever hope to know on these matters (a full citation appears in the perlfaq2 manpage).

Source: Perl FAQ: Regexps
Copyright: Copyright (c) 1997 Tom Christiansen and Nathan Torkington.

Next: What's wrong with using grep or map in a void context?

Previous: What good is \G in a regular expression?

(Corrections, notes, and links courtesy of RocketAware.com)

[Overview Topics]

Up to: NUL terminated String Comparison and Search

Rapid-Links: Search | About | Comments | Submit Path: RocketAware > Perl > perlfaq6/Are_Perl_regexps_DFAs_or_NFAs_A.htm