72 lines
2.9 KiB
Markdown
72 lines
2.9 KiB
Markdown
|
|
# 适用于NGRA字符串正则的IR形式
|
|
|
|
## 两个指针
|
|
|
|
1. 活动指针，记录当前的搜索位置，下文“不更新活动指针”的意思是算计结束后自行对活动指针进行复位
|
|
2. 锚点指针，记录一个区间的开始位置
|
|
|
|
## 检查点
|
|
|
|
检查点是锚点指针的一种形式，以栈形态存储，创建检查点时，上一个检查点自动压栈，并用当前检查点替换为当前的锚点指针
|
|
|
|
## 符号区
|
|
|
|
使用DEFINE指令定义的符号定义在符号区中，符号的类型通过第一次赋值确定，源生成模式下，可以通过第一个赋值指令推导其类型
|
|
|
|
## HIR算子
|
|
|
|
1. 搜索算子（SEARCH %str; SEARCH %unicode），向后搜索确定长度序列或者满足规则的字符集，更新活动指针，不更新锚点指针，搜索结果保存在全局上下文中
|
|
2. 搜索算子（SEARCH %set_expression），向后匹配一个满足字符集要求的字符，更新活动指针，不更新锚点指针，搜索结果保存在全局上下文中
|
|
3. 条件指令（CONDITION %cmd_true %cmd_fail），比较前一条SEARCH指令是否成功，并指定跳转到指定的位置，如果某种条件不需要跳转，可以写1。如果想要将fail向上级继续抛出，可以%cmd_fail写0.
|
|
4. 计数指令（COUNT %min %max %is_greedy %cmd），重复执行指令cmd，直到满足参数配置的数量为止
|
|
5. 快速序列计数指令（COUNT_SEQ %min %max %is_greedy %seq），快速搜索一个确定性序列，直到满足参数配置的数量为止
|
|
6. 快速字符集计数指令（COUNT_SET %min %max %is_greedy %set），快速搜索一个字符集，直到满足参数配置的数量为止
|
|
7. 尝试（TRY %count），对自身向后的一段内容在新的匹配栈层级中进行运行，被分层的指令数量由COUNT指令确定
|
|
8. 弹出（POP %is_success），提前终止一个try块，并用is_success表示弹出行为视为匹配成功还是失败
|
|
9. 打包指令（PACK %is_success %name），检查上一条语句的结果，将匹配结果打包并记录为指定的名字。如果名字为空，则使用默认的序号进行索引
|
|
|
|
## 优化策略
|
|
|
|
应当注意的是，将HIT进行进一步优化或者展开的目的：
|
|
|
|
1. 尽可能降低源生成或者运行时执行中，对多指令上下文的依赖，尽可能保证每一个IR可以单独输出最佳的代码
|
|
2. 减少多余的结构，使得一行指令尽可能处理多的数据
|
|
|
|
### AST优化器
|
|
|
|
1. ALT合并
|
|
将多个ALT CASE合并到一个链表中
|
|
|
|
2. SPAN合并
|
|
将连续的CHAR CONCAT合并为一个char span
|
|
|
|
3. alt合并
|
|
将多个alt分支中的公共部分提取出来
|
|
|
|
### IR优化器
|
|
|
|
1. .*a特征，优化为
|
|
FIND_SEQ(a, last)
|
|
.*?a特征，优化为
|
|
FIND_SEQ(a, first)
|
|
|
|
2. a+特征，优化为
|
|
MATCH_SEQ(a)
|
|
COUNT_SEQ(a,0,+inf,greedy)
|
|
|
|
完成
|
|
|
|
3. a{1} -> a
|
|
|
|
完成
|
|
|
|
4. .\*a\*特征，优化为.*
|
|
|
|
完成，最优先
|
|
|
|
5. a{m,n}特征，展开为
|
|
MATCH_SEQ(aa...m个a....aa)
|
|
COUNT_SEQ(a,0,n,greedy)
|
|
|
|
完成 |