一阶逻辑公式的解析算法

Question

我正在尝试编写一阶(谓词)逻辑将公式转换为抽象语法树的算法。对于命题逻辑，我使用了分流码算法，但是对于一阶逻辑，它并不是开箱即用的，因为括号可以用于对谓词(或函数)的范围进行分组或指定范围。是否有一个通用的调车场算法，可以处理这一特殊的复杂？

作为参考，我试图解析的字符串如下所示：

"AxEy(P(x) & R(x,y)) -> R(f(a),b)"

Answer 1

开括号是谓词作用域或函数参数列表分隔符，当且仅当它紧跟在谓词或函数之后。如果用于分组，则必须紧跟前缀或infix运算符或另一个开括号。

如果不能预先识别函数名，这并不重要，只要它们必须有名称；名称后面的括号要么是谓词作用域，要么是参数列表分隔符。当然，能够识别谓词是有帮助的。

当您将括号推到堆栈上时，需要标记它，以便在以后弹出与其对应的关闭括号时，可以创建正确的AST节点。如果是谓词作用域石斑鱼或参数列表石斑鱼，则需要将谓词/函数作为AST的一部分；它就在堆栈上的开括号下面。