앞서 보기 스트림

앞서 보기(lookahead) 스트림은 스트림 중에서도 다음에 읽을 원소를 최대 k개까지 볼 수 있는 기능을 제공하는 자료형이다. 파싱에 특히 유용하게 쓰이는데, 대부분의 파서에서는 다음 입력(들)을 보고 다음에 할 동작을 결정해야 하기 때문이다. 이를테면 문자로 이루어진 스트림이 앞서 보기를 지원할 경우 123 등의 정수를 이렇게 읽을 수 있다.

1. ‘읽은 정수’를 0으로 초기화한다.
2. 다음에 읽을 문자가 0부터 9 사이면(앞서 보기),
   • 해당 문자를 읽어서 0부터 9 사이의 ‘자릿수’를 결정한다.
   • ‘읽은 정수’에 10을 곱한 뒤 그 ‘자릿수’를 더한다.
   • 2번으로 다시 돌아간다.
3. 이제 더 이상 읽을 숫자가 없으므로 ‘읽은 정수’를 반환한다.

이 때 123,45 같은 입력이 들어 올 경우 3번에 도달했을 때 다음으로 읽게 되는 문자는 4가 아니라 그 앞의 ,가 된다. 이러한 동작은 다음에 있는 원소를 읽는 기능만 있을 경우 불가능하다.

앞서 보기를 할 수 없는 경우 파싱할 수 있는 언어가 크게 줄어든다는 것이 이론적으로 알려져 있으며, 특정 종류의 파서에서 최소 k개의 원소를 앞서 볼 수 있어야 파싱할 수 있는 언어를 LL(k), LR(k), LALR(k) 등으로 따로 부른다. 현실에서 보게 되는 거의 모든 문법들은 k ≤ 1이므로 앞서 보기 스트림도 k = 1로 구현된 경우가 가장 흔하다.

이러한 유용성에도 불구하고 앞서 보기 스트림의 인터페이스는 표준화가 잘 되어 있지 않은데다, 직접 만들어 써야 하는 경우도 드물지 않다. 일반적으로는 특정 인터페이스를 쓴다고 구현이 불가능해지는 경우는 없지만, 이 인터페이스가 구현 편의에 직접 영향을 미치기 때문에 허투루 고를 수도 없다.

peek #

이 인터페이스에서는 다음 연산을 지원한다.

• next := read()는 입력을 하나 읽어들여 반환한다.

• next := peek(n)은 다음 n번째 read()가 반환할 값을 반환한다(1 ≤ n ≤ k). n = 1일 때가 흔하므로 이 경우에는 보통 n을 생략한다. 물론 peek()을 몇 번이든 호출해도 다음 read()의 반환값은 바뀌지 않는다.

이 접근은 read()의 동작을 바꾸지 않기 때문에 기존의 스트림 인터페이스를 크게 바꾸지 않고, 실수할 여지도 별로 없으므로 일반적인 자료 구조에서 선호된다. 하지만 파서에서는 peek()했던 값을 곧바로 read()하는 경우가 아주 흔하기 때문에 대단히 귀찮다.

주요 사례

Rust std::iter::Peekable 등.

인자 없는 unread #

이 인터페이스에서는 다음 연산을 지원한다.

• next := read()는 입력을 하나 읽어들여 반환한다.

• unread()는 입력 위치를 앞으로 하나 당긴다. 단 가장 많이 읽은 입력으로부터 앞으로 k개까지만 당길 수 있다.

unread()의 k개 제한은 다소 이해하기 어려울 수 있는데, 보통 스트림에 있는 전체 입력을 다 가지고 있는 게 아니라 필요할 때마다 읽어 들이기 때문에, 고정 크기의 배열에 최근 입력을 보존하려다 보니 생기는 제한이다. 전체 입력을 바로 꺼내 볼 수 있는 경우 이런 제한은 필요하지 않다.

이 접근은 호출 숫자를 크게 줄일 수 있어서 특히 파서를 손으로 직접 짤 때 흔히 쓰인다. 하지만 read()를 하지 않았는데 unread()를 실수로 호출해서 입력 위치를 망가뜨리는 상황을 막을 수 없다는 단점이 있다.

인자 있는 unread #

이 인터페이스에서는 내부적으로 최대 k개까지의 입력을 보존할 수 있는 스택이 있어서, 다음 연산을 지원한다.

• next := read()는 스택에 값이 있으면 맨 위의 값을 꺼내서 반환하고, 아니면 새 입력을 하나 읽어 들여 반환한다.

• unread(prev)는 받은 값을 스택 위에 넣는다.

이 접근은 인자 없는 unread와 겉보기에 별 차이는 없지만 구현이 훨씬 간단하다. 특히 k > 1일 때 인자가 없으면 어디까지 unread를 했고 어디까지 read를 했는지를 따로 관리해야 하지만, 이 접근에서는 그냥 unread 이후 read에서 꺼내지 않은 입력의 숫자만 세면 된다.

이 접근의 단점이자 장점은 read()에서 반환한 값과 unread()에 전달되는 값이 다를 수 있다는 것이다. 따라서 조금만 실수해도 바로 이해하기 어려운 버그가 발생할 수 있다. 그럼에도 불구하고 이게 장점일 수 있는 이유는, 다른 연산들과는 달리 이 연산은 다른 인터페이스로 흉내낼 수 없는 새로운 기능이기 때문이다. 그래서 구현이 간단하다는 점과 맞물려 손으로 짤 때는 문제를 감수하고 이 접근을 쓰는 경우가 대단히 많다.

주요 사례

C ungetc 등.

체크포인트 #

이 인터페이스에서는 다음과 같은 연산을 제공한다.

• checkpoint := save()는 현재 스트림의 상태를 반환한다.

• restore(checkpoint)는 현재 스트림의 상태를 복원한다.

이 접근은 어느 시점에 생성한 checkpoint라도 올바르게 복원할 수 있다는 점에서 unread() 계열 접근과 구분된다. 따라서 읽을 수 있는 원소의 갯수 k에 제한이 없고, 토큰은 한 시점에서 여러 개 읽어서 쓸 수 있지만 체크포인트는 그런 경우가 드물기 때문에 실수로 엉뚱한 시점으로 복원할 가능성도 적다.

이 접근의 단점은 이런 방법을 쓸 수 있는 상황 자체가 한정된다는 것이다. 우선 전체 스트림을 어느 시점에라도 접근할 수 있어야 하며, save()가 자주 호출되기 때문에 상태도 아주 가벼워야 한다.

주요 사례

엄밀히는 스트림은 아니지만, 자바스크립트 RegExp.lastIndex가 이 인터페이스와 아주 유사하다. 이 때문에 가볍게 짠 자바스크립트 파서에서 특히 이런 접근이 자주 보인다.