2017 2017 08 03 10:30 12:00 I. I VI II. III. IV. a d V. VI. 80 100 60 1
I. Backus-Naur BNF X [ S ] a S S ; X X X, S [, a, ], ; BNF X (parse tree) (1) [a;a] (2) [[a]] (3) [a;[a]] (4) [[a];a] : [a] X 2 222222 [ S ] X a II. x(z yz yy yx)*x (L) xy(x (y*z) z)*y*yx (R) (B) (N) (1) xyyzzyyx (2) xyzzxyyx (3) xyxyxyyx (4) xyxyxxyx III. (1) (4) C (A) (E) (1) (4) 2
(1) #include <stdio.h> int main{void ( printf{"hello World!\n"; return 0; ) (2) printf #include <stdio.h> int main(void) { printf("hello, World!"); printf(); return 0; (3) #include <stdio.h> int main(void) { printf("hello! World\n"); return 0; (4) for ; #include <stdio.h> int main(void) { int i = 0; for (i < 5; i++) { printf("hello World!\n"); return 0; (1) (4) (A) (B) (C) (D) (E) 3
IV. BNF E id E ** E E & E E $$ E E < E ( E ) id 1 ** & $$ < ** & & $$ $$ < a ** b ** c a ** (b ** c) a & b & c (a & b) & c a $$ b $$ c a $$ (b $$ c) a < b < c a ** b & c (a ** b) & c a & b ** c a & (b ** c) a ** b $$ c (a ** b) $$ c a $$ b ** c a $$ (b ** c) a ** b < c (a ** b) < c a < b ** c a < (b ** c) a & b $$ c (a & b) $$ c a $$ b & c a $$ (b & c) a & b < c (a & b) < c a < b & c a < (b & c) a $$ b < c (a $$ b) < c a < b $$ c a < (b $$ c) (1) (5) < > \ ** & $$ < ( ) id < < < < < < ** (1) > > > < > < > & < (2) > (3) < > < > $$ < < (4) > < > < > < < < < (5) < > < > ( < < < < < < ) > > > > > > id > > > > > > 4
V. BNF S if E then S else S I begin L end II write E III F id IV ( E ) V L S L ; S E F E + F E - F S, F, L, E if, then, else, begin, end, write, id, (, ), ;, +, - start symbol S I, II (1) L BNF L S L VI L ε VII ; S L VIII E E (IX, X, XI, XII,...) (2) (4) (1) E L BNF $ (2) Follow(L ) (3) Follow(E ) (4) L, L, VI, VII, VIII (5) S, F, E, E BNF I V (1) BNF (IX, X, XI, XII,...) 5
S F L L E E if then else begin end write id ( ) ; + - $ (6) S, F, E, E1, L, L1 F, L, L1 S, F, E, E1, L, L1 S, F, E, E, L, L :, 1 ASCII id C id ID $ EOF yylex token eat token reporterror #include <stdio.h> /* printf(), EOF */ #include <stdlib.h> /* exit() */ #include <string.h> /* strcmp() */ #include <ctype.h> /* isalpha() */ /* */ #define IF 257 /* if */ #define THEN 258 /* then */ #define ELSE 259 /* else */ #define BEGIN 260 /* begin */ #define END 261 /* end */ #define WRITE 262 /* write */ #define ID 263 /* id */ int token; /* */ /* */ void reporterror(void); int yylex(void); void eat(int t); void S(void); void F(void); void E(void); void E1(void); 6
void L(void); void L1(void); /* **************************************************************** */ /* S, F, E, E1, L, L1 */ /* **************************************************************** */ /* */ void reporterror(void) { printf(" \n"); exit(0); /* */ int main() { /* main */ token = yylex(); /* */ S(); if (token == EOF) { printf("!\n"); else { reporterror(); int yylex(void) { /* */ int c; char buf[256]; do { /* */ c = getchar(); while (c == c == \t c == \n ); if (isalpha(c)) { /* */ char* ptr = buf; ungetc(c, stdin); while (1) { c = getchar(); if (!isalpha(c) &&!isdigit(c)) break; *ptr++ = c; *ptr = \0 ; ungetc(c, stdin); if (strcmp(buf, "if") == 0) return IF; if (strcmp(buf, "then") == 0) return THEN; if (strcmp(buf, "else") == 0) return ELSE; if (strcmp(buf, "begin") == 0) return BEGIN; if (strcmp(buf, "end") == 0) return END; if (strcmp(buf, "write") == 0) return WRITE; return ID; else { /* */ return c; /* ; */ 7
void eat(int t) { /* token token */ if (token == t) { /* */ token = yylex(); return; else { reporterror(); 8
VI. LR BNF LR E a I E E II E E III E * IV ( E ) V I, II E (, ), *,, a a 1 start symbol E bison LR : bison -v LR $ ( ) * a E 0 shift 2 shift 1 goto 3 1 reduce I 2 shift 2 shift 1 goto 4 3 shift 5 shift 2 shift 7 shift 6 shift 1 goto 8 4 shift 2 shift 9 shift 7 shift 6 shift 1 goto 8 5 accept 6 shift 2 shift 1 goto 10 7 reduce IV 8 reduce III shift 7 reduce III goto 8 9 reduce V 10 reduce II shift 2 reduce II shift 7 reduce II shift 1 goto 8 : shift s s goto s s reduce X X 9
? (1) a a * a * (2) a a a a * a (3) a a a a * (1) (A). 0 E 3 6 (B). 0 E 3 E 8 6 (C). 0 E 3 a 1 * 7 6 (D). 0 E 3 E 8 * 7 6 (2) (A). 0 E 3 * 7 (B). 0 E 3 E 8 * 7 (C). 0 E 3 E 8 E 8 * 7 (D). 0 E 3 E 8 E 8 E 8 * 7 (3) (A). 0 E 3 * 7 (B). 0 E 3 6 E 10 * 7 (C). 0 E 3 6 E 10 6 E 10 * 7 (D). 0 E 3 6 E 10 E 8 6 E 10 * 7 10
2017 2017 08 03 I. Backus-Naur (1) (2) (3) (4) (3 4) II. (3 4) (1) (2) (3) (4) III. (2 4) (1) (2) (3) (4) IV. (1) (2) (3) (4) (5) (2 5) V. (3, 3, 5, 4, 6, 5) E (1) E (2) { (3) {
(4) L L (5) S F E E if then else begin end write id ( ) ; + - $ void F(void) { if (token == ID) { else if (token == ( ) { else reporterror(); /* */ /* */ void L(void) { /* */ void L1(void) { /* */ (6) VI. LR (4 3) (1) (2) (3)