의미 분석(semantic analysis)과 형 검사

의미 분석

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

- 다음 단계인 중간 코드 생성에 이용하기 위해 자료형 정보를 수집하여 구문 트리나 기호표에 저장하는 것

- 의미 분석에서는 파스 트리가 입력되고, 출력으로는 의미 분석이 이뤄진 파스 트리가 생성

- 구문 지시적 번역(syntax directed translation)을 이용하면 직접 중간 코드를 얻을 수도 있음

 

- 그러나 형식 언어는 의미를 가지고 있지 않으니 뜻 풀이는 크게 중요하지 않음

- 기호표를 직접 작성, 참조하여 변수, 함수 등에 대한 정보를 관리

- 형 검사 수행하여 식별자가 올바르게 사용되는지

 

형 검사

- 각 연산자가 소스 프로그램 규칙에 의해 허용된 피연산자를 가졌는지 검사하는 것

 

의미 분석 과정에서 하는 일

- 상수 정의, 형 정의, 변수의 형 선언 등

 

상수 정의 과정

- 상수의 이름이 기호표에 들어가고, 각 상수는 정의된 값을 기호표에 보관하여 이후 적당할 때 기억 공간을 배정받고 초기값을 가짐

형 정의 과정

- 주어진 생성 규칙의 의미에 의해 형의 해당 자료 구조 구성, 자료 구조 기호표에 보관

- 구성된 자료 구조는 형 설명자(type descriptor)를 만들어서 구성된 형에 대한 자료 구조 크기나 성격 등을 보관, 이후 형들이 기억 공간을 배정받을 때 필요한 정보를 제공하게 함

변수의 형 선언 과정

- 선언되는 변수들이 선언된 형에 의해 설명자를 얻을 수 있어 변수 이름과 형 설명자가 모두 같이 기호표에 들어가며 이때 각 변수는 기억 공간을 배정 받아 해당 형을 구성

 

일반적으로 수식에 대한 연산은 크게 두 가지 종류

형 고정 연산(type specific op) : 프로그래밍 언어에서 피연산자와 연산 결과의 형이 고정되어 있는 연산

일반적 연산(generic op) : 프로그래밍 언어에서 피연산자와 연산 결과의 형이 변할 수 있는 연산

 

a + b 같은 산술식에서 a는 int b는 float이면

형 고정 연산은 에러

일반적 연산은 허용 (형변환)

 

형 변환(type conversion)

- 주어진 자료형의 값을 다른 자료형의 값으로 변환하는 것

- 묵시적 형 변환 : 시스템에서 자동으로 형을 변환

- 명시적 형 변환 : 프로그래머가 명시적으로 형 변환을 요구

 

명시적 형 변환은 cast 연산이라 부름

묵시적 형 변환은 시스템에서 자동으로 형을 변환하는 것으로 자동 변환(automatic type conversion) 혹은 강제 형 변환(coericon)이라 함

 

자동 변환을 하려면 형을 변환해야 하는데 이는 컴파일러 판단이 아니라 언어 정의 시간에 이미 어떤 연산으로 할 건지 결정해 놓음

 

 

기호표(symbol table)

- 식별자에 대한 기호표에는 식별자를 나타내는 문자열, 자료형을 나타내는 속성, 메모리에서 식별자의 위치 등 속성을 나타낸다

1. 식별자 이름은 문자열로 나타낸다. 같은 이름이 여러 개의 블록이나 프로시저에서 사용된다면 이 식별자가 속해 있는 블록이나 프로시저를 나타내는 것이 있어야 한다.

2. 식별자의 레벨, 형식 인자(formal parameter), 배열 등을 나타내준다.

3. 배열의 차원 수, 각 차원의 상한과 하한을 나타내야 한다.

4. 가능하다면 메모리에서 식별자의 위치를 나타내는 오프셋 등이 있어야 한다.

- 기호표는 특정 기호가 가진 속성을 포함하는 하나의 레코드로 구성

 

기호표의 효과적인 구성은 전체적인 컴파일 시간에 많은 영향

- 선형 리스트, 트리, 해시 테이블

 

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

- 시간이 n에 비례, 식별자 찾는 것도 평균적으로 n/2

- n개 식별자 m개 조회, n(m+n)

- 선형 리스트 방법은 프로그램의 크기가 작은 컴파일에 사용.. 장점은 최소한의 메모리를 사용하는 것

 

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

- 각 기호표의 왼쪽과 오른쪽에 2개의 링크 필드를 추가 .. 이진 탐색 트리

- n개 식별자 m개 조회, mlogn

- 식별자 이름의 수가 n일 때 n이 50보다 크면 선형 리스트보다 효율적

 

해시표 구조를 이용한 기호표 구성 (Direct searchng)

- 가장 좋은 효율. 새로 정의된 기호에 대해 해시 함수 써서 그 위치에 삽입

- 해시 함수는 제산법(division), 제곱값 중간법(mid-square), 폴딩법(folding) 등

- n개 식별자 m개 조회, n(n + m) / k

- k는 해시표가 0 ~ k-1 순서를 가진 k개의 단어로 구성되어 있다는 뜻

- 제수를 크게 할 수록 충돌은 줄지만 메모리 낭비

 

 

속성 문법

- 속성과 의미 규칙을 사용하여 문맥 자유 문법을 확장한 것. 각각의 논터미널 기호 또는 터미널 기호의 속성을 결합하여 의미 분석에 이용

- 속성은의 대표적인 예는 변수의 자료형, 식의 값, 메모리에서 변수의 위치, 어떤 숫자의 유효 자릿수 등..

- 이러한 속성을 확정하는 것을 바인딩이라 하고, 그 시간을 바인딩 시간이라 함

- 바인딩 시간이 프로그래밍 실행 이전인 경우 정적 바인딩, 실행 중인 경우 동적 바인딩

- 구문 지시적 정의(syntax-directed definition)는 문맥 자유 문법에 속성과 의미 규칙을 결합한 것. 속성은 문법 기호와 결합하고 의미 규칙은 생성 규칙과 결합

 

X가 문법 기호이고 a가 속성이면 X.a는 특정 파스 트리 노스 X에서의 a값

 

생성 규칙에 해당하는 의무 규칙을 기술할 때 논터미널 기호는 목적에 따라 문자열, 숫자, 자료형 등을 나타내기 위한 다양한 속성을 표현하고 이런 속성을 점(.) 연산자를 이용하여 나타냄

 

예를 들어 논터미널 기호 A의 속성으로 값을 나타내는 value와 기억 공간을 나타내는 addr 속성을 표현하기 위해 A.value와 A.addr로 표기한다. 속성 값은 구하는 위치에 따라 합성 속성과 상속 속성으로 구분

 

합성 속성은 생성 규칙의 왼쪽에 있는 논터미널 기호의 속성이 생성 규칙의 오른쪽에 의해 결정되는 것

상속 속성은 생성 규칙의 왼쪽에 있는 논터미널 기호의 속성을 이용하여 오른쪽에 있는 논터미널 기호의 속성이 결정되는 것

 

각 노드에서 속성 값을 주석으로 보여주는 주석 파스 트리를 만들 수 있음

 

ex. 산술식에 대한 주석 파스 트리

23 * 5 + 4$

---

형 검사

- 만약 어떤 연산자가 부적합한 피연산자에 적용되는 경우에 컴파일러는 에러를 보고하는데 이를 형검사라 함

- 형 검사를 수행하기 위해 컴파일러는 소스 프로그램의 각 요소에 형 표현식을 부여

- 형 표현식이 어떤 논리 규칙의 집합에 부합하는지를 결정하는데, 이 논리 규칙의 집합을 원시 언어의 형 시스템이라 함

 

형 표현식

- boolean, char, integer, real, void가 기본형

- 형 표현식은 이름을 가질 수 있으므로 형 이름도 형 표현식

- 형 표현식에 적용되는 형 생성자도 형 표현식

- 형 표현식을 값으로 가질 수 있는 변수도 형 표현식

 

자료형의 종류

- 기계어로 연산이 정의되어 있는 수치 자료형이나 boolean, char와 같이 구현하기 쉬운 특성을 가진 기본 자료형(elementary data type)을 기본형이라 함 (단순형, simple type)

- 정수를 표현하는 대표적인 방법은 2바이트나 4바이트를 사용한 2의 보수법

- 실수 또한 부동 소수를 표현하는 대표적인 방법은 4바이트나 8바이트를 사용하여 부호 비트, 지수부(exponential part), 맨티사(mantisa)로 나누어 나타내는 것

- 어떤 언어에서는 새로운 자료형 정의 가능. 예로 부분 범위형과 열거형

- 미리 정의된 형의 집합이 주어졌을 때 배열, 레코드, 구조체와 같은 형 생성자를 이용하여 새로운 형 생성 가능

- 이를 구조적 자료형(구조적 형)이라 하며 배열, 레코드, 공용체, 포인터 등..

- 배열형 생성자는 첨자형(index type)과 원소형(component type)을 매개변수로 받아 새로운 배열형을 생성

- 레코드 또는 구조체형 생성자는 이름과 형의 목록을 받아 새로운 형을 생성

 

레코드는 이질형의 원소가 묶일 수 있다는 점에서, 이름을 통해 각 원소를 참조한다는 점에서 배열과 다름

배열의 모든 원소는 동질형이고 첨자를 통해 참조됨

공용체형은 합집합 연산에 대응

포인터형은 다른 형의 값을 가리키는 값으로 이뤄져 있음. 포인터형의 값은 기본이 되는 형의 값이 저장된 메모리 위치의 주소가 됨

 

 

형 시스템

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

- 컴파일러가 수행하는 검사는 정적인 반면 목적 프로그램이 수행될 때 행해지는 검사는 동적이라 함

- 정적 검사에는 형 검사, 흐름 제어 검사, 유일성 검사, 이름에 관계된 검사 등

- 흐름 제어 검사는 제어를 이동시키는 흐름을 검사하는 것이고 유일성 검사는 어떤 객체가 정확하게 한 번만 정의되었는지를 검사

- 같은 이름이 두 번 이상 나타날 수 있는데 이를 검사하는 것이 이름에 관계된 검사

 

견고한 형 시스템은 형 에러를 동적으로 검사하지 않아도 되는 형 시스템

만약 프로그램이 형 에러 없이 실행된다는 것을 컴파일러가 보장할 수 있다면 이 언어의 구현은 강 타입

 

 

형 변환

- 고정 연산(type specific op) : 피연산자에 따라 연산 결과의 형이 고정되어 있는 연산

- 일반적 연산(generic op) : 피연산자와 연산 결과의 형이 변할 수 있는 연산

- 규칙은 언어마다 다양.. 자바는 확장 변환과 축소 변환을 구별

- 하나의 형에서 다른 형으로의 변환이 자동이면 묵시적, 강제 형 변환(coericon)

- 형 변환을 하기 위해 무언가를 명백하게 서술해야 하면 이 변환은 명시적, 캐스트

 

 

치환문의 형 검사하기

- ni = ba * po - 60 + ni / (abc + 50);

- ni, ba, po는 실수형, abc는 정수형

- 일반적인 연산을 허용, 정수형과 실수형의 연산은 정수형을 실수형으로 변환하여 실수형 결과를 나타낸다고 가정

 

ba * po : 문제 없음 (실수형)

60 : 60을 실수형으로 변환 필요

abc + 50 : 문제 없음 (정수형)

ni / (abc + 50) : (abc + 50)을 실수형으로 변환

 

형 검사와 관련된 중복 정의(오버로딩)와 다형형에 대해

- 같은 연산자 이름이 2개의 다른 연산에 사용된 경우 이 연산자는 중복 정의되었다고 함

- 중복 정의의 예로는 산술 연산자. 2 + 3, 2.0 + 3.0 ..

- 다형형이란 하나의 언어 구문에서 2개 이상의 형을 허용하는 것