PLT - Lecture 2 (parsing)

Parsing

: 프로그래밍 언어의 형식을 분석하고, 데이터를 이해하며, 실행방식으로 변환하는 핵심 과정

Abstract syntax tree (AST)

: 분석을 위한 필요한 구문론적 구조를 제공
: 가장 대중적으로 사용되는 tree 구조

AST as List 선언
(node-name node-left node-right)

EXERCISE

1. 2+3 --> (+ 2 3)

2. CFG : <add_expr> -> +
   code : 2+3
   AST as list : (+ (int 2) (int 3))

3. code : A = 2+3
   s-exp : (= A (+ 2 3))
   

4. begin
   a=2;
   c=a+3;
   end

   AST as list : (= a 2), (= c (+ a 3))
   
   AST의 마지막 자식은 항상 terminal이다.

S-expr : (prog (prog (assign a 2)) (assign c (+ a 3)))

Parsing Method

1. Top-down parsing
   : start-symbol 에서 시작하여 점진적으로 입력문자와 일치할 때까지 확장한다.
   : 더 복잡한 코드를 설명하기에 용이하다.
   : 좌측 재귀 처리에 어려움이 있다.
2. Bottom-up parsing
   : 입력 문자에서 시작해서, 점진적으로 start-symbol까지 줄어든다.
   : 구현이 복잡하다.