[PL] Semantic의 표현

Semantic 표현은 크게 Static Semantics와 Dynamic  Semantics로 나뉜다.

Static Semantics(정적 의미론)

static semantics는 CFG, BNF 만으로는 표현될 수 없는 규칙들을 표현하기 위해 고안된 것이다. 대표적 예시로 '프로그램 내에서 어떤 변수는 참조되기 전에 선언되어야한다' 라는 규칙은 BNF로 표현할 수 없다. 

 

Attribute Grammars

Attribute Grammar = BNF + 3 Semantic Rules

Semantic Rules

- 1) BNF에서 쓰이는 각각의 symbol x에다가 A(x)라는 속성을 부여할 수 있음

- 2) 각 속성을 정의 하기 위한 함수를 정할 수 있음

- 3) 속성에 대한 명제를 정의하기 위한 predicate(서술부, 참이 되어야 하는 조건)를 줄 수 있음

 

※ 속성의 종류

• synthesized attribute : 자식 노드로부터 값이 결정
• inherited attribute : 부모 / 조상 노드로부터 값이 결정
• intrinsic attribute : 스스로 값을 지닌 leaf 노드에게 할당 (변수들은 symbol table로부터 값을 가져옴)
  
  

 

※ Predicate(서술부) - 반드시 참이 되어야 하는 조건

ex1)

- syntax rule : <expr> -> <var>[1] + <var>[2], 

- semantic rule : <expr>.actual_type <- <var>[1].actual_type 일 때

- predicate : <var>[1].actual_type == <var>[2].actual_type,

                      <expr>.expected_type == <expr>.actual_type

 

ex2)

- syntax rule : <var> -> <id>

- semantic rule : <var> <- lookup(<var>.string)

- predicate : 없음

 

---

Dynamic Semantics(동적 의미론)

표현식, 문장, 프로그램 단위를 실행할 때 그것이 어떤 의미를 가지는지 파악하는 것. 즉, 소스코드가 실행되기 전에 그것이 어떤 의미를 가지는 지 분석할 수 있다는 뜻이다. 하지만 이는 실제로 불가능하다.

 

• Operational Semantics(연산 의미론)
  - 프로그램의 문장을 기계에서 실행(시뮬레이션)시켜 보고 프로그램의 의미를 기술
  - 기계의 상태 변화 감지, 가상 머신 필요
  - 단순하고 비형식적인 경우 의미론 기술에 효과적
  
  
• Denotational Semantics(표기 의미론)
  - 프로그램의 상태는 현재 프로그램의 모든 변수로 맵핑하여 나타냄
  - 재귀 함수 이론에 기초
  - 수학 함수에 의해 정의
  
  
•  Axiomatic Semantics(공리 의미론)
  - 형식 논리에 기초하여 프로그램 정확성을 검증
  - Axiom = {P} S {Q}
  - {P} = 전조건(precondition), S = logic expressions, {Q} = 후조건(postcondition)
  - weakest precondition : precondition들 중 가장 제약이 덜한 {P}
  - ex) S : y = x + 10, {Q} : y > 20 일 때 weakest precondition은 x > 10
  - 앞 문장의 후조건은 뒷 문장의 전조건으로 작용한다.

---