如何用Python Lex-Yacc为查询字符串添加括号以体现运算优先级？

我是Lex-Yacc新手，现有一个用于解析字符串查询的Python Lex-Yacc解析器，当前设置的优先级规则如下：

self.precedence = (
            ('left', 'AND', 'OR', 'NOT'),
        )

self.parser = yacc.yacc(module=self, debug=debug, write_tables=debug)

该规则可正常工作，但我希望添加步骤，让查询语句按照优先级规则自动添加括号。例如将：

query1 = expression OR expression AND expression OR expression  
query2 = expression OR expression AND ( expression OR expression )  

转换为：

query1 = expression OR ( expression AND expression ) OR expression 
query2 = expression OR ( expression AND ( expression OR expression ))

请问该如何实现这一需求？

1. 修正优先级规则 #

首先调整优先级顺序，符合常规逻辑：NOT优先级最高，其次是AND，OR优先级最低，同时设置正确的结合性（NOT为右结合，AND/OR为左结合）。错误的优先级会导致解析顺序不符合预期，后续加括号也会出错。

self.precedence = (
    ('right', 'NOT'),   # 单目运算符，右结合
    ('left', 'AND'),    # 优先级高于OR
    ('left', 'OR'),     # 优先级最低
)

2. 定义语法规则与括号生成逻辑 #

每个语法规则的动作函数返回**(生成的字符串片段, 表达式优先级)**的元组，通过辅助函数判断是否需要给子表达式添加括号。

辅助函数：判断是否添加括号

根据子表达式的优先级和类型，决定是否包裹括号：

def _maybe_parenthesize(self, sub_expr, current_precedence):
    sub_str, sub_prec = sub_expr
    # 基础表达式或带括号的表达式，直接返回原字符串（无需额外括号）
    if sub_prec == 4:
        return sub_str
    # 复合表达式：子优先级高于当前时，加括号明确运算顺序
    if sub_prec > current_precedence:
        return f"( {sub_str} )"
    # 右结合的NOT：同优先级子表达式需要加括号（如NOT NOT a → NOT (NOT a)）
    elif sub_prec == current_precedence and current_precedence == 3:
        return f"( {sub_str} )"
    # 左结合的AND/OR：同优先级无需加括号（如a AND b AND c）
    return sub_str

语法规则实现

每个规则对应不同的表达式类型，生成带括号的字符串：

# OR表达式：优先级1
def p_expr_or(self, p):
    'expr : expr OR expr'
    left = self._maybe_parenthesize(p[1], 1)
    right = self._maybe_parenthesize(p[3], 1)
    p[0] = (f"{left} OR {right}", 1)

# AND表达式：优先级2
def p_expr_and(self, p):
    'expr : expr AND expr'
    left = self._maybe_parenthesize(p[1], 2)
    right = self._maybe_parenthesize(p[3], 2)
    p[0] = (f"{left} AND {right}", 2)

# NOT表达式：优先级3
def p_expr_not(self, p):
    'expr : NOT expr'
    sub = self._maybe_parenthesize(p[2], 3)
    p[0] = (f"NOT {sub}", 3)

# 带括号的表达式：优先级4（最高，无需额外括号）
def p_expr_group(self, p):
    'expr : LPAREN expr RPAREN'
    p[0] = (f"( {p[2][0]} )", 4)

# 基础表达式：优先级4（如你例子中的"expression"，实际可替换为标识符等）
def p_expr_basic(self, p):
    'expr : EXPRESSION'
    p[0] = (p[1], 4)

# 错误处理
def p_error(self, p):
    print(f"Syntax error at {p.value if p else 'end of input'}")

3. 词法分析器补充 #

确保所有需要的Token被正确识别（示例匹配你给出的expression，实际可根据需求修改）：

def t_AND(self, t):
    r'AND'
    return t

def t_OR(self, t):
    r'OR'
    return t

def t_NOT(self, t):
    r'NOT'
    return t

def t_LPAREN(self, t):
    r'\('
    return t

def t_RPAREN(self, t):
    r'\)'
    return t

def t_EXPRESSION(self, t):
    r'expression'
    return t

# 忽略空格与制表符
t_ignore = ' \t'

4. 使用示例 #

解析查询语句后，取返回元组的第一个元素即可得到带括号的结果：

# 假设你的解析器类名为QueryParser
parser = QueryParser(debug=False)
# 解析query1
result1 = parser.parser.parse("expression OR expression AND expression OR expression")
print(result1[0])  # 输出：expression OR ( expression AND expression ) OR expression
# 解析query2
result2 = parser.parser.parse("expression OR expression AND ( expression OR expression )")
print(result2[0])  # 输出：expression OR ( expression AND ( expression OR expression ))

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