算法解析一阶逻辑公式 [英] Algorithm for parsing first order logic formulas
问题描述
我试图写一个算法，将在第一级（predicate）逻辑公式，以抽象语法树。对于命题逻辑，我用的调度场算法，但它不开箱的一阶逻辑，因为括号可以用来无论是在分组或指定的predicates（或功能）的范围。有没有在调度场算法的推广，可以用这个特殊的并发症处理？
有关的参考，我试图解析看起来像这样的字符串：
AxEy（P（x）及R（X，Y）） - ＆GT; R（F（A），B）
这是开括号是predicate范围或功能参数列表分隔符，当且仅当它紧跟一个predicate或功能，分别。如果是用于分组，它必须遵循preFIX或缀运算符或其他开括号。
这其实并不重要，如果你不能先验确定函数名，只要他们必须有名称;在名字括号要么是predicate范围或参数列表分隔符。这将是有帮助的，以便能够识别当然predicates，
您需要的时候你推入堆栈，以纪念括号，以便您可以创建正确的AST节点时以后，其对应的右括号弹出它。如果它是一个predicate范围石斑鱼或参数列表石斑鱼，你需要包括predicate /函数作为AST的一部分;这将是正下方堆栈上的开括号。
I am trying to write an algorithm for converting formulas in first order (predicate) logic to abstract syntax trees. For propositional logic, I used the shunting-yard algorithm, but it does not work out of the box for first order logic since parenthesis may be used either in grouping or specifying the scope of predicates (or functions). Is there a generalization of the shunting-yard algorithm that can deal with this particular complication?
For reference, the strings I'm trying to parse look something like this:
"AxEy(P(x) & R(x,y)) -> R(f(a),b)"
An open parenthesis is a predicate scope or function argument list delimiter if and only if it immediately follows a predicate or function, respectively. If it is used for grouping, it must following a prefix or infix operator or another open parenthesis.
It doesn't really matter if you can't a priori identify function names, as long as they must have names; a parenthesis following a name is either a predicate scope or an argument list delimiter. It would be helpful to be able to identify predicates, of course.
You need to mark the parenthesis when you push it onto the stack so that you can create the correct AST node when you later pop it with its corresponding close parenthesis. If it's a predicate scope grouper or an argument list grouper, you need to include the predicate/function as part of the AST; it will be just underneath the open parenthesis on the stack.
这篇关于算法解析一阶逻辑公式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
