Parser

Parser는 여러 곳에서 쓰이지만, 오늘은 컴파일러 이론 쪽에 중점을 두고 알아보았습니다.

What is Parsing(Parser)?

• 파싱(구문 분석)은 문장을 그것을 이루고 있는 구성 성분으로 분해하고 그들 사이의 위계 관계를 분석하여 문장의 구조를 결정하는 것이다.

• 컴퓨터 과학에서 파싱은 일련의 문자열을 의미있는 토큰으로 분해하고 이들로 이루어진 parse tree를 만드는 과정이다.

  

• 파서는 인터프리터나 컴파일러의 구성 요소 중 하나로, 입력 토큰에 내재된 자료 구조를 빌드하고 문법을 검사한다.
  • 프로그램을 컴파일하는 과정에서 특정 프로그래밍 언어가 제시하는 문법을 잘 지켜서 작성하였는지 검사한다.
  • 예시) XML 파서는 XML 문서가 XML 문법에 맞게 작성되었는지 검사하고, XML 문서를 태그명, 속성명, 속성값 및 엘리먼트 내용 등을 분리하여 해석할 수 있게끔 만든다.

What is Complier?

• 참고

• 컴파일러는 특정 프로그래밍 언어로 쓰여 있는 문서를 다른 프로그래밍 언어로 옮기는 언어 번역 프로그램이다.

    // 컴파일러 의사코드
    function compiler(originCode){
    	// AST = Abstract Syntax Tree
    	let ast = systaxAnalyzer(originCode); // <문법 분석>
    	let targetCode = codeGenerator(ast); // 코드 생성
    	return targetCode;
    }
  

  • 문법 분석(Syntax Analysis): 원본 언어의 문법을 이해하고(토큰화), 원본 언어를 추상 구문 트리로 만든다.

      // 문법 분석 의사코드
      function systaxAnalyzer(originCode){
      	let tokens = tokenizer(originCode); // 토큰화
      	let ast = parser(tokens); // 파싱(추상 구문 트리 생성)
      	return ast;
      }
    

    1. 토큰화(Tokenizing): 원본 언어를 언어 기본 요소들로 분류한다.
       • 토크나이저에서는 구문에서 의미있는 요소들을 토큰으로 쪼갭니다.
       • 렉서는 토큰의 의미를 분석하는 역할을 합니다.
       • 어휘 분석(Lexical Analysis), 스캐닝(Scanning) 등으로 불리기도 한다.
       • 공백이나 주석은 무시하고, 문자들을 언어의 문법에 정의된 토큰들로 분류한다.

        // 토큰화 의사코드
        function tokenizer(originCode){
        	let tokens = [];
        	// LOGIC
        	return tokens;
        }
       

       • 만약 다음과 같은 입력이 있다면, 토큰화를 통해 해당 출력이 나온다.

        // 입력
        while(count <= 100){
        	count++;
        }
                   
        // 출력
        while
        (
        count
        <=
        100
        )
        {
        count
        ++
        ;
        }
                   
        /*
        토큰화: 토큰들은 각각 특정 분류 또는 유형으로 나뉘며,
        while은 키워드, count는 식별자, <=는 연산자라는 식이다.
        */
       

    2. 파싱(Parsing): 토큰화 결과로 나온 언어 기본 요소 스트림을 언어의 문법 규칙에 맞춘다.
       • 보통 문법 규칙은 계층적이기 때문에 파서가 생성하는 출력은 추상 구문 트리(AST: Abstract Systax Tree)라고 불리는 트리 기반 데이터 구조로 기술된다.

        // 파서 의사코드
        function parser(tokens){
        	let ast = {};
        	// LOGIC
        	return ast;
        }
       

       • 토큰화를 통해 만들어진 토큰을 파서를 통과시키면 다음과 같은 AST가 만들어진다.

        statement
        		- whileStatement
        				- while
        				- (
        				- expression
        						- count <= 100
        				- )
        				- statement
        						- {
        						- statementSequence
        								- statement
        										- count++
        								- ;
        						- }
       

       • 토큰화가 단순히 소스코드의 구조 복사라면, 파싱은 구조를 복사하면서 의미도 가져오는 과정이다.

  • 코드 생성(Code Generation): 문법을 통해 프로그램의 의미(semantics)를 찾고, 추상 구문 트리를 대상 언어로 번역한다.

What is AST?

• 추상 구문 트리(AST: Abstract Systax Tree)는 프로그래밍 언어로 쓰여진 소스코드의 추상 구문 구조 트리이다.
• 구문이 추상적이라는 의미는 실제 구문에서 나타나는 모든 정보를 나타내지는 않는다는 것을 의미한다.
• 트리의 각 노드는 소스 코드에서 발생되는 구조이다.

• 다음 코드를 추상 구문 트리로 나타내면 다음과 같다.

    while b !== 0
    	if a > b
    		a := a - b
    	else
    		b := b - a
    return a
  

  

• cs