《 수기 SQL 컴 파일 러 - 역 추적 》 을 정독 하 다.

머리말
지난번 을 정독 하 다. 에 Js 함 수 를 어떻게 이용 하여 문법 분석 을 실현 하 는 지 에 대해 언급 했 을 때 역 추적 문 제 를 남 겼 는데 그것 이 바로 압축 파일, 읽 기 문제 이다.
우 리 는 문법 분석 나 무 를 미로 로 삼 아 직선 에 갈림길 이 있 고 미 로 를 벗 어 나 려 면 갈림길 을 만 났 을 때 미리 보관 해 야 한다. 뒤에서 잘못 걸 었 을 때 읽 기 파일 을 다음 갈림길 로 바 꾸 어 시도 해 야 한다. 이 기능 을 역 추적 이 라 고 한다.
이전 편 에서 우 리 는 분기 함 수 를 실 현 했 습 니 다. 분기 실행 에 실패 한 후에 TokenIndex 위 치 를 스크롤 하고 다시 시도 합 니 다. 그러나 함수 호출 스 택 에서 하위 함수 가 실행 되 고 스 택 이 뛰 어 나 면 우 리 는 원래 의 함수 스 택 을 찾 아 다시 실행 할 수 없습니다.
이 문 제 를 더욱 상세 하 게 묘사 하기 위해 예 를 들 어 다음 과 같은 갈림길 이 존재 한다.

a -> tree() -> c
     -> b1 -> b1'
     -> b2 -> b2'

위 에 두 가지 판단 가 지 를 묘 사 했 는데 각각 a -> b1 -> b1' -> c 과 a -> b2 -> b2' -> c 이 고 갈림길 b1 이 실 패 했 을 때 분기 함수 tree 는 b2 위치 로 복원 하여 재 집행 을 시도 할 수 있다.
그러나 구상 b1 -> b1' 이 통과 되 었 으 나 b1 -> b1' -> c 이 통과 하지 않 는 장면 은 b1' 이 실 행 된 후에 분기 함수 tree 의 호출 스 택 이 탈퇴 되 어 더 이상 노선 b2 -> b2' 을 시도 할 수 없습니다.
이 문 제 를 해결 하려 면 우 리 는 링크 수 동 구조 함수 집행 과정 을 통 해 임 의 위치 역 추적 을 실현 할 수 있 을 뿐만 아니 라 왼쪽 재 귀 문 제 를 해결 할 수 있 습 니 다. 함수 가 바로 실행 되 는 것 이 아니 기 때문에 실행 하기 전에 우 리 는 Magic 동작 을 추가 할 수 있 습 니 다. 예 를 들 어 실행 순 서 를 바 꿀 수 있 습 니 다!이 글 은 주로 링크 구조 함수 호출 스 택 을 통 해 역 추적 을 실현 하 는 방법 을 소개 한다.
정독
만약 에 우리 가 이런 함수 chain 를 가지 고 있다 고 가정 하면 더욱 간단 한 방식 으로 연속 적 인 매 칭 을 표시 할 수 있다.

const root = (tokens: IToken[], tokenIndex: number) => match('a', tokens, tokenIndex) && match('b', tokens, tokenIndex) && match('c', tokens, tokenIndex)
↓ ↓ ↓ ↓ ↓ ↓
const root = (chain: IChain) => chain('a', 'b', 'c')

분기 조건 을 만 났 을 때 배열 을 통 해 대체 tree 함 수 를 표시 합 니 다.

const root = (tokens: IToken[], tokenIndex: number) => tree(
  line(match('a', tokens, tokenIndex) && match('b', tokens, tokenIndex)),
  line(match('c', tokens, tokenIndex) && match('d', tokens, tokenIndex))
)
↓ ↓ ↓ ↓ ↓ ↓
const root = (chain: IChain) => chain([
  chain('a', 'b'),
  chain('c', 'd')
])

이 chain 함 수 는 두 가지 특질 이 있다.

즉시 집행 하지 않 으 면 우 리 는 집행 체인 을 미리 생 성하 고 체인 구 조 를 최적화 시 키 며 심지어 집행 순 서 를 제어 하여 역 추적 기능 을 실현 할 수 있다.

Token 을 전달 하 는 것 을 표시 하지 않 고 쓰기 에 일치 하 는 코드 의 양 을 줄 입 니 다.

패키지 스캐너, matchToken
우 리 는 scanner 함 수 를 만들어 token 에 대한 조작 을 밀봉 할 수 있 습 니 다.

const query = "select * from table;";
const tokens = new Lexer(query);
const scanner = new Scanner(tokens);

scanner 는 두 가지 주요 기능 을 가지 고 있 습 니 다. 각각 read 현재 token 내용 을 읽 고 next token 을 아래로 이동 합 니 다. 우 리 는 이 기능 에 따라 새로운 matchToken 함 수 를 봉인 할 수 있 습 니 다.

function matchToken(
  scanner: Scanner,
  compare: (token: IToken) => boolean
): IMatch {
  const token = scanner.read();
  if (!token) {
    return false;
  }
  if (compare(token)) {
    scanner.next();
    return true;
  } else {
    return false;
  }
}

token 이 소모 되 거나 비교 가 일치 하지 않 을 때 false 로 돌아 가 고 token 이 소모 되 지 않 습 니 다. 일치 할 때 token 을 소모 하고 true 로 돌아 갑 니 다.
이제 우 리 는 matchToken 함수 로 일치 하 는 코드 를 쓸 수 있다.

const query = "select * from table;";
const tokens = new Lexer(query);
const scanner = new Scanner(tokens);
const root =
  matchToken(scanner, token => token.value === "select") &&
  matchToken(scanner, token => token.value === "*") &&
  matchToken(scanner, token => token.value === "from") &&
  matchToken(scanner, token => token.value === "table") &&
  matchToken(scanner, token => token.value === ";");

우 리 는 결국 이런 구조 로 표현 하고 싶다.

const root = (chain: IChain) => chain("select", "*", "from", "table", ";");

chain 함수 가 단서 로 전체 절 차 를 관통 하 는 이상 scanner 함 수 는 chain 함수 의 패 킷 내부 에 포함 되 어 전달 되 어야 하기 때문에 우 리 는 첫 번 째 chain 을 구성 해 야 합 니 다.
패키지 createChainNodeFactory
우 리 는 createChinn Node Factory 함수 가 scanner 를 전송 하고 내부 에 몰래 저장 해 야 합 니 다. 외부 코드 에 전달 을 표시 하지 마 십시오. 또한 chain 함 수 는 고급 함수 로 즉시 실행 되 지 않 습 니 다. 이 를 통 해 2 단계 함 수 를 밀봉 할 수 있 습 니 다.

const createChainNodeFactory = (scanner: Scanner, parentNode?: ChainNode) => (
  ...elements: any[]
): ChainNode => {
  //        
  return firstNode;
};

두 가지 설명 이 필요 합 니 다.

chain 함수 가 첫 번 째 링크 노드 로 돌아 가면 visiter 함 수 를 통 해 전체 링크 를 방문 할 수 있 습 니 다.

(...elements: any[]): ChainNode 은 바로 chain 함수 자체 로 일련의 매개 변 수 를 받 아 유형 에 따라 기능 분 류 를 한다.

CreateChain Node Factory 가 있 으 면 실행 입 구 를 생 성 할 수 있 습 니 다.

const chainNodeFactory = createChainNodeFactory(scanner);
const firstNode = chainNodeFactory(root); // const root = (chain: IChain) => chain('select', '*', 'from', 'table', ';')

chain('select', '*', 'from', 'table', ';') 문법 을 지원 하기 위해 서 우 리 는 매개 변수 유형 이 텍스트 형식 일 때 matchToken 함 수 를 링크 노드 로 자동 으로 생 성 하 는 동시에 reduce 함 수 를 통 해 링크 노드 를 연결 해 야 합 니 다.

const createChainNodeFactory = (scanner: Scanner, parentNode?: ChainNode) => (
  ...elements: any[]
): ChainNode => {
  let firstNode: ChainNode = null;

  elements.reduce((prevNode: ChainNode, element) => {
    const node = new ChainNode();

    // ... Link node

    node.addChild(createChainChildByElement(node, scanner, element));

    return node;
  }, parentNode);

  return firstNode;
};

reduce 함 수 를 사용 하여 링크 의 상하 노드 를 연결 합 니 다. 이 단 계 는 일반적인 것 이기 때문에 무시 합 니 다. createchain ChildByElement 함 수 를 통 해 들 어 오 는 함 수 를 분류 합 니 다. 들 어 오 는 함수 가 문자열 이 라면 matchToken 함수 로 현재 링크 의 하위 요 소 를 삽입 하고 링크 를 실행 할 때 matchToken 함 수 를 실행 합 니 다.
중요 한 것 은 우리 가 링크 노드 에 대한 처리 이 고 먼저 링크 구 조 를 소개 하 는 것 이다.
링크 구조

class ChainNode {
  public prev: ChainNode;
  public next: ChainNode;
  public childs: ChainChild[] = [];
}

class ChainChild {
  // If type is function, when run it, will expend.
  public type: "match" | "chainNode" | "function";
  public node?: IMatchFn | ChainNode | ChainFunctionNode;
}

ChainNode 는 링크 노드 에 대한 정의 로 현재 글 내용 과 관련 된 부분 정 의 를 내 렸 습 니 다.여기 서 양 방향 링크 를 사 용 했 기 때문에 모든 node 노드 는 prev 와 next 속성 을 가지 고 각각 이전 노드 와 다음 노드 를 가리 키 고 childs 는 이 링크 아래 에 마 운 트 된 노드 로 matchToken 함수, 링크 노드 또는 함수 일 수 있 습 니 다.
전체 링크 구 조 는 이 럴 수 있 습 니 다.

node1  node2  node3  node4
            |- function2-1
            |- matchToken2-1
            |- node2-1  node2-2  node2-3
                              |- matchToken2-2-1

모든 노드 에 적어도 하나의 child 요소 가 존재 합 니 다. 만약 에 여러 개의 키 요소 가 존재 한다 면 이 노드 는 tree 노드 이 고 분기 상황 이 존재 한 다 는 것 을 나타 냅 니 다.
한편, 노드 유형 ChainChild 도 정의 에서 볼 수 있 는데 세 가지 유형 이 있 는데 우 리 는 각각 설명 한다.
matchToken 형식
이런 유형 은 가장 기본 적 인 유형 으로 다음 과 같은 코드 로 생 성 된다.

chain("word");

링크 가 실 행 될 때 match 는 가장 기본 적 인 실행 단위 로 문장 이 일치 하 는 지 여 부 를 결정 하고 Token 을 소모 하 는 유일한 단원 입 니 다.
node 형식
링크 노드 의 하위 노드 도 하나의 노드 일 수 있 습 니 다. 포 함 된 함수 와 유사 하여 다음 과 같은 코드 로 생 성 됩 니 다.

chain(chain("word"));

즉, chain 의 한 요 소 는 chain 자체 입 니 다. 그러면 이 chain 서브 링크 는 부모 급 노드 의 서브 요소 로 서 링크 노드 에 실 행 될 때 깊이 를 우선 적 으로 옮 겨 다 닙 니 다. 만약 에 실 행 될 경우 부모 급 으로 넘 어가 다음 노드 를 계속 찾 습 니 다. 그 집행 체 제 는 함수 호출 스 택 의 출입 관 계 를 비교 합 니 다.
함수 형식
함수 유형 은 매우 특별 합 니 다. 우 리 는 모든 함수 유형 을 재 귀적 으로 전개 할 필요 가 없습니다. 왜냐하면 문법 에 무한 재 귀적 인 상황 이 존재 할 수 있 기 때 문 입 니 다.
예 를 들 어 하나의 미로 와 같이 많은 구역 이 똑 같 고 반복 되 는 것 입 니 다. 만약 에 미 로 를 완전히 펼 치면 미궁 의 크기 가 무한대 에 달 할 것 입 니 다. 그래서 컴퓨터 에서 실 행 될 때 우 리 는 이런 함 수 를 한 걸음 한 걸음 전개 해 야 합 니 다. 미로 가 끝 날 때 Token 이 소모 되 거나 미로 에서 벗 어 나 거나 match 가 Token 에 미 치지 못 할 때 자원 을 소모 하 는 것 이 아 닙 니 다.함수 형식 노드 는 다음 코드 로 생 성 됩 니 다.

chain(root);

모든 함수 형식 노드 는 실 행 될 때 펼 쳐 집 니 다. 펼 칠 때 함수 노드 를 다시 만나면 보류 하고 다음 에 실 행 될 때 까지 기 다 렸 다가 펼 쳐 집 니 다.
갈래
일반적인 링크 는 분기 의 특수 한 상황 일 뿐 다음 코드 는 등가 입 니 다.

chain("a");
chain(["a"]);

다음 코드 를 비교 합 니 다:

chain(["a"]);
chain(["a", "b"]);

직선 이 든 분기 든 모두 분기 노선 으로 볼 수 있 고 직선 (분기 없 음) 의 상황 은 하나의 분기 만 있 는 분기 로 볼 수 있 으 며 링크 노드 에 비해 childs 는 하나의 요소 만 있 는 링크 노드 로 볼 수 있다.
돌 이 켜 보다
현재 chain 함 수 는 세 개의 피 드 요 소 를 지원 합 니 다. 하나의 분기 표현 방식:

chain("a"); // MatchNode
chain(chain("a")); // ChainNode
chain(foo); // FunctionNode
chain(["a"]); //    -> [MatchNode]

앞에서 언급 한 바 와 같이 chain 함 수 는 즉각 실행 되 는 것 이 아니 기 때문에 우 리 는 이 코드 를 실행 할 때 링크 구 조 를 생 성 할 뿐 실제 실행 내용 이 없고 내용 은 childs 에 포함 되 어 있 습 니 다.
우 리 는 exec Chain 함 수 를 구성 하여 링크 의 첫 번 째 노드 를 얻 고 visiter 함 수 를 통 해 링크 노드 를 옮 겨 다 니 며 진정 으로 실행 해 야 합 니 다.

function visiter(
  chainNode: ChainNode,
  scanner: Scanner,
  treeChances: ITreeChance[]
): boolean {
  const currentTokenIndex = scanner.getIndex();

  if (!chainNode) {
    return false;
  }

  const nodeResult = chainNode.run();

  let nestedMatch = nodeResult.match;

  if (nodeResult.match && nodeResult.nextNode) {
    nestedMatch = visiter(nodeResult.nextNode, scanner, treeChances);
  }

  if (nestedMatch) {
    if (!chainNode.isFinished) {
      // It's a new chance, because child match is true, so we can visit next node, but current node is not finished, so if finally falsely, we can go back here.
      treeChances.push({
        chainNode,
        tokenIndex: currentTokenIndex
      });
    }

    if (chainNode.next) {
      return visiter(chainNode.next, scanner, treeChances);
    } else {
      return true;
    }
  } else {
    if (chainNode.isFinished) {
      // Game over, back to root chain.
      return false;
    } else {
      // Try again
      scanner.setIndex(currentTokenIndex);
      return visiter(chainNode, scanner, treeChances);
    }
  }
}

상기 코드 에서 nestedMatch 는 포 함 된 함수 와 유사 하 며, treeChances 는 역 추적 을 실현 하 는 관건 입 니 다.
현재 노드 실행 실패 시
모든 노드 에 N 개의 child 가 포함 되 어 있 기 때문에 실 패 했 을 때 이 노드 의 child 에 표 시 를 하고 현재 노드 에 하위 노드 가 있 는 지 판단 하 며 모든 노드 가 실 패 했 을 때 false 로 돌아 갑 니 다.
현재 노드 실행 성공 시 위치 압축 파일 진행
노드 가 성공 할 때 후속 링크 의 실행 실 패 를 방지 하기 위해 현재 실행 위 치 를 기록 해 야 합 니 다. 즉, treeChances 를 이용 하여 저장 점 을 저장 해 야 합 니 다.
그러나 우 리 는 언제 전체 링크 가 실 패 를 당 할 지 모 르 기 때문에 전체 visiter 가 실 패 를 수행 할 때 까지 기 다 려 야 실 패 를 알 수 있 습 니 다. 그래서 우 리 는 실행 이 끝 날 때마다 메모리 포인트 (treeChances) 가 있 는 지 판단 해 야 합 니 다.

while (!result && treeChances.length > 0) {
  const newChance = treeChances.pop();
  scanner.setIndex(newChance.tokenIndex);
  result = judgeChainResult(
    visiter(newChance.chainNode, scanner, treeChances),
    scanner
  );
}

이 동시에 우 리 는 링크 구조 에 대해 필드 tokenIndex 를 추가 하여 역 추적 복원 사용 을 준비 하 는 동시에 scanner 함수 setIndex 방법 을 호출 하여 token 위 치 를 복원 해 야 한다.
마지막 으로 기회 가 다 되면 매 칭 에 실패 합 니 다. 임의의 기회 가 있 거나 한 명 만 통관 할 수 있다 면 매 칭 에 성공 합 니 다.
3 총화
이 글 에서 우 리 는 링크 를 이용 하여 함수 집행 체 제 를 재 작성 하여 일치 함수 로 하여 금 역 추적 능력 을 가지 게 할 뿐만 아니 라 표현 도 더욱 직관 적 으로 한다.

chain("a");

이러한 구조 방식 은 본질 적 으로 문법 구조 에 따라 코드 로 컴 파일 하 는 방식 과 같다. 다만 많은 품사 해석 기 는 텍스트 를 이용 하여 코드 로 해석 할 뿐 우 리 는 코드 를 이용 하여 문법 구 조 를 표현 하 는 동시에 자신 이 실행 한 결 과 는 '컴 파일 된 코드' 이다.
다음 에 우 리 는 왼쪽 재 귀 문 제 를 어떻게 자동 으로 해결 하 는 지 연구 할 것 입 니 다. 우 리 는 이러한 표현 식 을 쓸 수 있 습 니 다.

const foo = (chain: IChain) => chain(foo, bar);

다행히 chain 함 수 는 즉시 실행 되 는 것 이 아 닙 니 다. 우 리 는 스 택 에 넘 치 는 소용돌이 에 바로 빠 지지 않 지만 노드 를 실행 하 는 과정 에서 함수 가 무한 전개 되 어 스 택 이 넘 칠 수 있 습 니 다.
왼쪽 재 귀 를 해결 하 는 것 은 쉽 지 않 습 니 다. 수 동 또는 자동 으로 문법 을 다시 쓰 는 것 외 에 다른 방안 이 있 습 니까?댓 글 토론 을 환영 합 니 다.
4. 더 많은 토론
토론 주 소 는:
《 수기 SQL 컴 파일 러 - 역 추적 》 · Issue \ # 96 · dt - fe / weekly 정독
토론 에 참여 하고 싶다 면 여 기 를 클릭 하 세 요. 매주 새로운 주제 가 있 고 주말 이나 월요일 에 발표 하 세 요.