4장 어휘 / 구문 분석 (Term project 포함)

Presentation on theme: "4장 어휘 / 구문 분석 (Term project 포함)"— Presentation transcript:

1 4장 어휘 / 구문 분석 (Term project 포함)
순천향대학교 컴퓨터공학과 하상호

2 목차 어휘 분석 구문 분석: 재귀 하강 파싱

3 구문 분석 언어 처리기의 구문 분석은 다음 두 부분으로 구성 어휘 분석기 구문 분석기 정규 문법에 기반한 유한 오토마타
문맥-자유 문법(BNF)에 기반한 push-down 오토마타

4 어휘 분석 문자열에 대한 패턴 매칭기(pattern matcher) 어휘 분석기는 파서에서 호출되는 함수 어휘 분석기 구성
소스 프로그램에서 어휘 항목들을 식별하고 토큰을 연관 어휘 분석기는 파서에서 호출되는 함수 파서가 다음번째 토큰이 필요할 때 어휘 분석기를 호출한다 어휘 분석기 구성 토큰들을 서술하는 상태 다이어그램(state diagram)을 설계 이 상태 다이어그램을 구현하는 프로그램 작성

5 상태 다이어그램 예: 수식 교재 참고: pp getChar(): 입력 프로그램에서 다음번째 문자를 가져와서, nextChar에 저장하고, 그 문자 유형을 charClass에 저장 addChar(): nextChar의 문자를 lexeme에 저장 lookup(): lexeme에 포함된 문자열이 예약어인지를 판단

6 어휘 분석기: lex() int lex() { // before it is called, getChar() is first executed lexLen = 0; getNonBlank(); switch(charClass) { case LETTER: addChar(); getChar(); while (charClass == LETTER || charClass == DIGIT) { addChar(); getChar(); } nextToken = IDENT; break; case DIGIT: while (charClass == DIGIT) { nextToken = INT_LIT; case UNKNOWN: lookup(nextChar); getChar(); return nextToken; 교재 참고: pp

7 재귀 하강 파싱(recursive-descent parsing)
기본 원리 문법으로부터 직접 파서 프로그램을 작성 입력 스트링에 대한 유도를 하향식(top-down) 방식으로 찾아간다. 파서는 재귀적 부프로그램들로 구성 EBNF를 재귀 하강 파서의 기반으로 사용 구현 각 논터미널에 대해서 하나의 프로시저 작성 프로시저는 그 논터미널로부터 생성될 수 있는 문장들을 파싱 프로시저 호출은 해당 생성규칙 적용 프로시저 행동은 해당 생성규칙의 우변을 수행

8 재귀 하강 파싱 어휘 분석기 lex()는 다음번째 토큰을 nextToken에 저장한다고 가정
구현: 단지 한 개의 RHS만이 존재할 때 RHS의 각 터미널 기호에 대해서, nextToken과 비교한다 터미널기호와 매칭되면 파싱을 계속하고, 그렇지 않으면 오류 발생 RHS의 각 논터미널 기호에 대해서, 이와 연관된 프로시저를 호출한다.

9 재귀 하강 파싱 /* <expr> → <term> {(+ | -) <term>} */
void expr() { /* Parse the first term */   term(); /* nextToken이 +, -인 동안에 다음번째 term을 파싱 계속*/   while (nextToken == ADD_OP || nextToken == SUB_OP){     lex();     term();   } }

10 재귀 하강 파싱 논터미널이 2개 이상의 RHS를 포함할 때, 어느 RHS를 파싱할 것인지를 결정하는 것이 필요
입력의 다음번째 토큰(lookahead)에 기반하여 올바른 RHS를 선택 nextToken이 각 RHS로부터 생성될 수 있는 첫번째 토큰과 비교하여 매칭 시도 매칭이 일어나지 않으면 오류

11 재귀 하강 파싱 /* <factor> -> id | (<expr>) */
void factor() { /* 어느 RHS를 파싱할 것인지를 판단 */    if (nextToken) == ID_CODE)      lex();   else if (nextToken == LP_CODE) {        lex(); expr();     if (nextToken == RP_CODE) lex(); else error(); } /* End of else if (nextToken == ... */ else error(); /* Neither RHS matches */ }

12 예제: 수식 평가 재귀 하강 파싱 과정에서 수식 평가
<expr> → <term> { (+ | - ) <term> } <term> → <factor> { (* | / ) <factor> } <factor> → number | ( <expr> )

13 예제: 수식 평가 result <- result + term(); else
/* <expr> → <term> {(+ | -) <term>} */ void expr() { /* Parse the first term */ int result = term(); int prevToken; /* nextToken이 +, -인 동안에 다음번째 term을 파싱 계속*/   while (nextToken == ADD_OP || nextToken == SUB_OP){ prevToken = nextToken;     lex(); if (prevToken == ADD_OP) then result <- result + term(); else result <- result – term();   } }

14 Term Project 여러분이 설계한 새로운 언어에 대한 인터프리터를 개발하라. 일정 어휘 분석과 구문 분석을 포함할 것
5/31: 발표 6/13: 보고서 제출

15 Term Project 발표 및 보고서는 다음 사항을 포함해야 함 문제 정의(언어 설계 포함) 문제 분석 및 설계 소스 코드
테스트 및 검증 의견