Regular Expressions with Lookahead

被引：10

作者：

Berglund, Martin ^{[1
]}

van Der Merwe, Brink ^{[2
]}

van Litsenborgh, Steyn ^{[2
]}

机构：

[1] Stellenbosch Univ, Dept Informat Sci, Stellenbosch, South Africa

[2] Stellenbosch Univ, Comp Sci Div, Stellenbosch, South Africa

来源：

JOURNAL OF UNIVERSAL COMPUTER SCIENCE | 2021年 / 27卷 / 04期

关键词：

Regular expressions; Lookahead expressions; Boolean automata;

D O I：

10.3897/jucs.66330

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

This paper investigates regular expressions which in addition to the standard operators of union, concatenation, and Kleene star, have lookaheads. We show how to translate regular expressions with lookaheads (REwLA) to equivalent Boolean automata having at most 3 states more than the length of the REwLA. We also investigate the state complexity when translating REwLA to equivalent deterministic finite automata (DFA).

引用

页码：324 / 340

页数：17

共 23 条

[1] Formalising Boost POSIX Regular Expression Matching [J].

Berglund, Martin ;

Bester, Willem ;

van der Merwe, Brink .

THEORETICAL ASPECTS OF COMPUTING - ICTAC 2018, 2018, 11187 :99-115

[2]

Bojanczyk M, 2014, LECT NOTES COMPUT SC, V8573, P26

[3]

BRZOZOWSKI JA, 1980, THEOR COMPUT SCI, V10, P19, DOI 10.1016/0304-3975(80)90069-9

[4] ALTERNATION [J].

CHANDRA, AK ;

KOZEN, DC ;

STOCKMEYER, LJ .

JOURNAL OF THE ACM, 1981, 28 (01) :114-133

[5] Linear Parsing Expression Grammars [J].

Chida, Nariyoshi ;

Kuramitsu, Kimio .

LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS (LATA 2017), 2017, 10168 :275-286

[6]

Cox Russ, 2010, Regular Expression Matching in the Wild

[7]

DAntoni L., 2015, LIB SYMB AUT

[8] Why Aren't Regular Expressions a Lingua Franca? An Empirical Study on the Re-use and Portability of Regular Expressions [J].

Davis, James C. ;

Michael, Louis G. ;

Coghlan, Christy A. ;

Servant, Francisco ;

Lee, Dongyoon .

ESEC/FSE'2019: PROCEEDINGS OF THE 2019 27TH ACM JOINT MEETING ON EUROPEAN SOFTWARE ENGINEERING CONFERENCE AND SYMPOSIUM ON THE FOUNDATIONS OF SOFTWARE ENGINEERING, 2019, :443-454

[9] Rethinking Regex Engines to Address ReDoS [J].

Davis, James C. .

ESEC/FSE'2019: PROCEEDINGS OF THE 2019 27TH ACM JOINT MEETING ON EUROPEAN SOFTWARE ENGINEERING CONFERENCE AND SYMPOSIUM ON THE FOUNDATIONS OF SOFTWARE ENGINEERING, 2019, :1256-1258

[10] The Impact of Regular Expression Denial of Service (ReDoS) in Practice: An Empirical Study at the Ecosystem Scale [J].

Davis, James C. ;

Coghlan, Christy A. ;

Servant, Francisco ;

Lee, Dongyoon .

ESEC/FSE'18: PROCEEDINGS OF THE 2018 26TH ACM JOINT MEETING ON EUROPEAN SOFTWARE ENGINEERING CONFERENCE AND SYMPOSIUM ON THE FOUNDATIONS OF SOFTWARE ENGINEERING, 2018, :246-256

← 1 2 3 →