用PackratParser在Scala中构建布尔逻辑解析器
用PackratParser在Scala中构建布尔逻辑解析器
提问于 2022-08-17 18:51:34
我正在尝试构建一个布尔逻辑解析器，例如A == B AND C == D，以输出类似于And(Equals(A,B), Equals(C,D))的内容。
我的解析器有以下定义：
def program: Parser[Operator] = {
phrase(operator)
}
def operator: PackratParser[Operator] = {
leaf | node
}
def node: PackratParser[Operator] = {
and | or
}
def leaf: PackratParser[Operator] = {
equal | greater | less
}
def and: PackratParser[Operator] = {
(operator ~ ANDT() ~ operator) ^^ {
case left ~ _ ~ right => And(left, right)}
}我希望解析器映射到program -> operator -> node -> and -> operator (left) -> leaf -> equal -> operator (right) -> leaf -> equal。这不管用。但是，如果在上面的代码中我做了更改
def operatorWithParens: PackratParser[Operator] = {
lparen ~> (operator | operatorWithParens) <~ rparen
}并将and更改为
def and: PackratParser[Operator] = {
(operatorWithParens ~ ANDT() ~ operatorWithParens) ^^ {
case left ~ _ ~ right => And(left, right)}
}解析(A == B) AND (C == D)成功。
我不明白为什么前者不起作用，而后者却起作用。我应该如何更改我的代码以便能够解析A == B AND C == D
编辑:按照@Andrey的建议，我修改了语法以说明优先级
def program: Parser[Operator] = positioned {
phrase(expr)
}
def expr: PackratParser[Operator] = positioned {
(expr ~ ORT() ~ expr1) ^^ {
case left ~ _ ~ right => Or(left, right)} | expr1
}
def expr1: PackratParser[Operator] = positioned {
(expr1 ~ ANDT() ~ expr2) ^^ {
case left ~ _ ~ right => And(left, right)} | expr2
}
def expr2: PackratParser[Operator] = positioned {
(NOTT() ~ expr2) ^^ {case _ ~ opr => Not(opr)} | expr3
}
def expr3: PackratParser[Operator] = {
lparen ~> (expr) <~ rparen | leaf
}虽然PackratParser支持左递归语法，但我遇到了一个永远不会离开expr的无限循环。
回答 1
Stack Overflow用户
发布于 2022-08-17 22:20:23
看起来有一条从operator到较短的operator的路径
operator -> node -> and -> (operator ~ somethingElse)您似乎假设较短的operator (left)将以某种方式减少到leaf，而最外层的operator将跳过leaf并选择node，无论出于什么原因。相反，它所做的只是扼杀了它遇到的第一个leaf。
你可以试着在node之前移动leaf，这样当看到某事物时，整个operator就不会被第一个A阻塞。就像A == B AND ...。
否则，我建议把它重构成
- disjunctions
- of conjunctions
- of原子公式
其中的原子公式
or
- indivisible带括号的顶级元素(在本例中为括号大小的析取).
期望使用相当多的repSep。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/73393593
复制相关文章
相似问题
腾讯云开发者
