1st week, Feb

[JLGGG]

Crafting Interpreters - 로버트 나이스트롬의 인터프리터 in Java, C

5장 코드 표현

Logs start

[JLGGG]

5장 코드표현
컨텍스트 자유문법 (CFG): 임의로 깊게 중첩 가능한 표현식을 처리하기 위한 형식.

• 프로덕션: 문법에 맞는 문자열 생성. 헤드와 바디로 구성됨.
• 터미널: 리터컬 값, 즉 토큰.
• 넌터미널: 다른 문법 규칙을 가리키는 참조.

구문 트리: 표현식을 트리 모양으로 표현. 파스 트리에서 모든 문법 프로덕션 하나하나가 트리의 노드가 되고, AST에서는 불 필요한 프로덕션을 제거함.

표현식 문제:

• 새로운 함수를 전체 클래스들에 추가하기는 매우 어려움. 그런 문제를 해결하기 위해 visitor 패턴을 사용함.
• Visitor 패턴: OOP에서 함수형 스타일을 흉내낸 기법. 타입을 건드리지 않고 새로운 동작 (메소드)을 한번에 여러 타입에 정의할 수 있다.

class ConcreteComponentA;
class ConcreteComponentB;

class Visitor {
 public:
  virtual void VisitConcreteComponentA(const ConcreteComponentA* element) const = 0;
  virtual void VisitConcreteComponentB(const ConcreteComponentB* element) const = 0;
};

class Component {
 public:
  virtual ~Component() {}
  virtual void Accept(Visitor* visitor) const = 0;
};

class ConcreteComponentA : public Component {
 public:
  void Accept(Visitor* visitor) const override {
    visitor->VisitConcreteComponentA(this);
  }
  std::string ExclusiveMethodOfConcreteComponentA() const {
    return "A";
  }
};

class ConcreteComponentB : public Component {
 public:
  void Accept(Visitor* visitor) const override {
    visitor->VisitConcreteComponentB(this);
  }
  std::string SpecialMethodOfConcreteComponentB() const {
    return "B";
  }
};

class ConcreteVisitor1 : public Visitor {
 public:
  void VisitConcreteComponentA(const ConcreteComponentA* element) const override {
    std::cout << element->ExclusiveMethodOfConcreteComponentA() << " + ConcreteVisitor1\n";
  }

  void VisitConcreteComponentB(const ConcreteComponentB* element) const override {
    std::cout << element->SpecialMethodOfConcreteComponentB() << " + ConcreteVisitor1\n";
  }
};

class ConcreteVisitor2 : public Visitor {
 public:
  void VisitConcreteComponentA(const ConcreteComponentA* element) const override {
    std::cout << element->ExclusiveMethodOfConcreteComponentA() << " + ConcreteVisitor2\n";
  }
  void VisitConcreteComponentB(const ConcreteComponentB* element) const override {
    std::cout << element->SpecialMethodOfConcreteComponentB() << " + ConcreteVisitor2\n";
  }
};

void ClientCode(std::array<const Component*, 2> components, Visitor* visitor) {
  // ...
  for (const auto* comp : components) {
    comp->Accept(visitor);
  }
  // ...
}

int main() {
  std::array<const Component*, 2> components = {new ConcreteComponentA, new ConcreteComponentB};
  std::cout << "The client code works with all visitors via the base Visitor interface:\n";
  ConcreteVisitor1* visitor1 = new ConcreteVisitor1;
  ClientCode(components, visitor1);
  std::cout << "\n";
  std::cout << "It allows the same client code to work with different types of visitors:\n";
  ConcreteVisitor2* visitor2 = new ConcreteVisitor2;
  ClientCode(components, visitor2);

  for (const auto* comp : components) {
    delete comp;
  }
  delete visitor1;
  delete visitor2;

  return 0;
}

[Shinwon-Kang]

소스 코드 -> 토큰 ->컨텍스트 자유 문법(CFG(Context-Free Grammar)) -> 구문 트리(syntax tree)

프로덕션(prodection) -> 문법 규칙
터미널(termianl) -> 리터럴 값, 가장 작은 단위
넌터미널(nonterminal) -> 참조 값 (다른 프로덕션을 가리킴)

protein -> crispiness "crispy" "bacon" ;
(헤드) ->(바디) 넌터미널 "터미널" "터미널";

[yongdol503]

컨텍스트 자유 문법(Context Free Grammar)

• 스캐너 + 정규 언어 + 문자 -> 렉심, 토큰
• 파서 + 컨텍스트 자유 문법 + 토큰 -> 표현식
• 프로덕션 : 컨텍스트 자유 문법에서 표현식을 생산하는 규칙을 의미
  • 헤드와 바디로 구성되어 있음
  • 헤드는 하나의 심볼, 바디는 심볼 리스트로 이루어짐
• 심볼의 2가지 종류
  • 터미널 : 리터럴 값
  • 넌터미널 : 다른 문법 규칙을 가르키는 기명 참조

구문 트리

• 문법의 재귀적 특성에 의해 자료구조가 트리 모양을 뛰게되고, 이를 구문 트리라고 부름

트리 다루기

• 표현식 구현체는 파서가 만들기 간단하고, 인터프리터가 소비하기 쉬워야 함
• 객체 지향 : 타입에 연산이 연관
• 함수형 : 연산에서 타입을 매칭
• 비지터 패턴 : 객체 지향에서 함수형을 흉내

[mhlee0627]

5.1 컨텍스트 자유 문법

형식문법 : 알파벳이라는 원자적 조각들의 집합을 받아 문법에 있는 문자열의 집합을 정의

1. 렉시컬 문법 : 문자를 토큰으로 묶는 규칙, 정규언어(regular language)
2. 컨텍스트자유문법(CFG) : 임의로 깊게 중첩 가능한 표현식을 처리할 수 있는?, 재귀적!

문법 규칙(production) : 무한한 문자열을 열거하기 위해서 유한한 규칙 집합을 만드는 규칙

파생어(derivation) : 규칙에 맞게 생성된 문자열, 헤드와 바디로 구성

터미널(terminal) : 문법의 알파벳에 있는 글자다? 리터럴 값?

넌터미널(nonterminal) : 다른 문법 규칙을 가리키는 기명참조다.

postfix : * 0회 이상 반복, + 1회 이상 반복, ? 0이거나 1회만

록스 표현식 문법

1. 리터럴 : 숫자, 문자열, 불리언, nil
   1. NUMBER : 모든 숫자 리터럴
   2. STRING : 모든 문자열 리터럴
2. 단항식 : 접두어(!, -)
3. 이항식 : +, -, *, /, ==, !=, <=, >, >=
4. 괄호 : ()

5.2 구문 트리 구현

문법이 재귀적이라서 자료구조는 트리 모양을 뛰게 됨. 구문 트리라고 함