如何编写可生成易转Clojure代码AST的Instaparse解析器？

给定示例表达式："~a{b=1}&(a{b=1}|a{b=1})|a{b=1}|a{b=1}"，我用Instaparse写了如下解析器：

((insta/parser
  "
S = (group | exp)+
group = '~'? <'('> exp+ <')'> op?
exp = '~'? path <'='> (v | r) <'}'> op?
path = (p <'{'>)* p
op = '|' | '&'
<p> = #[a-z]
v = #[a-z0-9]
r = <'\\''> #[^\\']* <'\\''>
"
)
 "~a{b=1}&(a{b=1}|a{b=1})|a{b=1}|a{b=1}")

运行后得到的AST如下：

[:S
 [:exp "~" [:path "a" "b"] [:v "1"] [:op "&"]]
 [:group
  [:exp [:path "a" "b"] [:v "1"] [:op "|"]]
  [:exp [:path "a" "b"] [:v "1"] [:op "|"]]
  [:exp [:path "a" "b"] [:v "1"]]
  [:op "|"]]
 [:exp [:path "a" "b"] [:v "1"]]]

但这个结构很难转换成Clojure表达式，我需要生成更接近以下嵌套结构的AST：

[:S
 [:op "|"
  [:op "&"
   [:exp "~" [:path "a" "b"] [:v "1"]]
   [:group
    [:op "|"
     [:exp [:path "a" "b"] [:v "1"]]
     [:op "|"
      [:exp [:path "a" "b"] [:v "1"]]
      [:exp [:path "a" "b"] [:v "1"]]]]]]
  [:exp [:path "a" "b"] [:v "1"]]]]

这种嵌套结构方便用insta/transform转换成Clojure代码。请问怎么编写能解析这类结构、生成该类型AST的通用解析器？

要生成嵌套式AST，核心是利用Instaparse支持的运算符优先级与结合性规则，按层级递归解析表达式，而非将运算符作为元素后缀。具体实现如下：

1. 定义运算符规则 #

先明确逻辑：&优先级高于|，且两者均为左结合（符合常规逻辑运算习惯）。

2. 重构解析器语法 #

按表达式优先级从高到低拆分语法规则，构建递归解析结构：

((insta/parser
  "
S = expr
expr = or_expr
or_expr = and_expr ( <'|'> and_expr )* :op('|')
and_expr = primary ( <'&'> primary )* :op('&')
primary = negated_exp | group | exp
negated_exp = <'~'> primary :negate
group = <'('> expr <')'>
exp = path <'='> (v | r) <'}'>
path = (p <'{'>)* p
<p> = #[a-z]
v = #[a-z0-9]
r = <'\\''> #[^\\']* <'\\''>
"
)
 "~a{b=1}&(a{b=1}|a{b=1})|a{b=1}|a{b=1}")

语法规则说明： #

• S作为入口，指向最顶层表达式expr
• or_expr处理|运算：由多个and_expr通过|连接，通过( <'|'> and_expr )* :op('|')直接生成带:op标签的嵌套结构
• and_expr处理&运算：逻辑同or_expr，保证&优先级更高
• primary是原子表达式集合：包含取反表达式、括号组、普通属性表达式，优先级最高
• negated_exp处理~前缀的取反操作
• group处理括号包裹的子表达式，递归指向expr，确保括号内逻辑优先解析

3. 生成的目标AST #

运行上述解析器，会生成与你预期结构一致的嵌套AST：

[:S
 [:op "|"
  [:op "&"
   [:negate [:exp [:path "a" "b"] [:v "1"]]]
   [:group
    [:op "|"
     [:exp [:path "a" "b"] [:v "1"]]
     [:exp [:path "a" "b"] [:v "1"]]]]]
  [:exp [:path "a" "b"] [:v "1"]]
  [:exp [:path "a" "b"] [:v "1"]]]]

该结构可直接通过insta/transform转换为Clojure代码，比如将:op "|"映射为clojure.core/or，:op "&"映射为clojure.core/and，:negate映射为取反逻辑。

内容的提问来源于stack exchange，提问作者user3139545