三元运算符(ternary)解析
把 ...?...:... 处理成if_else(...,...,...) 的形式.
初衷是用正则替换把对应DSL的operator转换成python语言, 然后用python的ast 直接解析. 但是三元运算符的处理比较复杂, Python 中并没有直接对应的语法结构, 导致没法简单的替换.
可以把字符串token解析成AST 的构建过程理解成“对运算符按优先级排序”的过程.
| 方法 | 优缺点 | 类比排序思路 | 平均复杂度 |
|---|---|---|---|
| 用正则表达式替换三元运算符 | 思路naive, 但是可读性差，难以维护 | O(n logn)+kO(n) 全字符串扫描+递归 |
|
| 设计语法树解析器（Parser） | 灵活性高, 但实现较复杂 | 选择排序 | O(n logn) 近似二分递归 |
| 结合 Pratt Parser 优化解析 | 代码简洁, 可读性高, 扩展性好 | 插入排序/堆排序 | O(n) 线性扫描 |
直接用字符串替换
- 用字符串正则查找tenary并替换
- 递归处理?: 和括号, =, 逗号的关系
- 处理 括号, 逗号 都依赖栈来正确处理嵌套结构
写parser处理
可以通过编写自定义的解析器来处理三元运算符。下面是一些处理流程：
- 定义:
- 定义 AST 节点：设计不同类型的节点来表示表达式，如常量、变量、运算符等。
- Tokenize：将源代码字符串分割成 tokens（例如：数字、运算符、字符串等）。
- 例如: ``a<0.2?
→[(“NAME”,”a”) (“OP”,”<”) (“NUMBER”,”0.2”) (“QMARK”,”?”)]`
- 例如: ``a<0.2?
- 定义优先级: 找表达式中最低的优先级处理.
- 具体流程:
- 预处理（字符串替换/注释/关键字替换）
- 把wq expr 中的
'...'/"..."用占位符替换ts_sum(group_zscore(a<0.2? (a+0.7):(a>0.9? a:0.9),bucket(rank(cap),range='0.1, 1, 0.1')),5) -> ts_sum(group_zscore(a<0.2? (a+0.7):(a>0.9? a:0.9),bucket(rank(cap),range=__STR_CONST_0__)),5)
- 做若干文本替换（or/and/not → logical_or/logical_and/…、–→+、NaN→nan 等）。
- 删除注释（/* … */ 与行注释 // 或 #）。
- 按分号 ; 切分成多条语句，逐条 tokenize() → parse_expr() → to_python()。
- token 化
- 自顶向下递归解析（赋值 → 三元→ 二元按最低 precedence 为根 → 原子/函数/一元）
- 把wq expr 中的
- 解析每句代码:
- 顶层赋值检测
- 去掉最外层的分号
- 检查最外层(用括号记录层数)的赋值
=, 把赋值语句的左右两侧分开.
- 三元检测
- 检查最外层 ? 的第一个位置作为三元入口, 再从
?后扫描并找到对应的最外层:（depth=0）的位置 - 每当遇到括号要剥去括号重新检测三元
- 检查最外层 ? 的第一个位置作为三元入口, 再从
- 二元检测(binop)
- 检查最外层优先级最低的op. 优先级相同, 取最右边的op拆分(左结合)
- 一元检测(atom):
- 检查 一元运算符(!, -) -> 单token原子(number, string, name) -> function call -> 检查每个参数
- 顶层赋值检测
- 构建 AST
- 递归生成 Python 代码: 对不同节点分别处理
- 还原字符串并输出
- 每条语句生成的 Python 片段再还原字符串常量占位符.
- 收集所有处理过的语句并最终用 \n 拼接返回
- 预处理（字符串替换/注释/关键字替换）
- ⚠️ 注意点: ast解析一定要注意代码的覆盖率. 保证不会出现不认识的token, operator, 分支情况.
parse优化
token优化
把预处理步骤内化到token中统一处理.
pratt优化
Pratt parser 其实是 自顶向下递归下降解析器的一种优化方式: 不是从最低优先级的字符开始, 而是随着解析从左往右动态的构建ast.
- 每个token除了优先级外, 定义两个方法: (nud和led)
- nud(null denotation, 前序) 当token出现在表达式开头时
- led(left denotation, 中序) 当 token 出现在 表达式中间（左边有东西）时调用
下面是一个DSL对应的token行为表格.
| Token/操作符 | 进入 nud / led | 触发条件 | 动作描述 |
|---|---|---|---|
| NUMBER | nud | token 类型是 "NUMBER" |
- 若全是数字 → Const(int)- 否则 → Const(float) |
| STRING | nud | token 类型是 "STRING" |
构造 Const(str)，去掉引号 |
| NAME(变量) | nud | token 类型是 "NAME"且 peek不是 ( |
返回 Name |
| NAME (调用) | nud | token 类型是 "NAME" 且 peek=(函数调用 |
- 消费 ( → 解析参数列表- 参数支持关键字： key = value- 遇到 , 继续，否则结束- 消费 ) → 返回 Call(Name, args) |
| LPAREN | nud | 当前 token = (3 |
- 进入子表达式解析（rbp=-1000）- 必须遇到 ) 结束- 返回子树 |
| + / - (unary) | nud | token=OP 且值为 +/-，在前缀位置 |
以 get_prec("U+/-") 为 rbp 递归解析右操作数 → UnaryOp |
| ! (unary not) | nud | token=OP 且值为 ! |
以 get_prec("!") 为 rbp 递归解析右操作数 → UnaryOp("!", expr) |
| QMARK (?) | led | peek = QMARK 且 TERNARY_PREC > rbp |
- 消费 ?- 解析 true_part ( rbp=TERNARY_PREC)- 期望 :- 解析 false_part ( rbp=TERNARY_PREC)- 构造 Ternary(left, true, false) |
| 二元运算符 (如 + - * / ^ < > == != &&) |
led | peek 发现下一个 token 是操作符 (OP)，并且该操作符的优先级 lbp > rbp 1 2 |
- 消费当前操作符（op） - 结合性处理： 如果操作符是左结合（默认情况），则 next_rbp = lbp； 如果操作符是右结合（如 =、^），则 next_rbp = lbp - 0.0001（轻微调整优先级, 为了遇到相同的运算符时继续解析） - 递归调用 parse_expression(next_rbp) 来解析右操作数（right） - 生成 BinOp(left, op, right) 节点 |
| LPAREN (函数调用) |
led | peek = (3 支持更一般化的函数调用. 比如, (a+b)(x)、foo()(x) 这种高阶调用 |
- 消费 ( → 解析参数列表- 参数使用 parse_expression(rbp=-1000)- , 分隔，直到遇到 )- 构造 Call(left, args) |
表格解释 $\downarrow$ :
lbp（left binding precedence, 左操作数绑定优先级, 当前op的优先级）,rbp(右操作符绑定优先级, 上一个op的优先级)- 当下一个op优先级更高时, ast会不断加深. 当下一个op优先级不足时, ast会从底向上直到找到合适的位置添加
- 比如 a = b = c, 在第二个等号处, 把第一个等号的优先级稍稍降低, 保证右侧的优先级更高. 解析为 a = (b = c)
- 括号总是最优先的, 直接把rdp降到最低
a + b x c -d:
a = b = c:
