Lex and Yacc
- 1970년대 벨 연구소에서 개발되어, 후에 UNIX 표준 유틸리티로 선정되었다.
- Lex가 입력 문자열에 대한 일차적인 검색을 수행하고, 실질적인 분석은 Yacc가 수행한다.
- Source → Lex Scanner → Yacc Parser 순서로 처리한다.
- 즉, 입력 Syntax의 검색과 분석을 용이하게 위해 사용하는 언어들이다.
- 수치와 연산자를 구분하는 계산기 프로그램, 컴파일러, 인터프리터 언어의 문장 검색, 문법 분석 기능, SQL 언어의 문법 검사와 같은 기능들을 Lex와 Yacc로 구현할 수 있다.
Lex (Lexical Analyzer Generator, 어휘 분석 생성기)
- 1975년 AT&T Bell 연구소의 Eric Schmidt와 Mark Lesk가 UNIX 시스템의 유틸리티로 개발한 S/W이다.
- 일반적으로, Lex는 Yacc Parser Generator와 함께 사용된다.
- 일정한 구조를 가진 입력을 의미 있는 단위로 분해하여 관련성을 파악하는 프로그램이다.
- 입력을 Token 단위로 나누고, 식별할 수 있는 루틴(Scanner*)을 생성한다.
- Lex로 작성된 코드를 Lex Specification이라고 부른다.
* Scanner : Text의 어휘 패턴을 인식하는 프로그램이다.
※ Meta Symbols in Lex (정규표현식 기호, 참조 URL)
- 특정한 규칙을 가진 문자열의 집합을 표현하는데 사용하는 형식 언어이다.
- 먼저 작성된 규칙이 먼저 선택되는 구조이다. (먼저 작성된 규칙의 우선 순위가 높다. 그러므로 자세하게 기술된 규칙의 경우 윗 줄에 배치하도록 한다.)
* : 0회 이상의 반복을 의미한다.
+ : 1회 이상의 반복을 의미한다.
? : 0회 또는 1회 반복을 의미한다. (선택적 사항임을 정의)
| : or 기호를 의미한다.
. : 앞에 선언된 문자들을 제외한 모든 문자를 의미한다.
- Lex Code는 크게 Definitinos(정의절), Rules(규칙절), Use Code Section(서브루틴절)로 나뉜다.
1. Definitions (정의절)
- Rules에서 사용할 패턴을 간단하게 표기하기 위한 선언과 초기 조건을 명시하는 부분이다.
- %{ C-Code %} 형태로 C Code를 삽입할 수도 있다.
- 최종 프로그램에 포함하고자 하는 C 프로그램의 내용을 삽입할 수 있다.
- 출력을 위한 헤더, 분석한 코드의 카운트를 담당하는 변수가 포함될 수 있다.
- 즉, C 코드와 Lex 코드가 함께 기술될 수 있는 부분이다.
%% (정의절과 규칙절 사이를 %%로 구분한다.)
2. Rules (규칙절)
- 정의한 패턴에 매칭되는 문자열이 입력되었을 경우 수행되는 동작을 정의한다.
- { C-Code } 형태로 C Code를 삽입할 수도 있다.
Ex. 표준 입력을 표준 출력으로 내보내는 규칙절의 Lex Statement
.|\n {ECHO;}Ex. White Space를 무시하는 규칙절의 Lex Statement
[\t]+ ;
[\t]+ { }※ Lex Library (참조 URL)
yylex() // Scanner 함수이다. (입력된 문자를 처리하는 함수)
yywrap() // yylex()가 EOF를 만나면 호출된다. (return 값을 1로 해야한다.)
yytext // 정규 표현식에 따라 인식된 문자열이 저장되는 변수이다.
// Lex에서 사용되는 입력 텍스트에 대한 Global Character Pointer이다.
ECHO // 표준 입력을 에코한다.
yymore() // 인식된 토큰의 문자열을 yytext 뒤에 첨가한다.
yyless(n) // n문자만 yytext에 남기고, 나머지는 입력으로 되돌린다.
input() // 다음 문자를 리턴한다.
output(c) // 문자 c를 출력한다.
unput(c) // 문자 c를 입력받는다.
%% (규칙절과 서브루틴절 사이를 %%로 구분한다.)
3. Use Code Section (서브루틴절)
- yylex() 함수와 사용자가 원하는 C 언어 루틴으로 이루어지는 부분이다.
※ yywrap() 정의 예시
int yywrap(){
return 1;
}
Yacc (Yet Another Compiler Compiler, 또다른 컴파일러 컴파일러)
- C언어의 Parser Generator 컴퓨터 소프트웨어인 Yacc는 유닉스 시스템의 표준 Parser Generator이다.
- Parser란 컴파일러의 일부분으로 입력의 의미부를 구분해 주는 역할을 하며, Yacc는 BNF로 표기된 문법을 주면 그것에 따르는 파서를 만들 수 있는 C언어 코드를 만들어 준다.
- Parser는 들어온 토큰을 Shift(한 토큰씩 검토)하면서 어느 문법에 부합하는지를 검사하며 Parsing을 진행한다. 이 때, Parser는 해당 언어의 BNF 표기를 토대로 검사를 진행하게 된다.
※ BNF로 기술된 문법 레벨에서는 문맥 측면에서의 검토를 진행할 수 없다. 컴파일러가 문맥을 파악하여 적절히 처리하게 된다. BNF로는 문법 부합 여부만을 판단할 수 있다.
※ Bison
- GNU 파서 생성기로 yacc를 개선하고 대체하기 위해 만들어졌다.
- LALR* 방식으로 작성된 문법을 처리하고 해석하여 C코드로 만들어 준다.
- 사칙 계산기부터 고도의 프로그래밍 언어까지 다양한 범위의 언어를 만드는데 사용할 수 있다.
- 문법 정의 프로그램인 lex 또는 flex(fast-Lex)와 함께 사용되곤 한다.
* LALR Parser : Look Ahead Left to Right Parser
- 구문 분석 방식의 한 종류 이며 선행 예측(Lookahead) LR 방식의 특별 버전이다.
