172 2017.7.16 1 1.1? X A B A X B ( )? IBMPL/I FACOM PL1 ( ) X ( ) 1.2 1
2-0 ( ) ( ) ( ) (12) ( ) (112) (131) 281 26 1 (syntax) (semantics) ( ) 2 2.1 BNF BNF(Backus Normal Form) Joun Backus (grammer) English grammer grammer for programming language X BNF (metasymbol)? C + (? BNFC + 1 (meta) 1 C ( ) BNF ( ) 2
::= ( ) { ::= int double char void * ::= void ::=, ::= [] ::= C C (nonterminal symbol) int (termnal symbol) ::= BNF ( ) ( ) BNF ( ) ::= 1 ( ) { C? C (main x ) ( ) 2 int doublecharvoid? * int int* int* int** * BNF ( ) 3 void( ) 4 ( 1),,,, 5 ( )[] 6 ( ) 1 2-1 C BNF a. b. c. d. 3
2.2 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: ::= ǫ a a0 1(2) ::= + * 1 a a * a + 1 1(3)(4) 2 (ambiguous) 2? (3) ::= + ::= * ::= 1 a 1(5) 1 a1 1 4
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 3 3.1 (syntax checker)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 5
(syntax checker) 3.2 Toknizer Toknizer 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(); else { return false; Toknizer str pos pos-1 fwd() fwd() eof pos1 eof ( 1 ) length()substring() API chkfwd() chk() OK fwd() ( 3.3 static static Java static 2 MyClass mainmethod1 static MyClass main() method1 MyClass c = new MyClass(...) c.methods1(...) ( ) static 6
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 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.4 main 1 CharToknizer static tok tok prog() ( ) tok.iseof() import java.util.*; import java.io.*; public class Sam21 { 3 MyClass.sx 7
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() { return ab() && prog(); else { static boolean ab() { return tok.chkfwd("a") && tok.chkfwd("b"); // CharToknizer 2 BNF 2 1. P (true ) P false 2. P true EOF ( ) (recursive descent parsing) prog() ( ) 1 ( ) prog ::= ǫ ab prog ǫ ( ) true ab ( a ) OK ab() prog() OK ǫ true ab() 2 ab ::= a b a b fwd() checkfwd() false 3 8
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 { 3: S s() S if-else ǫ else (ǫ 1 else ) true true tok.chkfwd() ( ) tok.chkfwd() prog() true prog() 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. 9
3.5 2-3 2-3 ( ) a. a bb static boolean prog() { if(tok.chk("a") tok.chk("b")) { return ab() && prog(); else { static boolean ab() { return tok.chkfwd("a"); else { return tok.chkfwd("b") && tok.chkfwd("b"); prog() ab() a b ab() b. a1 a ( ) a static boolean prog() { tok.fwd(); return prog(); else { else { return false; a prog() ture a false c. aa()bb() prog() static boolean prog() { return aa() && bb() && prog(); else { 10
static boolean aa() { tok.fwd(); return aa(); else { else { return false; static boolean bb() { if(tok.chk("b")) { tok.fwd(); if(tok.chk("b")) { return bb(); else { else { return false; d. static boolean prog() { if(tok.chk("1")) { tok.fwd(); else if(tok.chk("(")) { return tok.chkfwd("(") && prog() && tok.chkfwd(")"); else { return false; 1 BNF e. ( ) prog static boolean prog() { if(term()) { 11
if(tok.chk("+") tok.chk("-") tok.chk("*") tok.chk("/")) { return op() && prog(); else { else { return false; static boolean term() { tok.fwd(); else if(tok.chk("1")) { tok.fwd(); else { return tok.chkfwd("(") && prog() && tok.chkfwd(")"); static boolean op() { return tok.chkfwd("+") tok.chkfwd("-") tok.chkfwd("*") tok.chkfwd("/"); 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. 12
4 2A ( )1 (y-kuno@uec.ac.jp) PDF LaTeX 2 Q1. BNF Q2. Q3. ( ) 13