RE2 - new regular expression library
Yesterday, Google released a new regular expression library - RE2 . The library is written in C ++.
There are two approaches to the implementation of regular expressions: non-deterministic finite automata (NFA) and deterministic finite automata (DFA). The first regular expression mechanism is used, for example, in Perl, Python, Ruby, and .NET. Unfortunately, in this case, the running time of the program can grow exponentially , and the stack usage can grow indefinitely. This behavior was unacceptable for Google projects such as Code Search, Sawzall and Bigtable, so the company's programmers wrote a library based on deterministic finite automata. RE2 guarantees linear search execution speed and limited stack usage. DFA is also used, for example, in lex and egrep. Unlike most similar implementations, RE2 supports almost all the main features of PCRE.
The library is distributed under the BSD license.
')
UPD : Removed Tcl from NFA examples, now they use DFA there.
There are two approaches to the implementation of regular expressions: non-deterministic finite automata (NFA) and deterministic finite automata (DFA). The first regular expression mechanism is used, for example, in Perl, Python, Ruby, and .NET. Unfortunately, in this case, the running time of the program can grow exponentially , and the stack usage can grow indefinitely. This behavior was unacceptable for Google projects such as Code Search, Sawzall and Bigtable, so the company's programmers wrote a library based on deterministic finite automata. RE2 guarantees linear search execution speed and limited stack usage. DFA is also used, for example, in lex and egrep. Unlike most similar implementations, RE2 supports almost all the main features of PCRE.
The library is distributed under the BSD license.
')
UPD : Removed Tcl from NFA examples, now they use DFA there.
Source: https://habr.com/ru/post/87319/
All Articles