L10_YACC_s : 컴파일러 자동화 도구 - 파서 생성기

컴파일러 자동화 도구 - 파서 생성기

YACC : Yet Another Compiler-Compiler

1. 소개

파서 생성기 (parser generator)는 파서 (구문 분석기)를 자동으로 생성하는 도구로써 파서 제작 시스템 (parser generating system, PGS)라 한다.

 

• YACC
• Bison

yyparse()는 파싱해주는 항수
yylex()는 구문을 분석해주는 함수

 

파서가 구문 분석기한테 토큰을 넘겨달라고 하면,
구문 분석기가 토큰을 넘겨준다.

2. YACC 표현

• Declarations (선택)
• Rules (필수)
• Action code (선택)

2.1. Declarations

: 선언 부분으로 생략이 가능하다.

• % token name1, name2 ...
  • 토큰을 나타내는 이름들을 미리 선언할 수 있다.
    • ex) %token TIDENT TPLUS
  • 선언 부분에서 선언되지 않은 이름들은 nonterminal symbol로 간주한다.
    • Nonterminal symbol은 최소한 한 번 이상 생성 규칙의 왼쪽에 나타나야 한다.
    • 이 조건을 만족하지 않으면 오류다.
• %start
  • 문법의 시작 심볼 지정
  • 명시적으로 시작 심볼을 지정하지 않을 경우, 시작 심볼은 첫 번째 생성 규칙의 lhs에 있는 nonterminal symbol이다.

2.2. Rules

생성 규칙 부분
: 생략이 불가하다.

구성은 아래와 같다.

 

 

생성 규칙 부분은 크게 세가지로 구성된다.

• A
  • 생성 규칙의 lhs
  • Nonterminal symbol
• Body
  • 생성규칙의 rhs
  • 일련의 이름이나 문자 상수들로 구성된다.
• action code
  • 의미 수행 코드
  • C statements 생성규칙이 매칭되면 실행되는 부분이다.

 

BNF는 컴파일러, 프로그래밍 언어 등의 문법을 형식적으로 표현하기 위한 표기법

• < > : nonTerminal
• ' ' : Terminal
• BNF → YACC 형식으로 바꾸는 이유는 간단히 말하면:

BNF는 이론적 표현이고, YACC은 실제 작동하는 파서를 만들기 위한 실용적인 문법이기 때문이다.

 

문자상수는 따옴포(quote; ') 사이에 표시하며, escape 문자 사용이 가능하다.
하나의 nonterminal symbol이 여러 개의 생성 규칙을 가질 경우에는 다음과 같이 표현한다.

 

 

| 연산자를 사용하고 마지막 부분에만 ;를 붙이면 된다.

앱실론 생성규칙의 경우, body 부분을 비워두면 된다.

• 생성 규칙 body 부분 : terminal, nonterminal심벌로 구성
• Terminal 심벌
  • 선언 부분에 토큰으로 정의된 것
  • 문자 상수
• 심벌은 길이 제한이 없다.
• 심벌은 대소문자를 구변한다.
  • 보통 1. 토큰 심벌 : 대문자, 2. nonterminal 심벌 : 소문자
• yy로 시작하는 심벌 이름은 피하는 것이 바람직하다.
  • yy로 시작하는 것에는 lex, yyac모두에서 변수, 함수 이름으로 정의하는 경우가 많기 때문에, 중복을 미연에 방지하고자 함이다.

2.3. Action code

{, } 로 둘러싸인 C 프로그램 코드다.

 

 

마지막은 꼭 ; 를 찍어주자.

생성 규칙의 중간에서 어떤 의미 수행 코드를 원할 경우

1. 생성 규칙을 둘로 나누거나
2. 생성 규칙 중간에 액션 코드를 삽입하는 것이다.
   
   

 

• 파스 트리를 구성하거나 직접 중간 언어를 생성하는 작업
• action에서 필요한 variable들은 선언 부분에 %{ 와 %} 를 쓰고 그 안에 선언한다.
  • 전역 변수로 선언이 된다.
  • 함수안 지역변수는 초기화 안하면 에러가 나니 꼭 초기화를 하자.

3. 우선순위

• %left : 좌측 결합을 만족하는 경우
• %right : 우측 결합을 만족하는 경우
• %nonassoc : 좌측 결합, 우측 결합 모두 만족하지 않는 경우
  • 좌측 결합이나 우측 결합을 선택해야 하는 경우는 에러다.
  • 논리식에서 A > B > C 는 에러다
• 같은 line에 정의된 내용은 same precedence(같은 우선순위)
• 뒤 line에 정의된 내용이 앞보다 higher precedence.(높은 우선순위)
  
  

 

이 경우, */ > +- > = 순의 우선순위를 갖는다.

• 가상 terminal 을 사용해 우선 순위를 표현한다.
  
  

 

사진에 쓰여진 statement : if expr ~~ 와 같은 구문 분석에 의하면

원하는 목표 입력을 표현하는 데에 두가지의 경우의 수가 가능하다.

즉, ambiguous 하다.
따라서, 2가지 구문 분석에서의 공통인 부분 if expr statment를 빼서 표현하려고 하는데, 첫번째의 경우에는 뒤에 아무것도 오지 않는 상황이 발생한다.

 

이 경우를 대비하여 가상의 Terminal symbol을 넣어주기로 한 것이다.
이것이 바로 LOWER_THEN_ELSE 이며 이는 결국 앱실론과 비슷한 역할을 하게 된다.
이런 가상의 터미널을 사용하게 되면서, "우선 순위 표현"을 할 수 있게 된 것이다.

4. Ambiguity and Conflicts

• Ambiguity : 문법이 모호하여, 몇 input 문자열을 구조화 할 때, 2개 이상의 방법이 나오게 되는 경우를 말한다.
• Ambiguous grammer always arise the conflicts : 모호한 문법은 항상 충돌을 일으킨다.
  • shift-reduce conflict : 새로운 symbol을 읽어와야 하는 지 (shift), reduce를 해야하는 지 결정하는 못하는 것을 말한다.
  • reduce-reduce conflict : reduce, 즉 되돌릴 수 있는 방법이 너무 많아 결정하지 못하는 경우를 ㅁ말한다.
• YACC invokes two disambiguating rules by default : Yacc은 기본적으로 모호함을 없애는 2가지 방법을 제시한다.
  • shift-reduce conflict -> the default is to do the shift
    • shift-reduce의 경우에는 shift작업을 먼저 한다.
  • reduce-reduce conflict -> the default is to do reduce by the earlier grammer rule
    • reduce-reduce 의 경우에는 먼저 선언된 것부터 reduce 한다.
• 이러한 모호성들은 파서의 속도,성능을 떨어뜨릴 수 밖에 없다.
• 따라서, 이런 conflict가 발생한다면? 가능한 다 없애도록 하자.