개요

컴파일러의 의미 분석과 형 검사에 대해 알아본다. 이 글은 내공 있는 프로그래머로 길러주는 컴파일러의 이해의 내용을 기반으로 함을 미리 밝힌다. 책 내용이 괜찮으니 관심있으신 분들은 사보는것을 추천한다.(필자는 이해관계자는 아님을 밝힌다.)

목차

컴파일러 강의 다른 포스팅은 아래의 링크를 참고하자.

학습목표

  • 의미 분석의 개요
  • 기호표
  • 속성 문법
  • 형 검사

의미 분석이란?

  • 구문 트리와 기호표에 있는 정보를 이용하여 소스 프로그램이 언어 정의에 의미적으로 일치하는지 검사 -> 구문 트리나 기호표에 저장

의미 분석의 개요

  • 형검사란 허용된 피연산자를 가졌는지 검사하는 것
  • 의미 분석 과정에서 하는 일
    • 상수정의
    • 형 정의
    • 변수의 형 선언

기호표

  • 3가지 방법
    • 선형 리스트
    • 트리
    • 해시표

선형 리스트를 이용한 기호표 구성

  • 삽입 : n시간
  • 조회 : n/2
  • 총 작업량 : n개 삽입, m개 조회 -> n(n+m)
  • n,m이 증가함에 따라 효율이 떨어지는 대신 메모리 사용량이 적어 프로그램 크기가 작은 컴파일에 사용됨

트리구조를 이용한 기호표 구성

  • 삽입 : $n * log(n)$
  • 조회 : $m * log(n)$
  • 총 작업량 : $(n+m) * log(n)$

해시표 구조를 이용한 기호표 구성

  • 세가지 기호표 구조중에 가장 효율이 좋은 검색법

속성 문법

  • 속성 문법은 속성과 의미 규칙을 사용하여 문맥자유 문법을 확장
  • 각 논 터미널 기호 또는 터미널 기호의 속성을 결합하여 의미분석에 이용함
  • 바인딩
    • 정적 바인딩
    • 동적 바인딩

구문 지시적 정의의 생성 규칙에 대한 의미 이해

합성속성, 상속 속성

산술식에 대한 주석 파스 트리 만들기

형 검사

  • 만약 어떤 연산자가 부적합한 피연산자에 적용되는 경우에 컴파일러는 에러를 리포트하는데 이를 형검사라고 함
  • 형 표현식
    • 기본형은 형 표현식이다. boolean, char, integer, real, void가 기본형이다.
    • 형 표현식은 이름을 가질 수 있으므로 형 이름도 형 표현식이다.
    • 형 표현식에 적용되는 형 생성자도 형 표현식이다.
    • 형 표현식을 값으로 가질 수 있는 변수도 형 표현식이다.

자료형의 종류

형 시스템

  • 형 시스템은 형 표현식을 프로그램의 여러 부분에 할당하는 규칙의 모임을 말함
  • 형 검사기는 이런 형 시스템을 구현한 것

형 변환

  • 연산은 두 가지 형태
    • 형고정 연산(type specific operation) 은 피연산자에 따라 연산 결과의 형이 고정
      되어 있는 연산이다.

      • 피연산자의 형이 다르면 바로 에러 메시지를 내보낸다.
    • 일반적 연산(generic operation) 은 피연산자와 연산 결과의 형이 변할 수 있는 연산을 말한다.
  • 일반적 연산의 형 변환 규칙
    • 정보를 보존하는 확장(widening) 변환
      • int는 float로 변환
    • 정보를 잃을 수 있는 축소(narrowing) 변환
  • 변환의 종류
    • 하나의 형에서 다른 형으로의 변환을 컴파일러가 자동적으로 수행한다면 이 변환 은 묵시적(implicit) 이다. 묵시적 형 변환은 강제 형 변환(coercion) 이라고도 하며 많은 언어에서 확장 변환만 허용한다.
    • 형 변환을 하기 위해 프로그래머가 무언가를 명백하게 서술해야 한다면 이 변환은 명시적(explicit) 이다. 명시적 형 변환은 캐스트(cast) 라고도 한다.

치환문의 형 검사하기 예제

형검사

테스트

기호표 자료구조 중에 선형리스트, 트리, 해시표의 효율성 비교 설명

  • 선형리스트
    • 메모리 사용량이 적어 프로그램 크기가 작은 컴파일러에 적합
    • n과 m이 증가함에 따라 효율이 떨어짐
  • 트리
    • 이진트리로 구성
  • 해시표
    • 가장 효율적인 검색법

해시 함수 적용의 문제

해시 충돌이 발생할 가능성이 있음

해시 충돌 문제 해결방법

해시표에 충돌을 일으킨 식별자를 연결 리스트로 저장

형검사와 형 변환에 대해 설명

  • 형검사 : 어떤 연산자가 부적합한 피연산자에 적용되는 경우 컴파일 에러를 리포트 하는 것
  • 형 변환 : 묵시적/명시적으로 피연산자의 결과에 따라 형이 변하는 것을 말함

10 + 5 * 8$에 대한 주석 파스트리

ni = ba * po – 60 + ni / (abc + 50);에서 ni와 ba는 실수형, po와 abc는 정수형이라고 하자. 정수형과 실수형의 연산은 정수형을 실수형으로 변환하여 실수형 결과를 나타낸다고 가정하고 연산