[프로그래밍 언어론] Attribute Grammars (AGs)

학교에서 들은 프로그래밍 언어론 강의 내용을 복습하면서 작성한 글입니다.
March 25, 2024 5:27 PM

 

Static Semantics (정적의미론)

• 프로그래밍 언어의 문법 구조만으로는 설명할 수 없는 언어의 의미를 정의하는 방법
• Context-free grammar는 모든 프로그래밍 언어의 문법을 설명할 수는 X
• 문제
  • 문맥 자유이지만 번거로움
  • 비문맥 자유: 변수 사용전에 선언해야함

context-free의 한계: 오류에 대한 처리, 변수 사용 전 선언 → AGs: 해결하기 위해 나옴

---

Attribute Grammars

• Context-free grammar에 확장: 파스 트리 노드에 의미 정보를 가지고 있음
• parsing하며 알 수 있는 간단한 semantic 정보 집어넣어놓음
• 이점
  • 프로그램의 정적 의미 명세 가능
  • 컴파일러 설계에서 중요한 역할: 정적 의미적 검사 수행 도움되는 규칙 정의 가능
• 추가 요소 3개
  • BNF에서 쓰이는 각각의 symbol x에다가 A(x)라는 속성을 부여할 수 있음
  • 각 속성을 정의 하기 위한 함수를 정할 수 있음
  • 속성에 대한 명제를 정의하기 위한 predicate(서술부, 참이 되어야 하는 조건)를 줄 수 있음
• 특징
  • rule: X₀ → X₁ ... Xₙ
  • Synthesized Attributes: S(X₀) = f(A(X₁), ..., A(Xₙ)) - 자식노드로부터 자신의 속성 결정
  • Inherited Attributes: I(Xⱼ) = f(A(X₀), ..., A(Xₙ)) , for i ≤ j ≤ n - 부모나 형제 노드로부터 자신의 속성 물려받아 결정
  • Initially Intrinsic Attributes: 초기에 각 리프노드에 (스스로) 내재 속성이 있음
  • Expected Type & Actual Type
    • Expected Type: 컴파일러나 인터프리터가 특정위치에서 예상하는 데이터 유형
    • Actual Type: 변수나 표현식이 실제로 가지고 있는 데이터 유형
    → 일치하지 않으면 일반적으로 type error 발생
  ex)

  <assign> -> <var> = <expr>
  <expr> -> <var> + <var> | <var>
  <var> A | B | C
  

  • actual_type: synthesized for <var> and <expr> → 변수와 표현식에 대한 실제유형은 synthesized 속성으로 정의됨: 각 변수 및 표현식의 유형을 계산하여 할당됨
  • expected_type: inherited for <expr> → 표현식에 대한 기대유형은 inherited 속성으로 정의됨: 즉, 이 속성은 표현식의 부모 노드로부터 전달되며 해당 표현식이 가져야할 유형을 나타냄

  Syntax rules:
  <expr> -> <var>[1] + <var>[2]
  Semantic rules:
  <expr>.actual type <- <var>[1].actual_type //표현식의 실제 유형은 변수1의 실제 유형과 동일
  Predicate(조건):
  <var>[1].actual_type == <var>[2].actual_type //변수1, 2의 실제 유형이 동일해야함
  <expr>.expected_type == <expr>.actual_type //표현식의 기대 유형은 실제 유형과 동일해야함
  

  Syntax rule: 
  <var> -> id  //변수가 식별자(id)로 구성됨
  Semantic rule: 
  <var>.actual_type <- lookup (<var>.string)  //변수의 실제 유형을 변수의 이름을 조회하여 설정
  Predicate: 없음
  

• 속성 값이 계산되는 방식 - computed
  • 모든 속성이 inherited: 상속된 속성으로만 이루어진 경우: 트리를 top- down order로
  • 모든 속성이 synthesized: 합성된 속성으로만 이루어진 경우: bottom-up order로(합성된 attribute 찾아가기)
  • 대부분은 두 속성 함께 사용됨→ bottom-up 과 top-down 모두 사용되어야함

  <expr>.expected_type <- inherited from parent
  <var>[1].actual_type <- lookup (A)
  <var>[2].actual_type <- lookup (B)
  <var>[1].actual_type =? <var>[2].actual_type
  <expr>.actual_type <- <var>[1].actual_type
  <expr>.actual_type =? <expr>.expected_type
  
  

• 위의 Syntax rule과 Semantic rule을 이용하여 주어진 AG(Attribute Grammar)에서 표현식(expr)과 변수(var)에 대한 실제 유형을 설정하고, 이를 활용하여 표현식의 유효성을 검사하는 것