프로그래밍 언어 처리 - 고수준 언어의 처리 방법(파스트리)

프로그래밍 언어 처리

어셈블리 언어

• 초기 프로그래머들은 각 명령어에 대한 비트 조합을 외워서 작성

• 니모닉(mnemonics)을 통해 명령어 작성

  • 기계어 명령어를 나타내는 단어
  • ADD AX, BX
  • 두 개의 레지스터(AX,BX) 값을 더하는 ADD 명령어를 기계어 명령어 0x02로 변환

• 주소에 이름(label)을 붙이고, 코드에 주석을 달아 쉽게 읽고 이해하는데 도움

• 어셈블러 : 어셈블리 언어로 작성된 코드를 읽고 기계어 코드를 생성해주는 프로그램

  • 변환 과정에서 레이블이나 심볼의 값을 결정해 채워 넣어줌

고수준 언어

• 어셈블리 언어보다 더 높은 추상화 단계에서 작동
• 소스 코드는 컴파일러에 의해 실행
  • 컴파일러는 소스 코드를 기계어로 번역(compile)
  • 기계어 코드를 목적 코드(object code)라고도 함

어휘 분석

• 코드를 기호(문자들)로 부터 단어와 같은 성격의 토큰으로 변환하는 과정
• BNF(배커스-나우르 표기법)
  • 언어를 정의하는 형식적인 방법
  • 인터넷 프로토콜을 정의하는 RFC등에서 사용됨
  • <digit> ::= "0" | "1" | ...
  • <digits> ::= <digit> | <digit><digit>
  • <e> ::= "e" | "E"
  • ::= 왼쪽에 있는 요소를 오른쪽에 있는 요소로 대치할 수 있다
  • | 선택, 연결된 여러 가지 중 하나가 가능

정규식

• 패턴 매칭에서 중추적 역할

• 왼쪽에서 오른쪽으로 처리됨

• [+-]?(([0-9]*\.?[0-9]+) | ([0-9]+\.?[0-9]*))([Ee][+-]?[0-9]+)?

  • [+-] : + 또는 -
  • ? : 바로 앞의 부호가 0번 또는 1번 나타남
  • [0-9] : 0부터 9까지의 숫자
  • * : 바로 앞의 [0-9]를 0번 이상 반복
  • \ : 다음에 오는 문자의 특별한 의미를 없앰
  • . : 소수점
  • + : 바로 앞의[0-9]를 1번 이상 반복
  • | : 또는

파스 트리

• 고수준 언어를 실행하는 방법이 컴파일 말고도 인터프리트 할 수도 있음

• 컴파일 언어는 소스 코드를 구체적인 기계에 맞는 기계어로 변환

  • 같은 프로그램에 대해 다른 컴파일러를 사용하면 다른 대상 기계를 위한 프로그램 만들기 가능

• 인터프리터 언어는 실제 기계에 사용할 기계어를 만들진 않음

  • 대신 가상 머신에서 실행됨
  • 몇몇 인터프리터 언어는 인터프리터에 의해 직접 실행되기도 하고 중간어로 컴파일 되기도 함

• 일반적으로 컴파일이 된 코드는 기계어이기 때문에 더 빠르게 실행됨

  • 컴파일러가 책을 번역해서 기록을 남기는 것이라면 인터프리터는 읽어주는 행위(휘발성)

• 인터프리터로 실행되는 코드는 하드웨어로 구현하기에 힘든 기능 제공 가능

• 일반적으로 컴파일러나 인터프리터는 파스트리를 구성

  • 언어 문법으로부터 만들어낸 DAG(유향 비순환 그래프) 데이터 구조
  • 1 + 2 * 3을 트리로 만들어 순서대로 처리되는 형태

인터프리터

• 프로그래밍 언어의 소스 코드를 바로 실행하는 컴퓨터 프로그램 또는 환경

  • 원시 코드를 기계어로 번역하는 컴파일러와 대비 됨

• 파스트리를 실행하는 역할

  • 연결 리스트를 순회
  • dfs로 재귀적 계산

• 변수와 변수의 값을 심볼 테이블에 저장, 값을 검색 하는 함수 필요

인터프리터 구조

입력 프로그램 -> | 어휘 분석 -> 문법 파싱 | -> 파스트리(중간 언어) -> 기계 백엔드

컴파일러

• 인터프리터와 비슷 하지만, 기계 백엔드 실행 코드 대신 코드 생성기가 들어감(기계어 생성)
  • 코드 생성기는 특정 대상 기계에 대한 기계어 코드를 만들어 냄

최적화

• 대부분의 언어에는 최적화기(optimizer)라는 추가 단계가 파스 트리와 코드 생성기 사이에 들어감
• 최적화기는 파스 트리를 분석하고 이 결과를 활용해 더 효율적인 코드를 생성해내도록 파스 트리를 변환
  • ex) 피연산자가 상수라는 사실을 분석하여 컴파일 시점에 미리 계산해서 실행 시점에 따로 계산 수행을 없앰

# 예시
# before
for (i=0; i<10; i++) {
  x = a + b;
  result[i] = 4 * i + x * x;
}

# after
x = a + b;
optimizer_created_temporary_variable = x * x
optimizer_created_4_times_i = 0;
for (i=0; i<10; i++) {
  result[i] = optimizer_created_4_times_i + optimizer_created_temporary_variable;
  optimizer_created_4_times_i = optimizer_created_4_times_i + 4;
}

• 경우에 따라 최적화를 하면 안되는 경우도 존재
  • 일부 언어에서는 최적화기에 손대지 말아야 할 부분을 알려주는 메커니즘 제공
    • C의 volatile 키워드