LL(1) Parser에 대한 개인적인 정리 컴파일러


파서는 렉서(스캐너)로 토큰단위로 자른 문자열을 심볼로 인식해서 파싱트리로 만들어주는 역할을 한다.

컴파일러는 파싱 트리를 가지고 입력으로 들어온 문자열들이 문법적으로 타당한지의 여부를 검사하게 된다.

즉, 파서는 각 문자열이 스캐너에 의해 토큰으로 나뉜 것에 의미를 부여하고 문법(CFG)의 타당성을 검사하는 역할을 한다.

파서에는 두 가지 종류로 나뉘게 되는 데 상향식 파서와 하향식 파서로 나뉘게 된다.

하향식 파서는 시작 심볼로 시작해서 주어진 입력문자열(터미널 심볼)로 만드는 과정이고, 상향식 파서는 주어진 입력문자열에서

시작 심볼까지를 만드는 과정이다. 즉, 하향식 파서는 파스 트리를 루트노드에서 부터 시작해서 트리를 만드는 과정이고, 상향식 파

서는 단말 노드에서 부터 시작해서 트리를 만드는 과정이다.

지금 내가 정리 할 부분은 하향식 파서이다.

하향식 파서는 predicctive 파서라고 부른다. 이 파서는 어떤 상태에서나 파스 트리의 다음 낮은 단계를 예측하려고 한다. 이러한

예측은 입력의 다음 토큰과 현재의 트리를 검사한 후, 다음에 시도할 생성규칙을 선택하는 것으로 행해진다.

따라서, 파서는 좌측유도(입력 토큰을 좌측부터 읽어서 변환 시키기 때문..)를 실시하면서, 위에서 아래로 파스 트리를 구축한다.

하향식 파서는 두 가지 방법으로 접근하게 된다.

1.재귀하강파싱

 - 재귀 하강 파싱은 파스 트리를 구성하기 위해서 재귀적인 방법을 사용해서 생성한다. 문법에 있는 각각의 난터미널에 대해서 그

난 터미널을 구문분석하는 프로시져를 가진다. 이 프로시져들은 입력을 읽으면서 생성규칙의 오른쪽에 있는 터미널 심볼들을 맞추

어보거나, 입력을 읽는 프로시져나 터미널 심볼들을 맞추어보는 프로시져를 호출한다. 이 방법은 좌측 재귀 방법을 제거해야한다.

왜냐하면 S -> SR 일 경우 각 심볼마다 프로시져가 있는 데, S심볼에 대한 프로시져는 무한루프에 빠지기 떄문이다.

그래서 왼쪽 반복이 제거되도록 해서 프로시져를 작성해야된다.

2.LL(1) 파싱

 - LL(1)파서는 구문 분석을 위해 테이블을 사용한다. 첫번째 L은 입력 스트링이 왼쪽에서 오른쪽으로 스켄됨을 의미한다. 

두 번째 L은 좌측우선유도로 구성됨을 의미한다. 1은 하나만 미리본다는 뜻이다. 단지 단 하나의 다음 심볼을 보겠다는 의미이다.

위에 재귀하강파싱 방법에서는 재귀하강파싱만의 문법(좌측 재귀 방법을 제거하기..)이 있듯이, LL파싱에서도 자기만의 문법이있다.

먼저 문법이 left-factoring이 되어야 한다. 가령, 문법이 E -> T+E | T , T -> int | int * T | ( E ) 일 경우, 

E에서 T로의 두 개의 경우로 분기하게 된다. 그리고 T가 두 개의 int로 분기하게 된다. left-factoring은 같은 기호들을 prefix로 가지는

2개 이상의 생성 규칙이 존재할 때에, 새로운 중간 생성 규칙을 두어서 하나의 prefix에 대해 1개의 생성 규칙으로 변환 시켜주는 것이다. 

만약에 그렇게 하지 않을 경우에는 결정적이지 못하고, 백트래킹을 하게 되므로 효율성이 많이 떨어지게 된다.

A -> aB1 | aB2 | aB3  일 때,

A -> aA'
A' -> b1 | b2 | b3 .. 

이렇게 바꾸면 된다.

LL(1)파싱은 테이블과 스택을 이용해서 하향식으로 파싱을 하게 된다. 테이블은 로우 인덱스는 논터미널 심볼로 구성되어있고,

테이블의 칼럼인덱스는 논터미널 심볼과 $로 구성이 된다. 파싱하는 방법은 아주 간단하다. 처음에 스택에 시작 심볼과 $를 넣는다.

>> 테이블을 이용한 파싱방법

1. 스택의 TOP과 입력문자열을 비교해본다.

1-1. 스택의 TOP과 입력 문자열이 같을 경우, 스택 TOP을 팝시키고, 다음 문자를 읽는다.

1-2. 스택의 TOP과 입력 문자열이 다를 경우,

   1-2-1 :  스택의 TOP과 입력 문자열에 T[S_TOP, Input] = a가 있을 경우 스택의 탑을 팝시키고, a를 스택에 넣는다.
   1-2-2 :  스택의 TOP과 입력 문자열에 T[S_TOP, Input] = NULL 일 경우 에러 처리시키면 된다.

2. 스택이 전부 빌때까지 계속 1번 과정을 반복한다.


>> 테이블을 만드는 방법

테이블은 각 논터미널 심볼에 대해서 FIrst,Follow set을 구한 다음에,  테이블 생성 알고리즘을 거쳐 각 칸마다 내용을 채워넣는다.

1. First Set 구하기

First(X) = { t | X ->* tA} U { eipsilon | X->* eipsilion} <- 이 경우는 S -> AB , A-> x | epsilon  일 경우 S의 FIRST는 B의 FIRST가 된다.

예  :  E -> TX, X -> +E | Epsilon , T -> ( E ) | int Y , Y -> *T | epsilon  일 때,

FIRST(E) = { ( , int }
FIRST(T) = { ( , int }
FIRST(Y) = { *, epsilon}
FIRST(X) = { +, epsilon}

2. Follow set 구하기

Follow(X) = { t | s -> *BXtY} , 여기서 B는 터미널 혹은 논터미널 심볼이다. 논터미널 심볼 X 다음에 터미널 심볼 t가 Follow(X)의 원소가 된다.

(1) IF X -> AB then FIrst(B) is Subset of Follow(A) : X -> AB ->* Atq 가 될 경우 Follow(A)는 t가 된다. 그리고 First(B)도 t가 되므로

First(B)는 Follow(A)의 Subset이 된다. <- 여기서는 왜 그런 관계가 되는지 아직 이해가 안된다.

(2) IF X->AB then FOLLOW(X) is Subset of Follow(B) :  S -> Xt ->ABt   but b go to epsilon FOLLOW(X) is subset of Follow(A)
(3) IF X is Start Symbol $ is element of Follow(X)


예  :  E -> TX, X -> +E | Epsilon , T -> ( E ) | int Y , Y -> *T | epsilon  일 때,

Start Symbol은 E 이므로, 먼저 Follow(e) = { $,  } 를 쓴다.

그리고 T -> ( E ) 에서 E 다음에 터미널 심볼 ) 이 나오므로, Follow(e) = { $ , ) , } 를 쓴다. 

X->+E에서  FOLLOW(X) < FOLLOW(E)가 된다. 그리고 E->TX에서 FOLLOW(E) < FOLLOW(X)가 된다. FOLLOW(X) == FOLLOW(E)가 되고

더 이상 E에 관해서 찾을 수 있는 것이 없으므로 FOLLOW(E) = { $, ) }, FOLLOW(X) = {$,)} 가 된다.

FOLLOW(T)를 찾아보자. 먼저 E->TX에서 X가 EPSILON에 갈수있으므로 FOLLOW(T)는 FOLLOW(E)를 서브셋으로 갖는다.

FOLLOW(T) = { $, ) , } 이고, E->TX->T+E가 되므로 FOLLOW(T) = { $, ), + , }이 된다. 

FOLLOW(Y)를 찾아보자.  T-> int Y 에서 FOLLOW(T)는 FOLLOW(Y)의 부분집합이 된다. 그리고 Y->*T에서 FOLLOW(Y)는 FOLLOW(T)의

부분집합이 된다. 그래서 FOLLOW(Y)와 FOLLOW(T)는 동치가 되서 FOLLOW(Y) = { $, ), +}이 된다.

정리해보면 

FOLLOW(E) = { $, ) } , FOLLOW(X) = {$,)} , FOLLOW(T) = {+,$,)}, FOLLOW(Y) = {+,$,)}이 된다.

3. Table 생성하기

For each Production A -> a(terminal or non terminal) in G do :

(1) terminal t is element of First(a) : if a lengh is more than 1, select to first character of a.
 
 T[A,t] = a 

(2) if epsilon is element of  FIRST(a), and for each t element of Follow(A)

 T[A,t] = a

 (3) if epsilon is element of FIRST(a) AND $ is element of FOLLOW(A)

  T[A,$] = a

이 세가지 방식으로 채워놓으면 된다. 



 

덧글

댓글 입력 영역