Scala PackratParsers는 필요한만큼 역 추적하지 않습니까?

Question

나는 논리식의 간단한 파서에 대한 다음 코드를했다 : 그 루트 파서 전체를 구문 분석을 시도

[1.4] failure: string matching regex `\z' expected but `&' found 

!a & !b 
^

와

import scala.util.parsing.combinator.RegexParsers 
import scala.util.parsing.combinator.PackratParsers 


object Parsers extends RegexParsers with PackratParsers 

// Entities definition 
sealed trait LogicalUnit 
case class Variable(name: String) extends LogicalUnit 
case class Not(arg: LogicalUnit) extends LogicalUnit 
case class And(arg1: LogicalUnit, arg2: LogicalUnit) extends LogicalUnit 


import Parsers._ 

// In order of descending priority 
lazy val pattern: PackratParser[LogicalUnit] = 
    ((variable) | (not) | (and)) 

lazy val variable: PackratParser[Variable] = 
    "[a-zA-Z]".r ^^ { n => Variable(n) } 

lazy val not: PackratParser[Not] = 
    ("!" ~> pattern) ^^ { x => Not(x) } 

lazy val and: PackratParser[And] = 
    ((pattern <~ "&") ~ pattern) ^^ { case a ~ b => And(a, b) } 


// Execution 
println(Parsers.parseAll(pattern, "!a & !b")) 

그래서, 문자열 !a & !b을 구문 분석을 시도하고 실패를 보인다 문자열을 pattern -> not -> variable으로 지정하고 !a이 아직 끝나지 않았다고 판단되면 다시 추적하지 않으므로 pattern -> and은 시도조차하지 않았습니다. PackratParsers을 사용하면 문제를 해결할 수 있다고 생각했지만 그렇지 않았습니다.

일부 문제는 무엇이 잘못 되었습니까?

Answer 1

일단 내가 성공적으로 뭔가를 수락하면 이러한 파서 중 하나를 되돌릴 방법이 없다고 생각합니다. 대안이 성공하면 다른 대안을 시도하지 않습니다. 이 동작은 이러한 조합자가 구현하는 표현식 구문 분석을위한 packrat 구문 분석 방법에 고유합니다 (대안 순서가 관련이없고 역 추적 동작이 구문 분석 방법에 의존하는 문맥 자유형 문법과 반대). 그래서 더 긴 입력과 일치 할 수있는 대체물이 먼저 주어져야합니다.

우선 순위와 관련하여 표준 접근 방식은 문맥 규칙 문법에서와 마찬가지로 연산자의 우선 순위와 결합을 문법 규칙으로 인코딩하는 것입니다. 대부분의 구문 분석에 대한 책에서는이를 수행하는 방법을 설명합니다. 슬라이드 24에서 시작하는 다음 노트에서 하나의 버전을 볼 수 있습니다 : http://www.sci.usq.edu.au/courses/CSC3403/lect/syntax-1up.pdf.

Answer 2

구체적인 이유는 모르지만 파서와 함께 이러한 문제가 발생할 때마다 가장 복잡한 것부터 가장 단순한 것으로 파싱 가능성을 나열합니다. 귀하의 경우에는

당신의 예를 구문 분석한다

lazy val pattern: PackratParser[LogicalUnit] = ((and) | (not) | (variable))을 할 것이다.

결과는 Not(And(Variable(a),Not(Variable(b))))이지만 원하지 않는 결과 일 수 있습니다.

a & !b이 유효한 패턴이므로 은 not부터 구문 분석 할 수 있습니다.

변경하려면 괄호를 사용하면됩니다. 이것은 하나의 간단한 가능성입니다 :

lazy val not: PackratParser[Not] = 
    ("!" ~> term) ^^ { x => Not(x) } 

lazy val term: PackratParser[LogicalUnit] = 
    variable | "(" ~> and <~ ")" 

이제 결과는 And(Not(Variable(a)),Not(Variable(b)))입니다.