Programmer's Digest

Top-down parsing(=Recursive descent Parsing) 정의 : 트리의 맨위에서부터 차례로 파싱 LL(1) Parsing : LL이란 'Left to Right' 와 'Leftmost Derivation'의 앞글자를 딴것이다, (1)은 'lookahead가 한개'를 의미한다. backtracking이 발생하지 않도록 하려면, 뒤에 올문자를 예측할 수 있는 parsing table을 만들면 된다. Bottom-up parsing 정의 : 트리의 맨아래에서부터 차례로 파싱 SLR(1) = simple LR : LR(0)와는 달리 완료 아이템일때 무조건 reduce 하는것이 아니라, 완료 아이템(예:A->r.)이면서 lookahead가 Follow(A)에 포함될 때에만 reduce LALR(1) = Look Ahead LR : LR(0) item은 같지만 ,lookahead만 다른 state가 많은데, 이러한 state를 통합하여 LR(0)의 DFA와 같은 모양을 만될되, 다른점은 lookahead set이 추가로 표현된다는 점이다. LR(1) Parsing : LR이란 'Left to Right'와 'Right-most Derivation의 역순' 그리고 (1)은 'lookahead가 한개'를 의미한다. *Handle 정의 : viable prefix가 production의 right hand side와 일치할경우, viable prefix와 production rule이 handle이 된다. (예를들어, E->n+n이라는 production이 있을때, handle은 "n+n"과 "E->"n+n"이 된다.

먼저 전체적인 과정은 다음 그림과 같다. Scanner의 역할 은 character stream을 가지고 token(의미를 가지는 최소단위)을 생성하는것이다. Parser의 역할 은 일련의 token들을 가지고 syntax tree/parse tree를 생성하는 것이다. Semantic analyzer 는 parse tree를 가지고 프로그램의 의미를 분석하는 일을 한다. Source code optimizer 는 syntax tree를 좀더 간략하게 만들고 three-address code를 좀더 심플하게 만드는 역할을 한다. Code generator 는 target machine으로 변환시키는 역할을 한다. Target code optimizer 는 target code를 개선시키는 역할을 한다.

먼저 컴파일러의 목적 은 다음과 같다. 먼저, 언어는 다음 3가지로 분류할 수 있다. machine language : 컴퓨터가 직접 실행 할 수 있는 프로그램 assembly language : 기계어 프로그램에서 명령과 메모리주소를 심볼 형태로 표시(특정 기계에 종속) high level language : 기계와 독립적, 간결하고 자연어와 유사 컴파일러의 목적은 high level language를 machine language로 번역하는것이다. 컴파일러와 관련된 프로그램은 아래와 같다. Interpreter : 즉시 소스코드를 실행, 컴파일된 코드보다 110배이상 느림 Assembler : 어셈블리어를 기계어로 바꿈 Linker : 컴파일된 코드들을 실행가능한 파일로 묶어줌 Loader : 코드를 메모리에 올려줌(base adddress 기준의 상대주소로 모두 재배치) Preprocessor : 실제 translation 이전에 compiler에 의해 호출(주석 삭제, 외부 파일 include,macro substitution 진행) Profiler : 실행에 관한 통계치들을 수집 아래는 관련된 프로그램과 컴파일러의 흐름도이다. 다음 포스트에서는 구체적인 translation process에 대해 알아보자.

Programming Language를 분류하는 기준중 하나로 '타입을 언제 확인하느냐'에 따라서 구분가능 1) static type 언어 : 컴파일 시점과 같이 실행전 시점에 타입이 올바른지를 체크 ex) C, Java, ... 2) dynamic type 언어 : 실행중에 동적으로 타입을 체크 ex) javascript, python, ...