使用递归实现正则匹配
💡
原文中文，约5800字，阅读约需14分钟。
📝
内容提要
本文介绍了使用递归实现正则匹配的方法，以Rob Pike的简洁而优雅的正则匹配函数为例，讲解了递归函数和指针的强大魅力。文章详细介绍了正则表达式的背景和原理，并给出了Rob实现的简化版正则匹配程序的核心代码。还提到了贪心匹配算法和其他语法的改进方法。附上了主函数代码供读者测试使用。
🎯
关键要点
- 本文介绍了使用递归实现正则匹配的方法，以Rob Pike的正则匹配函数为例。
- 优雅的代码通常简洁、清晰易懂，且具有通用性。
- 正则表达式由Stephen Kleene在1950年代发明，Ken Thompson在UNIX中实现了正则匹配功能。
- Rob Pike实现的简化版正则匹配程序代码仅有30行，支持基本的正则语法子集。
- 核心代码包括match、matchhere和matchstar三个函数，分别处理匹配逻辑、递归匹配和星号匹配。
- match函数根据正则表达式的开头是否有^进行分流，遍历文本进行匹配。
- matchhere函数是递归函数，处理正则单元的匹配，返回匹配结果。
- matchstar函数处理*的匹配逻辑，允许前面的字符出现零次或多次。
- Rob的实现是非贪心匹配，建议改为贪心匹配以匹配更长的内容。
- 建议初学者实现+、?和\.语法，及使用新的数据结构处理复杂的正则表达式。
- C语言的指针操作高效，Rob的实现展示了递归和指针的魅力。
➡️
