크게 2가지의 parsing 방법에 대해 알아보고자 한다.

• Top-down parsing
• Bottom-up parsing

Top-down parsing

bottom-up parsing에 비해 좀 더 직관적으로 이해할 수 있다. 그리고 손 코딩이 가능하다.
물론 bottom-up parsing도 손 코딩이 가능하긴 하지만 굉장히 힘들다고 한다.

Parsing

parsing이란 string의 derivation을 찾아내는 것이다. production rule에 따라 derivation이 있다면 가능한 string이지만 없다면 불가능하다. 당연한 소리인가?

근데 아무 배경 지식 없이 내가 parser를 만든다고 했을 때 token을 분석하면서 derivation을 찾는다면 시간 복잡도가 굉장히 높을 것 같다. 예를 들어, production rule에서 start symbol로부터 가능한 모든 경우의 수를 대조해본다면 아무도 그 컴파일러는 사용하지 않을 것 같다.

ambiguity가 없어도 $O(n^3)$이 걸릴 수 있다. CYK 알고리즘을 예로 들 수 있는데 궁금하면 구글링 해보자..

결론은 parsing하는데 너무 많은 시간을 소요할 수는 없다. 그냥 string을 한번 읽는 시간, 즉 $O(n)$의 시간복잡도가 적당하다. 그래서 그 접근 방법의 두 가지 후보가 바로 오늘 알아볼 Top-down parsing과 다음에 알아볼 Bottom-up parsing이다.

overview를 하자면, top-down은 말 그대로 start symbol부터 string까지 derivation을 찾는 것이다. derivation은 leftmost derivation 방식으로 진행된다. 예를 들어,

이런 production rule이 있을 때

The cat sees a rat

을 top-down parsing한다면

Sentence
$\rarr$ Subject Verb Object .
$\rarr$ the Noun Verb Object .
$\rarr$ the cat Verb Object .
$\rarr$ the cat sees Object .
$\rarr$ the cat sees a Noun .
$\rarr$ the cat sees a rat .

이렇게 진행되며 LL parser가 이런식으로 진행된다고 할 수 있다. (LL parser는 Top-down parser의 일종이다.)

같은 예시로 bottom-up parsing 과정을 살펴보자.

the cat sees a rat .
$\rarr$ the Noun sees a rat .
$\rarr$ Subject sees a rat .
$\rarr$ Subject Verb a rat .
$\rarr$ Subject Verb a Noun .
$\rarr$ Subject Verb Object .
$\rarr$ Sentence

보는 것처럼 string으로부터 parse tree의 root를 완성시키는 것을 확인 할 수 있다. bottom-up 중 LR parser의 진행과정이다. rightmost derivation의 역순으로 진행된다.

Top-down parser 개념

top-down parser는 우선 parse tree의 root로부터 시작한다. 그리고 non-terminal을 terminal까지 변환시키면서 input string의 요소와 일치한다면 다음 non-terminal을 변환시키면서 아래로 진행한다.

근데 여기서 문제가 발생한다. non-termianl의 derivation을 하나씩 대조해봐야한다는 치명적인 결함이 있다. 즉, input의 요소와 맞는 지 확인하면서 최악의 경우 모든 rule을 derivation해보다가 마지막에 찾거나 모든 rule을 적용하고 derivation이 불가능함을 판단하게 된다. 그럼 우리가 원하는 $O(n)$ time에 parsing을 하는 것은 불가능하다.

Predictive parsing

그래서 predictive parsing을 해야만 한다. 여기서 중요한 개념이 바로 lookahead symbol이다. symbol을 미리 가져와서 가능한 derivation으로 뻗어나가는 것이다. 마치 왼손에는 production rule을, 오른손으로는 다음에 오는 symbol을 들고 비교하는 꼴이다. 이렇게 되면 모든 경우의 수로 찾는 것이 아니라 symbol을 보고 가능한 경우의 수만 볼 수 있다. 쉽게 말해 backtracking이 사라진다.

$stmt ::= id = exp \ ; \ | \ return \ \ exp \ ;\ | \ if\ (\ exp\ )\ stmt\ |\ while\ ( \ exp\ ) \ stmt$

만약에 string이 $id$, $return$, $if$, $while$ 중 어느 것으로 시작하는 지만 알아도 단번에 derivation을 찾을 수 있게 된다. 만약 string이 아래와 같다면.

WHILE LPAREN EXP ...

lookahead symbol로 WHILE만 읽어도 stmt로부터 while로 parse tree를 뻗어나가면 된다는 뜻이다.

다음 시간에는 2개의 대표적인 Top-down parsing 알고리즘을 소개하고자 한다.

• Recursive descent 재귀 하방
• LL parsers

결론

아무래도 lexical analysis보다 parser쪽의 내용이 더 복잡한 것 같다. 앞의 내용을 잘 이해해야지 뒤의 내용이 잘 이해가 가는 과목이다. 지금까지는 복잡한 내용은 없지만 다음 시간에 parsing 알고리즘 내용이 익숙해지기 전까지는 알아듣기 힘들 수 있다.