[프로그래밍언어론] 10. 추상 구문 트리(AST)를 EBNF로 변환

구문을 파이썬으로 추상 구문 트리(Abstract Syntax Tree; AST)로 분석하고 EBNF로 구현해본다.

 

---

 

'a = 3 + b' 구문을 분석해보자.

파이썬에서는 ast 모듈을 사용하여 코드를 구문 분석할 수 있다.
ast 모듈의 사용법은 다음과 같다.

import ast

t = ast.parse('a = 3 + b')
s = ast.dump(t, annotate_fields=False, indent=4)
print(s)

코드 결과

Module([     Assign([         Name('a', Store())],         BinOp(             Constant(3),             Add(),             Name('b', Load())         )     ) ],[])

결과 각 노드에 대해 노드 유형(Module, Assign, Name)으로 시작하고 해당 하위 노드를 '( )'에 넣는다.
Constant(3)은 노드 유형이 Constant, 값이 3이다.

 

---

 

결과를 트리로 변환해보자

트리와 코드를 비교하면 다음의 특징이 있다.

1. Add()가 '+'를 나타낸다.
2. '='가 명시적으로 표현되지 않는데 Store()와 Load()의 의미를 생각해 보면 [ Name ]과 BinOp 사이에 '='가 들어간 것으로 추측할 수 있다.
3. 리프 노드에는 특정 값이 있다.
   예) 'a', 3, 'b'

 

---

이제 구문 분석된 AST를 통해 EBNF를 작성할 수 있다.

<Assign> ::= <Name> = <BinOp>
<BinOp> ::= <Constant> <Add> <Name>
<Constant> ::= 3
<Name> ::= a | b
<Add> ::= '+'

 

---

 

예) 다음 모든 구문을 포괄하는 EBNF를 작성해보자.

a = 3 + b
x = y
a = b + 5
a, b = 3, 5
c = 4 - 1

먼저 각 구문을 파이썬을 통해 분석해보자

a = 3 + b	Module(     [Assign(           [Name('a', Store())],           BinOp(               Constant(3),               Add(),               Name('b', Load())           )      )], [])
x = y	Module(     [Assign(         [Name('x', Store())],         Name('y', Load())     )], [])
a = b + 5	Module(     [Assign(         [Name('a', Store())],         BinOp(             Name('b', Load()),             Add(),             Constant(5)         )     )], [])
a, b = 3, 5	Module(     [Assign(         [Tuple(             [Name('a', Store()),             Name('b', Store())],             Store()     )],         Tuple(             [Constant(3),             Constant(5)],             Load())     )], [])
c = 4 - 1	Module(     [Assign(         [Name('c', Store())],         BinOp(             Constant(4),             Sub(),             Constant(1))     )], [])

 

AST를 EBNF로 나타내자.

1. <Assign> ::= <Name> = <BinOp> | <Name> = <Name> | <Tuple> = <Tuple1>
2. <BinOp> ::= <Constant> <Add> <Name> | <Name> <Constant> <Add> | <Constant> <Sub> <Constant>
   순서가 달라지면 다른 경우이다. <Constant> <Add> <Name>와 <Name> <Constant> <Add>는 다르다.
3. <Tuple> ::= <Name>, <Name>
   튜플사이에 ' , '이 빠지지 않도록 주의하자.
4. <Tuple1> ::= <Constant>, <Constant>
   튜플을 두 개로 나누기 않으면 '3, 5=a, b' 같은 상황이 생길 수 있다.
5. <Name> ::= a | b | c | x | y
6. <Constant> ::= 1 | 3 | 4 | 5
7. <Add> ::= '+'
8. <Sub> ::= '-'