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이 현재 입력과 일치할 수 있는 경우
- 가장 긴 매치가 우선된다.
- 같은 수의 문자와 일치하는 규칙 중 먼저 주어진 규칙이 우선된다.
=> 따라서 keyword action을 identifier보다 위에 두어야한다.- ex)
- integer keyword action;
- [a-z]+ identifier action;
- integers -> integers
- integer -> integer => 두 rule 모두에 매칭되지만, 위에 있는 rule 우선
- 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
과제 수행
'학교 > 컴파일러' 카테고리의 다른 글
[Compiler] 8. Normal forms (정규 표현) (0) | 2022.04.18 |
---|---|
[Compiler] 7. Context Free Grammar (0) | 2022.04.16 |
[Compiler] 5. Lexical analysis (0) | 2022.04.14 |
[Compiler] 4-2. Finite Automata (0) | 2022.04.14 |
[Compiler] 4-1. Finite Automata (0) | 2022.04.10 |