2018 2018 08 02 10:30 12:00 I. I VI II. III. IV. a d V. VI. 80 100 60 1
I. Backus-Naur BNF N N y N x N xy yx : yxxyxy N N x, y N (parse tree) (1) yxyyx (2) xyxyxy (3) yxxyxyy (4) yxxxyxxy N y N x N yx yx II. (wx*w)*w ( ) (L) (w xwwx)* ( ) (R) (B) (N) (1) wxwxxwxww (2) wxwwxwwww (3) wxwwxxwwx (4) wwwxxxxww III. (1) (4) C (A) (E) (1) (4) 2
(1) for ; : #include <stdio.h> int main(void) { int i; for (i = 0: i < 10: i++) { printf("hello!\n"); return 0; (2) #include <stdio.h> int main(void) { double *x; x = 3.14; printf("%f\n", x); return 0; (3) #include <stdio.h> int main(void) { printf("hello! \n"); return 0; (4) " #include <stdio.h> int main(void) { printf("hello!\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) (1) (5) < > \ ˆ == && > ( ) id < < < < < < ˆ (1) > > > < > < > == < (2) > (3) < > < > && < < (4) > < > < > > < < < (5) < > < > ( < < < < < < ) > > > > > > id > > > > > > 4
V. BNF C begin L end I stmt II id = E ; III L L C C E E ( E ) E. id id ( E ) C, L, E begin, end, stmt, id, =, ;, (, ),. start symbol C I, II (1) L BNF L C L IV L ε V C L VI E E VII, VIII,... (2) (4) (1) L, E BNF $ (2) First(C) (3) Follow(L ) (4) Follow(E ) (5) C, L, L, I VI (6) E, E (1) BNF (VII, VIII,...) 5
C L L E E begin end stmt id = ; ( ). $ (7) C, L, L1, E, E1 C, E, E1 C, L, L1, E, E1 C, L, L, E, E reporterror :. 1 ASCII begin C begin BEGIN $ EOF yylex token eat token reporterror #include <stdio.h> /* printf(), EOF */ #include <stdlib.h> /* exit() */ #include <string.h> /* strcmp() */ #include <ctype.h> /* isalpha() */ /* */ #define BEGIN 257 /* begin */ #define END 258 /* end */ #define STMT 259 /* stmt */ #define ID 260 /* id */ int token; /* */ /* */ void reporterror(void); int yylex(void); void eat(int t); void C(void); void L(void); void L1(void); void E(void); void E1(void); 6
/* **************************************************************** */ * C, L, L1, E, E1 */ /* **************************************************************** */ /* */ void reporterror(void) { printf(" \n"); exit(0); /* */ int main() { /* main */ token = yylex(); /* */ C(); 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, "begin") == 0) return BEGIN; if (strcmp(buf, "end") == 0) return END; if (strcmp(buf, "stmt") == 0) return STMT; if (strcmp(buf, "id") == 0) return ID; reporterror(); else { /* */ return c; /* ; */ void eat(int t) { /* token token */ if (token == t) { /* */ 7
token = yylex(); return; else { reporterror(); 8
VI. LR BNF S x I { B II B B S III ε IV LR I, II S, B {, x, (start symbol) S bison LR : bison -v LR $ x { S B 0 shift 1 shift 2 goto 3 1 reduce I 2 reduce IV goto 4 3 shift 5 4 shift 1 shift 2 shift 6 goto 7 5 6 7 accept reduce II reduce III : shift s s goto s s reduce X X 9
? (1) { { x x (2) { { x { x (3) { { x { x x x (1) (A). 0 { 2 B 4 x 1 (B). 0 { 2 B 4 { 2 6 x 1 (C). 0 { 2 B 4 S 7 x 1 (D). 0 { 2 B 4 { 2 B 4 6 x 1 (2) (A). 0 { 2 B 4 x 1 (B). 0 { 2 B 4 { 2 B 4 x 1 (C). 0 { 2 B 4 { 2 B 4 S 7 x 1 (D). 0 { 2 B 4 S 7 { 2 B 4 S 7 x 1 (3) (A). 0 { 2 { 2 B 4 { 2 B 4 6 (B). 0 { 2 { 2 x 1 { 2 x 1 x 1 6 (C). 0 { 2 B 4 { 2 B 4 { 2 B 4 6 (D). 0 { 2 B 4 { 2 B 4 { 2 B 4 x 1 6 10
2018 2018 08 02 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, 2, 3, 4, 3, 6, 5) E (1) E (2) { (3) { (4) {
(5) C L L (6) E E begin end stmt id = ; ( ). $ void C(void) { switch (token) { case BEGIN: /* */ case STMT: /* */ case ID: /* */ default: reporterror(); void E(void) { /* */ void E1(void) { /* */ (6) VI. LR (4 3) (1) (2) (3)