카테고리 없음

프로그래밍 언어론 5장

CodeHS 2024. 11. 14. 03:59

컴파일러의 기본 이해와 구조

1. 컴파일러의 정의와 기본 개념

1.1 컴파일러의 정의

  • 고급 프로그래밍 언어로 작성된 원시 프로그램을 기계어로 번역하는 프로그램
  • 목표 컴퓨터에서 실행 가능한 코드 생성
  • 컴파일러 자체도 하나의 소프트웨어 프로그램

1.2 컴파일러의 주요 특징

  • 원시 프로그램을 목적 프로그램으로 변환
  • 기계어 또는 어셈블리 언어 수준으로 번역
  • 하드웨어 의존적인 코드 생성

2. 컴파일러의 기본 구조

2.1 전단부(Front End)와 후단부(Back End)

  1. 전단부 (Front End)
    • 언어 의존적 부분
    • 문법 분석과 의미 분석 담당
    • 중간 코드 생성
  2. 후단부 (Back End)
    • 기계 의존적 부분
    • 코드 최적화
    • 목적 코드 생성

2.2 컴파일러의 단계(Phase)

A. 전단부 단계

  1. 어휘 분석기 (Lexical Analyzer)
    • 별칭: 스캐너(Scanner)
    • 토큰 단위로 분해
    • 정수값으로 변환
    • 심볼 테이블 생성
  2. 구문 분석기 (Syntax Analyzer)
    • 별칭: 파서(Parser)
    • 문법 규칙 검사
    • 추상 구문 트리(AST) 생성
  3. 의미 분석기 (Semantic Analyzer)
    • 의미적 오류 검사
    • 자료형 검사
    • 변수 선언 확인
  4. 중간 코드 생성기
    • 중간 표현 형태 생성
    • 기계 독립적 코드 생성

B. 후단부 단계

  1. 코드 최적화기
    • 실행 효율성 향상
    • 공간 효율성 개선
    • 지역/전역 최적화
  2. 코드 생성기
    • 목적 코드 생성
    • 기계어 명령어 선택
    • 레지스터 할당

3. 오류 처리

3.1 오류의 종류

  1. 구문 오류 (Syntax Error)
    • 문법 규칙 위반
    • 거의 100% 감지 가능
  2. 의미 오류 (Semantic Error)
    • 문법적으로 올바르나 의미적으로 잘못된 경우
    • 부분적 감지 가능
  3. 실행시간 오류 (Runtime Error)
    • 프로그램 실행 중 발생
    • 컴파일 시점에서 감지 어려움

3.2 오류 처리 과정

  • 오류 감지
  • 오류 회복
  • 오류 보고
  • 오류 수정

4. 컴파일러 구현의 특징

4.1 자동화 가능성

  • 전단부: 높은 자동화 가능성
  • 후단부: 하드웨어 의존적 요소로 자동화 제한

4.2 최적화 고려사항

  • 프로그램 의도 유지
  • 실행 속도 향상
  • 최적화 비용 대비 효과
  • 메모리 사용 효율성

컴파일러 자동화 도구

이번 시간에는 5장의 컴파일러 내용 중 컴파일러 자동화 도구에 대해 설명하도록 하겠습니다.

컴파일러의 구조와 자동화 필요성

앞 시간에 우리는 컴파일러의 구조를 살펴보았습니다. 컴파일러는 프론트엔드와 백엔드로 나뉘며, 프론트엔드에는 4개의 페이즈가, 백엔드에는 2개의 페이즈가 있다고 설명했습니다.

최근에는 컴파일러 개발자들이 각 페이즈별로 모든 프로그래밍을 직접 해야 하는 문제를 해결하기 위해, 컴파일러 생성 도구(Compiler Generating Tool)를 개발하게 되었습니다. 이를 컴파일러 컴파일러(Compiler Compiler) 또는 번역기 작성 시스템(Translator Writing System)이라고도 합니다.

자동화 도구 개발 배경

컴파일러 자동화에 대한 연구는 다음과 같은 배경에서 시작되었습니다:

  • 프로그래밍 언어가 계속 새롭게 개발됨
  • 하드웨어가 발달하고 새로운 기종들이 출현
  • 컴퓨터의 응용 분야가 확대됨 (웹 개발, 앱 개발 등)

특히 n개의 프로그래밍 언어와 m개의 서로 다른 하드웨어가 있을 때, 전체 구현에 n × m개의 컴파일러가 필요하다는 점이 중요한 고려사항이었습니다.

주요 컴파일러 자동화 도구

1. LEX (Lexical Analyzer Generator)

  • 1975년 Mike Lesk가 설계
  • 정규 표현(Regular Expression)을 입력으로 받아 토큰을 자동으로 찾아내는 프로그램 생성
  • UNIX 시스템에 기본 포함
  • 입력: 정규 표현과 액션 코드(C 언어)
  • 출력: lex.yy.c (C 소스 프로그램)

2. 파서 생성기 (Parser Generator)

  • 문법과 의미를 기초적으로 검사해주는 자동화 생성기
  • 대표적인 예:
    • YACC (Yet Another Compiler Compiler) - Bell 연구소
    • Stanford, Wisconsin 대학의 파서 생성기
    • KAIST PGS (Parser Generating System)

3. 코드 생성기 (Code Generator)

  • 백엔드 부분의 자동화 도구
  • 세 가지 주요 관점:
    • 머신 디스크립션 (ISA/HDL 사용)
    • 중간 언어 선정
    • 코드 생성 알고리즘
  • 패턴 매칭 방법과 테이블 핸들링 방식을 혼합하여 사용

4. 통합 컴파일러 생성 시스템

  1. PQCC (Production Quality Compiler-Compiler)
    • Carnegie-Mellon 대학의 Wulf 교수 개발
    • Tree 구조 기반의 중간 언어(TCL) 사용
    • 패턴 매칭 방식의 코드 생성
  2. ACK (Amsterdam Compiler Kit)
    • 네덜란드 Amsterdam 대학 Tanenbaum 교수팀 개발
    • EM 중간 코드 사용
    • n × m 개의 컴파일러를 n + m 정도로 줄이는 방식 제안

토큰 인식 이론

기본 개념

  • Letter (L): 알파벳 대소문자
  • Digit (D): 0-9 숫자
  • Special Characters: 연산자 및 특수 기호

유한 상태 기계 (Finite Automata)

  • 상태(State)와 전이(Transition)로 구성
  • 파이널 스테이트(Final State): 종결 상태
  • 정규 문법, 정규 표현식과 동등한 표현력

이론적 관계

정규 표현식(Regular Expression), 정규 문법(Regular Grammar), 유한 상태 기계(Finite Automata)는 서로 변환 가능한 동등한 표현 방식입니다. 자동화 도구에서는 주로 정규 표현식을 사용합니다.

구문 분석 (Syntax Analysis)

1. 구문 분석의 기본 개념

구문 분석(Syntax Analysis)은 입력 스트링이 주어진 문법에 맞는 문장으로 구성되어 있는지 검사하고, 올바른 문장에 대해 파스 트리(Parse Tree)를 구성하는 과정입니다. 구문 분석기(Parser)는 어휘 분석기가 전달한 토큰 스트링을 입력으로 받아 처리합니다.

구문 분석의 주요 기능

  • 문법 규칙 검사
  • 파스 트리 생성
  • 중간 언어 생성을 위한 기초 자료 제공

2. 언어와 문법의 수학적 표현

언어 L은 문법 G에 의해 정의되며, 다음과 같이 표현할 수 있습니다:

  • L(G) = {ω | ω는 문법 G로 생성 가능한 문장들의 집합}
  • 여기서 ω는 터미널 심볼(단어, 토큰)들의 시퀀스

문법의 구성 요소

  • 터미널 심볼: 실제 프로그램의 구성 요소 (키워드, 식별자, 연산자 등)
  • 논터미널 심볼: 문법 규칙을 구성하는 중간 단계의 심볼
  • 생성 규칙: 논터미널에서 터미널로 변환하는 규칙

3. 구문 분석 방법

구문 분석은 크게 두 가지 접근 방식이 있습니다:

3.1 하향식 분석 (Top-down Parsing)

  • 시작 심볼에서 출발하여 입력 문장을 생성
  • 대표적인 방법:
    • 재귀 하향 파서 (Recursive Descent Parser)
    • 예측 파서 (Predictive Parser)
  • 왼쪽 파스(Left Parse) 방식 사용
  • 결정적 파싱이 어려움 (백트래킹 필요)

3.2 상향식 분석 (Bottom-up Parsing)

  • 입력 문장에서 시작하여 시작 심볼까지 축소
  • 대표적인 방법:
    • 선행순위 파서 (Precedence Parser)
    • 이동-축소 파서 (Shift-Reduce Parser)
  • 오늘날 컴파일러의 99.9%가 사용
  • 우측 파스(Right Parse) 방식 사용
  • 더 효율적이고 실용적인 방법

4. 파스 트리와 추상 구문 트리

4.1 파스 트리 (Parse Tree)

  • 문장의 구문 구조를 트리 형태로 표현
  • 유도 트리(Derivation Tree)라고도 함
  • 구문 분석 과정의 모든 단계를 포함

4.2 추상 구문 트리 (Abstract Syntax Tree, AST)

  • 파스 트리에서 불필요한 정보를 제거한 간략화된 형태
  • 중간 코드 생성의 기초가 됨
  • 특징:
    • 리프 노드: 피연산자(식별자, 상수)
    • 내부 노드: 연산자
    • 더 효율적인 저장과 처리 가능

5. 구문 분석에서의 중요 개념

5.1 문장 형식 (Sentential Form)

  • 유도 과정의 중간 단계에 나타나는 문자열
  • 터미널과 논터미널 심볼이 혼합된 형태

5.2 문장 (Sentence)

  • 모든 심볼이 터미널로만 구성된 문자열
  • 최종 프로그램 코드에 해당

5.3 축소 (Reduce)

  • 생성 규칙의 우측 부분(RHS)을 좌측 부분(LHS)으로 대체하는 과정
  • 상향식 분석의 핵심 동작
저작자표시 (새창열림)

'카테고리 없음'의 다른글

  • 현재글프로그래밍 언어론 5장

티스토리툴바