# 컴파일러

깊게 다루지는 않았고 이론적으로만 참고하였다.

# Syntax 용어

# 프로그램 코드 (code)

문장의 집합

토큰들로 구성된 문자열들의 집합

# 식 / 표현식 (Expression)

1 이상의 피연산자(상수, 변수 등) 들이 연산자와 결합되어 그 계산 결과를 반환하는 식

프로그램 내에서 값을 만들어냄

# 문장 (Statement / Expression Statement)

표현식 등으로 구성되며, 그 결과에 따라 컴퓨터에 명령을 내리게 됨

# Syntactic Sugar

코드를 더 읽기 좋게 표현하는 대체 문법

# 컴파일러의 구조

# 컴파일러 compiler

프로그램 (프로그래밍 언어:코드) -> 컴퓨터에서 실행

must to

코드 -번역(컴파일러)-> 기계어

# 컴파일러의 구조

언어 분석 과정 요약

소스 프로그램
Lexical Analyzer (어휘 분석 : 토큰 분리)
Syntactic Analyzer (구문 분석 : 구문 트리 생성)
Type Checker (의미 분석 : 타입 검사)
Code Optimizer (코드 최적화)
Code Generator (코드 생성)
기계 코드

# 어휘 분석 Lexical Analysis (Scanning)

어휘 분석기 (Lexical Analyze, Lexer)

원시 프로그램을 읽어들여, 정규 문법에 따라 토큰 이라는 의미있는 문법 단위로 분류하는것.

토큰들을 생성하는것

예시

문자열 value
- <id, 1> 토큰으로 사상되는 어휘항목
- 토큰 이름(식별자): id
- 속성값: 1 , 심볼 테이블 내에서 해당 토큰의 위치
- 토큰의 이름이나 속성값은 컴파일러 설계자에 따라 달라질 수 있다.
문자열 =
- <assign, NULL> 토큰으로 사상되는 어휘항목
- 토큰 이름: assign : = 연산자를 가리키는 추상 기호
- 속성값: NULL 심볼 테이블에 입력될 필요가 없음
어휘 분석기가 위의 코드를 모두 토큰으로 사상하면 생성되는 토큰 스트림

어휘항목과 토큰의 정의와 구분이 사이트마다 모호한 경우가 있다. TODO

# 어휘항목 (lexeme)

어휘분석에서, 가장 낮은 단위로써 논리적으로 구분가능한(의미있는) 조각
어휘분석기는 어휘항목을 검출하여 토큰을 생성한다.
예약어, 식별자, 리터럴(문자열, 숫자), 특수기호, 키워드 등

# 패턴 (Pattern)

토큰이 어휘항목을 서술하는 규칙으로써, 정규 문법에 따라 표현된다.

# 토큰 (Token)

데이터쌍 구조 <토큰이름, 속성값>
각 토큰은 토큰의 패턴에 부합하는 어휘항목을 갖는다.
어휘 항목들을 구분할 수 있는 요소들

# 식별자 (Identifier)

프로그램 안에서는, 구성요소 간에 구별/식별성을 주는 이름

변수명, 상수명, 레이블명, 부프로그램명(함수명), 메서드명, 클래스명 등
주로 사용자/프로그래머가 정하는 이름

# 키워드/핵심어 (keyword)

프로그램의 구성단위를 강조한 용어

# 예약어 (reserved word)

의미가 고정되어서, 프로그램 도중에 그 의미가 변경될 수 없음

대부분 키워드/예약어가 같은 의미이나, 드물게 예약어 이지만 키워드가 아닐 수 있음

언어 표준에서 예약어로써 정하기만 했고, 키워드가 되기에는 아직 그 내용/기능이 구체적으로 정해지지 않은 경우

프로그래밍 언어에서는, 미리 정의되는 언어 구성자를 2가지로 구분

재정의 불가능 식별자 : 예약어
재정의 가능 식별자 : 미리 정의되지만 다르게 재정의 가능한 식별자

# 어휘 오류 검출

어휘 오류

소스 코드상에서 정의되지 않은 어휘항목이 발견되었을 때 발생하는 오류
명칭 검증 : 변수명 앞에 숫자가 올 수 없음 등의 변수명 검증 처리
식별자, 예약어 판단, 대소문자 구분, 줄바꿈 등

어휘 분석기가 독립적으로 어휘오류를 검출하는 것은 매우 어렵거나 많은 비용이 소모된다.

if2 (var === 5)

if2 를 if 가 잘못 입력된 것인가?
if2 라는 함수를 호출하는 구문인가?

위 판단은 심볼테이블을 참조해야 가능하다.

따라서 어휘 분석기는 심볼테이블을 생성하고, 구문분석기가 어휘 오류를 검출하는 것이 더욱 일반적이다.

# 구문 분석 / 파싱 (Syntax Analysis / Parsing)

구문분석기 / 파서 (Syntax Analyzer / Parse)

구문 문법을 적용하여 분석을 수행하는 것 주로 표현식, 문장 등 큰 단위들을 처리함

구문적으로 올바르다는 것을 보증
정형화된 형식 (구문 트리) 으로 변환함

# 구문 트리 Syntax Tree / 파스 트리 Parse Tree

소스 코드(문장)의 문법 구조를 그대로 트리 형식으로 옮겨놓은 구조
노드: 어휘 분석기에서 생성한 토큰들
표현: 토큰 간의 우선순위 / 토큰 간의 결합 관계

# 점검 : 문법 준수 여부

토큰 간의 관계를 서술함
구문 구조가 문법 규칙에 맞는지 여부를 따짐

# 출력 : 구문 트리 생성

어휘 분석으로 생성된 토큰을 입력하여
구조화된 구문트리를 생성하는 후처리

통상, 구문 분석이 끝나면 (구문 트리가 생성되면)

컴파일러에서는 그 내부에서만 사용하는 중간 코드 (Intermediate Code) 를 생성한다.
중간 코드를 생성하는 이유는 여러 종류의 프로그래밍 언어에 대응하기 위함이다.

# 파서의 종류

보편적(universal), 하향식(top-down), 상향식(bottom-up)

# 보편적 파싱방법

어떠한 문법도 파싱할 수 있지만 파싱과정이 매우 비효율적이므로 상용 컴파일러에는 적용될 수 없다.

예시: 2 + 3 - 1

# 하향식 파서

구문의 상위 구조로부터 일치하는 부분을 찾기 시작한다.
2 + 3 -> 2 + 3 - 1

# 상향식 파서

주로 컴파일러에서 이용되는 파서
구문의 낮은 수준에서 점차 높은 수준으로 일치하는 부분을 찾는다.
입력 값이 규칙에 맞을 때까지 찾아서 맞는 입력 값을 규칙으로 바꾼다. 부분적으로 일치하는 표현식은 파서 스택에 쌓인다.
입력 값의 처음을 가리키는 포인터가 오른쪽으로 이동

# 의미 분석 Semantic Analysis

지역변수 / 전역변수 구별
변수 선언 - 참조 연결
타입 검사 (Type Checking)
- 피연산자가 연산자에 부합하는지 검사함
의미적으로 올바르지 않은 코드의 유무 검사
- 정수와 문자열의 덧셈, 값을 0 으로 나누는 행동 등

구문 트리와 심볼 테이블에 있는 정보를 이용하여 소스 코드가 언어 정의에 의미적으로 부합하는지 검사함

구문 트리를 중심으로 의미를 부여하여, 코드 생성이 가능하게 함.

구문 트리를 사용하여 실행가능한 중간 코드를 생성하는 것

# 코드 생성 Code Generation

의미 분석을 통해 분석된 소스코드를 목표 기계에 맞는 어셈블리어나 기계어로 변환하는 단계

# BNF 표기법, EBNF 표기법

# 문맥 종속 문법 Context Dependent Grammar : 자연어

한국어, 영어, 독어, 일본어

# 문맥 무관 문법 Context Independent Grammar : 형식 언어

문법과 의미의 분리
프로그래밍 언어들에서, 일반적인(공통적인) 특성들을 더욱 추상화시킨 언어
대개의 프로그래밍 Context-free Language 의 구조
충분히 단순한 구조를 유지 -> 기계의 효율적인 번역
특정 언어의 구문을 명확하게/엄격하게 기술하는 표기법

# 문맥 자유 문법의 용도

프로그래밍 언어의 구문 문법, 통신 프로토콜 동작에 대한 구문 문법

# 문맥 자유 문법의 표기법

BNF, EBNF, 구문도표(Syntax Diagram) 등

# 문맥 자유 문법의 구성

비단말 기호 : 정의할 대상
단말 기호 : 해당 언어에서 직접 사용되는 표현
시작 비단말 기호 : 언어에서 독립적으로 사용되는 단위
각 규칙, 하나의 비단말 기호(정의할 대상)의 정의
- 단말 기호(표현)와 비단말 기호의 조합

# BNF 표기법 Backus-Naur Form

프로그래밍 언어의 구문을 서술할 수 있는 표기법

John Backus 가 Peter Naur 의 도움으로 개발
1963년, ALGOL 60 언어 구문을 기술할 때 처음으로 사용
이후에, Ada, Pascal, C, Java 등 대부분의 프로그래밍 언어의 구문에 대한 표기법으로 사용
규칙
- Symbol ::= Expression (심볼 ::= 표현식)
메타 기호
- ::= ⇒ 정의를 뜻함 (좌변을 우변으로써 정의함)
- | ⇒ 선택/택일(or)을 뜻함
- < > ⇒ 비단말 기호를 뜻함

# EBNF 표기법 Extended Backus-Naur Form

원래의 BNF 에 추가적인 메타 기호 등을 사용하고 확장한 표기법으로 많은 변종이 있음

Small_Alphabet ::= [a-z]
Number ::= [0-9]

# ABNF 표기법 Augmented Back-Naur Form

표준화된 확장 BNF 표기법

# 중간 정리

여기까지 가볍게 읽어 보았으면 다음 내용을 이해해 보자

어휘(token) 는 보통 정규 표현식으로 표현한다.
```
INTEGER : 0|[1-9][0-9]*  
PLUS : +  
MINUS : -  
```
1
2
3

구문은 BNF 형식에 따라 정의한다.

expression := term operation term  
operation := PLUS | MINUS  
term := INTEGER | expression

1
2
3

문법이 문맥 자유 문법(BNF 으로 표기) 이라면 언어는 정규 파서로 파싱할 수 있다.

여기까지 HTML 파서를 이해하기 위한 조금의 궁금증 해결을 위한 공부라고 생각해보자.

# Reference

https://d2.naver.com/helloworld/59361
http://www.ktword.co.kr/abbr_view.php?m_temp1=3673
http://www.ktword.co.kr/abbr_view.php?nav=&m_temp1=4859&id=871
http://www.ktword.co.kr/abbr_view.php?nav=&m_temp1=5787&id=588
http://www.ktword.co.kr/abbr_view.php?nav=&m_temp1=5788&id=588
https://untitledtblog.tistory.com/9?category=670012

← DOM Search HTML Parser →