2015 2015 07 30 10:30 12:00 I. I VI II. III. IV. a d V. VI. 80 100 60 1
I. Backus-Naur BNF S + S S * S S x S +, *, x BNF S (parse tree) : * x + x x S * S x + S S S x x (1) * x x * x (2) * + x x x (3) + x * x + x x (4) * * x x + x x II. (yx x(yz)*)* yxxyzyzyyzxy yxxyzyz : yxxyzyzy, yxxyzyzyy,..., yxxyzyzyyzxy 7 (1) xyzyzyxyzyxy (2) xyzyzyxxyzyz (3) yxzxyzyxxyzx (4) xyzyxxyzyxxx III. (1) (4) C (A) (E) (1) (4) 2
(1) #include <stdio.h> int main(void) { /* printf("hello World!\n"); return 0; (2) ; #include <stdio.h> int main(void) { printf("hello World!\n") return 0 (3) #include <stdio.h> int main(void) { printf( Hello! World\n ); return 0; (4) " #include <stdio.h> int main(void) { printf(hello); return 0; (1) (4) (A) (B) (C) (D) (E) 3
IV. BNF E id E!! E E : E E == E ( E ) id 1!! : ==!! : : == (1) (5) 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) < > \!! : == ( ) id < < < < <!! (1) > > < > < > : < (2) > < > < > == < (3) (4) < > < > ( < < < < (5) < ) > > > > > id > > > > > 4
V. BNF L A L! A L ˆ A A N A & N N ( L ) id L, A, N!, ˆ, &, (, ), id start symbol L (1) A BNF A N A A ε & N A L L (2) (4) (1) L A BNF (2) Follow(L ) (3) Follow(A ) (4) A, A $ L L A A N id ( )! ˆ & $ (4) (A) N A (B) ε (C) & N A (D) (5) L, L1, A, A1, N A, A1, N L, L1, A, A1, N L, L, A, A, N : & 1 ASCII id C id ID yylex token eat token 5
reporterror #include <stdio.h> #include <stdlib.h> /* exit() */ #include <string.h> /* strcmp() */ #include <ctype.h> /* isalpha() */ /* */ #define ID 257 /* x */ int token; /* */ /* */ void reporterror(void); int yylex(void); void eat(int t); void L(void); void L1(void); void A(void); void A1(void); void N(void); /* **************************************************************** */ * L, L1, A, A1, N */ /* **************************************************************** */ /* */ void reporterror(void) { printf(" \n"); exit(0); /* */ int main() { /* main */ token = yylex(); /* */ L(); if (token == EOF) { printf("!\n"); else { reporterror(); int yylex(void) { /* */ int c; char buf[256]; do { /* */ c = getchar(); while (c == c == \t c == \n ); 6
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); return ID; else { /* */ return c; /* & */ void eat(int t) { /* token token */ if (token == t) { /* */ token = yylex(); return; else { reporterror(); 7
VI. LR I, II E id I { X II E { X III E # id IV X id = E V X ; id = E VI LR E, X id, {,, #, =, ; id 1 start symbol E bison LR : bison -v LR id { # = ; $ E X 0 shift 1 shift 2 goto 3 1 reduce I 2 shift 4 goto 5 3 shift 7 shift 8 shift 6 4 shift 9 5 shift 10 shift 11 6 accept 7 shift 4 goto 12 8 shift 13 9 shift 1 shift 2 goto 14 10 11 shift 15 reduce II 12 shift 16 shift 11 13 reduce IV 14 reduce V shift 7 reduce V shift 8 reduce V 15 16 reduce III shift 17 17 shift 1 shift 2 goto 18 18 reduce VI shift 7 reduce VI shift 8 reduce VI : shift s s goto s s reduce X X 8
? (1) {b=c;s=t{ x=y (2) a{b=c#x{s=t#y; u=v (3) {a={x=y;z=u# a (1) (3) (A). (B). (C). (D). (E). (F). (G). (H). (I). 0 E 3 { 7 id 4 0 E 3 # 8 id13 0 E 3 { 7 X12 ;11 id15 0 E 3 { 7 id 4 = 9 E14 ;11 id15 0 E 3 { 7 id 4 = 9 E14 # 8 id13 0 E 3 { 7 id 4 = 9 E14 16 { 7 id 4 0 E 3 { 7 X12 ;11 id 4 = 9 E14 ;11 id15 0 E 3 { 7 id 4 = 9 E14 ; id 11 4 = 9 E14 ;11 id15 0 E 3 { 7 id 4 = 9 E14 16 { 7 id 4 = 9 E14 16 { 7 id 4 9
2015 2015 07 30 I. Backus-Naur (1) (2) (3) (4) (3 4) II. (3 4) (1) (2) (3) (4) III. (3 4) (1) (2) (3) (4) IV. (1) (2) (3) (4) (5) (2 5) V. (3, 4, 4, 6, 5) L (1) L (2) { (3) {
(4) A A id ( )! ˆ & $ void A(void) { /* */ void A1(void) { /* */ (5) void N(void) { if (token == ID) { /* */ else if ( ) { /* */ eat( ( ); L(); eat( ) ); else reporterror(); VI. LR (1) (2) (3) (4 3)