[컴파일러] SDD (Syntax-Directed Definition)

👑 SDD (Syntax-Directed Definition) 이란?

SDD(Syntax-Directed Definition)은 문맥자유 문법에 속성과 의미 규칙을 결합한 것으로,

프로그래밍 언어의 구문 구조에 의미 정보를 부여하는 방법이다. SDD는 문법의 각 생성 규칙에

의미 규칙을 추가함으로써 언어를 향상시킬 수 있다.

SDT(Syntax Directed Translation)은 SDD에서 정의된 의미 규칙에 따라 고급 언어 프로그램을

중간 언어나 기계어로 변환하는 작업이다. SDT의 동작은 입력 코드를 번역하기 위해 구문 분석 과정과

협력하여 이루어진다.

💡 상속 속성 & 합성 속성

SDD에서 사용되는 속성의 두 가지 유형에는 합성 속성과 상속 속성이 있다.

• 합성 속성 (Synthesized Attributes)

  • 자식 노드의 값에서 유도된 값을 가지는 속성이다.

  • 파스 트리에서 노드의 합성 속성 값은 해당 노드의 자식 노드들의 속성 값을 기반으로 계산된다.

  • terminal 기호는 합성 속성은 가질 수 있지만, 상속 속성은 가질 수 없다.

  • 아래 규칙에서 E.val은 E1.val과 T.val로부터 값을 유도한다.

  $ E → E_1 + T \;\; \lbrace E.val = E_1.val + T.val \rbrace $

• 상속 속성 (Inherited Attributes)

  • 부모 노드나 형제 노드의 값에서 유도된 값을 가지는 속성이다.

  • 아래 규칙에서 C.in은 부모 노드 A의 in 값을 상속받고, C.type은 형제 노드 B의 type 값을
    기반으로 결정된다.

  $ A → B C D \;\; \lbrace C.in = A.in, C.type = B.type \rbrace $

💡 Semantic Action

Semantic Action은 구문 분석 과정 중에 실행되는 코드로, 문법에 정의된 각 생성 규칙에

따라 특정 작업을 수행하여, 컴파일러나 인터프리터가 입력 코드를 처리하고 번역하는 데 필요한 정보를

생성한다. 파스트리가 다 만들어진 후 각 노드를 순회하며 각 노드에 해당하는 action을 수행한다.

다음의 문법을 예시로 들면 문법에 대한 SDD는 다음과 같이 만들어질 수 있다.

S → E
E → E1 + T
E → T
T → T1 - F
T → F
F → digit

아래는 입력 스트링 5 - 2 + 3에 대한 주석 파스 트리(annotated parse tree)를 그린 것이다.

💡 정리

SDD(Syntax-Directed Definition)는 구문 분석과 의미 분석을 연결하는 중요한 기술로,

프로그래밍 언어의 구문 구조에 의미 정보를 부여하는 방법이다. 이를 통해 컴파일러나 인터프리터가

더 효율적으로 동작할 수 있으며, 코드의 타입 검사, 코드 생성, 최적화 등의 다양한 작업을 자동으로

처리할 수 있다. SDD에서 정의된 속성들은 프로그램의 의미를 계산하는 데 필요한 데이터를 제공하며,

합성 속성과 상속 속성은 각각 자식 노드와 부모/형제 노드로부터 값을 유도하는 방식으로 동작한다.

이 속성들은 구문 분석 트리에서 계산되며, 프로그램의 의미를 체계적으로 처리할 수 있게 한다.

또한, 의미 동작(Semantic Action)은 구문 분석 중에 실행되어, 문법 규칙에 따른 타입 검사,

코드 생성, 메모리 관리 등의 중요한 작업을 수행한다. 이러한 동작은 구문 분석이 진행되는 동안 자동으로

이루어지며, 입력 코드의 의미를 올바르게 해석하는 데 도움을 준다. SDD와 SDT를 사용함으로써,

프로그래밍 언어의 구문과 의미를 결합하여 더 강력하고 효율적인 컴파일러 및 인터프리터를 구축할 수 있다.