4. 구문 분석 (Syntax Analysis)

 ★ 파서 만드는 절차 
  - Writing grammar 
  - ambiguous 제거  (top down 이면 recursion 제거)
  - parsing table 생성

 ex) E -> E + T | T   
      T -> T * F | F  (애매모호한 문장)
      F -> ( E ) | id
  
     E -> TE' 
     E'-> +TE' | e
     T -> FT'          (모호성과 왼쪽순환 제거)
     T'-> *FT' | e 
     F -> ( E ) | id

 ★ FIRST & FOLLOW
 - FIRST는 말 그대로 FIRST가 무엇인지.. 
 - ↑ grammar로 본다면 FIRST(E) = FIRST(T) = FIRST(F) = {(, id}, FIRST(E') = {+,e}, FIRST(T') = {*,e}
 - FOLLOW(E) = FOLLOW(E') = {), $} 
  ☞ FOLLOW(Start Symbol) = { $ } & Production의 바디 부분 E의 다음 FIRST는 ')' 
   FOLLOW(T) = FOLLOW(T') = {+, ), $}
  ☞ FIRST(E') = {+}  & FOLLOW(E') = { ), $ }
   FOLLOW(F) = {+, *, ), $}
  ☞ FIRST(T') = { * } & FOLLOW(T') = { +, ), $ }

 ★ Top-down 파싱 테이블을 만들경우 엠티(e)로 갈 때
  - 스택과 입력을 하나씩 구하다가 nonterminal의 Follow가 나올 때.

  
 ★ 하향식 파싱 (top-down)

 ★ 알고리즘
-> X - 스택의 top symbol , a - 포인터 ip 가 가르키고 있는 input symbol , M - 파싱테이블

 repeat (반복)
  if X가 터미널이면
   if X = a 면 
    pop X 하고 포인터 ip가 입력의 다음 심볼을 가르킴
  else error()
 else (X가 넌터미널)
   if M[X, a] = X->Y1 Y2...Yk then begin
     pop X;
     push Yk Yk-1....Y1, Y1이 스택의 탑에 위치
     output the production X->Y1 Y2...Yk
  end

 else error()
until X = $;

 1 .터미널이면 스택의 탑 심볼과 ip가 가리키는 심볼 비교 같으면 둘다 pop 아니면 error
 2. 넌터미널일 경우 스택의 top심볼을 pop 후, 파싱테이블에서 넌터미널에 맞는 입력 기호를 대조하여 찾은 문법을 넣어준다(단 처음심볼을 pop으로). 그리고 넣은 문법을 출력한다.
 3. 터미널 넌터미널이 아닐경우 error()
 4. X = $를 만날때까지 반복

 ★ 상향식 파싱(bottom-up)

   ★ 알고리즘
-> 입력문자열 가리키는 포인터 ip, ip가 가리키고 있는 기호 a. 스택의 맨 위의 상태를 s 

 ip를 입력문자열의 처음 기호에 설정한다.
 repeat forever begin
  if action[s,a] = shift s'면 begin
   스택에 a 푸시하고, 다음에 s' pop
   ip를 다음의 입력 기호로 보낸다.
  end
  
  else if action[s.a] = reduce A->b then begin
    스택에서 2*|b|개수의 기호를 제거
    스택의 맨 위의 상태를 s'라고 함.
    스택이 A를 푸시하고, 다음에 goto[s', A]를 pop
    생성규치 A->b를 출력
  end

  else if action[s,a] = accept then
   return
  else error()
end

 처음에 스택의 맨 위에 초기상태를 넣고 입력 버퍼에 입력문자열을 넣는다. 그리고 accept나 오류를 만날 때까지 무한반복.