[Compiler] 6. Lex

Lex

Lexical Analyzer(Scanner) Generator

스캐너 프로그램을 만드는 프로그램이다.

• 문장 입력 stream의 lexical processing을 위해 설계된 프로그램 생성기
• Input
  • 문자열 정규표현식에 대한 High-level specification
  • 정규식과 관련된 프로그램 조각
• Output
  • 범용 언어로 된 프로그램
  • 입력 스트림의 식을 인식한다. 입력 스트림을 이 식과 일치하는 문자열로 분할한다.
  • 엄밀히 C 코드가 생성된다.

 

An overview of Lex

• Source에 C 코드 추가 가능

 

Lex

lexical analysis 단계를 수행하기 위해 parser 생성기와 함께 사용한다.

• Scanner : Lex가 만든다.
• Parser : yacc이 만든다.

lexical level에서 변환, 분석, 통계 수집에 단독으로 사용한다.

 

Lex with Yacc

 

General format of Lex source

{definitions}  // optional
%%
{rules}  // 필수
%%
{user subroutines}  // optional

• 크게 3 parts
• %%로 구분
• optional 부분은 없어도 된다.
  %%
  {rule}
  => 이렇게만 입력 가능

 

Example of Lex source

%{
    #include <math.h>
%}
DIGIT                   [0-9]
ID                      [a-z][a-z0-9]*
%%
{DIGIT}+                {printf("An integer: %s (%d) \n", yytext, atoi(yytext));}
{DIGIT}+"."{DIGIT}*     {printf("A float: %s (%g)\n", yytext, atof(yytext));}
if|then|begin|end       {printf("A keyword: %s\n", yytext);}
{ID}                    {printf("An operator: %s\n", yytext);}
"+"|"-"|"*"|"/"
%%
main(argc, argv) int argc; char **argv;
{
    ++argv, --argc;
    if(argc > 0)
        yyin = fopen(argv[0], "r");
    else
        yyin = stdin; yylex();
}

 

Rule

사용자의 제어 결정을 나타낸다.

• 형식
  • Left column : regular expressions
  • Right column : regular expressions이 인식될 때 실행할 actions, program fragments
  • ex)
    integer    printf("found keyword INT");
  • integer -> Left column
  • printf~ -> Right column
  • input stream에서 integer문자열을 찾아서 matching되면 Right column을 수행
• expression의 끝
  • 첫 번째 공백 혹은 탭 문자
• action의 끝
  • 동작이 단지 단일 C 식인 경우
  • 줄이 하나 이상 필요한 경우 대괄호{}로 묶는다.

 

Regular-expression

일치시킬 문자열 집합 지정

• 텍스트 문자 + 연산자 문자
• 텍스트 문자(비교 중인 문자열의 해당 문자와 일치)
• 연산자 문자(반복, 선택 및 기타 기능)

알파벳 문자와 숫자는 항상 텍스트 문자다.

• ex ) regular expression : integer
  -> integer라는 문자열과 매칭된다.

 

Operator character

- 연산자가 아닌 text로 인식시키려는 경우

• ""로 감싸기     ex) "+"
• 앞에 \ 붙이기 ex) \+

- [] : character classes

• ex)
  [abc]
  [abc]+

- - : ranges

• [a-z] : lower case letters
• [a-z0-9] : lower case letters, digits
• [a-z0-9<>_] : lower case letters, digits, <, >, _

- ^ : not

• [^abc] : abc를 제외한 모든 문자
• [^a-zA-Z] : 영문자를 제외한 모든 문자

- \ : ASCII

• [\40-\176] : ASCII 40번부터 176번까지

- ? :  optional exement

• [ab?c] : ac || abc

- Repeated expressions

• * : 0 이상의 길이인 문자열
• A* : , A, AA, AAA, ...
• + : 1 이상의 길이인 문자열
• A+ : A, AA, AAA, ...

- | : alternation

• ab|cd : ab || cd

- () : grouping

• (ab|cd)
• (ab|cd+)?(ef)*

- ^ : beginning of a line

• ^abc : 라인의 시작에 문자열 abc가 나타났을 때만 토큰으로 처리
• *** not과 구별해야 한다!!

- $ : end of line

• 라인의 끝에서만 인식

- / : trailing context

• ab/cd : ab 다음에 cd가 이어서 나타날 때만 ab가 토큰으로 처리

- {} : repetitions or definition expansion

• {digit} : definition expansion
• a{1, 5} : 1 ~ 5까지 반복하는거 찾는다.

- .

• newline을 제외한 모든 문자

 

Lex actions (Right column 기술)

Default action

• 인식되지 않은 문자에 대해 input을 output으로 복사한다.

yytext

• lex의 전역 변수
• 문자의 배열형
• regular expression에 의해 실제로 매칭된 문자열 값을 저장
• ex)
  [a-z]+    printf("%s", yytext);
  [a-z]+    ECHO;

yyleng

• 매칭된 문자열의 길이를 저장
• ex)
  [a-zA-Z]+    printf("%d", yyleng);
  aabbc 23aab => 결과 : 5 3
• 활용
  yytext[yyleng - 1] -> 매칭된 문자열의 마지막 문자

yymore()

• 매칭된 문자열의 끝에 다음에 인식될 문자열 첨가

yyless(n)

• n개의 문자만을 yytext에 남겨두고 나머지는 다시 처리하기 위하여 입력 스트림으로 되돌려 보내는 함수.

 

Ambiguous Source Rules

두 개 이상의 expression이 현재 입력과 일치할 수 있는 경우

1. 가장 긴 매치가 우선된다.
2. 같은 수의 문자와 일치하는 규칙 중 먼저 주어진 규칙이 우선된다.
   => 따라서 keyword action을 identifier보다 위에 두어야한다.
   • ex)
   • integer    keyword action;
   • [a-z]+     identifier action;
   • integers -> integers
   • integer -> integer => 두 rule 모두에 매칭되지만, 위에 있는 rule 우선
3. single quotes 안의 문자만 인식하기
   • ex) 'first' quoted string here. 'second' here
   • Regular expression : '.*'
   • Output : 'first' quoted string here. 'second' here
     => why? : 1번의 가장 긴 매칭을 우선한다고 했기 때문이다.
   • 또 다른 Regular expression : '[^.\n']*'

 

Definition

macros (매크로)

%{
    #include <math.h>
%}
D       [0-9]
%%
{D}+    printf("integer");

• 헤더 파일, 변수, 코드를 Import 한다.
• 헤더파일, 변수 등이 lex.yy.c에 그대로 복붙이 된다.

 

User subroutines

%%
main(argc, argv) int argc; char **argv;
{
    ++argv, --argc;
    if(argc > 0)
        yyin = fopen(argv[0], "r");
    else
        yyin = stdin; yylex();
}

• 코드들이 generate source 코드에(lex.yy.c) 그대로 붙는다.

 

Practice exercise

lex sourceFile
gcc lex.yy.c -ll
lex -o outputFile sourceFile

 

과제 수행

https://github.com/ekdud0529/compiler/tree/main/lex