Sökning: id:"swepub:oai:DiVA.org:umu-192864" >
Formalising and imp...
Formalising and implementing Boost POSIX regular expression matching
-
- Berglund, Martin, 1981- (författare)
- Department of Information Science and Centre for AI Research, University of Stellenbosch, Matieland, South Africa
-
- Bester, Willem (författare)
- Division of Computer Science, University of Stellenbosch, Matieland, South Africa
-
- van der Merwe, Brink (författare)
- Division of Computer Science, University of Stellenbosch, Matieland, South Africa
-
(creator_code:org_t)
- Elsevier, 2021
- 2021
- Engelska.
-
Ingår i: Theoretical Computer Science. - : Elsevier. - 0304-3975 .- 1879-2294. ; 857, s. 147-165
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- Whereas Perl-compatible regular expression matchers typically exhibit some variation of leftmost-greedy semantics, those conforming to the posix standard are prescribed leftmost-longest semantics. However, the posix standard leaves some room for interpretation, and Fowler and Kuklewicz have done experimental work to confirm differences between various posix matchers. The Boost library has an interesting take on the posix standard, where it maximises the leftmost match not with respect to subexpressions of the regular expression pattern, but rather, with respect to capturing groups. In our work, we provide the first formalisation of Boost semantics, analyze the complexity of regular expression matching when using Boost semantics, and provide efficient algorithms for both online and multipass matching.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Regular expression matching
- Posix
- Boost
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas