### Abstract

Given a regular expression R and a string Q, the regular expression parsing problem is to determine if Q matches R and if so, determine how it matches, e.g., by a mapping of the characters of Q to the characters in R. Regular expression parsing makes finding matches of a regular expression even more useful by allowing us to directly extract subpatterns of the match, e.g., for extracting IP-addresses from internet traffic analysis or extracting subparts of genomes from genetic data bases. We present a new general techniques for efficiently converting a large class of algorithms that determine if a string Q matches regular expression R into algorithms that can construct a corresponding mapping. As a consequence, we obtain the first efficient linear space solutions for regular expression parsing.

Original language | English |
---|---|

Title of host publication | Proceedings of 44th International Symposium on Mathematical Foundations of Computer Science |

Editors | Joost-Pieter Katoen, Pinar Heggernes, Peter Rossmanith |

Number of pages | 14 |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Publication date | 1 Aug 2019 |

Article number | 71 |

ISBN (Electronic) | 9783959771177 |

DOIs | |

Publication status | Published - 1 Aug 2019 |

Event | 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019 - Aachen, Germany Duration: 26 Aug 2019 → 30 Aug 2019 |

### Conference

Conference | 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019 |
---|---|

Country | Germany |

City | Aachen |

Period | 26/08/2019 → 30/08/2019 |

Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 138 |

ISSN | 1868-8969 |

### Keywords

- Algorithms
- Finite automata
- Regular expression parsing
- Regular expressions

## Cite this

*Proceedings of 44th International Symposium on Mathematical Foundations of Computer Science*[71] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs, Vol.. 138 https://doi.org/10.4230/LIPIcs.MFCS.2019.71