강의계획서 (Syllabus) 2018 학년도제 1 학기 교과목명 Title) 형식언어 학수번호 No. -Class No.) CSE4031-01 이수구분 Classification) 강의실 / 수업시간 (Classroom & Time) 전공 학점 (Credit) 월 7.0-8.0, 수 7.0-8.0 401-5145( 신공학관 ( 기숙사 ) 5145 강의실 ),401-5145( 신공학관 ( 기숙사 ) 5145 강의실 ) 3 담당교수 (Instructor) 담당조교 (Teaching Assistant) 이름 (Name) 손윤식이름 (Name) 연구실위치 (Office) 연락처1( 연구실 ) (Office Phone Number) 연락처 1( 연구실 ) (Office Phone Number) e- 메일 (E-mail) e- 메일 (E-mail) 연락처 2( 휴대폰 ) (Cellular Phone) 상담시간 (Office Hours) 강의후 1 시간또는사전연락후개별상담 연락처 2( 휴대폰 ) (Cellular Phone) 상담시간 (Office Hours) 강의개요 Description) 형식언어이론을컴파일러를제작하는적용측면에서학습하는강좌로서정형화된방법으로프로그래밍언어를표현하는기법과다양한문법이론을공부한다. 또한, 특정한문법형태에따른언어를인식할수있는인식기의구조및구문분석방법에대해강의한다. 강의목표 Objectives) 1. 촘스키분류에따른문법이론과오토마타의특징을이해한다. 2. 정규언어를기반으로어휘분석개념을이해하고어휘분석ㄱ기를구현한다. 3. 문맥자유언어를기반으로구문분석개념을이해한다. 1 학습성과목록 (Learning Outcomes) 수학, 기초과학, 인문소양및컴퓨터 - 정보 ( 공 ) 학지식을컴퓨팅분야의문제해결에응용할수있는능력 2 이론이나알고리즘을수식또는프로그래밍등을통해검증할수있는능력 학습성과 3 컴퓨팅분야의문제를정의하고모델링할수있는능력 4 5 컴퓨팅분야의문제를해결하기위해최신정보, 연구결과, 프로그래밍언어를포함한적절한도구등을활용할수있는능력사용자요구사항과현실적제한조건을고려하여하드웨어또는소프트웨어시스템을설계할수있는능력 1/6
학습성과목록 (Learning Outcomes) 학습성과 6 컴퓨팅분야의문제를해결하는과정에서팀구성원으로서팀성과에기여할수있는능력 7 다양한환경에서효과적으로의사소통할수있는능력 8 컴퓨팅분야의해결방안이안전, 경제, 사회, 환경등에미치는영향을이해할수있는능력 9 컴퓨터정보 ( 공 ) 학인으로서의직업윤리와사회적책임을이해할수있는능력 10 기술환경변화에따른자기계발의필요성을인식하고지속적이고자기주도적으로학습할수있는능력 강의방법 (Teaching Method) 요소출석중간고사기말고사과제물기타 1 기타 2 기타 3 기타 4 비율 (%) 10% 35% 35% 20% 성적평가 (Grading) 만점 (Full Marks) 요소기타 5 기타 6 기타 7 기타 8 기타 9 기타 10 기타 11 기타 12 비율 (%) 만점 (Full Marks) 수강요건 ( 선수과목포함 ) PreRequisites) PRI4027 이산수학 시험기출문제및모범답안공개여부 (provide previous exams and answer keys) 2/6
강의구성구분 (Structure) 비율 (Percentage) 강의구조 Structure) 강의 (Lecture) 100 과제명 (Assignment Title) 제출일자 (Due Date) 제출방법 (Mode of Submission) 과제 (Assignments) 교재연습문제 2~5 장 어휘분석기구현 교재및참고서적 (Textbooks & Reference books) 구분 (Type) 주교재 (Primary Textbook) 부교재 (Secondary Textbook) 교재명 (Title) 컴파일러입문, 개정판 Problem Solvinging Automata, Languages, and Complexity 저자 (Author) 출판사 (Publisher) 출판년도 (Publish ed Date) 지정도서 Reserved books) 실험실안전교육계획 기타안내사항 (Other Information) 3/6
주별강의일정 (Class Schedule) 주 (Week) 1 2 3 4 5 6 7 강의내용 (Class Topic & Contents) 강좌개요 - 프로그래밍언어의구조및종류 - 번역기의기능및특징설명 - 일반적인컴파일러의구조. - 컴파일러자동화도구 - LEX, PGS, PQCC, ACK중심 - LLVM 소개 - 최신형식언어 & 컴파일러응용기술소개형식언어 / 문법 - 형식언어 (Formal Language) - 언어와문법과의관계 - 형식언어를위한문법정의 G=(VN,VT,P,S) - 언어와문법관계 - 촘스키계층구조정규언어 / 정규표현 - 정규언어 (Regular Language) - 정규문법 ( 좌선형문법 vs. 우선형문법 ) - 정규표현 (regular expression) - 정규표현의대수학적성질정규문법 / 유한오토마타 - 정규문법으로부터정규표현식생성 - 유일해를이용해서정규문법으로부터정규표현식의생성 - 유한오토마타 (FA: Finite Automata) 의정의및특성 - 결정적유한오토마타 (DFA) vs. 비결정적유한오토마타 (NFA) NFA/DFA - NFA에서 DFA로의변환 - 변환알고리즘 - 도달불가능한상태 (inaccessible state) 제거 - 상태수최소화 (state minimization) - 동치관계 (equivalence relation), 상태수합침 (state merge) RG, RE, FA와의관계 - 정규문법, 정규표현및유한오토마타와의관계 - 정규문법과유한오토마타 - 유한오토마타와정규표현 - 정규언어의닫힘성질 - 정규언어에대한펌핑렘마어휘분석 - 어휘분석 (Lexical Analysis) 토큰인식 : 명칭, 정수, 실수, 스트링, 주석문인식 - 어휘분석기의설계및구현 - Mini C 언어의어휘분석기구현 비고 4/6
주 (Week) 강의내용 (Class Topic & Contents) 어휘분석기생성기 - 어휘분석기생성기 - 어휘분석기생성기의기능및특성 비고 8 - LEX - LEX 의기능및입력설계 - 어휘분석응용기술소개 9 중간고사 Context-Free 문법 / 문법변환 (I) - Context-Free 문법 - 유도 (derivation), 유도트리 (derivation tree), 모호성 (ambiguity) 10 - 문법변환 (I) - 불필요한생성규칙 (useless production) 의제거 - ε-생성규칙의제거문법변환 (II) - 문법변환 (II) 11 - 단일생성규칙 (singleproduction) 의제거 - 문법의기본적인형태 (canonicalform) --- CNF, GNF Context-Free Grammar 표기법 / Push-Down Automata - Context-Free Grammar 표기법 - BNF, EBNF, 문법흐름도 (syntax diagram) 12 - Push-Down Automata - Push-Down Automata의기능과구성 - Extended PDA CFG와 PDA/PDA와 Parser - Context-Free Grammar & Push-Down Automata - Context-Free Grammar에서 Push-Down Automata 구성 13 - Push-Down Automata에서 Context-Free Grammar 구성 - PDA와Parser와의관계 - CFG로부터 Top-down 구문분석 ( 좌측유도 ) - CFG로부터 Bottom-up 구문분석 ( 우측유도 ) 구문분석 - 구문분석 (Syntax Analysis) 14 - 구문분석방법의개론 - 구문분석기의출력 Parsing Method - Parsing Method - Top-Down Method 15 - Bottom-Up Method - Shift-Reduce Parsing --- shift, reduce, accept, error - 구문분석응용기술소개 16 기말고사 5/6
장애학생지원내용 본과목을수강하는장애학생은수업에필요한별도의지원이필요한경우, 담당교강사및장애학생지원센터 ( 서울 02-2260-3043) 로필요한사항을요청하시기바랍니다. 6/6