형식언어 - 어휘분석기의 구현

수업 일자 : 2022/05/06

4.3 어휘분석기의 구현

• 어휘분석기의 설계방법
  • 기존 프로그래밍 언어를 사용하여 어휘 분석기를 프로그래밍(Programming)
  • EX와 같은 컴파일러 생성 도구를 사용하여 어휘 분석기 생성(Generating, Constructing)

 

4.4 Lex (Lexical Analzer Generator)

-> 참고 : http://contents.kocw.or.kr/document/lec/2012/ChungBuk/LeeJaeSung/cp-6.pdf

4.4.1 Introduction

• Lex는 문자 입력 스트림의 어휘 처리를 위해 설계된 프로그램 생성기이다.

(1). LEX는 사용자의 Expression과 Action을 호스트 범용 언어로 번역한다. (생성된 프로그램의 이름 : lex.yy.c)

(2). yylex 함수는 stream의 표현식을 인식하고, 각 표현식이 탐지될 때마다 지정된 액션을 수행한다.

 

4.4.2 Lex Source

• 형태
  • { definitions } // 정의 부분
    %%
    { rules } // 규칙 부분
    %%
    { user subroutines } // 사용자 부프로그램 부분
  • 두번째 %%는 선택 사항, 첫 번째 %%는 규칙의 시작을 표시해야한다.
  • Lex에 의해 해석되지 않은 모든 source는 생성된 프로그램에 복사된다.
• Rule ::= regular expressions + actions

 

4.4.3 Lex regular expressions 

• Lex regular expressions
  • ::= text characters + operator characters
• text characters
  • 비교되고 있는 문자열에서 상응하는 characters와 매치한다.
  • 알파벳과 숫자들은 항상 text characters이다.
• Operator characters --- ′′ [] ^ − ? . * + () $ / {} % <>
  1. ” (double quote) --- 쌍따옴표 사이에 있는 모든 문자를 텍스트 문자로 취급
       ex) XYZ"++" <=> XYZ++
  2. \ (backslash) --- 한 개의 문자를 escape
       ex) XYZ\+\+ <=> XYZ++
  3. [ ] --- 문자들의 종류
       (가) - (dash) --- 범위를 표시
       ex) [a-z0-9] 모든 소문자와 숫자를 포함한 character class를 표시한다.
              [-+0-9] 두개의부호화 숫자를 매치한다.
       (나) ^ (hat) --- 부정이나 여집합을 표시 ex) [^a-zA-Z]는 영문자를 제외한 모든 문자를 나타낸다.
       (다) \ (backslash) --- 8진법의 escape처럼 문자를 escape
       ex) [\40-\176] 아스키 값 40인 공백부터 176인 ~(tilde)까지 모든 인쇄 가능한 문자를 나타낸다.
  4. . --- 개행 문자를 제외한 모든 문자들을 나타낸다.
       ex) "--".*는 -- 부터 한 라인의 끝까지
  5. ? --- 선택을 의미하는 연산자
       ex) ab?c <=> ac 또는 abc
  6. * , + --- 반복 표현
       a*는 a가 0번 이상 반복될 수 있음을 나타낸다.
       a+는 한 번 이상 반복될 수 있음을 나타낸다.
       ex) [a-z]+
                          [0-9]+
                                        [A-Za-z_] [A-Za-z0-9_]* --- Identifier
  7. | --- 하나의 선택을 의미하는 연산자
       ex) (ab | cd) 는 ab or cd.
  8. ^ --- 라인의 시작에서만 인식
  9. $ --- 오직 라인의 끝에서만 인식
  10.  / --- 접미 문맥을 명시할 때 사용
        ex) ab/cd ab 다음에 cd가 이어서 나타날 때만 ab가 토큰으로 처리된다.
        ex) ab$ <=> ab/\n (11) < > --- 시작 상태 표시 
  11. { } --- 정의된 이름을 확장할 때 사용

 

4.4.4 Lex actions

• 정규 표현에 일치되는 문자열, 즉 토큰이 인식되었을 때 실행해야 할 행동
• default action
  • 인식되지 않은 모든 문자에 대해 실행되는 default action은 입력을 출력으로 그대로 복사
• null action - 입력을 무시하고 싶을 경우
  • ex) [\t\n];
    구분자로 사용된 공백, 탭, 개행 문자를 입력에서 무시하고 싶을 때 처리하는 방법
• | (alternation-교체)
  •  동일한 액션 코드의 반복적인 표기를 생략
      ex) [\t\n ] ; <=> " " |
                                 "\t" |
                                 "\n" ;
• 전역 변수와 함수 (Lex 명령 작성시 사용할 수 있는 변수 및 함수)
  1. yytext : 정규 표현과 매칭된 실제 문자열
       ex) [a-z]+ printf("%s",yytext);
  2. yyleng : 매칭된 문자열의 길이를 나타내는 변수
       ex) yytext[yyleng-1] : 매칭된 문자열의 마지막 문자
  3. ECHO : 출력에 매칭된 문자열을 출력
       ex) ECHO <===> printf("%s",yytext);
  4. yymore : 현재 매칭된 문자열의 끝에 다음에 인식된 문자열이 덧붙여지도록 하는 함수
  5. yyless(n) : n개의 character만을 yytext에 남겨두고 나머지는 reprocess를 위하여 input으로 되돌려 보낸다.
  6. I/O routines
     1) input() 입력 스트림으로부터 다음 문자를 읽는 함수
     2) output(c) 출력 스트림으로 문자 c를 내보내는 함수
     3) unput(c) 다시 처리될 수 있도록 문자 c를 입력 스트림으로 되돌려 보내는 기능을 하는 함수, input()에 의해 다시 읽혀진다.
  7. yywrap() : Lex가 입력 파일의 끝에 도달할 때 요청된다.

 

4.4.5 모호한 Rule

• 규칙 모호성
  • 하나의 문자열이 여러 개의 규칙에 적용될 경우
• 해결
  1. 가장 길게 인식할 수 있는 정규 표현을 우선한다.
  2. 인식할 수 있는 토큰의 길이가 같은 경우, 먼저 기술된 정규 표현을 선택한다.
     ex) integer     Keyword action;
              [a-z]+     identifier action;
• 기본 동작 원칙
  • Lexsms 보통 각 표현의 가능한 모든 match를 찾는 것이 아니라 입력 스트림을 분할하는 것이다. 즉, 각 문자는 한 번만 처리한다는 의미이다.

 

4.4.6 Lex definitions // 정의 부분

• Definitions
  ::= 선언부 + 매크로 정의
• 선언부
  • %{                  %} 사이에 있는 코드
  • Lex에 의해 아무 처리 없이 lex.yy.c의 앞부분에 복사된다
• 매크로 정의
  • Lex 규칙의 정규표현에 사용할 표현을 미리 정의
                  name                  translation
  • 매크로 정의의 사용 : {name}
    ex)          D                          [0-9]
                    L                          [a-zA-Z]
                    %%
                    {L}({L}|{D})*        return IDENT;

4.4.7 Usage (사용법)

4.4.8 Lex and Yacc