[컴파일러] 9. Yacc

4/13

 

Yet Another Compiler-Compiler(YACC)

: CFG(Context-Free Grammar)와 각 문법에 해당하는 명령(Action)을 받아 프로그램 생성

 

Lex와 Yacc의 모델

 

 

파서 액션

• (LR Parser): shift reduce, accept, error
• shift: 파서는 어휘 분석기를 호출하여 토큰을 가져오고 이를 stack에 push
• reduce: rule에서 제공한 사용자 코드 실행. return한 후 reduction이 수행(stack의 handle이 축소되어 LHS의 비단말 기호로 변경)
• 스택이 현 상태를 유지하면서 value stack은 어휘 분석기와 규칙들과 관련된 동작들로부터 값을 가지며 평행하게 작동.

 

입력 명세

declarations	//(선언)
%%
rules	//(생성 규칙)
%%
programs	//(사용자 프로그램)

선언부

• 생략 가능
• %token을 나타내는 이름 선언
• %start 시작 심볼을 명시적 선언
• default 시작 심볼은 규칙 부분의 첫 번째 생성규칙의 LHS

생성규칙부분

• 형식-  A : RHS {액션 코드} ;
• 문법규칙(A:RHS)+명령({액션 코드})
  • 각 문법 규칙에 사용자 액션 코드를 연관
  • 규칙은 입력 프로세스에서 인식
• 문법규칙-형식: A:RHS
  • A: 하나의 비단말기호
  • RHS(Right Hand Side): 비단말기호, 토큰, 리터럴 조합
    • 리터럴: 타옴표가 붙은 문자열.
    • 비단말기호의 이름: 식별자와 같이 임의 길이의 문자열. 문자는 점과 언더바 포함. 대소문자 구별.
    • 수직바를 반복을 피하기 위해 사용할 수 있다.
  • 액션 표현: 중괄호에 둘러쌓인  임의의 C언어 표현
    • 파스 트리를 구성하거나 직접 코드 생성을 위해 사용할 수 있다.
    • YACC은 규칙의 중간과 끝에 액션 허용
    • YACC 파서는 오직 yy로 시작하는 이름 허용. 사용자는 이런 이름을 피해야함.
  • 문법 속성
    • 문법 규칙에 있는 심볼에 대한 값/속성을 정의하기 위한 기능
    • $$, $1, $2 ... : 각 문법 심볼의 속성 값들을 나타낸다.
    • $$: LHS의 속성 $1: RHS 첫 심볼 속성...
  • 파스트리 구축 예
    • node(L, n1, n2)은 레이블이 L인 노드 생성, 자식 노드 n1과 n2를 붙이고, 새로 생성된 노드의 인덱스 리턴.

모호성:

• 주어진 문법에 대해 두개 이상의 파스트리가 구축될 수 있다면 문법 규칙은 모호하다고 표현.
• 파싱 도중 한 입력 토큰에 대해 shift와 reduce 액션이 2개 이상 가능한 경우

YACC 충돌 해결 규칙

• shift/reduce 충돌은 shift 우선
• reduce/reduce 충돌은 우선된(먼저 기술된) 문법 규칙에 따라 reduce 실행.
• 근데 그냥 모호하게 만들지를 말자.

Error 처리

• 오류 회복: 오류가 발견되면 더 많은 구문 오류를 찾기 위해 종료하지 않고 입력 스캐닝을 지속한다.
• 토큰 error: 오류 처리를 위해 예약된 것이며 문법 규칙에 사용. 오류가 예상되는 위치에 사용. 파서가 정상이 될 때까지 stack 정리.

 

사용자 프로그램 부분

• 생성된 프로그램 내부로 그대로 복사