[컴파일러, Compiler] Lex & Yacc 를 이용한 Parser Report

소개

parser란 compiler에서 syntax analysis를 하는 부분이다.
parser의 역할을 보면 다음과 같다. lexical analyzer로부터 token을 받아들인다. 그리고 source language에 대해 string이 grammar에 의해 generate될 수 있음을 증명하며, compile시 일반적으로 나타나는 error를 recover하여 processing을 진행시킨다.
parser의 type은 3가지로 구분된다. universal parsing method는 어떤 grammar도 parsing할 수 있지만, 비효율적이라 일반적으로 잘 사용하지 않는다. 대표적인 방법으로는 top-down parsing과 bottom-up parsing이 있다. top-down parsing은 parsing tree의 root부터 leaves로 확장시키면서 parsing을 한다. LL parsing이라고도 한다. 주로 hand made parser에 사용된다. bottom-up parsing은 parsing tree의 leaves에서 root로 올라가는 방법이다. 이 parsing은 복잡하여 기계나 tool에 의해 이루어지며, LR parsing이라고도 한다. top-down과 bottom-up 모두 left-to-right이며, 한번에 하나의 input symbol을 읽는다.

목차

1. 설명 및 algorithm
2. List
3. 결 과

본문내용

1. 설명 및 algorithm
parser란 compiler에서 syntax analysis를 하는 부분이다.
parser의 역할을 보면 다음과 같다. lexical analyzer로부터 token을 받아들인다. 그리고 source language에 대해 string이 grammar에 의해 generate될 수 있음을 증명하며, compile시 일반적으로 나타나는 error를 recover하여 processing을 진행시킨다.
parser의 type은 3가지로 구분된다. universal parsing method는 어떤 grammar도 parsing할 수 있지만, 비효율적이라 일반적으로 잘 사용하지 않는다. 대표적인 방법으로는 top-down parsing과 bottom-up parsing이 있다. top-down parsing은 parsing tree의 root부터 leaves로 확장시키면서 parsing을 한다. LL parsing이라고도 한다. 주로 hand made parser에 사용된다. bottom-up parsing은 parsing tree의 leaves에서 root로 올라가는 방법이다. 이 parsing은 복잡하여 기계나 tool에 의해 이루어지며, LR parsing이라고도 한다. top-down과 bottom-up 모두 left-to-right이며, 한번에 하나의 input symbol을 읽는다.
parsing에 사용되는 syntax는 context-free grammar를 이용하여 표현하게 된다.
predictive parser는 top-down parsing(즉, LL parsing)의 하나로 right most derivation을 이용하여 derivation의 각 step에서 right most nonterminal을 우선적으로 바꾸어 나간다. predictive parser를 사용하는 것은 일반적인 LL parsing을 사용하는 parser에서 나타나는 backtracking을 막기 위함이다.
predictive parser는 input buffer, stack, parsing table, output stream으로 구성된다. input buffer는 input symbol의 access를 빠르게 하기 위해 저장해 두는 역할을 한다. stack은 grammar symbol의 sequence를 저장하는 역할을 한다.

참고자료

· 없음