Recursive-Descent parsing(재귀하향파싱)을 이용한 계산기 프로그램

소개

<요구사항>

Recursive-Descent parsing(재귀하향파싱)을 이용한 계산기 프로그램
만들기
- 문법에 맞지 않는 에러 검색이 잘되고 가독성이 좋은 프로그램
- AST(Abstract Syntax Tree) 사용
- 기본 2칙 연산(덧셈, 뺄셈) + (곱셈, 나눗셈)
- id가 될 것

프로그래밍언어 시간에 과제로 제출해서
100점 만점에 100점 받은 과제입니다.

컴파일 실행환경

Microsoft Visual Studio 2008 (C++)

본문내용

Ⅱ. 관련지식 조사

Ⅱ-1. Recursive-Descent parsing(재귀 하향 파싱)

parser는 컴파일 과정 중 구문 분석을 담당하는 syntax analyzer
입니다. parser는 string(문장)을 입력으로 받아 그 string이 정의된
문법의 문장이 맞는지 아닌지를 확인하여 아니라면 에러 메시지를
출력합니다. 즉, 주어진 string이 정의된 문법에 의해 생성될 수 있는지
의 여부를 결정하는 프로그램입니다.

parser의 입력은 어휘분석으로 얻은 token들이고 출력은 일련의 생성
규칙 번호(parse)와 parse tree(또는 abstract syntax tree), 그리고
에러 메시지입니다.

parser의 종류는 top-down parser와 bottom-up parser로 나눌 수
있습니다. resursive-descent parser는 top-down parser 중에
하나입니다. top-down parser는 parse tree를 루트로부터 단말 노드로
만들어 나가는데 일반적으로 backtracking을 합니다. parse tree를
만드는 작업이 parsing이고 곧 구문 분석을 한다는 뜻입니다.
backtracking은 가능한 생성규칙을 모두 적용해 보는 것으로 시간이
많이 소요됩니다. top-down parser 중 backtracking을 하지 않는 것을
LL parser라 합니다.

recursive-descent parser는 backtracking을 하고 recursion을
이용합니다. 그리고 생성규칙이 바뀌면 프로그램 자체를 수정해야
합니다.

참고자료

· 프로그래밍 언어론