컴파일러구성 - [제5장] 어휘분석기와 LEX

컴파일러구성 - [제5장] 어휘분석기와 LEX

어휘분석기 설계 및 구현 ·LEX 소개 및 실행

컴파일러 용어정리

토큰(token) : 의미 있는 문법적 최소 단위

예약어(reserved word) : 언어 구현시 이미 지정되는 지정어로 IF, WHILE, DO, FUNCTION 등

연산자(operator) +,*,/,-, :=, AND,OR 등으로 사칙연산자, 치환연산자, 논리연산자 등이 있다.

구분자(delimiter) 단어와 단어를 구분하기 위해 사용되는 기호들

복귀값(return value) 프로그램에서 함수(function)를 호출(call)하였을 때 그 결과로서 돌려받는 값. 수행 결과나 ‘0’, ‘－1’ 등 미리 지정된 값을 받을 수도 있으며, 그 반환값을 출력하는 대신 하나의 변수에 할당할 수도 있다.

식별자(identifier) 변수나 프로그램 이름, 함수 이름, 프로시주어 이름, 서브루틴 이름 등으로 데이터 항목에 이름을 부여하여 일시적으로 규정하거나, 그 데이터의 어떤 특성을 표시하기 위해서 사용하는 기호 또는 기호의 집합.

어휘분석기 생성기 컴파일러 생성기(compiler generator) 또는 컴파일러-컴파일러(compiler compiler)의 일부분으로서 어휘분석기를 자동으로 생성하는 도구이다. 어휘분석기의 종류에는 LEX, FLEX, ScanGen, PCLEX, JLEX 등이 있다.

LEX 1975년 Bell 연구소의 Lesk 와 Schmidt에 의해서 개발된 어휘분석 생성기이다. Lex의 입력은 정의부분, 변환규칙부분, 사용자 부 프로그램 부분으로 구성되며 C 언어로 된 결과를 출력한다.

요점정리

1. 어휘분석(lexical analysis)이란 원시 프로그램을 읽어 들여 토큰(token)이라는 의미 있는 문법단위로 분리하는 것을 말하며, 어휘분석을 담당하는 도구를 어휘분석기(lexical analyzer) 또는 스캐너(scanner)라 한다.
2. 토큰(token)이란 의미있는 문법적 단위로서 일반적으로 식별자(identifier), 상수(constant), 예약어(reserved word), 연산자(operator), 구분자(delimiter) 등이 사용된다. 토큰의 종류와 형태는 프로그래밍 언어 설계자나 컴파일러 설계자에 의해 결정된다.
3. 어휘분석기를 설계하기 위해서 우선 정규문법이 주어져야 하며(이 정규문법은 일반적으로 정규표현으로 표시된다 주어진 문법에 대한 토큰표(token table)를 작성한다. 다음으로 문법을 보고 NFA를 구성하고, NFA를 DFA로 변환한 다음, DNF를 최소화시키면 어휘분석기가 된다.
4. 어휘분석기를 구현할 때에는 문법이 어떻게 주어지는지 명확하게 정의되어야 하며, 어떤 토큰들을 많이 사용하는지 확률개념을 도입해야 한다. 또한 구문분석을 하면서 부프로그램처럼 어휘분석기를 호출할 것이냐 아니면 어휘분석기를 먼저 수행시킨 다음 그 결과를 구문분석기에 전달할 것이냐 하는 것도 구현시 고려되어야 한다. 이외에 예약어의 처리 및 실수의 내부표현 등도 고려해야 한다.
5. 어휘분석기 생성기는 컴파일러 생성기(compiler generator) 또는 컴파일러-컴파일러(compiler compiler)의 일부분으로서 어휘분석기를 자동으로 생성하는 도구이다. 어휘분석기의 종류에는 LEX, FLEX, ScanGen, PCLEX, JLEX 등이 있다.

연습문제

• 

  토큰을 종류별로 구분했을 때이다. 관계없는 것은?

  답을 체크하세요

  1. 식별자
  2. 예약어
  3. 피연산자
  4. 구분자

  정답 :

  ③

  토큰의 종류: 식별자, 상수, 연산자, 예약어, 구분자

• 

  다음은 토큰에 대한 설명이다. 옳지 않은 것은?

  답을 체크하세요

  1. 식별자 : SUM, A, B와 같은 일반적으로 프로그래머가 정의하는 변수들
  2. 상수 : 1, 2, 3, 'abc'와 같이 정수형 상수, 실수형 상수, 문자형 상수들
  3. 구분자 : (, [, ;, :, , 등과 같이 단어와 단어를 구분하기 위해 사용되는 기호들
  4. 연산자 : DO, IF, WHILE 등과 같이 언어 구현시 이미 정의되는 지정어

  정답 :

  ④

  예약어에 대한 설명이다. 

• 

  다음은 어휘분석기를 설계하는 과정이다. 틀린 것은?

  답을 체크하세요

  1. 정규문법이 주어지고 정규표현으로 표시한다. 그리고 주어진 문법에 대한 기호표를 작성한다.
  2. 5 종류의 토큰들 중에서 어느 것이 사용되는가를 조사하여 토큰표를 작성한다. 토큰표에는 토큰이름, 토큰번호, 토큰값을 표시한다.
  3. 문법을 보고 NFA 를 구성하고 이를 다시 DFA 변환한 후 최소화 한다.
  4. 예약어표 검색은 상태전이도로 구현하거나, 표를 만들어 저장한 다음 검색하도록 한다.

  정답 :

  ①

  ①번에서 "정규문법이 주어지고 정규표현으로 표시한다. 그리고 주어진 문법에 대한 토큰표를 작성한다." 가 되어야한다. 즉, 기호표가 아니고 토큰표가 올바르다. 

• 

  토큰을 종류별로 구분했을 때이다. 관계없는 것은?

  답을 체크하세요

  1. 식별자
  2. 예약어
  3. 피연산자
  4. 구분자

  

  

  정답 및 해설

  정답 :

  ③

  토큰의 종류: 식별자, 상수, 연산자, 예약어, 구분자

• 

  다음은 토큰에 대한 설명이다. 옳지 않은 것은?

  답을 체크하세요

  1. 식별자 : SUM, A, B와 같은 일반적으로 프로그래머가 정의하는 변수들
  2. 상수 : 1, 2, 3, 'abc'와 같이 정수형 상수, 실수형 상수, 문자형 상수들
  3. 구분자 : (, [, ;, :, , 등과 같이 단어와 단어를 구분하기 위해 사용되는 기호들
  4. 연산자 : DO, IF, WHILE 등과 같이 언어 구현시 이미 정의되는 지정어

  

  

  정답 및 해설

  정답 :

  ④

  예약어에 대한 설명이다.

• 

  다음은 어휘분석기를 설계하는 과정이다. 틀린 것은?

  답을 체크하세요

  1. 정규문법이 주어지고 정규표현으로 표시한다. 그리고 주어진 문법에 대한 기호표를 작성한다.
  2. 5 종류의 토큰들 중에서 어느 것이 사용되는가를 조사하여 토큰표를 작성한다. 토큰표에는 토큰이름, 토큰번호, 토큰값을 표시한다.
  3. 문법을 보고 NFA 를 구성하고 이를 다시 DFA 변환한 후 최소화 한다.
  4. 예약어표 검색은 상태전이도로 구현하거나, 표를 만들어 저장한 다음 검색하도록 한다.

  

  

  

  

  정답 및 해설

  정답 :

  ①

  ①번에서 "정규문법이 주어지고 정규표현으로 표시한다. 그리고 주어진 문법에 대한 토큰표를 작성한다." 가 되어야한다. 즉, 기호표가 아니고 토큰표가 올바르다.

• 

  어휘분석기 생성기로써 1975년 Bell 연구소의 Lesk 와 Schmidt에 의해서 개발되었으며 정의부분, 변환규칙부분, 사용자 부프로그램 부분으로 구성된 것은?

  답을 체크하세요

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

  정답 :

  ①

  어휘분석기 생성기 : Lex, Scan gen
  구문분석기 생성기 : YACC, LALRGEN
  Lex: 1975년 Bell 연구소의 Lesk 와 Schmidt에 의해서 개발되었으며 정의부분, 변환규칙부분, 사용자 부프로그램 부분으로 구성되어 있다.

• 

  다음 설명 중 틀린 것은 ?

  답을 체크하세요

  1. Lex는 Bell 연구소의 Lesk와 Schmidt 에 의하여 개발된 어휘분석 생성기이다.
  2. Lex의 입력은 정의부분, 변환규칙부분, 사용자 부 프로그램 부분으로 구성되며 C 언어로 된 결과를 출력한다.
  3. Scangen은 이식성이 쉽고, 언어와 기계에 대해 고도로 독립적인 장점이 있는 구문분석 생성기이다. option, class 정의, 정규표현 정의 등 3 부분으로 구성되어 있다.
  4. YACC는 Bell 연구소에서 개발되었으며 입력으로는 문법규칙과 수행 코드들이며 선언부분, 변환규칙부분, 사용자 프로그램부분으로 구성된다.

  정답 :

  ③

  ③번을 보면 Scangen은 이식성이 쉽고, 언어와 기계에 대해 고도로 독립적인 장점이 있다. 그리고 option, class 정의, 정규표현 정의 등 3 부분으로 구성되어 있다. 그러나 구문분석 생성기가 아니고 어휘분석생성기이다.