모나 딕 파싱에 비해 응용 파싱의 이점은 무엇입니까?

모나 딕 파싱에 비해 응용 파싱의 이점은 무엇입니까?

---

모나드가 아닌 응용 프로그램으로 Parsec을 사용해야한다는 합의가있는 것 같습니다. 모나 딕 파싱에 비해 응용 파싱의 이점은 무엇입니까?

• 스타일
• 공연
• 추출

모나 딕이 파싱되고 있습니까?

---

모나 딕 파싱과 응용 파싱의 주요 차이점은 순차 구성이 처리되는 방식입니다. 응용 파서의 경우를 사용 (<*>)하는 반면 모나드에서는를 사용 (>>=)합니다.

(<*>) :: Parser (a -> b) -> Parser a -> Parser b
(>>=) :: Parser a -> (a -> Parser b) -> Parser b

모나 딕 접근 방식은 두 번째 부분의 문법이 첫 번째 부분의 결과에 의존 할 수 있기 때문에 더 유연하지만 실제로는 이러한 추가 유연성이 거의 필요하지 않습니다.

추가적인 유연성이 있다고 생각할 수 있지만 실제로는 그렇게 할 수 있습니다. 그것은 우리가 그것을 실행하지 않고 파서에서 유용한 정적 분석을 수행하는 것을 방해합니다. 예를 들어 파서가 빈 문자열과 일치 할 수 있는지 여부와 일치 할 수있는 첫 번째 문자가 무엇인지 알고 싶다고 가정 해 보겠습니다. 우리는 기능을 원합니다

empty :: Parser a -> Bool
first :: Parser a -> Set Char

응용 파서를 사용하면이 질문에 쉽게 답할 수 있습니다. (여기 조금 부정하고있다. 우리는 데이터 생성자에 해당하는이 상상 (<*>)과 (>>=)우리의 후보 파서 "언어"에서).

empty (f <*> x) = empty f && empty x
first (f <*> x) | empty f   = first f `union` first x
                | otherwise = first f

그러나 모나 딕 파서를 사용하면 입력을 알지 못하고 두 번째 부분의 문법이 무엇인지 알 수 없습니다.

empty (x >>= f) = empty x && empty (f ???)
first (x >>= f) | empty x   = first x `union` first (f ???)
                | otherwise = first x

더 많이 허용함으로써 우리는 더 적게 추론 할 수 있습니다. 이것은 동적 및 정적 유형 시스템 간의 선택과 유사합니다.

그러나 이것의 요점은 무엇입니까? 이 추가 정적 지식을 어디에 사용할 수 있습니까? 예를 들어 다음 문자를 first각 대안 집합과 비교하여 LL (1) 구문 분석에서 역 추적을 방지하는 데 사용할 수 있습니다 . first두 개의 대안 집합이 겹치는 지 확인하여 이것이 모호한 지 여부를 정적으로 결정할 수도 있습니다 .

또 다른 예는 S. Doaitse Swierstra 및 Luc Duponcheel의 Deterministic, Error-Correcting Combinator Parsers 논문에서 볼 수 있듯이 오류 복구에 사용할 수 있다는 것 입니다.

그러나 일반적으로 응용 파싱과 모나 딕 파싱 사이의 선택은 사용중인 파싱 라이브러리의 작성자가 이미 선택했습니다. Parsec과 같은 라이브러리가 두 인터페이스를 모두 노출하는 경우 사용할 인터페이스를 선택하는 것은 순전히 스타일입니다. 어떤 경우에는 응용 코드가 모나 딕 코드보다 읽기 쉽고 때로는 그 반대입니다.

---

구문 분석기가 순전히 적용 가능한 경우, 실행하기 전에 구조를 분석하고 "최적화"할 수 있습니다. 파서가 모나 딕 인 경우 기본적으로 Turing-complete 프로그램이고 거의 모든 흥미로운 분석을 수행하는 것은 중지 문제를 해결하는 것과 같습니다 (즉 불가능).

아, 그리고 네, 문체 차이도 있습니다 ...

---

모나 딕 파서보다 응용 파서를 선호하는 주된 이유는 어떤 상황에서든 모나 딕 코드보다 응용 코드를 선호하는 주된 이유와 동일합니다. 덜 강력하고 응용 프로그램을 사용하기가 더 간단합니다.

이것은보다 일반적인 엔지니어링 용어의 예입니다 . 작업을 완료하는 가장 간단한 도구를 사용하십시오. 돌리가 할 때 지게차를 사용하지 마십시오. 쿠폰을 자르기 위해 테이블 ​​톱을 사용하지 마십시오. IO순수 할 수있을 때 코드를 작성하지 마십시오 . 단순하게 유지하십시오.

하지만 가끔은, 당신이 필요로 하는 추가 전력을 Monad. 이것의 확실한 신호는 지금까지 계산 된 것을 기반으로 계산 과정을 변경해야 할 때입니다. 파싱 ​​용어에서 이것은 지금까지 파싱 된 내용을 기반으로 다음에 오는 내용을 파싱하는 방법을 결정하는 것을 의미합니다. 즉, 이러한 방식으로 상황에 맞는 문법을 구성 할 수 있습니다.

---

Parsec을 사용하면 Applicative를 사용하는 이점은 스타일뿐입니다. Monad는 더 강력하다는 장점이 있습니다. 상황에 맞는 파서를 구현할 수 있습니다.

Doaitse Swierstra의 UU 구문 분석은 응용 적으로 만 사용하는 경우 더 효율적입니다.

---

모나드는 Applicatives보다 엄격하게 더 기능적인 추상화 입니다. 당신은 쓸 수 있습니다

instance (Monad m) => Applicative m where
  pure  = return
  (<*>) = ap

하지만 쓸 방법이 없습니다

instance (Applicative a) => Monad a where
  return = pure
  (>>=) = ???

예, 본질적으로 스타일 의 문제 입니다 . 난 당신이 사용하는 경우 상상 return하고 ap, 그 다음이 없어야합니다 어떠한 성능 손실 사용하여 이상 pure하고 <*>. Applicative는 Monad보다 엄격히 작은 인터페이스이기 때문에 <*>때때로 ap. (하지만 영리한 GHC 재 작성 규칙을 사용하면 종종 동일한 최적화를 달성 할 수 있습니다.)

모나 딕이 파싱되고 있습니까?

Monads는 Applicatives의 하위 집합이기 때문에 applicative 구문 분석은 모나 딕 구문 분석의 하위 집합이라고 결론을 내립니다.

참고 URL : https://stackoverflow.com/questions/7861903/what-are-the-benefits-of-applicative-parsing-over-monadic-parsing