프로그래밍언어론 - 중간고사 기출문제

2005-2
1. 신택스와 시맨틱스에 대해서 설명하시오.
- 신택스(syntax)는 언어 구성 요소의 외부적인 형태, 즉 문법에 관한 것으로서 언어의 구성 요소들을 결합하여 다른 요소를 만드는 방법을 설명한 것이다.
- 언어의 신택스는 공식적 정의로 표현되는 경우가 많으며 대부분 文脈無關型 문법(context-free grammar)으로써 정의되고 있다.
- 시맨틱스는 언어의 의미이다.
- 신택스의 경우와는 달리 시맨틱스를 공식적으로 정의할 수 있는 방법으로 널리 인정받고 있는 것이 아직은 없지만 실행적(operational) 방법, 함수적 혹은 표시적(denotational) 방법, 공리적(axiomatic) 방법이 대표적이다.
- 실행적 방법에서는 하나의 假想 컴퓨터를 想定하고 프로그래밍 언어의 각 요소가 가상의 컴퓨터에서 어떻게 실행될 것인가로 그 의미를 결정한다.
- 함수적 혹은 표시적 방법에서는 입력을 받아 출력을 계산하는 함수로써 프로그램의 의미를 설명한다.
- 공리적 시맨틱스에서는 실행 전과 실행 후에 가지게 될 변수의 성질(술어 논리의 형태를 취함)로 프로그램의 의미를 설명한다.


2. 모호한 문법을 분석나무와 관련하여 설명하고, 어떠한 문제점을 갖게 되는지 설명하시오.
주어진 입력에 대하여 하나이상의 분석나무가 존재하는 경우, 즉 하나의 입력에 대해 하나이상의 해석방법이 존재하는 경우 모호하다고 한다.
숫자 135의 유도과정을 살펴보면
방법1
<수> ⇒<수><숫자>
⇒<수><숫자><숫자>
⇒<숫자><숫자><숫자>
⇒1<숫자><숫자>
⇒13<숫자>
⇒135
방법2
<수> ⇒<수><숫자>
⇒<수>5
⇒<수><숫자>5
⇒<수>35
⇒<숫자>35
⇒135
과 같이 두 가지 유도 방법이 발생한다. 하나의 문법에 대해 두 가지 이상의 분석나무가 존재할 경우 문제점이 발생할 수 있는데 A-B*C의 유도과정에서 오는 모호성 문제를 분석나무로 풀어보면 다음과 같다.

위와 같이 하나의 문법에 대한 다른 해석으로 상이한 분석나무가 나타나는 문제점이 발생한다. 이런 모호성은 우선순위에 의한 방법이나 결합규칙에 의한 방법을 통해 해결할 수 있다.

3. 정적 범위 규칙과 동적 범위 규칙에 대해서 설명하시오.
이름의 바인딩 결정 규칙에는 다음과 같이 두 가지 종류가 있다.
- 외형적 구조에 의한 결정 규칙
(정적 범위 규칙)
- 실행 순서에 따른 결정 규칙
(동적 범위 규칙)

이중  정적범위(규칙)은 어휘적 범위라고도 하며 외형적 구조에 따라 변수가 포함된 블록부터 바인딩을 시도하는 방법이다. 정적범위규칙은 이해하기 쉽고, 지역변수를 보호하기도 쉬우며 형 오류를 실행 전에 검출할 수 있다. 하지만 다양한 프로시저 호출로 인한 오류 검출의 어려움, 전역 변수의 보호 문제, 또 블록의 내포관계가 논리적 구조를 반영하는 데 미흡하다는 문제점 등을 가지고 있다.
동적범위(규칙)은 비지역 변수에 대한 바인딩이 호출 순서에 따라 이루어지는 방법으로 실행할 때 어떻게 호출되느냐에 따라 관리된다. 즉, 프로시저를 호출한 블록의 호출된 역순으로 추적되어지므로 실제적으로 실행되면서 형 바인딩이 일어나는 방법이다. 동적범위규칙은 프로시저 호출시 매개변수 전달이 편리하고, 바인딩을 위한 자료구조가 필요 없기 때문에 번역기 구현이 용이하다는 장점을 가지고 있다. 하지만 의미가 실행순서에 따라 달라지므로 난해하고, 지역 변수를 보호하기 어려우며, 실행되지 전까지는 변수에 대한 형 조사를 할 수 없으므로 비지역 변수의 형 오류를 검출하기가 어렵다.또 비지역 변수에 대한 접근 시간이 정적 범위 규칙에 비해  증가하는 단점을 가지고 있다.

2004-2
1. 명령형 언어의 특징을 설명하라.
명령형 언어(imperative language)는 가장 많은 종류의 프로그래밍언어를 포함하고 있는 분류로 폰노이만 구조를 가장 잘 추상화 형태이다.
전통적인 프로그램은 변수 값을 변경시키기 위한 명령문을 순서대로 나열한 것이다. 변수가 바로 메모리 셀을 추상화한 것이고 변수에 대한 지정문도 메모리 구조를 반영한 것이며, 명령문의 나열 또는 루프 구조 역시 실행이 다음 위치에 대하여 반복되는 구조를 추상화한 것이다. 명령형 언어는 폰노이만 기계 구조를 반영한 언어이기 때문에 저수준의 기계 특성이 언어의 여러 부분에서 나타나며 프로그램의 정확성을 증명하기가 어렵다.

2. 속성과 바인딩의 정의를 설명하라.
변수, 프로시저, 문 등 프로그램 實體(entity)들마다 갖는 성질을 그 실체의 속성(attribute)이라고 한다.
- 변수의 속성 : 이름, 값, 형, 저장위치 등
- 프로시저의 속성 : 이름, 매개변수, 매개변수 전달 방식, 수행할 코드
- 명령문 : 수행 연산
실체의 속성을 특정한 값으로 정하는 것을 바인딩(binding)이라고 한다.

3. 모호한 문법을 정의하고 모호성이 나타나는 원인과 모호성을 제거하는 방법을 설명하라.
동일한 문자열에 대하여 상이한 분석나무가 나타날 수 있는 문법을 모호한 문법(ambiguous grammar)이라고 한다. 다시말하면 주어진 입력에 대하여 하나이상의 분석나무가 존재하는 경우, 하나의 입력에 대해 하나이상의 해석방법이 존재하는 경우 모호하다고 한다. 모호성을 해결하는 방법으로는 연산의 우선순위를 설정하거나 결합법칙을 설정하는 방법이 있다.
- 우선순위에 의한 모호성의 제거 → 새로운 비종결자의 추가
- 결합규칙에 의한 모호성의 제거
  - 좌결합 규칙 : (A-B)-C → 좌순환 규칙
  - 우결합 규칙 : A-(B-C) → 우순환 규칙

2003-2
1. 프로그래밍 언어의 대표적인 4가지 전형을 들고 그 주된 특징을 간략하게 기술하라.
전형은 명령형 언어, 함수 언어, 논리 언어, 객체지향 언어의 4가지 전형으로 구분된다.

명령형 언어는 폰 노이만 기계 구조를 가장 잘 추상화한 형태이다.
즉, 폰 노이만 구조를 반영한 명령형 언어의 변수가 바로 메모리 셀을 추상화한 것이고, 변수에 대한 지정문도 메모리 구조를 반영한 것이며, 명령문의 나열 또는 루프 구조 역시 실행이 다음 위치에 대하여 반복되는 구조를 추상화한 것이다. 실제로 사용되는 명령형 언어에는 이러한 기본적인 추상에다가 프로그래밍의 편의를 위해 보다 고수준의 추상, 예를 들면 프로시저, 함수, 자료형, 병렬 구조 등이 추가되었다.
이러한 명령형 언어는 폰 노이만 기계 구조를 반영한 언어이기 때문에 저수준의 기계 특성이 언어의 여러 부분에서 나타나며 프로그램의 정확성을 증명하기가 어렵다는 단점을 갖는다.
명령형 언어로는 Fortran, C, Cobol 등이 있다.

함수 언어는 순환 함수(recursive function)에 기초하여 만들어진 것으로서 적용적(applicative) 언어라고도 하는데, 계산을 행하는 주된 방법이 매개변수에 함수를 적용하는 것이다. 함수 언어에는 명령형 언어에 사용되는 형태의 변수 및 이들에 대한 값 지정이라는 개념이 없기 때문에 프로그램에 부작용이 나타날 수 없어서 프로그램이 보다 간단해지고 안정적으로 된다. 함수 언어로는 LISP, Scheme, ML 등이 있다.
 
논리 언어는 술어논리에 기초하고 있는데, 술어 논리는 공리와 규칙으로 새로운 사실을 추론해 나가는 전형이다. 논리 프로그램은 공리, 사실, 추론 규칙, 증명할 정리나 질의로 구성된다. 어떠한 질의가 있게되면 주어진 공리와 사실로부터 추론 규칙에 따라 그 질의가 참인지 거짓인지를 결정하여 그 값을 출력하게 된다.
논리 프로그램에는 어떠한 사실이나 사실들간의 관계를 나타내주는 선언문만이 나타나게 된다. 이와 같이 실행 순서는 필요 없이 사실이나 관계만을 선언하면 되므로 논리 프로그래밍을 선언형 프로그래밍(declarative programming)이라고 한다.
여러 종류의 논리 프로그래밍 언어가 개발되었으나 현재 쓰이고 있는 것은 Prolog뿐이다.

객체지향 언어는 객체들이 모여서 하나의 프로그램이 되며 객체의 상호작용에 의하여 계산을 진행해 나간다. 객체마다 고유의 자료와 연산이 정의되어 있고 프로그램의 진행은 객체에 정의된 연산을 호출하여 이루어진다. 순수한 객체 지향 언어에 가장 가까운 것은 Smalltalk이지만 현재 가장 많이 쓰이는 것은 Java, C++, Eiffel 등이다.


2. BNF에서 사용되는 메타기호로는 어떠한 것이 있는가? 그 의미는 무엇인가?
각진 괄호나 “→”, “?”들은 모두 기호를 위한 기호, 다시 말해서 언어의 기호가 아니라 신택스 정의 표기법을 위한 기호인데 우리는 이를 메타기호(metasymbol)라고 한다.
“→” 기호는 ‘좌측은 우측의 것으로 이루어진다’ 혹은 ‘좌측은 우측과 같다’를 의미한다. 그리고 각진 괄호는 문법 성분의 이름으로서 문법을 나타내기 위해 도입한 일종의 변수라고 생각하면 된다.
괄호 없이 나열된 것은 실제의 단어, 즉 토큰으로서 이 토큰만이 우리가 사용하는 실제 문장에 나타날 수 있는 것이다. 한편 “|” 기호는 선택적인 구조임을 나타낸다. 다시 말해서 이 기호로 분리된 것들 중의 어느 하나가 선택될 수 있음을 나타내는 것이다. 예를 들어 규칙 3은 관형사에 “큰” 또는 “작은”이 올 수 있음을 나타낸다.
BNF란 아래의 3가지의 메타기호만으로 구성된 것을 말한다.
1) ::= : 좌측은 우측의 것으로 이루어지다. 혹은 좌측은 우측과 같다.
2) │ : 선택 혹은 또는의 의미를 나타낸다
3) <> : 문법 구조의 이름과 실제의 단어, 즉 토큰을 구분하기 위한 것이다

3. 바인딩이 무엇인지 정의하고 바인딩 시각의 종류를 설명하라.
- 속성에 실제적인 값이 할당되는 것이 바인딩
☞ 프로그램 언어들이 갖게 되는 공통의 성질이 속성이며 그 속성의 성질이 결정되는 것(특정한 값을 갖게 되는 것)이 바인딩

● 바인딩 : 실체의 속성을 특정한 값으로 정하는 것
- 정적바인딩: 실행이전에 바인딩(정적속성)
- 동적바인딩: 실행시에 바인딩(동적속성)

● 바인딩시각의 종류
<정적바인딩>
언어 정의시 : 자료형의 결정
언어 구현시 : 실제범위 결정
번역시 : 변수의 형
링크시 : 함수의 본체
로드시 : 전역 변수의 위치 결정
<동적바인딩>
실행시 : 변수의 값 결정

2002-2
1. 명령형 언어, 객체 지향 언어, 함수 언어의 주요한 특징만을 간략히 기술하라.
2. 아래에 주어진 BNF 문법에 따라 지정문 “A:=B*(A-B*C)"에 대한 분석 나무를 그려라.
   <지정문> ::= <변수> := <식>
   <식> ::= <식>-<항> | <항>
  <항> ::= <항>*<인수> | <인수>
  <인수> ::= (<식>) | <변수> | <수>
  <수> ::= <수><숫자> | <숫자>
   <변수> ::= A | B | C
  <숫자> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
3. 동적 형 바인딩에 관하여 아는 바를 기술하라.

2001-2
1. 프로그래밍 언어의 대표적인 4가지 전형을 들고 그 특징을 설명하라.
2. BNF에서 사용되는 메타기호로는 어떠한 것이 있는가? 또 그 의미는 무엇인가?
3. 다음은 C 언어의 내포된 블록의 예이다. (가), (나), (다), (라)로 표시된 각 지점에서 가시적인 변수는 어디서 선언된 어떤 것인지를 밝혀라.
main()
{   int a, b, c;  /* 지점 1 */
    ......
  {  int b, c, d;  /* 지점 2 */
      ...... (가)
      {   int c, d, e;  /*지점 3 */
       ...... (나)
      }
      ...... (다)
  }
  ...... (라)
}