컴파일러 강의

[강의교재] [참고도서]
  1. 컴파일러 디자인: 이론과 실제, 유관종-유기영-황대준, 희중당
  2. lex & yacc, J. R. Levine et. al, O'Reilly & Associates, Inc.
  3. Principles of Compiler Design, Aho and Ullman, Addison Wesley
  4. A Small C Compiler, J. E. Hendrix, M & T Publishing Inc.
  5. Machines, Languages, and Computation, Denning, Dennis and Qualitz, Prentice Hall
[실습 프로그램] 
1. 간단한 문법에 대한 언어인식 프로그램

    예제 프로그램 lrs0.c를 참조하여

     (1) getchar() 대신에 스트링을 문자배열에 읽어서 처리하도록 수정하시오.

     (2) 2장의 예8, 예9, 연습문제(2.5, 2.6, 2.8, 2.9)에 대한 언어인식 프로그램을 작성하시오.

2. 주어진 문법에 맞는 스트링을 출력하는 프로그램

    예제 프로그램 lgs0.c과 수정된 실행파일 lgs2.zip, 데이터 파일 grammar.txt를 참조하여
    <참고> 텍스트 파일을 save하려면 마우스 오른쪽 버튼에서 "Save Link As...(다른 이름으로 저장)"을 선택

     (1) 2장의 예8, 예9, 연습문제(2.5, 2.6, 2.8, 2.9)의 문법들에 대해 테스트하시오.

     (2) 스택에 들어있는 sentential form 중에서 길이가 짧은 것부터
          긴 순서로 스트링을 생성하도록 프로그램을 수정하시오.

     (3) 함수 expand()에 포함되어 있는 문법을 데이터 파일에서 읽어서
          처리하도록 수정하시오.

     (4) 특정 입력스트링을 인식할 때까지 스트링들을 생성하도록 수정하시오.

3. p.82 알고리즘에 의해 DFA를 인식하는 프로그램을 작성하시오.
   (예제 프로그램 dfa.c를 참조하여 입력을 getchar() 대신에 스트링을 입력하는 방법으로 수정)

4. NFA를 DFA로 변환하는 프로그램(nfa2dfa.c)을 참조하여 epsilon NFA를 DFA로
   변환하는 프로그램을 작성하시오. [답] Enfa2dfa.c

5. DFA의 상태수를 최소화하는 프로그램(dfa-opt.c, 실행파일 dfa-opt.exe)을 참조하여
   상태수 제약을 받지않고 처리될 수 있도록 수정해 보시오.

6. 어떤 DFA에 대해 inaccessible states를 제거하는 프로그램을 작성하시오.

7. 정규표현(Regular Expression), 예: a*b + b*a,을 epsilon NFA로 변환하는 프로그램을 작성하시오.
[기말과제 프로그램 주제] 
아래 주제 중에서 1개를 선택하여 제안서, 중간보고서, 최종보고서 작성하여 제출

1. LEX 프로그램 작성
   LEX 사용법 및 위 3-7번 프로그램을 하나로 통합하여 정규표현으로부터 DFA를 구하는 LEX 프로그램을 작성
   (1) 정규표현 --> epsilon NFA
   (2) epsilon NFA --> DFA
   (3) DFA --> minimized DFA
   (4) minimized DFA에 의해 입력스트링을 accept 또는 reject 기능 추가
   (5) 2차원 배열로 저장된 minimized DFA를 C source code로 출력하는 기능 추가
   (6) LEX 입력과 유사한 형태로 입력을 받아 yylex() 함수를 생성

2. YACC 프로그램 작성
   YACC 사용법 및 6,7,8장 내용을 공부하여 파싱표를 만들어 주는 프로그램 작성

3. 임의의 CFG에 대해 proper한 문법으로 변환하는 프로그램 작성
   (1) non-terminating nonterminal과 inaccessible symbol 제거
       terminating nonterminal, accessible symbol을 구한다.
   (2) epsilon 생성규칙 제거
   (3) 단일 생성규칙 제거
   (4) cycle-free 문법으로 변환

4. 자기가 설계한 언어에 대한 Compiler 구현
   자기가 스스로 설계한 언어로 작성한 프로그램에 대해 기계어(어셈블리어) 코드를 생성하는 프로그램
   (1) 새로운 언어 설계
   (2) lex를 이용하여 어휘분석
   (3) yacc를 이용하여 parsing(구문분석)
   (4) 구문분석 결과에 대한 어셈블리어 코드 생성 및 실행 -- 시스템 프로그래밍 시간에 배운 어셈블리어 코드로 생성 및 실행

5. 인터넷 검색엔진의 불린 질의어를 SQL문으로 변환하는 프로그램
   (1) 불린 질의문 정의
   (2) lex 이용하여 질의문에 대한 어휘분석
   (3) yacc를 이용하여 parsing
   (4) parsing 결과에 대해 SQL문 생성

6. MFC를 이용하여 간단한 에디터 프로그램 작성(아래 기능이 추가되어야 함)
   (1) 정규표현으로 스트링을 검색하는 기능
   (2) 계산기 기능 -- LEX, YACC를 이용하여 구현해야 함
[기말레포트] 주제 중에서 하나를 선택하여 제안서, 중간보고서, 기말보고서 제출
[연습문제 풀이] 
제2장 -- 문법 관련 문제 풀이
제3장 -- 3.1부터 3.10까지
제4장 -- lex 입력파일 작성
Lex와 Yacc