Download presentation
Presentation is loading. Please wait.
1
www.msharpmath.comSeoul National University 1 / 24 컴퓨터 개론 및 실습 강의 11 (parser)
2
www.msharpmath.comSeoul National University 2 / 24 parser ■ 컴파일러의 기초 start list eof list expr ; list | e expr term moreterms moreterms + term { print("+") } moreterms 3 + 4 * 5 = 3 + ( 4 * 5 ) | - term { print("-") } moreterms | e term factor morefactors morefactors * factor { print("*") } morefactors | / factor { print("/") } morefactors | div factor { print("DIV") } morefactors | mod factor { print("MOD") } morefactors | e factor (expr) | id { print(id.lexeme) } X = 3 ; 5 + X ; | num { print(num.value) }
3
www.msharpmath.comSeoul National University 3 / 24 ■ + - * / DIV MOD ( ) ID - 식별자 NUM - 숫자 DONE - 파일의 끝 token
4
www.msharpmath.comSeoul National University 4 / 24 ■ 2 + 3 * 5 ; 12div 5 mod 2 ; -3 ; // homework sample run
5
www.msharpmath.comSeoul National University 5 / 24 #include #define STRMAX 999 #define SYMMAX 100 #define BSIZE 128 #define NONE -1 #define EOS '\0' #define NUM 256 #define DIV 257 #define MOD 258 #define ID 259 #define DONE 260 int lookahead = 0; int tokenval = NONE; int lineno = 1; int lastchar = -1; int lastentry = 0; parser program list
6
www.msharpmath.comSeoul National University 6 / 24 char lexbuf[BSIZE]; char lexemes[STRMAX]; struct entry { char *lexptr; int token; }; struct entry symtable[SYMMAX]; struct entry keywords[] = { "div", DIV, "mod", MOD, 0, 0 }; parser program list
![National University 6 / 24 char lexbuf[BSIZE]; char lexemes[STRMAX]; struct entry { char *lexptr; int token; }; struct entry symtable[SYMMAX]; struct entry keywords[] = { div , DIV, mod , MOD, 0, 0 }; parser program list](http://images.slidesplayer.org/39/10989302/slides/slide_6.jpg "National University 6 / 24 char lexbuf[BSIZE]; char lexemes[STRMAX]; struct entry { char *lexptr; int token; }; struct entry symtable[SYMMAX]; struct entry keywords[] = { div , DIV, mod , MOD, 0, 0 }; parser program list")
7
www.msharpmath.comSeoul National University 7 / 24 int lookup(char s[]); int insert(char s[], int tok); void init(); void parse(); void expr(); void term(); void factor(); void match(int t); void emit(int t, int tval); int lexan(); void error(char *); void main() { init(); parse(); //exit(0); } void init() { struct entry *p; for (p = keywords; p->token; p++) insert(p->lexptr, p->token); } parser program list
![National University 7 / 24 int lookup(char s[]); int insert(char s[], int tok); void init(); void parse(); void expr(); void term(); void factor(); void match(int t); void emit(int t, int tval); int lexan(); void error(char *); void main() { init(); parse(); //exit(0); } void init() { struct entry *p; for (p = keywords; p->token; p++) insert(p->lexptr, p->token); } parser program list](http://images.slidesplayer.org/39/10989302/slides/slide_7.jpg "National University 7 / 24 int lookup(char s[]); int insert(char s[], int tok); void init(); void parse(); void expr(); void term(); void factor(); void match(int t); void emit(int t, int tval); int lexan(); void error(char *); void main() { init(); parse(); //exit(0); } void init() { struct entry *p; for (p = keywords; p->token; p++) insert(p->lexptr, p->token); } parser program list")
8
www.msharpmath.comSeoul National University 8 / 24 int lookup(char s[]) { int p; for (p = lastentry; p > 0; p = p - 1) if (strcmp(symtable[p].lexptr, s) == 0) return p; return 0; } int insert(char s[], int tok) { int len; len = strlen(s); if (lastentry + 1 >= SYMMAX) error("symbol table full"); if (lastchar + len +1 >= STRMAX) error("lexemes array full"); lastentry = lastentry + 1; symtable[lastentry].token = tok; symtable[lastentry].lexptr = &lexemes[lastchar + 1]; lastchar = lastchar + len + 1; strcpy(symtable[lastentry].lexptr, s); return lastentry; } parser program list
![National University 8 / 24 int lookup(char s[]) { int p; for (p = lastentry; p > 0; p = p - 1) if (strcmp(symtable[p].lexptr, s) == 0) return p; return 0; } int insert(char s[], int tok) { int len; len = strlen(s); if (lastentry + 1 >= SYMMAX) error( symbol table full ); if (lastchar + len +1 >= STRMAX) error( lexemes array full ); lastentry = lastentry + 1; symtable[lastentry].token = tok; symtable[lastentry].lexptr = &lexemes[lastchar + 1]; lastchar = lastchar + len + 1; strcpy(symtable[lastentry].lexptr, s); return lastentry; } parser program list](http://images.slidesplayer.org/39/10989302/slides/slide_8.jpg "National University 8 / 24 int lookup(char s[]) { int p; for (p = lastentry; p > 0; p = p - 1) if (strcmp(symtable[p].lexptr, s) == 0) return p; return 0; } int insert(char s[], int tok) { int len; len = strlen(s); if (lastentry + 1 >= SYMMAX) error( symbol table full ); if (lastchar + len +1 >= STRMAX) error( lexemes array full ); lastentry = lastentry + 1; symtable[lastentry].token = tok; symtable[lastentry].lexptr = &lexemes[lastchar + 1]; lastchar = lastchar + len + 1; strcpy(symtable[lastentry].lexptr, s); return lastentry; } parser program list")
9
www.msharpmath.comSeoul National University 9 / 24 start list eof list expr ; list | e void parse() { lookahead = lexan(); while (lookahead != DONE) { expr(); match(';'); } void match(int t) { if (lookahead == t) lookahead = lexan(); else error("syntax error"); } parser program list
10
www.msharpmath.comSeoul National University 10 / 24 expr term moreterms moreterms + term { print("+") } moreterms 3 + 4 * 5 = 3 + ( 4 * 5 ) | - term { print("-") } moreterms | e void expr() { int t; term(); while (1) switch (lookahead){ case '+': case'-': t = lookahead; match(lookahead); term(); emit(t, NONE); continue; default: return; } parser program list
11
www.msharpmath.comSeoul National University 11 / 24 term factor morefactors morefactors * factor { print("*") } morefactors | / factor { print("/") } morefactors | div factor { print("DIV") } morefactors | mod factor { print("MOD") } morefactors | e void term() { int t; factor(); while (1) switch (lookahead){ case '*': case '/': case DIV: case MOD: t = lookahead; match(lookahead); factor(); emit(t, NONE); continue; default: return; } parser program list
12
www.msharpmath.comSeoul National University 12 / 24 factor (expr) | id { print(id.lexeme) } X = 3 ; 5 + X ; | num { print(num.value) } void factor() { switch (lookahead){ case '(': match('('); expr(); match(')'); break; case NUM: emit(NUM, tokenval); match(NUM); break; case ID: emit(ID, tokenval); match(ID); break; default: error("syntax error"); } parser program list
13
www.msharpmath.comSeoul National University 13 / 24 void emit(int t, int tval) { switch (t) { case '+': case '-': case '*': case '/': printf("%c\n", t); break; case DIV: printf("DIV\n"); break; case MOD: printf("MOD\n"); break; case NUM: printf("%d\n", tval); break; case ID: printf("%s\n", symtable[tval].lexptr); break; default: printf("token %d, tokenval %d\n", t, tval); } void error(char *m) { //fprintf(stderr, "line %d: %s\n", lineno, m); printf("line %d: %s\n", lineno, m); //exit(1); } parser program list
![National University 13 / 24 void emit(int t, int tval) { switch (t) { case + : case - : case * : case / : printf( %c\n , t); break; case DIV: printf( DIV\n ); break; case MOD: printf( MOD\n ); break; case NUM: printf( %d\n , tval); break; case ID: printf( %s\n , symtable[tval].lexptr); break; default: printf( token %d, tokenval %d\n , t, tval); } void error(char *m) { //fprintf(stderr, line %d: %s\n , lineno, m); printf( line %d: %s\n , lineno, m); //exit(1); } parser program list](http://images.slidesplayer.org/39/10989302/slides/slide_13.jpg "National University 13 / 24 void emit(int t, int tval) { switch (t) { case + : case - : case * : case / : printf( %c\n , t); break; case DIV: printf( DIV\n ); break; case MOD: printf( MOD\n ); break; case NUM: printf( %d\n , tval); break; case ID: printf( %s\n , symtable[tval].lexptr); break; default: printf( token %d, tokenval %d\n , t, tval); } void error(char *m) { //fprintf(stderr, line %d: %s\n , lineno, m); printf( line %d: %s\n , lineno, m); //exit(1); } parser program list")
14
www.msharpmath.comSeoul National University 14 / 24 int lexan() { int t; while (1){ t = getchar(); if (t == ' ' || t == '\t') ; else if (t == '\n') lineno = lineno + 1; else if (isdigit(t)) { ungetc(t, stdin); scanf("%d", &tokenval); return NUM; } else if (isalpha(t)){ int p, b = 0; while (isalnum(t)) { lexbuf[b] = t; t = getchar(); b = b + 1; if (b >= BSIZE) error("compiler error"); } parser program list lexbuf[b] = EOS; if (t != EOF) ungetc(t, stdin); p = lookup(lexbuf); if (p == 0) p = insert(lexbuf, ID); tokenval = p; return symtable[p].token; } else if (t == EOF) return DONE; else { tokenval = NONE; return t; }
![National University 14 / 24 int lexan() { int t; while (1){ t = getchar(); if (t == || t == \t ) ; else if (t == \n ) lineno = lineno + 1; else if (isdigit(t)) { ungetc(t, stdin); scanf( %d , &tokenval); return NUM; } else if (isalpha(t)){ int p, b = 0; while (isalnum(t)) { lexbuf[b] = t; t = getchar(); b = b + 1; if (b >= BSIZE) error( compiler error ); } parser program list lexbuf[b] = EOS; if (t != EOF) ungetc(t, stdin); p = lookup(lexbuf); if (p == 0) p = insert(lexbuf, ID); tokenval = p; return symtable[p].token; } else if (t == EOF) return DONE; else { tokenval = NONE; return t; }](http://images.slidesplayer.org/39/10989302/slides/slide_14.jpg "National University 14 / 24 int lexan() { int t; while (1){ t = getchar(); if (t == || t == \t ) ; else if (t == \n ) lineno = lineno + 1; else if (isdigit(t)) { ungetc(t, stdin); scanf( %d , &tokenval); return NUM; } else if (isalpha(t)){ int p, b = 0; while (isalnum(t)) { lexbuf[b] = t; t = getchar(); b = b + 1; if (b >= BSIZE) error( compiler error ); } parser program list lexbuf[b] = EOS; if (t != EOF) ungetc(t, stdin); p = lookup(lexbuf); if (p == 0) p = insert(lexbuf, ID); tokenval = p; return symtable[p].token; } else if (t == EOF) return DONE; else { tokenval = NONE; return t; }")
15
www.msharpmath.comSeoul National University 15 / 24 parser program list (uminus installed version) start list eof list expr ; list | e expr term moreterms moreterms + term { print("+") } moreterms 3 + 4 * 5 = 3 + ( 4 * 5 ) | - term { print("-") } moreterms | e term factor morefactors morefactors * factor { print("*") } morefactors | / factor { print("/") } morefactors | div factor { print("DIV") } morefactors | mod factor { print("MOD") } morefactors | e factor (expr) | id { print(id.lexeme) } X = 3 ; 5 + X ; | num { print(num.value) } | - factor { print('UMINUS') }
16
www.msharpmath.comSeoul National University 16 / 24 #define DONE 260 #define UMINUS 261 void factor() { switch (lookahead){ case '(': match('('); expr(); match(')'); break; case NUM: emit(NUM, tokenval); match(NUM); break; case ID: emit(ID, tokenval); match(ID); break; case '-': match('-'); factor(); emit(UMINUS, NONE); break; default: error("syntax error"); } void emit(int t, int tval) { switch (t) { case '+': case '-': case '*': case '/': printf("%c\n", t); break; case DIV: printf("DIV\n"); break; case MOD: printf("MOD\n"); break; case NUM: printf("%d\n", tval); break; case ID: printf("%s\n", symtable[tval].lexptr); break; case UMINUS: printf("UMINUS\n"); break; default: printf("token %d, tokenval %d\n", t, tval); } parser program list (uminus installed version)
![National University 16 / 24 #define DONE 260 #define UMINUS 261 void factor() { switch (lookahead){ case ( : match( ( ); expr(); match( ) ); break; case NUM: emit(NUM, tokenval); match(NUM); break; case ID: emit(ID, tokenval); match(ID); break; case - : match( - ); factor(); emit(UMINUS, NONE); break; default: error( syntax error ); } void emit(int t, int tval) { switch (t) { case + : case - : case * : case / : printf( %c\n , t); break; case DIV: printf( DIV\n ); break; case MOD: printf( MOD\n ); break; case NUM: printf( %d\n , tval); break; case ID: printf( %s\n , symtable[tval].lexptr); break; case UMINUS: printf( UMINUS\n ); break; default: printf( token %d, tokenval %d\n , t, tval); } parser program list (uminus installed version)](http://images.slidesplayer.org/39/10989302/slides/slide_16.jpg "National University 16 / 24 #define DONE 260 #define UMINUS 261 void factor() { switch (lookahead){ case ( : match( ( ); expr(); match( ) ); break; case NUM: emit(NUM, tokenval); match(NUM); break; case ID: emit(ID, tokenval); match(ID); break; case - : match( - ); factor(); emit(UMINUS, NONE); break; default: error( syntax error ); } void emit(int t, int tval) { switch (t) { case + : case - : case * : case / : printf( %c\n , t); break; case DIV: printf( DIV\n ); break; case MOD: printf( MOD\n ); break; case NUM: printf( %d\n , tval); break; case ID: printf( %s\n , symtable[tval].lexptr); break; case UMINUS: printf( UMINUS\n ); break; default: printf( token %d, tokenval %d\n , t, tval); } parser program list (uminus installed version)")
17
www.msharpmath.comSeoul National University 17 / 24 parser program list (power installed version) ■ power 거듭제곱 (power) 는 곱하기, 나누기 보다 우선순위가 높으므로 5 * 2 ^ 3 ; 은 5 * 2 ^ 3 = 5 * (2 ^ 3) = 5 * 8 = 40 으로 계산된다. 더하기, 빼기, 곱하기, 나누기, 거듭제곱의 우선 순위를 생각하면 4 + 5 * 2 ^ 3 = 4 + ( 5 * ( 2 ^ 3 ) ) 으로 처리되야 하므로 거듭제곱에 관한 파서를 만들어 보기로 한다. 하지만 다음에 제시하는 파서는 중대한 오류가 있다. 이것을 찾아서 고쳐야 하는데 일단 틀린 버전에 대해 생각해보자.
18
www.msharpmath.comSeoul National University 18 / 24 parser program list (power installed version) but wrong !!! start list eof list expr ; list | e expr term moreterms moreterms + term { print("+") } moreterms | - term { print("-") } moreterms | e term power morepowers morepowers * power { print("*") } more powers | / power { print("/") } more powers | div power { print("DIV") } more powers | mod power { print("MOD") } more powers | e power factor morefactors morefactors ^ power { print("^") } morefactors | e factor (expr) | id { print(id.lexeme) } | num { print(num.value) } | - factor { print('UMINUS') } start list eof list expr ; list | e expr term moreterms moreterms + term { print("+") } moreterms | - term { print("-") } moreterms | e term factor morefactors morefactors * factor { print("*") } morefactors | / factor { print("/") } morefactors | div factor { print("DIV") } morefactors | mod factor { print("MOD") } morefactors | e factor (expr) | id { print(id.lexeme) }; | num { print(num.value) }
19
www.msharpmath.comSeoul National University 19 / 24 #define UMINUS 261 #define POWER 262 void power(); void term() { int t; power(); while (1) switch (lookahead){ case '*': case '/': case DIV: case MOD: t = lookahead; match(lookahead); power(); emit(t, NONE); continue; default: return; } void power() { int t; factor(); while (1) switch (lookahead){ case '^': t = lookahead; match(lookahead); factor(); emit(t, NONE); continue; default: return; } parser program list (power installed version) but wrong !!!
20
www.msharpmath.comSeoul National University 20 / 24 void factor() { switch (lookahead){ case '(': match('('); expr(); match(')'); break; case NUM: emit(NUM, tokenval); match(NUM); break; case ID: emit(ID, tokenval); match(ID); break; case '-': match('-'); factor(); emit(UMINUS, NONE); break; default: error("syntax error"); } void emit(int t, int tval) { switch (t) { case '+': case '-': case '*': case '/': case '^': printf("%c\n", t); break; case DIV: printf("DIV\n"); break; case MOD: printf("MOD\n"); break; case NUM: printf("%d\n", tval); break; case ID: printf("%s\n", symtable[tval].lexptr); break; case UMINUS: printf("UMINUS\n"); break default: printf("token %d, tokenval %d\n", t, tval); } parser program list (power installed version) but wrong !!!
![National University 20 / 24 void factor() { switch (lookahead){ case ( : match( ( ); expr(); match( ) ); break; case NUM: emit(NUM, tokenval); match(NUM); break; case ID: emit(ID, tokenval); match(ID); break; case - : match( - ); factor(); emit(UMINUS, NONE); break; default: error( syntax error ); } void emit(int t, int tval) { switch (t) { case + : case - : case * : case / : case ^ : printf( %c\n , t); break; case DIV: printf( DIV\n ); break; case MOD: printf( MOD\n ); break; case NUM: printf( %d\n , tval); break; case ID: printf( %s\n , symtable[tval].lexptr); break; case UMINUS: printf( UMINUS\n ); break default: printf( token %d, tokenval %d\n , t, tval); } parser program list (power installed version) but wrong !!!](http://images.slidesplayer.org/39/10989302/slides/slide_20.jpg "National University 20 / 24 void factor() { switch (lookahead){ case ( : match( ( ); expr(); match( ) ); break; case NUM: emit(NUM, tokenval); match(NUM); break; case ID: emit(ID, tokenval); match(ID); break; case - : match( - ); factor(); emit(UMINUS, NONE); break; default: error( syntax error ); } void emit(int t, int tval) { switch (t) { case + : case - : case * : case / : case ^ : printf( %c\n , t); break; case DIV: printf( DIV\n ); break; case MOD: printf( MOD\n ); break; case NUM: printf( %d\n , tval); break; case ID: printf( %s\n , symtable[tval].lexptr); break; case UMINUS: printf( UMINUS\n ); break default: printf( token %d, tokenval %d\n , t, tval); } parser program list (power installed version) but wrong !!!")
21
www.msharpmath.comSeoul National University 21 / 24 parser program list (power installed version) but wrong !!! ■ 프로그램 실행결과 앞에서 작성한 파서를 이용하여 4 + 5 * 2 ^ 3 ; 을 파싱하면 4 5 2 3 ^ * + 가 되어 2^3 을 계산하여 4 5 8 * + 이므로 4 40 + 와 같이 44 를 얻는다. 이것은 맞은 결과이다. 그러면 무엇이 잘못되었는가 ?
22
www.msharpmath.comSeoul National University 22 / 24 parser program list (power installed version) but wrong !!! ■ 프로그램 실행결과 - 3 ^ 2; 을 파싱하면 3 UMINUS 2 ^ 그러면 3 UMINUS 가 실행되어 (-3) 2 ^ 이므로 (-3)^2 = (-3)*(-3) = 9 를 얻는다. 하지만 원래의 수식은 3 의 제곱에 음수를 붙인 것이므 로 -9 가 정답이다. 따라서 파서의 설계가 잘못 되었다. 이것을 어떻게 수정하면 될 것인지를 생각해보자.
23
www.msharpmath.comSeoul National University 23 / 24 parser program list (power installed version) but wrong !!! ■ 문제해결을 위한 방안 앞의 문제에서 처음부터 단항연산자 UMINUS (부호를 바꾸는 연산)의 설계에 문제가 있는지 부터 생각해보자. 단항연산자 UMINUS 를 빼기와 구별하기 위하여 [-]로 나타내기로 한다. - 3 * 2; 를 파싱하는 방법에는 두 가지가 있다. (-3)*2 ; 또는 -(3*2); 는 모두 같은 결과를 얻고, 파싱 하게 되면 - ( 3 * 2 ) ; --> 3 2 * [-] ; (-3) * 2; --> 3 [-] 2 * ; 위의 결과에서 곱하기 * 를 ^ 으로 바꾸어 쓰면 -3^2 의 경우 - ( 3 ^ 2 ) ; 3 2 ^ [-] ; (-3)^2 ; --> 3 [-] 2 ^ ; 으로 되고 두 번째의 경우가 앞에서 잘못된 결과에 해당한다. 따라서 첫 번째 처럼 파싱하면 문제가 해결될 것이다. 그렇다면 UMINUS 의 처음 설계부터 고쳐야 하는지 고민하게 된다.
24
www.msharpmath.comSeoul National University 24 / 24 parser program list (power installed version) but wrong !!! ■ Home Work (HomeWork) 홈페이지에서 C program list 실습 docx 파일을 내려받는다. 마지막에 포함된 프로그램을 수정하여 -3 ^ 2 ; 인 명령이 3 2 ^ UMINUS 와 같이 파싱되도록 수정하라. 과제의 제출은 (1) 6월 8일 기말시험 튜토링 시간(2시-3시)에 제출한다. (3시-4시는 시험 시간) (2) 내려받은 프로그램에서 수정된 부분을 포함하는 함수만 프린트한다.
Similar presentations
