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

Size: px

Start display at page:

Download "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) * *"

あおしふくだ
6 years ago
Views:

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

2 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

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

4 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

5 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

6 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

7 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

8 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 shift 15 reduce II 12 shift 16 shift reduce IV 14 reduce V shift 7 reduce V shift 8 reduce V reduce III shift shift 1 shift 2 goto reduce VI shift 7 reduce VI shift 8 reduce VI : shift s s goto s s reduce X X 8

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

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

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

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