:30 12:00 I. I VI II. III. IV. a d V. VI

Size: px

Start display at page:

Download ":30 12:00 I. I VI II. III. IV. a d V. VI"

くうしょううなだ
4 years ago
Views:

1 :30 12:00 I. I VI II. III. IV. a d V. VI

2 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

3 (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

4 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

5 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

6 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

7 /* **************************************************************** */ * 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

8 token = yylex(); return; else { reporterror(); 8

9 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 accept reduce II reduce III : shift s s goto s s reduce X X 9

10 ? (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

13 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) {

14 (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)

I. Backus-Naur BNF : N N 0 N N N N N N 0, 1 BNF N N 0 11 (parse tree) 11 (1) (2) (3) (4) II. 0(0 101)* (

I. Backus-Naur BNF : N N 0 N N N N N N 0, 1 BNF N N 0 11 (parse tree) 11 (1) (2) (3) (4) II. 0(0 101)* ( 2016 2016 07 28 10:30 12:00 I. I VI II. III. IV. a d V. VI. 80 100 60 1 I. Backus-Naur BNF : 11011 N N 0 N N 11 1001 N N N N 0, 1 BNF N N 0 11 (parse tree) 11 (1) 1100100 (2) 1111011 (3) 1110010 (4) 1001011