论文标题
Glushkov的功能性换能器的构造
Glushkov's construction for functional subsequential transducers
论文作者
论文摘要
Glushkov的结构具有许多有趣的属性，并且在应用于传感器时变得更加明显。本文努力展示该算法可能的扩展和优化范围。引入了正则表达式的特殊风味，可以有效地转换为$ε$ - 无功能加权有限状态传感器。产生的自动机非常紧凑，因为它们仅包含一个原始表达式的每个符号（来自输入字母）的状态，而对于每个符号范围的范围都只有一个过渡，无论多大。这种压缩的过渡范围允许在自动机评估期间有效地进行二进制搜索查找。此处介绍的所有方法和算法均用于实现多核传感器正则表达式的开源编译器。
Glushkov's construction has many interesting properties and they become even more evident when applied to transducers. This article strives to show the wast range of possible extensions and optimisations for this algorithm. Special flavour of regular expressions is introduced, which can be efficiently converted to $ε$-free functional subsequential weighted finite state transducers. Produced automata are very compact, as they contain only one state for each symbol (from input alphabet) of original expression and only one transition for each range of symbols, no matter how large. Such compactified ranges of transitions allow for efficient binary search lookup during automaton evaluation. All the methods and algorithms presented here were used to implement open-source compiler of regular expressions for multitape transducers.
