컴파일러구성 - [제13강] YACC와 LALRGen (실습과정 소개)

컴파일러구성 - [제13강] YACC와 LALRGen (실습과정 소개)

YACC 소개 ·YACC의 실행 예 ·LALRGen

컴파일러 용어정리

• YACC
  문법규칙에 대한 수행코드를 일반적인 프로그래밍 언어로 기술할 수 있도록 만든 LALR(1) 구문분석기 생성기
• YACC 선언 부분
  선언 부분은 생략될 수 있으며, 만약 사용자 프로그램 부분이 생략될 경우, 두 번째 %% 기호도 생략 가능.
  선언 부분은 문법규칙의 토큰에 대한 선언과 변환규칙 부분과 프로그램 부분에서 사용될 임시변수들에 대한 선언을 함.
• YACC 변환규칙 부분
  변환규칙 부분은 일련의 문법규칙으로 구성되고 각 규칙은 LHS(Left Hand Side)와 body의 형태를 취함.
  여기서 LHS는 논터미널의 이름이고 body는 문법규칙의 오른쪽 부분에 나오는 기호들로 이름이나 일련의 상수문자가 될 수 있음.
  YACC의 각 규칙에 대한 수행코드들이 C언어로 기술되고, 수행코드는 각 규칙이 reduce될 때 실행됨.
• YACC 사용자 프로그램 부분
  사용자 프로그램 부분은 YACC를 보조하는 C루틴들로, 오류처리 루틴 등이 첨가됨. YACC는 컴파일러 자동생산을 염두에 두고 설계되었으나, 아직도 컴파일러 작성자에게 의미수행코드와 컴파일러의 코드생성 단계 그리고 코드최적화 단계의 제공을 요구함.
•  LALRGen
  option, 문법의 터미널 기호, 문법의 생성규칙 등 3부분으로 구성되어 있는 LALR(1) 구문분석기 생성기

요점정리

1. YACC는 1975년 Bell 연구소에서 Stephen C. Johnson을 중심으로 개발된 LALR(1) 구문분석기 생성기로 문법규칙에 대한 수행코드를 일반적인 프로그래밍 언어로 기술할 수 있도록 만들었다.
2. YACC의 입력은 문법규칙과 각 규칙에 대한 수행코드들이며 다음과 같이 세 부분으로 구성된다.
   1) 선언 부분
     선언 부분에서는 문법에서 사용할 토큰의 선언, 구문분석기에서 사용할 타입을 선언한다. %start로 start 기호를 정의한다. %{ .. %}내에
     내용을 기술하게 되며 어휘분석기에서 반환되는 모든 토큰에 대한 정의를 %token 으로 정의한다.
   2) 변환규칙 부분
     문법 규칙과 수행코드로 구성된다. 변환규칙 부분에서는 문법의 규칙을 정의한다. BNF(Backus Naur Form)과 유사한 방식으로
     문법규칙들을 기술한다.
   3) 사용자 프로그램 부분
     생성될 파서코드의 뒤로 그대로 복사될 C 코드로 보통은 main()함수 내에서 구문분석기 함수인 yyparse()를 호출한다. 이 함수는 Lex 입력
     파일을 yyin으로 토큰을 읽어 들여 지정된 문법 규칙에 따라 파싱을 수행한다.
3. LALRGen은 Wisconsin-Madison 대학의 Jon Mauney에 의해서 만들어졌다. LALRGen은 option, 문법의 터미널 기호, 문법의 생성규칙 등 3부분으로 구성되어 있다.
4. 지금까지 우리는 컴파일러의 핵심 구성요소인 구문분석기를 만들기 위해서 유한 오토마타를 설명했고 LR 구문분석에 대하여 설명을 했다. 그러나 실제로 컴파일러를 작성할 때는 앞에서 예를 보여준 것처럼 일일이 유한 오토마타를 만들고, canonical collection을 만들고 이것을 다시 goto그래프를 작성하고 나서 일일이 파싱표를 만드는 것이 아니라 지금 예에서 본 것처럼 LEX, YACC. LALRGen 등 컴파일러 전용 소프트웨어를 사용하여 쉽게 작성을 한다. 이로서 보다 정확한 컴파일러를 손쉽게 구성할 수가 있다. 

연습문제

• 

  Bell 연구소에서 Stephen C. Johnson을 중심으로 개발된 LALR(1) 구문분석기 생성기로 선언부분(declation), 변환규칙 부분(translation rules), 사용자 프로그램 부분(user program) 등의 세 부분으로 구성된 것은?

  답을 체크하세요

  1. Lex
  2. Scan gen
  3. YACC
  4. LALR GEN

  정답 :

  ③

• 

  다음 빈 괄호에 알맞은 것은?
  

  연습문제 설명

  YACC의 입력은 문법규칙과 각 규칙에 대한 수행코드들이며 선언부분, (        ), 사용자 프로그램 부분 등의 세 부분으로 구성된다.

  답을 체크하세요

  1. 구문분석기 부분
  2. 변환규칙 부분
  3. 어휘분석기 부분
  4. 수행코드 부분

  정답 :

  ②

  YACC는 1975년 Bell 연구소에서 Stephen C. Johnson을 중심으로 개발된 LALR(1) 구문분석기 생성기로 문법규칙에 대한 수행코드를 일반적인 프로그래밍 언어로 기술할 수 있도록 만든다.
  YACC의 입력은 문법규칙과 각 규칙에 대한 수행코드들이며 선언부분(declation),변환규칙 부분(translation rules), 사용자 프로그램 부분(user program) 등의 세 부분으로 구성된다.
  

  선언 부분(Declaration Part)
  %%
  변환규칙 부분(Translation Rules Part)
  %%
  사용자 프로그램 부분(User Program Part)

  
  (주요용어 설명 참조.)

• 

  다음 빈칸의 A,B에 들어갈 내용이 알맞은 것은?
  

  연습문제 설명

  

  
  

  

  

  

  답을 체크하세요

  1. A: 어휘분석기, B: YACC
  2. A: YACC, B: 어휘분석기
  3. A: 원시코드, B: YACC
  4. A: 어휘분석기, B: LALRGen

  정답 :

  ②

• 

  구문 분석 생성기로써 Jon Mauney에 의해서 만들어졌으며 option, 문법의 터미널기호, 생성규칙으로 구성된 것은?

  답을 체크하세요

  1. Lex
  2. Scan gen
  3. YACC
  4. LALR GEN

  정답 :

  ④

• 

  다음과 같은 형식의 구문 분석 생성기는?
  

  <comments>
    ＊ ecp
    <options>
    ＊ define
    <constant definitions>
    ＊ terminals
    <terminal specifications>
    ＊ productions
    <production specifications>
    ＊ end
    <comments>

  답을 체크하세요

  1. Lex
  2. Scan gen
  3. YACC
  4. LALR GEN

  정답 :

  ④

  YACC와 마찬가지로 LALR(1) 구문분석기 생성기인 LALRGen은 Wisconsin-Madison 대학의 Jon Mauney에 의해서 만들어 졌다. LALRGen은 다음과 같이 option, 문법의 터미널 기호, 문법의 생성규칙 등 3부분으로 구성되어 있다.
  
  <comments>
    ＊ ecp
    <options>
    ＊ define
    <constant definitions>
    ＊ terminals
    <terminal specifications>
     ＊ productions
    <production specifications>
    ＊ end
    <comments>
  
  모든 토큰들은 하나 이상의 공백이나 탭 혹은 한 줄의 끝에 의해서 분리되어야 하고, 토큰들이 “<”와 “>”에 의해서 사용되지 않는다면 공백이나 탭을 사용할 수 없다. 연속적인 줄을 사용할 수 없으며 하나의 토큰이 “<”으로 시작하면 “>”으로 끝나야 한다.