Browser_Compiler

컴파일러#

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

Syntax 용어#

프로그램 코드 (code)#

문장의 집합

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

식 / 표현식 (Expression)#

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

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

문장 (Statement / Expression Statement)#

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

Syntactic Sugar#

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

컴파일러의 구조#

컴파일러 compiler#

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

must to

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

컴파일러의 구조#

image

언어 분석 과정 요약

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

어휘 분석 Lexical Analysis (Scanning)#

어휘 분석기 (Lexical Analyze, Lexer)

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

  • 토큰들을 생성하는것

예시

image

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

image

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

어휘항목 (lexeme)#

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

패턴 (Pattern)#

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

토큰 (Token)#

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

image

식별자 (Identifier)#

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

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

키워드/핵심어 (keyword)#

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

예약어 (reserved word)#

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

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

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

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

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

어휘 오류 검출#

어휘 오류

  • 소스 코드상에서 정의되지 않은 어휘항목이 발견되었을 때 발생하는 오류

  • 명칭 검증 : 변수명 앞에 숫자가 올 수 없음 등의 변수명 검증 처리

  • 식별자, 예약어 판단, 대소문자 구분, 줄바꿈 등

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

if2 (var === 5)

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

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

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

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

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

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

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

구문 트리 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 표기법

중간 정리#

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

  1. 어휘(token) 는 보통 정규 표현식으로 표현한다.
    INTEGER : 0|[1-9][0-9]*
    PLUS : +
    MINUS : -
  2. 구문은 BNF 형식에 따라 정의한다.
    expression := term operation term
    operation := PLUS | MINUS
    term := INTEGER | expression

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

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

Reference#

Last updated on