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

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

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

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

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

어휘 분석기: 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.185-190

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

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

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

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

재귀 하강 파싱 /* <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 */ }

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

예제: 수식 평가 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();   } }

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

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