LL(1) 파싱 알고리듬 - 파싱 테이블과 파싱 방법

앞의 글에서 문법에 대해 RDP(Recursive Descent Parser)를 직접 만드는 방법을 살펴보았습니다. 그러나 문법이 아주 큰 경우 모든 넌터미널 심볼에 대해 직접 메소드를 만들고 모든 터미널 심볼을 직접 다루는 것은 결코 쉬운 일이 아닙니다. 그래서 많은 경우 토큰을 읽어들이는 일은 Lexer라는 툴을 많이 이용하고 파서는 역시 파서를 만들어주는 툴을 많이 사용합니다. 그리고 그런 파서는 LL 또는 LR 파싱 방법으로 구현되어 있습니다. 여기서는 LL 파싱 알고리듬이 어떻게 동작하는지를 설명해 보려고 합니다. 사실 이것을 몰라도 바로 파서생성기를 이용하는 것이 가능하나 RDP 방법을 익힌 다음이라면 체계적인 파싱 알고리듬으로서 LL 알고리듬을 이해하는 것이 어렵지 않습니다.

앞의 글에서 살펴본 문법은 { }으로 반복을 나타내는 확장된 CFG였습니다. 여기서는 그것을 일반 CFG로 바꾸어 LL 알고리듬을 적용해 보겠습니다. 여기서 e는 epsilon을 표현합니다. 즉 넌터미널이 그냥 없어질 수 있는 경우입니다.

S -> St S'
S' -> ; St S' 
S' -> e
St -> id = E
E -> T E'
E' -> + T 
E' -> - T 
E' -> e
T -> F T'
T' -> * F 
T' -> / F 
T' -> e
F -> id 
F -> num 
F -> ( E )

앞의 글에서 문법과 Follow의 개념을 익혔습니다. LL 파싱은 그것을 체계화시킨 방법이라고 볼 수 있습니다.

파싱이란 문법의 유도 과정을 통해 입력 문자열에 매치되는 생성규칙을 적용하면서 유도되는 넌터미널로 트리를 완성해 가는 과정입니다. 이를 위해서는 다음 토큰에 대응하는 유도 과정을 차례로 적용할 수 있어야 되고 대응하는 터미널 심볼이 있으면 입력을 매치시키고 다음 심볼에 대해 또 필요하면 유도를 하는 과정을 거치게 되고 한 생성규칙의 유도가 모두 매치되면 그것을 넌터미널의 부분트리로 대치하고 다음 과정으로 진행하게 해주는 것입니다.

예를 들다면 a = 5 ; b = a + 3 $라는 입력을 가지고 파싱하는 과정을 고려해 보겠습니다. 

• (1) a를 만났으므로 St -> id = E라고 하는 생성규칙에 매치되었음을 알 수 있고 a가 id가 되고 다음 토큰이 =이어야 함을 알 수 있습니다. 이것을 LL 파서에서는 shift라고 합니다. 터미널 심볼이 문법의 생성규칙에 매치되어 처리되고 다음으로 진행되는 것입니다.
• (2) 그럼 a =까지는 입력이 처리되었고 다음 입력인 5를 E라는 넌터미널을 통해 처리해야 합니다. 5는 F -> num에 의해 처리되어야 하는 토큰입니다. 그러므로 E -> T가 되고 T -> F가 되는 유도 과정이 적용되어야 합니다. 그러고 나면 5가 num에 대응되어 처리됩니다.
• (3) 다음 심볼인 세미콜론(;)은 S -> St왼 { ; St }에서 처리되어야 하는 터미널 심볼입니다. 이것을 처리하기 위해서는 St -> id = E가 유도가 끝나고  St가 되어야 합니다. 그리고 나서 ;이 처리되고 다시 St가 다음으로 등장하게 됩니다. 이러한 과정을 LL 파서에서는 reduce라고 합니다. 즉 생성규칙이 처리가 끝나고(서브트리가 완성되고) 왼쪽의 넌터미널이 되면서 트리의 부모 노드로 올라가는 과정이라고 볼 수 있습니다.

이러한 유도 과정은 다음과 같이 표시할 수 있습니다. 여기서 => 는 생성규칙을 적용해 가는 유도 과정을 보여주고 ^는 다음에 유도될 넌터미널을 보여줍니다. 그런데 파싱은 사실은 유도의 과정을 거꾸로 가게 됩니다. 즉 트리를 선방문 순서로 만들어 나가므로 id = 를 매치한 후 다음 토큰 num이 F가 되고 다시 T가 되었다가 E가 된 후 그 전체가 St로 바뀌어 다음 세미콜론을 받게 됩니다. 그래서 토큰을 매치하는 것을 shift 액션, 넌터미널로 바뀌는 것을 reduce 액션이라고 하고 이것을 반복하는 것이 파서가 됩니다.

S => ^ St ; St $
  => id = ^ E ; St $
  => id = ^ T E' ; St $
  => id = ^ F T' E' ; St $
  => id = num ^ T' E' ; St $
  => id = num ^ E' ; St $
  => id = num ; ^ St $
  => id = num ; id = ^ E $
  => id = num ; id = ^ T E' $
  => id = num ; id = ^ F E' $
  => id = num ; id = num ^ E' $
  => id = num ; id = num + ^ T $
  => id = num ; id = num + ^ F T' $
  => id = num ; id = num + num ^ T' $
  => id = num ; id = num + num ^ $
  => id = num ; id = num + num $ ^

그럼 여기서 해결되어야 하는 문제는 문법에서 어느 생성규칙을 적용할 것이냐 입니다. 예를 들면 E'는 + T나 - T가 될 수도 있고 e이 될 수도 있습니다. + T나 - T로 가는 것은 별로 어려울 것이 없습니다. 그러나 e이 문제입니다. 언제 E'이나 T'이 e으로 갈 것인가를 결정해야 합니다. LL 파서에서는 이런 문제를 First와 Follow라는 것을 이용해 해결합니다.

First는 그 넌터미널 심볼이 만들어낼 수 있는 서브트리에서 처음에 올 수 있는 터미널 심볼을 의미합니다. 그러면 우리는 해당하는 심볼을 가진 생성규칙으로 유도해 가면 됩니다. 여기서 중요한 점은 LL(1) 파서가 되기 위해서는 어떤 넌터미널이 가지는 생성규칙들이 같은 First를 가지면 안된다는 것입니다. 즉 E가 다음에 유도할 생성규칙을 판단하기 위해 다음 토큰 하나만 보고, 즉 생성규칙의 우측에 제일 앞에 나오는 심볼의 First를 보고 결정할 수 있어야 한다는 점입니다. 다음과 같은 문법은 LL(1) 파서를 만들 수 없는 문법입니다. St라는 심볼이 id를 보고 앞의 생성규칙을 유도할지 뒤의 생성규칙을 유도할지 알 수 없습니다. 다음 토큰 두 개를 보면 알 수 있으니까 LL(2) 파싱은 가능하겠지요?

 

St -> id = E | id ( Params )

그러면 그것을 Left Factoring이라는 방법을 통해 하나의 생성규칙마다 First가 다 달라지게 문법을 변형해야 합니다.

St -> id St'
St' -> = E | ( Params )

이렇게 바꾸면 id를 보면 일단 St'을 유도한 후 지정문으로 갈지 함수 호출로 갈지 결정할 수 있으므로 LL 파싱이 가능합니다.

그리고 e이 되는 생성규칙은 Follow를 이용해서 판단합니다. 즉 e이 될 수 있는 심볼인데 다음 토큰이 그 심볼의 Follow에 속하면 e으로 그냥 사라질 수 있음을 의미합니다. 여기서도 주의할 사항은 e이 되기 위한 Follow와 다른 생성규칙이 되기 위한 First가 겹쳐도 LL(1) 파싱을 할 수 없다는 점입니다. 다음 예는 그런 문법을 보여줍니다.

E -> T E'
E' -> + T | - T | e
T -> F
F -> num | ( E + Alpha )

이 문법으로 ( 3 + 5 )를 파싱한다면 LL 파서에서는 ( 3 까지를 파싱한 후 E => ... => ( num ^ E' + ) 상태가 됩니다. 그럼 여기서 + T로 가야 할지 아니면 E'이 e이 된 후 + Alpha로 가야 할지 토큰 하나만 보고는 판단할 수 없습니다. 이것을 shift-reduce 충돌이라고 합니다. 즉 First와 Follow가 겹치는데 e이 될 수도 있는 경우 두 가지 생성규칙이 다 가능하므로 LL(1) 파서가 어느 쪽으로 갈지 판단할 수 없는 것입니다.

이런 문제가 없는 문법이 LL(1) 문법이고 이것은 다음에 살펴볼 파서생성기 antlr의 조건이기도 합니다.

그럼 이런 문제가 모두 해결되었다고 하면 이제 우리는 LL(1) 파싱테이블을 만들어볼 수 있습니다. 파싱테이블은 왼쪽에 넌터미널을 행으로 표시하고 위는 터미널 심볼을 열로 가지는 테이블입니다. 그리고 각 셀에는 해당 생성규칙을 적용하여 유도를 할지, 아니면 Follow를 보고 reduce를 할지를 정해 줍니다.

 위의 파싱테이블에서 각 셀에 표시된 숫자는 해당 번호의 생성규칙(오른쪽 문법에서 번호)을 적용하라는 의미입니다. 즉 각 생성규칙의 첫번째에 올수 있는 터미널 심볼에 대해 해당 생성규칙 번호를 써줍니다. 또 그 행의 넌터미널이 e이 될 수 있다면 Follow에 해당하는 심볼에 대해 epsilon reduce 생성규칙을 적용하라는 뜻으로 r과 생성규칙 번호를 씁니다.

이렇게 파싱테이블이 만들어지면 이제 이것을 이용해서 LL 파싱을 수행할 수 있습니다. 파싱과정은 위의 테이블과 파싱스택, 그리고 입력심볼들을 보면서 진행하게 됩니다. 파싱스택이란 (1) 생성규칙을 적용할 유도할 때는 넌터미널을 팝하여 적용할 생성규칙의 우변을 역순으로 푸시해 주는 스택입니다. (2) e 생성규칙을 적용할 때는 넌터미널을 그냥 팝하여 사라지게 합니다. 그리고 (3) 스택의 탑에 있는 터미널 심볼과 입력의 다음 토큰이 일치하면 shift하게 됩니다. 이 스택을 통해 파서는 유도와 shift와 e으로 reduce하는 액션을 적용하며 파싱을 해 나가게 됩니다.

다음 그림은 입력 심볼을 보면서 다음 토큰에 대해 적용할 액션을 선택하고 그것을 적용한 파싱스택의 상태를 보여줍니다. 

이와 같이 LL 파서는 다음과 같은 과정을 거치면서 만들어진다고 볼 수 있습니다.

• (1) LL 파싱이 가능한 문법을 작성 (Left Factoring을 만족하는 CFG를 작성, LL 충돌이 없어야 함)
• (2) 각 생성규칙에 대해 First를 계산하고 e이 될 수 있는 넌터미널에 대해서는 Follow를 계산합니다.
• (3) LL 파싱 테이블을 작성합니다. (여기서 충돌, 즉 한 셀에 여러 개의 생성규칙이 적용될 수 있으면 문법을 수정해야 함)
• (4) LL 파싱을 이용해 입력과 LL 스택의 변화를 보여주는 파싱 과정을 시뮬레이션해 볼 수 있습니다. 이것은 LL 파서 프로그램에 의해서 수행될 것입니다.