jooyunghan/댓글.md

## 댓글.md

      
    Raw
  

              댓글.md
            
          
    hikaMaeng 님께서 질문 주신 글에 대한 답변입니다.
FAIL??

FAIL 같은 건 좀 필요없어 보이기도 하네요. 흠.
그냥 파서 함수 코드를 읽기 쉽게 하려다 보니 쉽게 접근한거 같습니다.
먼저 Recursive Descent Parser를 짧게 소개하면서
"문법에 따라 거의 기계적으로 만들 수 있기 때문에"라고 했습니다.
바로 이 부분을 강조하려고 하다보니 이러한 모양이 나왔습니다.
글에서 예제로 사용하는 괄호 맞춤 파서는 워낙 간단해서 사실 RD 파서를 쓸 일도 없습니다.
질문에 주신 것처럼 배열 하나를 스택처럼 쓰면 간단히 해결됩니다.
다만 이 글의 목적은 "깊은 중첩 호출로 발생할 수 있는 스택오버플로 문제를 제너레이터를 이용하여 우회할 수 있더라"라는 발견을
공유하려는 것이었습니다. 그러다보니 스택오버플로가 쉽게 나타나는 사례 중 하나로 RD 파서를 고른 것이고
RD 파서에서 재귀 호출이 깊게 발생할 수 있는 문법 사례로 간단한 괄호 맞춤이 선택된 것이에요.
다시 "RD 파서는 기계적으로 만들수 있다"라는 점으로 돌아와서..
이 부분을 드러내려고 일부러 코드 생성 패턴을 일반화 시켰습니다.
기본적으로는 아래의 규칙을 따르고..

문법 룰마다 파싱 함수가 매치된다.
파싱함수는 룰에 해당하는 반환값을 가진다.
실패하는 경우는 FAIL을 반환하고 파싱 위치는 변경되지 않는다.

생성규칙은 대략..

각 파싱 함수는 let s; 로 시작한다.
하위 파싱함수를 불러서 s = subParser() 식으로 반환값을 받는다.
반환값은 반드시 (s === FAIL)로 검사하여 실패 여부를 판단한다.

정도입니다.
여기서 각 파싱함수가 반환할 수 있는 값은 문법 규칙에 따라 결정되는데,
이 때 반환값이 true/false 일 수도 있습니다.
이 때문에 다른 어떤 값과도 중복될 수 없는 파서 내부의 값을 결정할 필요가 있고, 그래서
FAIL 이라는 값을 만들어 identity 를 비교했습니다.
예를 들어 boolean 값 파서 문법을 다음처럼 정의했다면..
bool = "true" | "false"

bool 파서 함수는 "기계적 변환"으로..
function bool() {
  let s;
  s = match("true");
  if (s !== FAIL) return s;
  s = match("false");
  if (s !== FAIL) return s;
  return FAIL; 
}
그런데 만약 match("true") 함수는 매치된 문자열을 반환하고, bool() 파싱함수는 실제로 해석된 true/false를 반환하고 싶다면
function bool() {
  let s;
  s = match("true");
  if (s !== FAIL) return true;
  s = match("false");
  if (s !== FAIL) return false;
  return FAIL;
}
FAIL 하나 설명하려다 길어졌네요.
_input, _pos

이것도 사실 위에서 글의 목적이라고 밝힌 부분처럼 "스택오버플로 회피하기"에 초점을 맞추다 보니
재귀 호출 구조를 보여주는 예제로서의 RD 파서에서 _input과 _pos를 파싱 컨텍스트로 감싸서 넘기는 것조차
사족이라 생각해서 그냥 전역으로 뒀던 것인데요. 아마 이런 자유 변수가 불편하셨나 봅니다. :-)
실제로 처음 예제를 만들 때는 완전 전역은 아니었어요. ^^ 대충 아래와 같은..
function Parens() {   // parser creator
  const FAIL = {};
  let _pos;
  let _input;

  function parse(input) {
    ...
  }

  // parens
  // paren
  // p1, p2, p3
  // ..

  return {
    parse
  }
}

const p = Parens();
p.parse("...");
그럼 왜 파서 함수의 인자로 사용하지 않았느냐는 물음이 남는데,
어차피 위처럼 파서라는 컨텍스트 안에서 parse() 함수만 노출되고,
각 파싱함수가 모두 인자로 받아서 "업데이트" 하기 때문에 전역이나 마찬가지고,
오히려 실제로 사용되는 것은 대부분 문법 생성 룰의 최하위 즉 terminal 이기 때문에
드러내지 않는 것이 코드를 더 간결하게 해준다고 봤습니다. :-)
만약 함수형 프로그래밍을 적용했다면 상태 모나드를 사용할 테고,
그렇다면 역시나 중간 과정의 파싱함수 조합 중에는 드러나지 않다가,
실제 필요한 지점에서만 참조/업데이트 했겠죠. 같은 효과가 나올 것 같습니다.
이미 로컬 스택과 while 아닌가?

고쳐서 올려주신 코드 중 첫번째 것 역시 RD 파서이고, 따라서 괄호가 10만개쯤 중첩되면 파싱하다가
스택오버플로를 발생시키죠.
굳이 RD파서의 스타일을 유지해야 하나?

꼭 그래야 하는 것은 아니지만, 대개의 경우 RD 파서가 쉽거든요. :-)
"기계적" 이라고 얘기한 이유는 실제로 이렇게 파서를 만들어주는 라이브러리도 많습니다.
저는 peg.js 나 ometa.js 정도만 알고 있지만.. 이 라이브러리는 문법만 던져주면 RD파서를 만들어줍니다.
그런데 당연히 이들이 생성하는 코드도 deeply nested 구조에서 스택오버플로를 발생시킵니다.
정말 아주아주 복잡한 문법이라면 정말 파서생성기를 써야 할테고,
간단한 경우는 또 굳이 RD파서니 뭐니 쓸 필요도 없을테고,
그렇지만 손으로 직접 파서를 만들어야 하는 적당한 수준의 문제는 있으니까,
그런 경우라면 RD파서가 쉽고 간편한 해결책이 아닐까 싶어요 :-)
제너레이터가 도움을 주는 부분은?

"제네레이터가 도움을 줄 수 있는 부분은 드릴다운했다가 나올 때의 상황을 제네레이터가 유지하고 있으니 코드 상으로는 동기로직처럼 유지하게 하는게 장점인건가?"
그렇죠. 함수 호출한 결과를 그 뒤에서 사용해야 하는데 함수를 호출하면 안된다면.. 이라는 문제에서 이글이 출발한 거라서
여기에 딱 맞아떨어진 것이 제너레이터였던 거죠. 대신 일반적인 이터레이터 생성을 위한 목적이 아니라 각 파싱 함수를
코루틴으로 만들고 그 위에 디스패치 루프를 씌우는 식으로 사용한 것이죠.
덕분에 호출스택의 증가로 인한 오버플로 문제는 없어지고요.