컴파일러구성 - [제14강] 의미분석과 중간언어

컴파일러구성 - [제14강] 의미분석과 중간언어

기호표 ·의미분석, 중간언어 ·중간코드 종류 ·구문지시적 변환

컴파일러 용어정리

• 의미분석
  구문분석 단계로부터 얻어진 파스트리를 중심으로 의미를 부여하여 코드 생성이 가능하게 하는 일
• 기호표
  식별자에 대한 자료구조 선형리스트, 트리, 해쉬표의 3가지 방법을 이용하여 구성할 수 있다.
•  중간코드
  중간코드를 이용하여 기계와 독립적인 최적화가 가능하고 기계코드로 바뀐 상태에서 행하는 것보다 훨씬 효율적인 최적화 수행이 가능. 후위표현, 3-주소 코드, 트리구조, 가상적인 기계코드 등 여러 종류가 있음
• 구문지시적 변환
  구문분석을 하면서 중간코드를 생성하는 방법
  context-free문법의 각 생성규칙들과 그와 결합하여 쓰여지는 부프로그램이나 의미수행 코드들로 구성

요점정리

1. 의미분석을 통하여 구문분석 단계로부터 얻어진 파스트리를 중심으로 의미를 부여하여 중간코드 생성이 가능하게 한다. 의미분석 과정에서는 상수정의, 유형정의, 변수의 유형선언, 프로시저 선언 등이 이루어진다.
2. 기호표는 의미분석 단계에서 기호표에 수집된 속성과 참조된 식별자의 사용이 타당한지를 검사하는 역할을 한다. 기호표에서 식별자와 관련될 수 있는 자료는 식별자 이름, 유형, 레벨, 오프셋, 차원수 등이며 특히 기호의 유형은 의미분석시 유형검사를 위해 중요한 요소가 된다.
3. 기호표의 구성은 전체적인 컴파일 시간에 많은 영향을 끼치며, 기호표는 크게 선형리스트, 트리, 해쉬표의 3가지 방법을 이용하여 구성할 수 있다. 이 중에서 해쉬 기호표 구성방법이 가장 효율이 좋은 검색법을 갖는 것으로 알려지고 있다.
4. 중간코드를 이용하면 기계와 독립적인 최적화가 가능하고, 기계코드로 바뀐 상태에서 행하는 것보다 훨씬 효율적인 최적화를 수행할 수 있다. 이러한 중간코드는 후위표현, 3-주소 코드, 트리구조, 가상적인 기계코드 등 여러 종류가 있다.
5. 후위표현은 산술연산자를 괄호 사용없이 표현할 수 있는 형식으로 구문트리의 선형화된 표현방법이다. 인터프리터를 사용하는 언어의 중간언어로 적합하지만 최적화를 위해서는 부적합한 중간언어이다.
6. 3-주소 코드는 상용 컴파일러에서 가장 많이 사용하는 중간언어로서 코드를 재구성하기에 편리하기 때문에 코드를 최적화하는 컴파일러에서 주로 사용된다. 이 3-주소 코드는 연산자와 피연산자를 위한 필드와 함께 레코드로 구현될 수 있는데, triple, quadruple 혹은 간접 triple의 형태로 구현된다.
7. 구문지시적 변환(syntax-directed translation)은 구문분석을 하면서 중간코드를 생산하는 방법이다. 이는 context-free 문법의 각 생성규칙들과 그와 결합하여 쓰여지는 부 프로그램이나 의미수행(semantic action) 코드들로 구성된다. 구문지시적 변환의 장점은 컴파일러의 설계자가 원시언어의 구문구조에 따라 직접 중간언어 생성을 표현할 수 있다는 것이다.

연습문제

• 

  다음은 의미분석 과정에서 하는 일들에 대한 설명이다. 틀린 것은?

  답을 체크하세요

  1. 상수의 이름이 기호표에 들어가고, 각 상수는 정의된 값을 기호표에 보관하여, 이후 적당한 기회에 기억장소를 배정받고 초기값을 갖는다.
  2. 주어진 생성규칙들의 의미에 의하여 유형의 해당 자료구조가 구성되며, 유형설명자를 만들어서 이후 유형들이 기억장소 배정을 받을 때 필요한 정보를 제공하게 한다.
  3. 선언되는 변수들이 선언된 유형에 의하여 설명자가 주어지고 변수명칭과 유형 설명자가 모두 같이 기호표에 들어가며 기억장소를 배정 받는다.
  4. 문법의 각 생성규칙들과 그와 결합된 의미수행코드들을 구성하고 호출되면 중간코드를 만든다.

  정답 :

  ④

  4번은 중간코드 생성 방법 중에서 구문지시적 변환에 대한 설명이다.

• 

  다음은 의미분석에 대한 설명이다. 빈칸 ‘가’, ‘나’, ‘다’ 에 각각 알맞은 것을 순서대로 나열한 것은?
  

  연습문제 설명

  (  가  ) 이외의 (  나  )의 의미분석은 (  다  ) 를 이용하여 중간코드를 생산하는 일을 하게 된다. 여러 가지 형태의 문들을 원래 뜻과 같은 중간코드로 생산하는 것이 의미분석의 목표가 된다.

  답을 체크하세요

  1. 선언문-실행문-기호표
  2. 선언문-실행문-해쉬함수
  3. 선언문-실행문-트리구조
  4. 선언문-실행문-선형리스트

  정답 :

  ①

  선언문 이외의 실행문의 의미분석은 기호표를 이용하여 중간코드를 생산하는 일을 하게 된다. 여러 가지 형태의 문들을 원래 뜻과 같은 중간코드로 생산하는 것이 의미분석의 목표가 된다.

• 

  다음은 기호표 구성에 관한 설명이다. 틀린 것은?

  답을 체크하세요

  1. 선형 리스트 구조: n개의 이름에 대한 삽입과 m개의 조회에 대한 모든 시간은 cn(m＋n)이다. 단, c 는 연산에 필요한 시간
  2. 이진트리 구조 : n개의 이름을 삽입하는 데 필요한 시간은 n log n이고, m개의 조회를 하는 데 필요한 시간은 m log n이다.
  3. 이진트리 구조 : 삽입과 조회에 필요한 시간은 (n＋m)log n에 비례한다. 만일 n이 50보다 크다면 선형리스트보다 효율적이다.
  4. n개의 식별자 이름의 추가와 m개의 조회가 있다면, 전체적으로 필요한 시간은 (n＋m)log k 에 비례한다. 단, 해쉬표가 k개의 단어로 구성되어 있다.

  정답 :

  ④

  시간은 (m＋n) 에 비례한다.

• 

  번역과정에서 중간언어를 사용함으로써 얻어지는 장점이 아닌 것은?

  답을 체크하세요

  1. 원시 프로그램의 이식성(portability)을 증가시킬 수 있다.
  2. 고급 원시언어와 저급 목적코드간의 의미적 차이를 이어주는 교량 역할을 중간코드가 담당함으로써 번역과정이 좀더 쉽게 표현되고 효율적으로 처리될 수 있다.
  3. 중간코드를 이용하여 최적화를 수행함으로써 기계와 독립적인 최적화가 가능해졌으며 또한 기계코드로 바뀐 상태에서 행하는 것보다 훨씬 효율적인 최적화를 수행할 수 있다.
  4. 중간언어를 사용함으로써 목적코드로 직접 번역하는 것보다 효율적인 코드를 생산한다.

  정답 :

  ④

  목적코드로 직접 번역하는 것보다 중간코드 생성과정을 거치므로 컴파일 시간이 더 소요되고 비효율적인 코드를 생산한다.

• 

  다음 중 인터프리터에서 많이 사용되며 코드 이동을 할 수가 없어서 최적화에는 부적합한 중간언어는?

  답을 체크하세요

  1. 후위표현
  2. triple 표현
  3. 간접 triple 표현
  4. quadruple 표현

  정답 :

  ①

  후위표현은 산술연산자를 괄호 사용 없이 표현할 수 있는 형식으로서 연산자 스택을 이용하여 쉽게 연산할 수 있고 원시프로그램으로부터 변환이 비교적 쉽고 빠르게 이루어질 수 있기 때문에 인터프리터를 사용하는 언어의 중간 언어로 적합하다. 그러나 코드 이동을 할 수가 없어서 최적화에는 부적합한 중간언어이다.

• 

  다음은 A := -B*(C+D)를 3 주소 코드로 표현한 것이다. 이 방법의 이름은?
  

  연습문제 설명

  번호	op	피연산자 1	피연산자 2	결과
  (0)	uminus	B		T1
  (1)	+	C	D	T2
  (2)	*	T1	TZ	T3
  (3)	:=	T3		A

  답을 체크하세요

  1. triple
  2. 간접 triple
  3. U코드
  4. quadruple

  정답 :

  ④

  quadruple 방법이다. 

• 

  구문분석을 하면서 중간코드를 생성하는 방법은?

  답을 체크하세요

  1. 프리프로세서
  2. 구문지시적 변환
  3. 파스 트리
  4. 의미수행 규칙

  정답 :

  ②

  구문지시적 변환(syntax-directed tanslation)은 구문분석을 하면서 중간코드를 생산하는 방법이다. 이는 context-free 문법의 각 생성규칙들과 그와 결합하여 쓰여지는 부프로그램이나 의미수행(semantic action) 코드들로 구성된다. 장점은 컴파일러의 설계자가 원시언어의 구문구조에 따라 직접 중간언어 생성을 표현할 수 있다는 것이다.