레포트 자료 어휘 분석기
[레포트] 어휘 분석기
1. 숙제의 주제를 기술
● C언어 어휘 분석기를 설계하고 프로그램 한다.
● C언어의 토큰의 종류(“A Book on C” 4th edition Al Kelley & IraPohl의 부록 B를 참고 할 것)
⇒ auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch typedef union unsigned void volatile while
⇒ 식별자 : 알파벳 또는 언더스코어 또는 숫자로 구성된 단어로 첫 자는 알파벳 문자나 언더스코어로 시작해야 한다. 식별자는 첫 31자가 구별 되어야 하며, 인식된 식별자는 심볼 테이블에 넣어져야 한다.
⇒ 상수 : 십진, 팔진, 십 육진 상수를 비롯하여 문자형 스트링 상수들을 구분한다.
⇒ 코멘트를 처리한다.
● 구현에 필요한 한계 값들을 정할 것
● 입력은 일반적인 텍스트
● 출력은 발견 된 토큰과 토큰은 종류, 발견 된 줄 번호 등이고 모든 입력이 처리된 후에는 심볼 테이블을 알파벳 순서로 출력한다.
2. 문제 해결을 위한 개략적 방법을 제시
? 텍스트 파일을 입력 받아 입력 받은 텍스트 파일의 데이터들을 한 글자씩 읽어서 영문자인지 아닌지를 구별하여, 그것에 맞는 연산과 Binary Tree를 생성하고, 삽입한다.
단어를 삽입 할 때에도 노드를 생성 할 수 있는 함수와 노드를 삽입하는 함수를 만들어서
Binary Tree를 이루도록 할 것이다.
마지막으로 inorder 방법을 통해서 알파벳 순서대로 출력하고, 발견된 토큰과 토큰의 종류, 발견된 줄 번호와 추가로 몇 번째 단어인지를 출력하게 된다.
3. 세부 문제에 대한 구체적인 해결 방안 제시
? 먼저 linked list를 사용하기 위한 구조체와 tree를 생성하기 위한 구조체를 선언한다. main 함수는 root를 선언하고, 초기화를 하며, root를 매개변수로 하는 inputNODE() 함수와 출력함수 outputNODE()를 호출한다.
inputNODE() 함수는 파일을 열어 읽어 와서 getchar 함수를 통해 한 글자씩 읽으면서 while문을 수행하게 되고, 이 while문은 파일의 끝이 아닐 때까지 수행하게 된다.
while문에서는 줄마다 단어를 검사하게 되는데 한 줄의 끝이 아니면서 영문자 일 때에는 str 변수에 한 글자씩 저장하게 되며, 영문자가 끝나거나 아닐 때에는 insertTREE() 함수에서 노드를 삽입하게 되고, 단어수를 1 증가시킨다. 그리고 str 변수를 다시 NULL로 초기화시킴으로써 다음 단어를 저장할 수 있게 해준다.
한 줄의 끝일 때에는 라인을 나타내는 함수 l_num을 1증가 시켜고, 다음 줄의 새로운 단어가 다시 저장되기 때문에 단어의 수를 나타내는 w_num 변수는 1로 정해준다.
insertTREE() 함수에서는 root와 단어가 들어있는 str 변수와 단어 수, 라인 수를 나타내는 w_num, l_num를 매개변수로 받는다. 처음에 createNODE() 함수를 통해서 new라는 새로운 트리의 노드가 생성된다. 그리고 new 노드에 있는 data에 매개변수로 전달 받은 단어가 저장된다. 그 다음에 insertLIST() 함수를 통해서 linked list에 노드를 삽입하게 된다.
root가 NULL이 아닐 경우 root의 값을 pwalk에 할당이 되고, 새롭게 생성된 노드, 즉 new의 data의 값과 pwalk의 data의 값을 비교하여서 삽입 될 노드(new)의 data의 값이 작을 때에 pwalk의 왼쪽으로 계속 이동하고, 삽입 될 노드(new)의 data의 값이 클 경우에는 pwalk의 오른쪽으로 저장하게 된다. 이것이 계속 반복이 되다가 pwalk의 값이 NULL이 되면 종료하게 되고, while문의 반복 과정에서 pwalk의 값을 parent에 할당했으므로, parent는 잎 로드를 뜻하게 된다. 같을 때에는 이미 단어가 존재하므로 더 실행되지 않고 break문을 통해서 종료하게 된다.
이러한 과정으로 while문이 종료하게 되면 삽입할 노드의 위치를 찾았으므로, 삽입할 노드의 위치를 나타내는 parent의 data와 비교하여 왼쪽 또는, 오른쪽에 삽입하게 된다.
이러한 과정을 통해서 binary tree가 형성하게 된다.
파일의 끝이 되고, binary tree가 다 만들어지게 되면, 출력을 하게 된다. 출력은 inorder 방법을 사용하게 된다. inorder 방법은 왼쪽 부분 트리를 먼저 처리하고, 이어서 루트를 처리하며, 최종적으로 오른쪽 부분 트리를 처리한다. 왼쪽 부분 트리가 먼저 처리되어야 하기 때문에 다른 노드를 처리하기 전에 루트로부터 가장 왼쪽에 있는 잎 노드로 가기 위해 root의 left를 매개변수로 하는 되부름 함수를 통해서 가장 왼쪽으로 이동한다. 그래서 차례대로 왼쪽 부분 트리의 노드를 출력하고, 그의 부모인 노드를 출력, 마지막으로 오른쪽 부분 트리를 출력하는 방법으로 binary tree에 있는 단어들을 라인 수, 단어수와 함께 모두 출력하게 된다.
4. 실험
① 프로그램의 소스
● scanner.c
#include
#include
#include
#define MAX 256
struct LIST
{
int word_num;
int line_num;
struct LIST *next;
};
struct NODE
{
char data[MAX];
struct LIST *plist;
struct NODE *left;
struct NODE *right;
};
void printNODE(struct NODE *);
void printLIST(struct LIST *);
void outputNODE(struct NODE *);
자료출처 : http://www.ALLReport.co.kr/search/detail.asp?pk=11038350&sid=ddangkung&key=
댓글 없음:
댓글 쓰기