YACC 문법 구조

 Yacc 문법은 세 부분으로 구성되며 각각 정의절, 규칙절, 그리고 사용자 서브루틴절 이라고 한다.

 
{%
  ..  C 코드  ( 변수 선언 등 )

%}
정의절

%%
규칙절
 %%

사용자 서브루틴

각 부분은 퍼센트 기호 두개를 담고있는 행으로 구분된다. 처음 두 부분은 그 안에 내용이 없더라도 반드시 존재해야 한다. 세번째 부분과 그 앞에 있는 %% 행은 생략할 수 있다.  (Lex같은 동일한 구조를 갖는다.)

 

기호

Yacc 문법은 언어에서 문법을 구성하는 "단어"에 해당하는 기호들로 이루어 진다. 기호란 글자, 숫자, 마침표, 그리고 밑줄 등으로 이루어진 문자열이며, 첫 문자가 숫자이면 기호가 아니다. error라는 기호는 에러 복구를 위해서 예약되어 있다. 이렇게 미치 예약된 기호를 제외한 나머지 기호들에는 미리 설정된 의미가 없다.

렉서를 통해 생성되는 기호들은 터미널 기호(terminal symbols) 혹은 토큰(token)이라고 한다. 규칙의 왼쪽에 놓인 기호들은 비터미널 기호(non-terminal symbol)혹은 비터미널이라고 한다. 토큰은 또한 따옴표로 둘러싸인 리터럴 문자열이 될 수도 있다. 관례적으로 토큰의 이름은 모두 대문자로 작성하고, 비터미널은 소문자로 작성한다.

 

정의절

정의절은 생성되는 C 파일의 시작 부분으로 그대로 복사되는 리터럴 블록을 포함하고 있는데, 보통 이부분에는 변수선언, #include 와 같은 내용을 담는다. 보통 $union, %token, %type, %left, %right, %nonassoc 과 같은 선언들이 정의절에 위치한다. 또한 정의절에는 일반 C 언어 형식처럼 /* 와 */ 로 둘러싸인 주석을 담을 수도 있다.

이러한 내용은 모두 선택사항이기 때문에 간단한 파서에서는 정의절이 비어 있을 수도 있다.

 

규칙절

규칙절에는 문법의 규칙과 C 코드로 된 동작을 담는다.

 

사용자 서브루틴절

Yacc는 사용자 서브루틴절에 있는 내용을 C 파일에 그대로 복사한다. 이 절에는 대부분 동작 코드에서 실행하는 루틴을 담는다.

 

큰 프로그램에서는 이와 같은 지원 루틴들을 개별적인 파일에 저장하여 Yacc 파일이 변경되었을 떄 다시 컴파일 해야 할 코드의 양을 최소화 하는 것이 좋다.

 

동작(Action)

동작은 Yacc에서 문법에 있는 규칙에 매치 했을 때 실행되는 C 코드이다. 동작은 반드시 완전한 C 문장이어야 한다.

 

    date: month'/'day'/'year            { printf("date found");}

 

동작에서는 앞에 달린 기호가 붙은 숫자를 통해 규칙에 있는 기호와 연관된 값을 참조할 수 있다. 이때 콜론 뒤에 처음으로 등장하는 기호를 나타내는 숫자 값은 1 이다.

 

   date: month'/'day'/'year        {printf("date %d-%d-%d found",$1,$3,$5);}

 

"$$" 는 콜론의 왼쪽에 있는 기호에 대한 값을 가리킨다.  여러가지 C 타입이 기호의 값이 될 수 있다.

 

Yacc에서는 동작이 없는 규칙에 대해 다음과 같은 기본 값을 이용한다.

{$$ = $1;}

 

규칙에 내장된 동작

Yacc의 파싱 기법에 따르면 동작이 규칙의 맨 끝에 있어야 하지만, 동작이 규칙에 내장되어 있더라도 큰 상관은 없다. 동작을 규칙 안에 작성하면, Yacc는 새로운 규칙을 생성하여 해당 규칙의 오른쪽 내용은 비워두고 왼쪽 내용에는 임의로 지어낸 이름을 둔다. 또한 본래 내장되어 있던 동작을 새로 고안된 규칙에 대한 동작으로 지정한다. 마지막으로 본래 규칙에 포함되어 있는 동작을 앞서 지어낸 이름으로 대체한다. 예를 들면, 다음 두 규칙은 동일하다.

thing:   A { printf("seen an A");} B;

thing:   A fakename B;

fakename:  {printf("seen an A");} ;

이 기능이 상당히 유용한 것은 사실이지만 내장된 동작이 규칙 안에서 기호로 대체 되므로, 그 값은 다른 기호들의 경우와 마찬가지로 규칙의 끝에 있는 동작에서 접근할 수 있게 된다.

 

thing:          A{$$=17;} B C

                     {pringf("%d",$2);};

 

이 예를 실행하면 "17" 을 출력한다. 여기서 두 동작 모두 A의 값을 $1을 통해 참조하고 있고, 규칙의 맨 끝에 있는 동작에서는 규칙 안에 내장된 동작의 값을 $2를 통해서 참조하며 B와 C의 값은 각각 $3 과 $4로 참조하기 때문이다.

 

내장된 동작은 문법에서 이동/감소 충돌을 야기할 수도 있다. 다음 문법에서는 아무 문제도 발생하지 않는다.

%%

thing: abcd | abcz;

abcd:  'A' 'B' 'C' 'D';

abcz:  'A' 'B' 'C' 'Z';

 

그러나 다음과 같이 내장된 동작을 추가하면 이동/감소 충돌이 일어난다.

%%

thing: abcd | abcz;

abcd:  'A' 'B'   { somefunc();} 'C' 'D';

abcz:  'A' 'B' 'C' 'Z';

첫번째 경우에는 파서가 토큰 네개를 전부 살펴보아서 정확한 판단을 내릴 수 있게 되기 전까지는 abcd를 파싱하고 있는지, 아니면 abcz를 파싱하고 있는지 미리 판단할 필요가 없었다. 하지만 두번째 경우에는 'B'를 파싱하고 난 다음 바로 판단을 내려야 하는데 아직 충분한 입력 정보를 읽지 않았기 때문에 판단을 내릴 수가 없다. 내장된 동작이 'C' 다음에 있다면, Yacc가 토큰 한개정도는 미리 볼 수 있는 기능이 있기 때문에 다음 토큰이 'D'인지 'Z'인지 판단할 수 있으므로 아무 문제가 없을 것이다.