[프로그래밍언어]LL LR 파서 (parser) 구현

소개

안녕하세요 ^^ 제가 이번에 Programming language 를 배우면서 했던

파서 입니다. 일단은 보고서도 같이 보냅니다. ^^

PL 시간에 텀프로젝트로 LL 과 LR 파서를 구현하는 과제가 나왔는데요

각각 LL 과 LR 파서를 콘솔로 구현하고 나서

그 콘솔로 구현된 파서에 API(MFC)를 씌워서 UI 를 디잔인 했습니다.

자세한 내용은 파일안에 포함된 보고서 파일이 있는데요

그걸 찾고 하시면 되겠구요..

필요로 하시는분 받으시길 바랍니다

컴파일 실행환경

Windows XP
Visual Studio
한글 2005(2002)

본문내용

LL parsing과 LR parsing을 위한 드라이버 루틴을 작성하라.
( 단, 문법과 파싱 테이블은 입력한다. )

1) 프로그램은 입력 스트링을 읽어서, 각각 LL parsing 과 LR parsing 을 수행해야 한다.

2) 또한 파싱 과정에서 스택이나 input 버퍼의 내용이 변화될 때마다 스택과 버퍼의 내용을 출력하라.

3) 만일 파싱이 성공적으로 완료되면 입력 스트링에 대한 파스 트리를 표현하라.
(리스트 표현, 문자 지향 그래픽 표현 등)

4) 파싱이 실패하면, reject 한다는 표현을 출력하라.

5) 여러 개의 입력 스트링을 이용하여 이 프로그램이 제대로 작동하는지 확인하라.

① LL parser
: LL파서는 Table을 이용하는 Top-Down 방식이다. 그렇기 때문에 테이블을 참조하는 메소드류와 입력 문장과 현재 스택 비교와 관련된 메소드, 그리고 실제로 삽입과 교체 과정의 메소드류를 구현해야 한다. 그리고 최종적으로 View Tree 를 구현하기 위한 Tree 구조를 형성하여야 한다.

② LR parser
: LR 파서는 Table을 이용하는 Bottom-Up 방식이다. 이 방식은 성능면에서는 LL 파서보다 좋지만 구현이 조금 힘들다. 내부적으로 Reduce 와 Shift 연산에 따르는 메소드를 구현하여야 하며 LL파서보다 복잡한 테이블 연산과 state를 변형해주는 부분 그리고 state를 참조하고 stack 을 바꿔주는 부분등의 메소드들을 구현하여야 한다. LR 파서 역시 최종적으로 View Tree 를 구현하기 위해 Tree 구조를 가져야 한다.

③ View Tree
: LL, LR 파서에서 생성되는 Tree 를 가지고 View Tree를 표현해야 한다. 내부적으로 재귀적인 형태로 트리의 노드를 따라다니며 그리며 이때 영역과 비율 그리고 레벨 등을 참조하여 균형적이며 가시적인 트리를 구현한다.

참고자료

· 없음