基于lookahead-TDFA的词法分析器生成器RE 2C的实现与应用研究

软件影响6（2020）100027原始软件出版物RE 2C：一个基于lookahead-TDFA的词法分析器生成器乌利亚·特罗菲莫维奇不隶属于某个组织A R T I C L E I N F O保留字：词法分析正则表达式有限自动机A B标准RE2C是一个正则表达式编译器：它将正则表达式转换为有限状态机，并将其编码为目标语言的程序。RE 2C的核心是lookahead-TDFA算法，它允许它执行快速和轻量级子匹配提取。本文介绍了RE2C中使用的算法，并给出了一个TDFA构造实例代码元数据当前代码版本2.0用于此代码版本的代码/存储库的永久链接https://github.com/SoftwareImpacts/SIMPAC-2020-29可复制胶囊的永久链接https://codeocean.com/capsule/6014695/tree/v1法律代码许可证公共领域使用Git的代码版本控制系统使用C++、Bison、RE2C（自托管）的软件代码语言、工具和服务编译要求，操作环境依赖OS：Linux，BSD，Nix/Guix，GNU Hurd，OS X，Windows等支持：C++编译器、Bash、CMake或Autotools。 可选Bison和Docutils。链接到开发人员文档/手册https://re2c.org问题支持电子邮件re2c-general@lists.sourceforge.net1. 介绍正则表达式引擎可以分为两类：运行时库和词法分析器生成器。运行时库执行正则表达式的解释或实时编译。它们使用各种各样的算法，从递归回溯到自动机、字符串搜索，或者以上的某种组合。 另一方面，词法分析器生成器执行提前编译。它们使用基于确定性有限自动机（DFA）的算法，并花费大量时间进行编译和优化，以生成更好的代码。因此，lexer生成器通常不支持无法在vanilla DFA上实现的功能。其中一个特性是子匹配提取--能够找到正则表达式的各个部分与输入字符串的各个部分之间的对应关系。子匹配提取是解析问题的一个特例：除了解决识别问题外，它还必须找到输入字符串的派生 在正则表达式定义的语法与完全解析不同，子匹配提取仅需要部分推导。因此，执行完整的解析是浪费的，具有与子匹配细化成比例的开销。对于像RE2C [1，2]这样的优化词法生成器，重要的是生成的代码至少与手写代码一样快和内存效率，并且如果不使用子匹配提取，则开销为零2. Tagged DFA上述要求严格限制了子匹配提取算法：它应该是一个基于DFA的单通道算法，在恒定内存中工作，与输入长度无关。这种算法是由VilleLaurikari发明的[3]。 它的工作原理如下。 首先，将正则表达式转换为具有标记转换的非确定性有限自动机（TNFA）。标记是子匹配标记，可以放在正则表达式中的任何位置;例如，本文中的代码（和数据）已由Code Ocean认证为可复制：（https://codeocean.com/）。更多关于生殖器的信息徽章倡议可在https://www.elsevier.com/physical-sciences-and-engineering/computer-science/journals上查阅。电子邮件地址：skvadrik@gmail.com。https://doi.org/10.1016/j.simpa.2020.100027接收日期：2020年7月28日;接收日期：2020年7月29日;接受日期：2020年8月4日2665-9638/©2020作者。由Elsevier B. V.发布，这是CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表软件影响杂志 首页：www.journals.elsevier.com/software-impacts联合特罗菲莫维奇软件影响6（2020）1000272Fig. 1. Lookahead-正则���表达式���1（���2���）的TDFA构造，���带有匹配字符串......的标记���1和���2���������������������������（标记1标记s和s之间的边界，标记2标记最后一个）���。上图：TNFA（省略���闪烁���标记，阴性标记表示不匹配）。中间：lookahead-TDFA正在构造中，具有状态集、寄存器矩阵和前视标记（���是当前位置，而numb是不匹配）。左下角：施工后的lookahead-TDFA。右下角：优化后的lookahead-TDFA（编号寄存器的数量被最小化并且一些寄存器操作被移除）。捕获组可以用一对用于左括号和右括号的标记来表示。TNFA本质上是一个非确定性有限状态转换器，它将符号串重写为标记串。Laurikari算法最重要的部分是TNFA确定。 它的基本原理与将NFA转换为DFA的幂集构造相同：在所有可能的输入字符串上模拟NFA，在每一步都维护一组状态。如果当前状态集是新的，则它成为新的DFA状态，否则它被映射到现有的DFA状态。在Laurikari算法中，状态集用标签信息扩充：每个TNFA子状态具有存储标签值的寄存器的相关联的向量，使得整个状态集是由TNFA状态和标签索引的矩阵。需要寄存器，因为不同的TNFA路径到达不同的子状态，并且沿着一条路径的标签可能与沿着另一条路径的标签不一致。 路径，其值存储到新的寄存器中。扩充状态集不能以与普通DFA状态相同的方式映射，因为一对状态集可能具有相同的TNFA子状态，但具有不同的寄存器。关键的见解是，如果它们的寄存器之间存在双射，则这种状态集的映射仍然是可能的：双射变换可以以TDFA转换上的寄存器重新排序操作的形式编码。在确定之后，TDFA状态集中的所有信息都被擦除，并且所得到的TDFA就像普通的DFA一样，扩展了固定数量的寄存器和对转换的操作，这些操作更新和重新排序存储在寄存器中的标签值。像最小化这样的算法也适用于TDFA，但它们需要区分不同寄存器操作的转换。3. 前瞻TDFA对Laurikari算法的一个改进是使用先行符号[4]，该改进允许大大减少寄存器操作的数量。这个想法是延迟寄存器操作的应用，直到知道先行符号，并将操作附加到该符号上的输出转换，而不是之前的输入转换。洞察是，已经达到当前TDFA状态的TNFA路径中的一些在应用先行符号之后被取消，并且与这些路径相关联的所有寄存器操作也可以被取消。换句话说，延迟一个步骤允许对先行符号进行分割寄存器操作，而不是执行所有操作，只执行相关部分。这需要对底层TDFA状态集进行修改：除了寄存器之外，每个子状态还需要有一个相关的前瞻标签列表。附加信息在确定之后被擦除，并且所得到的总的来说，这个想法类似于LALR解析器对LR解析器的改进：在状态中使用前瞻信息大大减少了冲突的数量（对于TDFA，冲突不是错误，但它意味着额外的寄存器和寄存器操作）。 一个lookahead-TDFA结构的例子可以在图中看到。1.一、4. 模糊度解算使解析比识别更难的挑战之一是歧义：可能有几种方法来解析输入字符串。 选择哪种方式通常由消歧策略定义联合特罗菲莫维奇软件影响6（2020）1000273TDFA算法可以在不同的策略上参数化;例如，RE 2C支持Perl最左贪婪策略和POSIX最长匹配策略[5]。 消歧发生在确定时（在闭包构造中），并且所得到的TDFA在运行时不执行任何消歧：歧义解决决策嵌入到其结构中。5. 影响RE2C是需要快速词法分析器的项目的首选词法分析器生成器。它有一个灵活的用户界面，允许一个自定义 生成的代码用于特定的环境和输入模型。快速和轻量级的子匹配提取是另一个使RE2C成为其他lexer生成器的良好替代品的特性。使用RE2C的主要项目如下：• Ninja，专注于速度的构建系统。 [6] Ninja被用于大量的开源项目，它是许多操作系统和平台的必要构建块• PHP，一种流行的通用脚本语言。[七]《中国日报》• BRL-CAD是一个构造性立体几何实体造型计算机辅助设计系统。[八]《中国日报》• STEPCode是ISO 10303标准的一种实现。[9]第一章• Apache SpamAssassin，一个垃圾邮件过滤程序。[10个国家]• Yasm，Modular Assembler Project。[第十一届]• Wake，SiFive构建工具。[12个]RE 2C有一个许可证，允许它在prori- etary软件中使用。该项目已被移植到许多操作系统;根据Repology [13]，它被打包在60多个发行版中。除了是一个有用的实用工具外，RE2C还是自动机和形式语言领域新算法开发的研究场所。6. 结论和今后的工作在RE2C中实现的子匹配提取算法既是一个重要的理论发展，也是一个有用的实用改进。它允许一个程序的词法分析器能够子匹配提取，而不诉诸手动后处理或使用字符串搜索功能。子匹配提取的开销与子匹配细化成比例：如果不需要子匹配信息，则开销为零，即使对于大型子匹配重正则表达式（如符合RFC的URI和HTTP解析器），开销也是适度的（与DFA上的简单识别相比，大约为1.25倍[4]）。未来的工作可能会将TDFA与其他解析自动机（如DSST [14]和sta-DFA [15]）联系起来，并研究使用标记计数器自动机进行计数重复的可能性[16]。信用作者身份贡献Ulya Trofimovich：概念化，软件，验证，形式化分析，写作-原始草稿。竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作致谢我想感谢我的父母弗拉基米尔和叶琳娜，我的朋友和研究员同事安吉洛·博尔索蒂，我的学校数学老师塔季扬娜·莱奥尼多夫娜和德米安·弗拉基米罗维奇，最重要的是谢尔盖。引用[1]RE2C，一个面向C、C++和Go的词法生成器。网址：https://re2c.org，源代码：https://github.com/skvadrik/re2c。[2]作者：Peter Bumbulis，Donald D. Cowan，RE2C：一个更通用的扫描仪生成器，ACMLett。嗯。浪系统（LOPLAS）2（1-4）（1993）70[3]Ville Laurikari，具有标记转换的NFA，它们到确定性自动机的转换和对正则表达式的应用，在：第七届字符串处理和信息检索国际研讨会论文集，2000年。SPIRE 2000，pp. 181http://laurikari.net/ville/spire2000-tnfa.pdf[4]Ulya Trofimovich，标记确定性有限自动机与前瞻，2017年，cs。[5]Angelo Borsotti，Ulya Trofimovich，NFA上的高效POSIX子匹配提取，预印本，2019，URL：https://re2c.org/2019_borsotti_trofimovich_efficient_posix_submatch_extraction_on_nfa.pdf。[6]Ninja 构 建 系 统 ， URL ： https://ninja-build.org ， 使 用 RE2C 构 建 文 件 ：https://ninja-build.org/build.ninja.html。[7]PHPInternalsBook，chapterBuildingPHP，URL：http://www.phpinternalsbook. com/php7/build_system/building_php.html。[8]BRL-CAD：工具，URL：http://sourceforge.net/p/brlcad/code/HEAD/tree/brlcad/trunk/misc/tools/re2c。[9]STEPCode：Build Process，URL：https://stepcode.github.io/docs/build_process.[10] SpamAssassin（sa-compile），网址：https://spamassassin.apache.org/full/3.2.x/doc/sa-compile.html。[11] Yasm，URL：https://yasm.tortall.net.[12] Wake，URL：https://github.com/sifive/wake.[13] 回复：RE2C。 网址：https://repology.org/project/re2c/information。[14] Niels Bjørn Bugge Grathwohl ， Parsing with Regular Expressions& ExtensionstoKleene Algebra，DIKU，哥本哈根大学，2015年。[15] Mohammad Imran Chowdhury，StaDFA：一种有效的子表达式匹配方法（硕士论文），佛罗里达州立大学，2018年。[16] Michela Becchi，高效正则表达式求值的数据结构、算法和架构，圣路易斯华盛顿大学工程与应用科学学院，2009年。