프로그래밍언어론 2023-04-04 수업정리

Flow

• Language - Syntax Review
• Language - Semantics

Language - Syntax Review

---

• 프로그래밍 언어의 설계는 Syntax와 Semantics로 나눌 수 있다.

문법의 표기

• Syntax는 CFG또는 BNF표기를 통해 나타낼 수 있으며 둘은 동치이다.
• 어떤 문법 G는 {N, T, P, S}인데 이때 P(Production Rule)을 CFG, BNF로 표기한다.

구문 트리

• Production Rule에 따라 derivation 과정을 tree형태로 나타낸 것이 구문 트리이다.
• 구문 트리는 추상 구문 트리와 파스 트리가 있다.
  • 추상 구문 트리 : 터미널 심볼만을 트리 형태로 나타낸 것이다.
  • 파스 트리 : 유도 과정을 모두 트리 형태로 나타낸 것이다.

문법의 모호성

• 문법 G의 Production Rule에 따라 생성되는 파스 트리가 2개 이상일 경우 이 문법은 모호한(Ambiguous) 문법이라고 한다.
• 모호성은 문법의 속성이며, 모호성을 제거하기 위해서는 아래와 같은 두 가지 방법을 사용하면 된다.
  • 결합 방향 명시 : 새로운 N을 생성하여, CFG에서 N에 대해 좌결합, 우결합을 명시하여 N이 특정 위치에 일관적으로 위치하도록 명시한다.
  • 우선순위 명시 : 새로운 N을 생성하여, 유도 과정에서 우선순위를 명시한다.

lambda expression

q = x!=0 ? (y/x) : y;

• 위의 C++ statement를 추상 구문 트리로 나타내면 아래와 같다.
• 이는 아래와 같이 generalized list로 표현할 수 있다.

  (= q
  	(?: (!= x 0)
  		(/ y x)
  		(y))
  

• Scheme Code에서는 labmda expression을 사용하여 아래와 같이 표현한다.

  (define f
  	(lambda (x y)
  		(if (not (= x 0)) (/ y x)
  		y)))
  (define q (f x y))
  

Language - Semantics

---

• Semantics는 Syntax에 비해 매우 복잡하고, 표현에 있어 여러 가지 방법이 존재한다.
• Semantics는 크게 Static Semantics와 Dynamic Semantics로 구분할 수 있다.
  • Static Semantics : 컴파일 시간에 검사 가능함
    • Attribute Grammar
  • Dynamic Semantics : runtime에 검사 가능함
    • Operational Semantics
    • Denotational Semantics
    • Axiomatic Semantics
• 다음 C++언어 구문을 살펴보자

  q = (x==0) ? (y/x) : y;
  

  • 위 구문에서 (y/x) 와 y의 type이 같아야 한다.
  • 또한, x와 0은 서로 비교 가능해야 한다.(compatiable)
  • 마지막으로, (x!=0)이 bool 타입이어야 한다.
  • 이러한 조건들은 컴파일 이전에 확인 가능하다. -> Attribute Grammar를 이용하여 compile time에 검사가 가능하다.
  • 하지만 x가 0일 경우 (y/x)를 수행해야 하는데, 이렇게 되면 zero division에러가 발생한다.
  • 이는 컴파일 타임에 검사가 불가능하다. -> Dynamic Semantics를 통해 확인해야 한다.

Static Semantics

• CFG의 한계를 넘어서는 특성을 검사해야 하는 경우 정적 의미론 또는 동적 의미론을 이용하여야 한다.
• 정적 의미론은 Attribute Grammar를 통해 검사 가능하다.
• 영역 규칙, 타입 검사 규칙 등이 정적 의미론을 통해 검사 가능한 규칙이다.

Attribute Grammar

• Attribute Grammar(속성 문법)은 Production Rule과 Attribute Evaluation Rule로 표기한다.
• 아래는 Attribute Grammar의 예시이다.

	S -> 
		| (S)S
		;

• 위의 EBNF로 표기된 생성 규칙에 속성 계산 규칙을 아래의 표와 같이 추가할 수 있다.
• 이러한 속성 문법을 이용하여 S1 = "()()", S2 = "()(())"라고 했을 때, S1, S2의 depth는 각각 1, 2임을 계산할 수 있다.

Dynamic Semantics

• 프로그램 수행 의미를 기술한다.
• 수행 의미론이라고 부르기도 하며, 실질적인 의미론이라고 볼 수 있다.
• 동적 의미론은 표준 방법이 여럿 존재한다.
  • Operational Semantics
  • Axiomatic Semantics
  • Denotational Semantics
• 일반적으로 프로그램의 의미를 파악하는 방법은 테스트이다.
• 하지만 테스트만으로 의미(Semantics)를 완벽하게 기술할 수는 없다. 테스트를 통해서 behavior는 알 수 있어도 Semantics는 알 수 없다.
• Semantics는 굉장히 모호한 개념이다. 이를 우리가 잘 아는 분야로 가져와서 프로그램의 의미를 기술하는 접근법을 택한다.
  • 추상 기계 코드 - Operational Semantics
  • 논리식 - Axiomatic Semantics
  • 람다식(함수식) - Denotational Semantics

Operational Model(Imperative Model)

• 단순화된 가상 기계(abstract machine)상에서 해당 프로그램의 수행 의미를 파악한다.
  • 실제 컴퓨터와 유사한 가상기계(추상기계)의 동작을 통해 프로그램 의미를 표현한다.
• 작은 단위 의미론(small-step semantics)과 큰 단위 의미론(big-step semantics)로 나뉜다.
• 가상 기계
  • State : memory, registers, I/O devices에 대한 추상화
  • State Transition Mechanism : Processor에 대한 추상화
• Operational Model을 이용하여 상태변환 Semantics를 표현한 예시이다.

  <z:=x; x:=y, y:=z, [x->5, y->7, z->0]>
  => <x:=y; y:=z, [x->5, y->7, z->5]>
  => <y:=z, [x->7, y->7, z->5]>
  => <, [x->7, y->5, z->5]
  

  • x와 y에 저장된 값을 서로 swap하는 동작을 표현했음을 알 수 있다.
• 하지만 이런 Operational Model을 이용한 방법은 프로그램의 의도와 정확히 일치할 수 없다는 비판점이 있다.
  • 실제로 위의 예시에서 x와 y의 값만 교체되는 것이 아니라 z의 값 역시 바뀐다.

Denotational Semantics(Applicative Model)

• 프로그램의 의미를 함수로 파악한다.
  • 이를 위해 lambda expression(A.Church, 엘런 튜링의 스승)을 사용한다.
  • Syntax domain P를 의미 함수에 대입시켜 Semantic domain의 .
  • 의미 함수는 대괄호 안에 구현을 삽입한 형태(denotation)로 표현한다.
  • 의미 함수(semantic functions)는 의미영역의 값을 다루는 함수이다.
  • denotational semantics는 의미 함수들로 구성된다.
• 아래는 의미 함수의 예시이다.

  Bin : B -> N
  	Bin[[0]] = 0
  	Bin[[1]] = 1
  	Bin[[B0]] = 2 * Bin[[B]]
  	Bin[[B1]] = 2 * Bin[[B]] + 1
  

• Non-Terminal statement "1011"을 위의 의미 함수에 대입한 결과는 아래와 같다.

  Bin[[1 0 1 1]] 
  	= 2 * Bin[[1 0 1]] + 1
  	= 2 * (2 * Bin[[1 0]] + 1) + 1
  	= 2 * (2 * (2 * Bin[[1]]) + 1) + 1
  	= 2 * (2 * (2 * 1) + 1) + 1
  	= 11
  

• 제시된 의미 함수를 통해 "1011"이 "11"로 변환되는 것을 확인할 수 있다.
  • 위 프로그램의 Semantics는 1011 -> 11 즉, 2진수 statement의 10진수로의 변환이다.

Axiomatic Semantics

• 프로그램 요소에 대한 사전조건(Preconditions) P와 사후조건(postconditions) Q를 통해 프로그램의 의미를 파악한다.
• 프로그램 수행 측면 중 일부는 무시된다.
• Preconditions는 프로그램 수행 전의 조건이며 C언어의 assert library를 통핸 수행 조건 검사를 생각하면 이해하기 편하다.
• 간단히 요약해 Axiomatic Semantics에 의하면, 프로그램의 Semantics란 사전 조건으로부터 사후 조건을 도출해 내는 것이다.