Python实现Prolog：解析器优先级通用实现方法问询

嗨，很高兴你已经在Python里搭起了Prolog的原型！关于带操作符优先级的解析，这里给你梳理下核心术语和通用实现思路：

首先明确几个关键概念，方便你查资料或者和其他开发者交流：

• 运算符优先级解析（Operator Precedence Parsing）：这就是你要解决的问题的通用叫法，专门处理不同优先级运算符的表达式解析，确保运算顺序符合规则。
• 结合性（Associativity）：Prolog的操作符分左结合（比如+）、右结合（比如is）、非结合（比如=）三类，这是解析时必须考虑的——比如a + b + c要解析成+(+(a,b),c)，而X is Y is 5要解析成is(X, is(Y,5))，全靠结合性控制。
• 调度场算法（Shunting-yard Algorithm）：Dijkstra提出的经典算法，专门把中缀表达式转成后缀表达式（逆波兰表示），同时完美处理优先级和结合性，是很多表达式解析器的首选方案。
• 递归下降优先级分层解析：另一种手写解析器常用的方法，为每个优先级层级写对应的解析函数，从高到低递归处理，代码结构非常直观。

因为你是预加载操作符表，不需要动态修改，所以可以先把操作符整理成包含**优先级、结合性、操作符类型（前缀/中缀/后缀）**的结构化数据，比如一个Python字典：

# 示例：key是操作符，value是(优先级, 结合性类型)
# 结合性类型对应Prolog的fx/fy/xfx/xfy/yfx/xf/yf
operators = {
    '\+': (900, 'fy'),    # 右结合前缀
    '*': (400, 'yfx'),    # 左结合中缀
    '+': (500, 'yfx'),    # 左结合中缀
    'is': (700, 'xfy'),   # 右结合中缀
    '=': (700, 'xfx'),    # 非结合中缀
    '!': (1000, 'xf')     # 非结合后缀
}

下面两种方法都可以基于这个表实现：

方法一：调度场算法 #

这个方法的核心是用两个栈（操作符栈+输出队列）把中缀表达式转成后缀表达式，再转成Prolog的AST（抽象语法树），步骤如下：

1. 词法分析：先把输入字符串拆成tokens（比如操作符、变量、常量、括号），比如X is 5 + 3 * 2拆成['X', 'is', '5', '+', '3', '*', '2']。
2. 遍历处理每个token：
   • 如果是变量/常量，直接加入输出队列；
   • 如果是左括号(，压入操作符栈；
   • 如果是右括号)，弹出栈顶操作符到输出队列，直到遇到左括号，然后弹出左括号（不加入输出）；
   • 如果是操作符O1：
     • 只要操作符栈不为空，且栈顶不是左括号，且满足以下条件之一：
       • 栈顶操作符O2的优先级高于O1；
       • O2和O1优先级相同，且O1是左结合的；
     • 就弹出O2到输出队列，重复这个过程；
     • 最后把O1压入操作符栈。
3. 收尾：遍历完所有tokens后，把操作符栈剩余的元素全部弹出到输出队列。
4. 生成AST：把后缀表达式转成Prolog风格的树形结构，比如后缀序列5,3,2,*,+,X,is会变成is(X, +(5, *(3,2)))。

要注意扩展处理Prolog的前缀/后缀操作符：比如遇到前缀操作符时（比如token流开头、前一个token是操作符/左括号），要单独处理其入栈逻辑，避免和中缀混淆。

方法二：递归下降优先级分层解析 #

这种方法更适合手写，代码结构清晰，容易调试，适合你已有静态语法解析基础的情况：

1. 按优先级分组：把操作符按优先级从高到低排序，比如最高优先级是前缀/后缀操作符、括号，然后是*，再是+，最后是is/=。
2. 为每个层级写解析函数：
   • 最高优先级：parse_factor()，处理括号、变量、常量，以及前缀/后缀操作符：

     def parse_factor():
         # 处理前缀操作符
         if current_token in prefix_ops:
             op = current_token
             next_token()
             operand = parse_factor()
             return (op, operand)
         # 处理括号
         elif current_token == '(':
             next_token()
             node = parse_expression()
             expect(')')
             return node
         # 处理变量/常量
         else:
             node = current_token
             next_token()
             # 处理后缀操作符
             while current_token in suffix_ops:
                 op = current_token
                 next_token()
                 node = (op, node)
             return node
     

   • 中间优先级：比如parse_term()处理*这类操作符（左结合）：

     def parse_term():
         node = parse_factor()
         # 左结合：每次处理完高优先级元素后，检查当前是否是本层级操作符
         while current_token in term_ops:
             op = current_token
             next_token()
             right = parse_factor()
             node = (op, node, right)
         return node
     

   • 最低优先级：parse_expression()处理is/=这类操作符（根据结合性处理）：

     def parse_expression():
         node = parse_term()
         # 右结合：递归调用自身而不是高优先级函数，实现右结合
         while current_token in expr_ops and is_right_associative(current_token):
             op = current_token
             next_token()
             right = parse_expression()
             node = (op, node, right)
         # 非结合：遇到相同优先级的操作符直接报错
         while current_token in expr_ops and is_non_associative(current_token):
             raise SyntaxError(f"Non-associative operator {current_token} cannot be chained")
         return node
     

3. 入口函数：调用最低优先级的parse_expression()即可完成整个表达式的解析。

两种方法各有优劣：

• 调度场算法更通用，适合操作符集合复杂的场景，代码可以复用；
• 递归下降分层解析更直观，和你现有的静态语法解析逻辑更容易衔接，调试起来也更方便。

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