컴파일러 시간에 첫번째 과제로 제출했던 '재귀 하강 파서1(Recursive descent parser)로 PL/0 파싱 및 실행'2에 대해 정리해놓으려고 한다. 과제를 진행한 순서로 정리한 글이라 초반에 생각을 잘못해서 나중에 좀 괴랄한 방법으로 구현된 부분도 있고, 함수 이름이 중간에 바뀌기도 하고 그렇다. 과제 후기라고 생각하면 될듯.
#PL/0
링크 걸어놓은 위키에서도 설명하고 있지만 PL/0는 2가지 언어를 가리키는데, 그 중 하나는 IBM에서 만든 PL/I 언어의 부분집합이고, 다른 하나는 파스칼 언어에서 몇가지 복잡한 기능을 삭제한 연습용 언어이다. 이 중에서 후자를 파싱해보도록 한다. PL/0은 Algorithms + Data Structures = Programs 라는 책에서 처음으로 소개되었는데, 안타깝게도 좀 오래 전에 쓰여진 책이라 지금은 절판 되었다. (pdf 조차도 찾을 수 없어서 수업시간에 복사해서 썼다) 물론 워낙 간단한 언어라 상세한 스펙은 위키에도 나와있지만, 저 책에 대한 정보가 그만큼 인터넷에 없기 때문에 책에 나와있는 문법 다이어그램을 구글링해서 찾을 수가 없었다. 그래서 책의 복사본을 스캔,캡쳐해서 사용할 것이다. (수업시간에 필기한게 보이긴 하지만 별 문제는 아니다)
지금 기준으로 좀 오래된 파스칼 언어를 기반으로 하고 있지만, 프로그래밍 언어가 원래 패러다임이 완전 반대쪽이지 않는 이상 비슷한 구석이 있기 때문에 알아먹는데 그렇게 어렵진 않을것이다.
아래는 앞으로 파서의 인풋으로 넣게될 PL/0 코드다. 곱셈, 나눗셈, 최대 공약수를 구하는 함수를 한번씩 호출하는 코드이다.
const m = 7, n = 85;
var x,y,z,q,r;
procedure multiply;
var a,b;
begin
a := x; b := y; z := 0;
while b > 0 do
begin
if odd b then z := z + a;
a := 2 * a; b := b/2;
end
end;
procedure divide;
var w;
begin
r := x; q := 0; w := y;
while w <= r do w := 2*w;
while w > y do
begin q := 2 * q; w := w/2;
if w <= r then
begin r := r-w; q := q+1;
end
end
end;
procedure gcd;
var f,g;
begin f := x; g := y;
while f <> g do
begin
if f < g then g := g-f;
if g < f then f := f-g;
end;
z := f;
end;
begin
x := m; y := n; call multiply;
x := 25; y := 3; call divide;
x := 84; y := 36; call gcd;
end.
앞으로 이 코드를 파싱하고, 중간 코드 생성해서, 실행까지 시킬것이다.
보편적인 C/C++ 이나 자바 같은 언어에 익숙한 사람이라면 느낄만한 다른점을 나열해 보자면
- 변수선언은 var 이름 형식이다. (어차피 정수 이외의 타입은 지원하지 않는다. 그렇기 때문에 const 선언에서 생략가능)
- 값을 집어넣을때 = 가 아닌 := 를 사용한다. (=는 c에서 ==와 같은 의미)
- <>는 c에서의 !=를 의미한다 (엑셀에서 이렇게 쓰는거 같던데.. 책에는 다른 특수문자였지만 수업시간에 이걸로 하자고 합의함)
- {, } 가 아닌 begin, end를 사용한다.
- if then end, while do end (마치 루아처럼)
- else와 for문은 지원하지 않는다. (for문은 while과 동치라 없음, else는 dangling else3 문제를 배우기 전이라 없음)
- function 이 아닌 procedure를 사용. (procedure는 리턴 타입이 void인 함수라고 생각하면 된다)
- 프로시저를 호출할때 call 이름 으로 호출. (인자 전달 없음)
- odd 연산자가 있다. 어떤 수가 홀수이면 true 짝수이면 false가 되는 신기한 연산자.
- 프로그램 마지막에 . 을 찍는다.
추가바람
이 언어의 문법을 그림으로 표현해보자면, 다음과 같다.4 (BNF 표기법56으로 표현할 수도 있으나 재귀 하강 파싱의 특성상 그림으로 이해하는게 편하다.)
몇가지 기능을 제거하기도 했고, 원래 파스칼이 문법 설계가 잘되어 있어서 이렇게 간단한 그림 몇 개만으로 문법을 표현할 수 있다고 한다. (문법이 깔끔해야 파싱하기도 편한데 그러기가 힘들다고..)
#재귀 하강 파싱
보통 프로그래밍을 하다가 간단한 문자열 파싱 작업을 할때, 대개는 문자열을 가리키는 char 포인터 하나 잡아놓고 while 문 안에서 포인터를 하나씩 증가시키면서 내부에 파싱하는 로직을 구성하곤 한다. 근데 만약에 저 PL/0를 while문 하나에서 전부 파싱하려면? while문도 엄청 길어지고, 버그라도 터지면 이리저리 꼬인 로직을 따라 디버깅하기도 힘들어지겠지. 이때 문법 규칙을 덩어리들로 나누어서 하나씩 각자 자신의 문법 덩어리만을 파싱하는 함수들을 만들고, 그 함수들을 이용해서 파싱 로직을 구성하는게 (한 마디로 함수로 빼놓는게) 더 편할것이다. 그 문법 덩어리가 위에 있는 그림에서의 'Program', 'Block', 'Statement', 'Condition', 'Expression', 'Term', 'Factor', 'Ident', 'Number'7들이다.
얘네들을 BNF표기법에서 'Non terminal' 이라고 부른다. BNF나 파싱트리에 대한 글이 아니니 간단하게 언급하자면 non terminal은 '아직 더 쪼갤수 있는 문법 덩어리' 라고 할 수 있겠다. 그럼 반댓말인 'terminal'은 '더 이상 쪼갤 수 없는 것'이라고 이야기 할 수 있겠고. 89
이렇게 각각 Non terminal을 파싱하는 함수들을 만들어서, 상호간의 재귀적인 호출로 코드의 윗부분부터 아랫부분까지 스캔해 나가며 파싱하는것이 재귀 하강 파싱방법이다.
예를 들어, 위의 문법을 보면 Program은 Block과 . 으로 이루어져 있다. Program을 파싱하기 위해선 간단하게 Block을 파싱해 주는 함수와 다음 문자열이 . 으로 끝났는지만 확인해 보면된다. Block을 파싱해주는 함수를 만들기 위해선 첫 문자열이 "const" 로 시작하는지 또는 "var" 로 시작하는지 등을 확인해보고 파싱하면 되고.
void Program(){
Block();
if ( current token is NOT "." ) {
error();
}
}
void Block(){
if ( current token is "const" ) {
...
}
if ( current token is "var" ) {
...
}
...
}
이런식이다.
적당히 길어진거 같으니 다음글로...
- 뭐... 따지자면 '재귀적'이 더 맞겠지만 이렇게도 많이 쓰니까 그냥 이렇게 쓴다. [본문으로]
- 첫 과제가 파싱이었고, 다음 과제가 실행이었다. [본문으로]
- 토큰을 하나씩 바라보는 파싱 방법에서 else 구문을 처리하기 어려운 문제 [본문으로]
- 사족이지만, JSON의 문법을 알려주는 사이트도 이런 형태의 그림으로 설명하고 있다. http://www.json.org/json-ko.html [본문으로]
- 언어의 문법를 표현하는데 쓰는 메타 언어. [본문으로]
- PL/0의 BNF는 위키에 있다. [본문으로]
- Ident 는 식별자를 의미하고, Number는 숫자열을 의미 한다. 식별자나 숫자에 대한 문법은 기타 다른 언어에서 흔히 볼 수 있는 만큼 책에서 생략한듯 싶다. [본문으로]
- +,-,*,/, odd같은 연산자들이나 if, while 같은 키워드, 식별자, 숫자와 같은 '실제로 코드를 이루는 문자열의 조각들'을 terminal, '블록', '절', '조건문', '수식' 같은 추상적인 덩어리를 non terminal이라고 한다. [본문으로]
- 왜 'terminal' 이냐면 terminal들은 파싱 트리의 '말단'에 오기 때문이고. Non terminal은 terminal이 아닌것들이라 non terminal이라 부른다. [본문으로]
'대학' 카테고리의 다른 글
| A* (a-star) 알고리즘 휴리스틱 (1) | 2015.03.19 |
|---|---|
| 재귀 하강 방식으로 PL/0 파싱,실행하기 (Recursive descent parser) - 2 (1) | 2015.02.09 |