컴퓨터과학[3-2]/컴파일러16 컴파일러구성 - [제4장]정규문법,정규표현과 결정적 유한오토마타[DFA] 의 동치관계 컴파일러구조 - [제4장]정규문법,정규표현과 결정적 유한오토마타[DFA] 의 동치관계 DFA 상태수 최소화 동치관계 증명 융어정리 동치관계 : Equivalence relation, 반사적이고, 대칭적이고, 추이적인 관계를 만족하는 관계, 정규문법-> 정규표현->유한오토마타 관계가 성립하고 다시 유한오토마타-> 정규문법이 성립하므로 동치관계를 만족한다. 동치류 : 서로 동치(同値)인 것을 하나로 모은 집합. 유한 오토마타 : 어떤 알파벳 T로부터 만들어지는 문자열의 특별한 것들을 받아들이는 시스템의 수학적 모델로서, 그 시스템의 변화할 수 있는 상태가 유한개인 것 정규문법 : A→tB A→t (우선형) 또는 A→Bt A→t(좌선형) 단, t ∈ V*t 정규표현 : 정규문법을 가장 잘 표현할 수 있는 표현.. 2016. 7. 10. 컴파일러구성 - [제3장]정규언어와 유한오토마타 컴파일러구조 - 정규언어와 유한오토마타 용어정리 유한 오토마타 : 어떤 알파벳 T로부터 만들어 지는 문자열의 특별한 것들을 받아들이는 시스템의 수학적 모델로서, 그 시스템이 변화할 수 있는 상태가 유한개인 것 비결정적 유한 오토마타 NFA: 어떤 상태에서 주어진 하나의 입력기호를 보고, 갈수 있는 다음 상태가 두개 이상 존재할 수 있는 유한 오토마타 결정적 유한 오토마타 DFA : 하나의 입력문자열에 대하여 오직 하나의 다음 상태가 결졍되는 것 상태전이도(transition diagram) :오토마타의 각 상태(state)를 노드(node)로 나타내며, 이동함수 δ(q,a) ＝ p에 대해서는 상태 q에서 p로 가는 레이블(label)이 a인 지시선(directed arc)으로 표기. 또한 종결상태들은 이.. 2016. 7. 10. 컴파일러구성 - [제2장]형식언어와 형식문법 컴파일러구성 - [제1장]형식언어와 형식문법 주요용어 형식언어 : 어떤 알파벳 에서 얻은 기호 심볼들로 구성되는 문자열 스트림의 집합 형식문법 : 형식언어를 생성하기 위한 규칙 컨텍스트 프리 문법 : A는 Y이다. 단, A는 논터미날 기호이고 y는 V프라임에 속하는 문자열이다. 촘스키 계층구조 : 생성규칙의 형태에 가해지는 제한에 따라 미국의 영문학자 촘스키가 4종류로 나눈 형식문법 컨텍스트-센서티브 문법 : Y 이면 베타이다. 단, y의 절다값은 베타의 절다값보다 작거나 같으며 베타는 V프라임의 원소이다. 생성규칙에 y의 절대값은 베타의 절다값보다 작거나 같다는 제한을 가하는 것으로 바위측형 난컨트렉팅 문법에 속함 공문자열 : 문자열의 길이가 0인 것, 엡실론 또는 람달로 표시 A이면 tB이고 A이면 .. 2016. 7. 10. 컴파일러구성 - [제1장]컴파일러 개요 컴파일러구성 - [제1장]컴파일러 개요 컴파일러 주요 용어 원시프로그램 : 번역기에 입력되는 프로그램 목적프로그램 : 번역기에서 출력되는 프로그램 어셈블러 : 어셈블리어로 작성된 프로그램을 그에 대응하는 기계어로 번역하여 주는 번역기 컴파일러 : 고급언어(basic, JAVA, C, C++ 등)로 작성된 프로그램을 저급언어로(어셈블리어나 기계어)로 번역해주는 번역기 프리프로세서 : 프로그래밍 언어에 유용한 기능들을 추가하여 언어를 확장시켜 주는 역할을 하는 것으로서, 원시언어와 목적언어가 모두 고급언어인 번역기 인터프리터 : 고급언어를 입력으로 받아들여서 번역과 동시에 실행을 한 후, 그 결과를 출력하기 때문에 APL SNOBOL 등과 같은 대화용 언어를 구현할 경우 사용 디버깅 : 프로그래밍의 오류를 .. 2016. 6. 26. 이전 1 2 3 다음
