[프로그래밍 언어론] 어휘 및 문법 분석 단계

1. 어휘 분석 단계(컴파일러 구성 중 제일 윗 단계)
 - 어휘를 문법적 의미가 있는 단위로 나눈다(lexeme과 token으로 나눠서 저장)
  ex) result = 10 * count + 1
      

 
2. 구문 분석(Parser를 이용한 Parsing 과정)
 - 파스 트리를 만들면서 구문을 분석하는 것으로 2가지 방법이 있다.
  > Top - down : start -> string   // 대표 LL
  > Bottom-up : String -> start     // 대표 LR
 - 토큰이 문법 순서에 맞게 들어오면 승인, 그렇지 않으면 오류를 발생해준다.
 - 대부분의 컴파일러는 Bottom-up방식을 따른다.
 ex) <S> -> a<A>c
       <A> -> a<A>|b
       라는 문법을 가진 것에 aabc라는 사용자 입력이 있었다. 이것이 참인지를 보여라.
        ⓐ Top - down 방식
        문법 순서에 따라서 "유도"를 한다.

         

  
       ⓑ Buttom - up 방식 
       입력을 "축약"하면서 해답을 찾아간다.

       

3. Recursive - Decent Parser 
 - Parser가 자기 자신을 쓸때가 많아서 recursive라는 말이 붙었다.
 - 특징
  ⓐ 각각의 Non-terminal에 대해서 최소 1개씩 sub program이 존재해야 한다.
  ⓑ grammar rule(EBNF) 을 잘 만들면 간단히 작성이 가능하다.
 - left - recursive는 절대 있어서는 안된다.
  > recursion을 없에는 알고리즘에 의거하여 지워야 한다.
  ex) <A> -> <A>b 라는 문법을 함수로 정의하면...
        void A(){
          A();
           ...
         }  // A뒤에 무슨 문장이 와도 무한한 함수 호출로 실행되지 않게 된다.

 - 각각 (Buttom-up, Top-down)에 대한 예
  LL방식은 함수의 정의로 끝난다.

 

  LR방식일 경우는 실행하기 위해서 다음 3가지가 존재해야한다. 
  ⓐ Stack :  현재 Parsing이 어떤 상황인지 보관하는 곳
  ⓑ Input Buffer : 검사하기 원하는 String
  ⓒ Table : 수행하는 작업을 정리해놓은 표

------------------------

마지막 사진은.. 적당한 예가 없어서 강의 노트 내용을그대로 스샷으로...