172 2017.7.16 1
? X A B A X B ( )? IBMPL/I FACOM PL1 ( ) X 2
( ) 3
2-0 ( ) ( ) ( ) (12) ( ) (112) 31) 281 26 1 4
(syntax) (semantics) ( ) 5
BNF BNF(Backus Normal Form) Joun Backus (grammer) English grammer grammer for programming language X BNF (metasymbol)? C + (? BNFC + 1 (meta) 1 6
BNF C ( )BNF ( ) ::= ( ) { ::= int double char void * ::= void ::=, ::= [] ::= C C (nonterminalsymbol) int (termnal symbol) ::= BNF ( ) ( ) BNF ( ) 7
BNF ::= 1 ( ) { C? C (main x ) ( ) 2 intdoublecharvoid? * int int* int* int** * BNF ( ) 3 void( ) 4 ( 1),,,, 5 ( )[] 8
BNF 6 ( ) 1 2-1 C BNF a. b. c. d. 9
BNF ::= ǫ a a0 a a a a a a ǫ == a a a a a a 1(1) (a) ( ǫ) (b) (c) ( a ::= a ) (syntax tree) (1) (2) (3) (4) (5) a a a a a a a * a + 1 a * a + 1 a * a + 1 1: 10
::= ǫ a a0 1(2) ::=+ * 1 a a * a + 1 1(3)(4) 2 (ambiguous) 2? (3) ::= + ::= * ::= 1 a 1(5) 1 1 a1 11
2-2 a. a + a * a + 1 a + 1 + a * a b. a + a + a ( ) c. ::= 1 a () d. ( ) ::= ǫ ::=; while () if () { while if e. ::= if ()else 2 C Java 12
(syntaxchecker)java 2 1 BNF prog ::= ǫ ab prog ab ::= a b prog BNF <program> BNF ab2 0 % java Sam21 abab true % java Sam21 aba false % java Sam21 true % 2 13
(syntax checker) 14
Toknizer Toknizer 1 1 Toknizer class CharToknizer { String str, tok; int pos = -1; boolean eof = false; public CharToknizer(String s) { str = s; fwd(); public boolean iseof() { return eof; public String curtok() { return tok; public boolean chk(string s) { return tok.equals(s); public void fwd() { if(eof) { return; pos += 1; if(pos >= str.length()) { eof = true; tok = "$"; return; tok = str.substring(pos, pos+1); public boolean chkfwd(string s) { if(chk(s)) { fwd(); return true; else { return false; Toknizer str pos pos-1 fwd() 15
Toknizer fwd() eof pos1 eof ( 1 ) length() substring() API chkfwd() chk() OK fwd() ( ) 16
static static Java static public class MyClass { static int sx; static int sy; int ix; int iy; public static void main(string[] args) {...... public void method1(...) {...... class Innter {... static class StaticInnter {... NG OK 2: static 2 MyClass mainmethod1 static MyClass main() method1 MyClass c = new MyClass(...) c.methods1(...) ( ) static 17
static sx/syix/iy ix/iy 1 mehotd1 static main sx/systatic 1 ( )method1 main static 3 (inner class) static static static ix/iy static ( ) static static 3 MyClass.sx 18
main 1 CharToknizer static tok tok prog() ( ) tok.iseof() 19
import java.util.*; import java.io.*; public class Sam21 { static CharToknizer tok; public static void main(string[] args) throws Exception { tok = new CharToknizer(args[0]); System.out.println(prog() && tok.iseof()); static boolean prog() { if(tok.chk("a")) { return ab() && prog(); else { return true; static boolean ab() { return tok.chkfwd("a") && tok.chkfwd("b"); // CharToknizer 2 BNF 2 20
1. P (true ) P false 2. P true EOF ( ) (recursive descent parsing) prog() ( ) 1 ( ) prog ::= ǫ ab prog ǫ ( ) true ab ab ( a ) OK ab() prog() OK ǫ true 21
ab() 2 ab ::= a b a b fwd() checkfwd() false S ::= T11 x T13 y T22 T3 static boolean s() { if(t1 chosen) { return t11() && tok.chkfwd("x") && t3(); else if(t2 chosen) { return tok.chkfwd("y") && t22(): else if(t3 chosen) { return t3(); else { return true; 3: 3 22
S s() S if-else ǫ ǫ else (ǫ 1 else ) true true tok.chkfwd() ( ) tok.chkfwd() prog() true 23
2-3 a. prog ::= ǫ ab prog ab ::= a bb b. prog ::= a a prog c. prog ::= ǫ Aa bb prog aa ::= a a aa bb ::= b b bb d. prog ::= 1 ( prog ) e. prog ::= term term op prog term ::= a 1 ( prog ) op ::= + - * / f. 24
2-3 2-3 ( ) a. a bb static boolean prog() { if(tok.chk("a") tok.chk("b")) { return ab() && prog(); else { return true; static boolean ab() { if(tok.chk("a")) { return tok.chkfwd("a"); else { return tok.chkfwd("b") && tok.chkfwd("b"); prog() ab() a b ab() 25
2-3 b. a1 1 a ( ) a static boolean prog() { if(tok.chk("a")) { tok.fwd(); if(tok.chk("a")) { return prog(); else { return true; else { return false; a prog() ture a false c. aa()bb() prog() 26
2-3 static boolean prog() { if(tok.chk("a")) { return aa() && bb() && prog(); else { return true; static boolean aa() { if(tok.chk("a")) { tok.fwd(); if(tok.chk("a")) { return aa(); else { return true; else { return false; 27
2-3 static boolean bb() { if(tok.chk("b")) { tok.fwd(); if(tok.chk("b")) { return bb(); else { return true; else { return false; 28
2-3 d. static boolean prog() { if(tok.chk("1")) { tok.fwd(); return true; else if(tok.chk("(")) { return tok.chkfwd("(") && prog() && tok.chkfwd(")"); else { return false; 1 BNF 29
2-3 e. ( ) prog static boolean prog() { if(term()) { if(tok.chk("+") tok.chk("-") tok.chk("*") tok.chk("/ return op() && prog(); else { return true; else { return false; static boolean term() { if(tok.chk("a")) { tok.fwd(); return true; else if(tok.chk("1")) { tok.fwd(); return true; else { return tok.chkfwd("(") && prog() && tok.chkfwd(")"); static boolean op() { return tok.chkfwd("+") tok.chkfwd("-") tok.chkfwd("*") tok.chkfwd("/"); 30
2-3 prog() 2-4 e. a. CJava 1 b. if c. d. 2-5 Expr prog ( ) a. prog ::= { statlist statlist ::= ǫ stat statlist stat ::= Expr ; { statlist b. stat stat ::= w ( Expr ) stat d stat w ( Expr ) ; c. stat stat ::= i ( Expr ) stat i ( Expr ) stat e stat d. 31
2A ( )1 (y-kuno@uec.ac.jp) PDF LaTeX 2 Q1. BNF Q2. Q3. ( ) 32