符号字符串逻辑表达式的 AST 抽象

1. 括号 ()
• 最高优先级
• 用于改变默认的运算顺序
• 可以嵌套使用

2. 非（NOT）
• 一元运算符
• 对操作数取反
• 符号表示：¬, !, NOT, ~

3. 与（AND）
• 二元运算符
• 所有操作数为真时结果为真
• 符号表示：∧, &&, AND, ·

4. 或（OR）
• 二元运算符
• 任一操作数为真时结果为真
• 符号表示：∨, ||, OR, +

文法规则

文法规则是一组用于描述特定语言结构的规则。它们定义了如何将语言中的不同元素组合在一起形成有效的语句或表达式。可以将文法规则想象成语言的“骨架”，它决定了句子如何被构建。

• EXPR := TERM { 'or' TERM }: 一个 EXPR (表达式) 由一个 TERM (项) 开始，后面可以跟零个或多个由 "or" 连接的 TERM。 这表示 "or" 运算具有最低的优先级。{} 表示大括号内的内容可以重复零次或多次。

• TERM := FACTOR { 'and' FACTOR }: 一个 TERM (项) 由一个 FACTOR (因子) 开始，后面可以跟零个或多个由 "and" 连接的 FACTOR。这表示 "and" 运算的优先级高于 "or"。

• FACTOR := 'not' FACTOR | VARIABLE | '(' EXPR ')': 一个 FACTOR (因子) 可以是 "not" 后跟一个 FACTOR，或者是一个 VARIABLE (变量)，或者是一个由括号包围的 EXPR。这表示 "not" 运算具有最高的优先级，而括号可以用来改变运算顺序。

• VARIABLE := 字母开头的标识符: 一个 VARIABLE (变量) 是一个以字母开头的标识符（这里简化了，实际上标识符的规则更复杂）。

递归下降解析器

递归下降解析器是一种自顶向下的解析器，它通过为文法规则中的每个非终结符 (non-terminal) 编写一个函数来实现解析。这些函数相互递归调用，以匹配输入字符串中的结构，就像文法规则所描述的那样。

• 特点:
• 易于理解和实现: 递归下降解析器的结构通常与文法规则非常相似，因此相对容易理解和实现。
• 递归性质: 解析过程是递归的，因为函数会相互调用来解析子结构。
• 自顶向下: 解析从文法的起始符号（在本例中是 EXPR）开始，然后逐步向下解析到更小的组成部分。

当前代码如何实现递归下降？

• 与文法规则的对应关系:
• parse_expression 对应文法规则 EXPR := TERM { 'or' TERM }
• parse_term 对应文法规则 TERM := FACTOR { 'and' FACTOR }
• parse_factor 对应文法规则 FACTOR := 'not' FACTOR | VARIABLE | '(' EXPR ')'

• 递归调用: 这些函数根据文法规则相互递归调用。例如：
• parse_expression 调用 parse_term 来解析 "or" 运算符两侧的项。
• parse_term 调用 parse_factor 来解析 "and" 运算符两侧的因子。
• parse_factor 在遇到括号时会调用 parse_expression 来解析括号内的表达式，形成递归。

• 自顶向下解析: 解析从 parse 函数开始，它调用 parse_expression，然后 parse_expression 调用 parse_term，parse_term 调用 parse_factor，形成自顶向下的解析过程。

• 处理优先级和结合性: 通过函数的调用顺序和循环结构，解析器隐式地处理了运算符的优先级和结合性。例如，parse_expression 在循环中处理 "or"，而 parse_term 在循环中处理 "and"，这确保了 "and" 的优先级高于 "or"。

• 构建 AST: 在递归调用的过程中，每个函数都构建 AST 的一部分，并将部分结果返回给调用它的函数。最终，parse 函数返回完整的 AST。

所以，有无已有的第三库实现？🧐

ast 标准库

1. mode="eval"：指定解析模式为"eval"：
• 输入的字符串将被解析为一个可求值的表达式
• 与其他模式相比（如"exec"用于执行语句，"single"用于交互式输入），"eval"模式专门用于处理单个表达式

2. 返回值：返回一个ast.Expression对象，这个对象包含了表达式的语法树结构，可以通过.body属性访问具体的语法树节点

• 一个BoolOp节点（表示布尔运算）

• 运算符And

• 两个Name节点（分别代表A和B）

lark

Lark 是一个用于 Python 的现代解析库，专注于易用性、性能和模块化设计。它能够解析任何上下文无关文法（Context-Free Grammar），并且提供了多种解析算法供选择，包括 Earley、 LALR(1) 和 CYK。 lark 能够根据文法自动构建解析树（Parse Tree），无需额外的构建代码。

1. 最顶层是 expr，处理 or 运算

2. 中间层是 term，处理 and 运算

3. 底层是 factor，处理 not 运算、括号和变量

1. 当解析器遇到语法规则中定义的模式时，会调用对应的方法

2. 每个方法接收一个 children 参数，包含该规则的所有子节点

3. 方法返回一个简化的表示形式，通常是元组

1. variable 方法处理 A 和 B，返回它们的值

2. and_expr 方法处理 A && B，返回 ("and", "A", "B")

3. not_factor 方法处理整个表达式，返回 ("not", ("and", "A", "B"))

基于 AST 的逻辑表达式取反

1. 基本情况 - 变量: 如果遇到一个变量（字符串），函数会在它前面加上 "not" 来表示取反，并返回结果。

2. 操作符处理: 如果遇到一个操作符（元组），函数会根据操作符的类型进行不同的处理：
• "not": 如果是 "not" 操作符，函数会直接返回被取反的子表达式，相当于去除了一层 "not"。
• "and" 和 "or": 如果是 "and" 或 "or" 操作符，函数会应用德摩根定律。函数会将当前的 "and" 或 "or" 操作符替换成对应的 "or" 或 "and"，然后递归地对两个子表达式进行取反操作。

PHP 逻辑表达式抽象为符号逻辑表达式

• 识别逻辑运算符：&&, ||, !, (, )

• 处理复杂的 PHP 表达式，包括：
• 函数调用：function_name($param)
• 变量访问：$variable
• 对象属性访问：$obj->property
• 数组访问：array[index]
• 比较表达式：===, !==, ==, !=, >=, <=
• 能处理嵌套的括号结构

总结