LL파싱 프로그램 구현

소개글

일반 생활에서 사용되어 지는 산술식(+,-,*,/)의 계산을 수업시간에 배웠던 구문분석기(Lexical Analyzer)를 통하여 분석한 후 각각의 문법에서 first()와 follow()를 구하여 parsing table을 만들고, LL 파서를 통하여 파싱하는 프로그램을 구현하였다.

컴파일 실행환경

Microsoft visual studio, window xp

본문내용

4. 세부설명 및 토의
이번 과제는 첫 번째 과제였던 구문분석기를 LL파서에 적용시켜 파싱을 하는 프로그램을 구현하는 것이었다. 일반적인 산술식만을 계산하게 해주는 프로그램이라서 그것에 맞는 구문분석기를 수정하여 구현해야만 했다. 메인함수와 각각의 함수처리루틴에서 숫자나 +,-,*,/ 가 아닌 다른 문자들을 입력하였을 때 에러가 나도록 처리하였으며, 각각의 입력문자들은 파일로 저장되어서 처리가 되도록 하였다.
우선적으로 메인함수에서 입력값을 받게 되면, 그 입력값을 스택에 집어 넣고, LL파싱을 하여 파스트리를 만들게 되는데, 그것이 void process_one_sentence(void) 함수이다. 그곳에서는 구문분석기를 통하여 입력된 문자들을 각각 하나하나씩 입력받아서 처리하게 하였는데, 교과서에 나온 스택과 입력값 간의 처리 관계표를 보고 하나하나씩 처리해 나갔다. 비단말 기호가 올때까지 스택에 단말기호들은 입력의 비단말기호와 맞는 파싱 테이블의 값을 가지고 점점 트리를 구성하게 되고, 스택에서 비단말 기호가 나오면 각각의 입력과 스택의 내용들을 서로 삭제되고, 입력은 구문분석기를 통해 새로운 문자를 가져오도록 하였다. 그렇게 하여 LL파싱이 성공적으로 실행되어 지면 완성된 트리를 따라서 값을 구하는데 그것이 void evaluate_tree(n_ptr ROOT)함수 이다. 이 함수는 파스트리를 depth-first search 로 방문하면서 결과값을 노드에 넣어 놓는다. 그렇게 하여 각각의 결과값들이 나중에 ROOT의 값까지 올라와서 계산이 되어지면, 그것이 처음에 입력했던 산술식의 계산 결과값이 되어서 출력하게 되고, 프로그램은 종료하게 된다.
수업시간에 배운데로 LL파싱의 오류를 발견할 수 있었는데, 화면 결과에서처럼 12-3+5같은 산술식에서처럼 올바른 답인 14가 아니라 4가 나오는 것을 볼 수 있다. 그것은 LL파싱이 오른쪽을 우선하여 식을 계산하게 되어 12-(3+5)와 같은 결과로 계산하여 나가기 때문에 그런 결과를 볼 수 있는 것이다.

참고 자료

없음