목차
2023학년도 2학기 충남대학교 조은선 교수님의 컴파일러개론 수업 정리자료입니다.
📁 Semantic Analysis(의미 분석) 이전 처리
컴파일은 어휘분석, 구문분석, 의미분석 순으로 이루어진다.
이때 구문분석의 결과 parsing tree를 얻을 수 있는데, 이렇게 얻은 parsing tree로 바로 의미분석을 진행할 것인지, 몇가지 처리를 한 후 의미분석을 진행할 것인지 선택할 수 있다.
이때 의미 분석 전에 이루어지는 처리과정에서 사용되는 중요한 도구에는 Syntax-Directed Definition/Translation(SDD/SDT)와 Abstract Syntax Tree (AST)가 있다.
📁 Syntax-Directed Definition (SDD)
Syntax-Directed Definition은 파싱 단계에서 파싱이 되었다고 가정하고, 그 이후에 다른 의미있는 일을 추가적으로 할 수 있도록 하는 도구이다.
각 규칙마다 해당 규칙이 reduce 혹은 유도될 때 해야할 일인 Semantic Action을 적어두는 방식으로 사용한다.
SDD를 이용하면 생성된 파서에 삽입될 semantic action을 사용자가 직접 정의할 수 있기 때문에, Yacc과 같은 파서 생성기에서 많이 쓰인다.
🌱 (Semantic) Actions
어떤 규칙이 reduce되거나 유도될 때 해야할 일을 Action이라고 부른다. 파스트리가 다 만들어진 후 각 노드를 순회하면서 해당하는 Action을 수행하거나, 파스트리가 만들어지면서 Action을 수행한다.
Action으로서 수행될 수 있는 일은 계산, 타입 검사 등 아주 다양하다.
1. 계산 Action
E -> E + E라는 규칙에 대한 action은 RHS의 첫번째 E와 두번째 E를 덧셈하는 일이다.
하지만 위와 같은 action을 코드로 작성하기 위해서는 세 개의 E가 모두 구별이 되어야한다. 이때 terminal 혹은 nonterminal마다 본인의 값을 저장하는 메모리공간이 존재하기 때문에 이를 가리키는 변수를 만들어 지칭하는 방식으로 구별한다.
위 규칙에 의해 reduce되거나 유도된 트리를 보자.
맨 위 노드인 E는 본인만의 메모리 공간이 존재한다. 이를 $$라는 변수 이름을 만들어 지칭한다. children node들도 각자의 메모리 공간을 갖고 있고, 그들 각각이 계산된 결과값이 저장된다. 이때 children node들 또한 $1, $2, $3 등과 같이 변수 이름을 매겨준다.
이때 '+'라는 토큰 노드에도 $2라는 변수 이름을 짓는데, 토큰도 값을 가질 수 있고 이를 메모리공간에 저장해야하기 때문이다.
이렇게 변수 명을 만들면, 다음과 같이 규칙 옆에 Action code를 작성할 수 있다.
LHS의 expr는 $$, RHS의 expr 두개는 각각 $1, $3이라고 매겨진 변수명을 이용하여 오른쪽에 action code가 작성되었다. Bottom-up이므로 이미 $1과 $3 내부의 값은 계산이 다 된 값일 것이고, 이 값을 이용해 더하기 연산을 하는 과정이 진행된다.
parent node에 $$, children node에 $1, $2,.. 와 같이 변수명을 짓는 방식은 Yacc/Bison에서 사용하는 방식이고, ANTLR에서는 $<name> 형태를 사용한다.
expr은 $expr, unary_expr은 $unary_expr이라는 변수 이름이 된다.
$$, $1, $unary_expr 등 은 규칙 내의 로컬변수이다. 예를 들어 $$, $1, $2는 expr : expr PLUS expr이라는 규칙 내에서만 사용되는 로컬변수이다.
예를 들어 위 트리에서 child node 중 $1 아래에 규칙이 reduce 혹은 유도되어 비슷한 생김새의 트리가 위치한다면, 이때 $1의 메모리 공간은 $$라는 변수명을 갖는다.
action code를 위해 매겨지는 변수명들은 가상의 local 변수이므로, 같은 메모리라도 규칙에 따라 다른 이름의 변수명을 갖는다.
2. Type Declaration
이번에는 변수와 같은 요소들의 타입을 저장하는 Action을 보자.
오른쪽 tree를 bottom-up 방식으로 propagation해서, int a, b라는 변수 선언문 내에서 a와 b의 타입이 int임을 확인할 수 있다.
위와 같은 문법 및 트리도 int a, b를 나타내지만, bottom-up 방식으로만 진행하면 L을 유도할 때 type을 알 수 없다. 이런 경우에는 오른쪽 트리의 파란색 화살표 방향으로 타입이 전달되어야한다.
위와 같이 children node들만으로도 action 진행이 모두 가능한 경우가 있는 반면, children node들만 보고서는 계산이 불가능한 경우가 있다.
children node들에 의해서만 bottom-up 방식으로 계산이 가능한 attribute를 synthesized attribute라고 하고, parent나 sibling node들에 의해서 계산해야하는 attribute를 inherited attribute라고 한다.
예를 들어 A -> XYZ라는 규칙이 있으면, A.attr = f(X.attr, Y.attr, Z.attr);로 계산되는 경우 synthesized, Y.attr = f(A.attr, X.attr, Z.attr)로 계산되는 경우 inherited이다.
이때 terminal에는 synthesized attribute만 존재한다.
attribute가 무엇인지는 아래서 설명한다.
📁 Yacc의 SDD로 계산기 만들기
우측의 중괄호 안에 있는 과정이 Action이다.
g4 ANTLR 실습시간에, 중괄호 안에 System.out.println("룰이름"); 과 같은 코드를 중괄호 안에 넣으면 해당 규칙이 불러와질때 터미널에 해당 룰 이름이 출력되었었다.
이때 하나의 노드가 가지는 값을 위 예시의 val과 같이 별도의 이름을 사용해서 나타낼 수도 있다. 이와 같이 노드가 가지는 값을 속성(attribute)라고 부른다.
📁 ANTLR의 Listener Style
📝 문제 풀어보기
위는 중첩 괄호식를 위한 Yacc 의 규칙부분이다. 매치된 괄호식의 nesting depth를 구해서 depth 라는 속성에 저장하기 위한 적절한 코드 를 적으시오. 단 LPAREN과 RPAREN은 왼쪽 괄호와 오른쪽 괄호를 나 타내는 토큰 심벌이다.
