본문 바로가기
반응형

컴파일러

LEX - LEX는 1975년 Bell 연구소의 Lesk와 Schmidt에 의해서 개발 - Lex는 사용자가 정의한 정규표현과 수행코드를 입력으로 받아, 일반 범용언어인 C로 쓰여진 프로그램을 출력 - 출력된 C 프로그램은 입력문자열에서 정규표현에 해당하는 토큰을 찾았을 때, 그에 결합된 수행코드를 수행한다. LEX의 입력 세 부분 정의부분(Definition Part) %% 변환규칙부분(translation rules part) %% 사용자 부프로그램부분(user subprograms part)각 부분은 생략될 수 있으며 %%에 의해 구분 정의부분 - 이름과 일련의 표현식들로 구성 - 이름은 적당한 식별자이고 표현식은 이름에 해당하는 정규표현이다. 변환규칙 부분 - 표현식들과 일련의 수행코드들로 구성되며 표현.. 더보기
어휘 분석 ( lexical analysis ) 어휘 분석(Lexical Analysis) - 원시 프로그램을 읽어서 토큰(token, 의미있는 문법단위)으로 분리하는 작업 토큰(token) - 의미있는 문법적 단위. 식별자/상수/예약어/연산자/구분자 등 어휘 분석기 설계(순서) 1. 정규문법이 주어져야 함 2. 주어진 문법에 대한 토큰표 작성 3. NFA작성 4. NFA->DFA변환 5. DFA최적화 어휘 분석기 구현 - 문법이 어떻게 주어지는지 명확하게 정의 - 토큰 사용빈도를 확률개념으로 분석해야 함 - 구문분석과 어휘 분석의 선후관계 결정 - 구현방법 예 : 프로그래밍 언어를 이용하여 직접 구현하거나 자동화도구 사용 어휘분석기 생성기 - 컴파일러 생성기 또는 컴파일러-컴파일러의 일부분 - 어휘분석기를 자동생성하는 도구 LEX, FLEX, Sca.. 더보기
형식언어와 오토마타 ( formal language and automata ) 목표 - 형식언어의 문법 및 표기법 이해 - 정규언어와 유한 오토마타의 관계 - 정규표현, 정규문법, 유한 오토마타가 서로 변환되는 관계 요약 - 형식언어 : 어떤 알파벳에서 얻은 기호들로 구성되는 문자열들의 집합 - 형식문법 : 형식언어를 생성하기 위한 규칙. 정규표현(regular expression) 문법도표(syntax diagram) BNF(Backus-Naur Form) EBNF(Extended BNF) - 유한 오토마타 : 형식언어 인식을 위한 방법 결정적 유한 오토마타(Deterministic Finite Automata,DFA) = 하나의 입력문자열에 대해서 오직 하나의 다음 상태가 결정됨 비결정적 유한 오토마타(Nondeterministic Finite Automata,NFA) = 다음.. 더보기
토큰(Token) 식별자(identifier) SUM, A, B와 같은 일반적으로 프로그래머가 정의하는 변수들 상수(constant) 1, 2, 3, 'abc'와 같이 정수형 상수, 실수형 상수, 문자형 상수들 예약어(reserved word) DO, IF, WHILE들과 같이 언어 구현시 이미 정의되는 지정어 연산자(operator) -, +, *, / 등과 같이 연산시 사용되는 기호들 구분자(delimiter) (, [, ;, :, , 등과 같이 단어와 단어를 구분하기위해 사용되는 기호들 더보기
컴파일러의 논리적 구조 6단계 컴파일러의 논리적 구조 6단계 1. 어휘분석(Lexical Analysis) 원시프로그램을 읽어 들여 문법적 단위(토큰,token)으로 분리하여 출력하는 기능 2. 구문분석 토큰들이 주어진 문법에 맞는지 검사하여, 맞는 문장은 구문구조(파스 트리,parse tree)를 만들어 출력하고, 틀린 문장은 오류 메시지를 작성함. 생성된 파스 트리를 바탕으로 구문트리(syntax tree)를 생성함 3. 의미분석(Syntax Analysis) 구문트리를 검사하여 산술식,연산자,피연산자,형(type)에 대한 검사를 수행 4. 중간코드 생성 구문지시적 변환(Syntax-directed translation)을 수행함 5. 코드최적화 코드 실행시 기억공간이나 실행시간을 절약하기 위해 지역최적화 또는 전역최적화를 수행함.. 더보기
촘스키 계층구조(Chomsky Hierarchy) 촘스키 계층구조(Chomsky–Schützenberger hierarchy) -> http://en.wikipedia.org/wiki/Chomsky_hierarchy -> http://www.aistudy.co.kr/linguistics/chomsky_hierarchy.htm 아~, 이건 대체 무슨 심오한 의미인지 ,,, 어렵다. 더보기
반응형

티스토리툴바