# 10. 編譯器 (I) | 教學 | 主題 | 影片 | |--------|-----|------| | PDF | [Chapter 10. Compiler I: Syntax Analysis](http://www.nand2tetris.org/lectures/PDF/lecture%2010%20compiler%20I.pdf) | | | 範例 | [剖析數學運算式 (JavaScript)](../ai/parseExp.md) | | | 範例 | [產生數學運算式 (C)](cExpGen.md) | | | 範例 | [數學運算式編譯器 (C)](cExpCompiler.md) | | | 影片 | gcc 編譯器工具鏈的用法 | [影片](https://www.youtube.com/watch?v=CcaegVVaxT8) | ## Lexer 範例 ``` if (x < 153) {let city = ”Paris”;} ``` 轉為 XML ```xml if ( x < 153 ) { let city = Paris ; } ``` ## Jack 語言的結構 ```jack class ClassName { field variable declarations; static variable declarations; constructor type { parameterList ) { local variable declarations; statements } method type { parameterList ) { local variable declarations; statements } function type { parameterList ) { local variable declarations; statements } } ``` ## 典型的語法範例 ```bnf program: statement; statement: whileStatement | ifStatement | // other statement possibilities ... | '{' statementSequence '}' whileStatement: 'while' '(' expression ')' statement ifStatement: simpleIf | ifElse simpleIf: 'if' '(' expression ')' statement ifElse: 'if' '(' expression ')' statement 'else' statement statementSequence: '' // null, i.e. the empty sequence | statement ';' statementSequence expression: // definition of an expression comes here // more definitions follow ``` ## Jack 的設計原則 * The Jack language is intentionally simple: * Statement prefixes: let, do, ... * No operator priority * No error checking * Basic data types, etc. ## Jack 的 BNF https://github.com/wokibe/Jack2C/blob/master/bnf.txt ``` ; BNF definitions for the Jack2 language ;======================================= ; kittekat jan/2017 ; additions to Jack from http://nand2tetris.org/: ; named constants ; character constants ; break ; my xBNF syntax: ; 'xxxx' terminal value, text enclosed in quotes will appear ; xxxx non-terminal value, will be replaced by other constructs ; x y concatenation, sequence of constructs ; x | y either x or y can appear ; x? x appears 0 or 1 times ; x* x appears 0 or more times ; ( ) parentheses are used for grouping of constructs ; %xab shorthand for hex representation of character, e.g.: %x61 for 'a' ; %xab-cd value range, e.g.: %x30-33 for '0' | '1' | '2' | '3' ; Syntax for the Tokenizer ;------------------------- token = whitespace | integerConstant | stringConstant | keyword | keywordConstant | symbol | identifier symbol = '{' | '}' | '(' | ')' | '[' | ']' | '.' | ',' | ';' | '+' | '-' | '*' | '/' | '&' | '|' | '<' | '>' | '=' | '~' | quote keyword = 'class' | 'constructor' | 'function' | 'method' | 'static ' | 'field' | 'void' | 'int' | 'char' | 'boolean' | 'let' | 'do' | 'if' | ‘else’ | 'while' | 'return' | 'break' | 'const' keywordConstant = 'true' | 'false' |'null' | 'this' ; Syntax for the Parser ;---------------------- class = 'class' className '{' (classVarDec | constDec)* subroutineDec* '}' classVarDec = ( 'static' | 'field' ) type varName ( ',' varName )* ';' type = 'int' | 'char' | 'boolean' | className subroutineDec = ( 'constructor' | 'function' | 'method' ) ( 'void' | type ) subroutineName '(' parameterList ')' subroutineBody parameterList = (( type varName ) ( ',' type varName )* )? subroutineBody = '{' (varDec | constDec)* statements '}' varDecl = 'var' type varName ( ',' varName )* ';' constDec = 'const' '=' constValue ';' constValue = constName '=' (('-'* integerConstant) | charConstant) ';' className = identifier subroutineName = identifier varName = identifier constName = identifier statements = statement* statement = letStatement | ifStatement | whileStatement | doStatement | returnStatement letStatement = 'let' varName ( '[' expression ']')? = expression ';' ifStatement = 'if' '(' expression ')' '{' statements '}' ( 'else' '{' statements '}' )? whileStatement = 'while' '(' expression ')' '{' whileBody '}' whileBody = statements ('break' statements)* doStatement = 'do' subroutineCall ';' returnStatement = 'return' expression? ';' expression = term (op term)* term = integerConstant | stringConstant | keywordConstant | charConstant | varName ( ‘[’ expression ']' )? | subroutineCall | '(' expression ')' | unaryOp term subroutineCall = subroutineName '(' expressionList ')' | ( className | varName ) '.' subroutineName '(' expressionList ')' expressionList = ( expression ( ',' expression )* )? op = '+' | '-' | '*' | '/' | '&' | '|' | '<' | '>' | '=' unaryOp = '-' | '~' keywordConstant = 'true' | 'false' | 'null' | 'this' integerConstant = digit (digit)* ; in the range -32767..32767 stringConstant = '"' ( stringCharacter )* '"' charConstant = quote printable quote identifier = ( letter | underscore) (letter | digit | underscore)* letter = %x41-5A | %x61-7A ; A..Z, a..z digit = %x30-39 ; 0..9 underscore = '_' stringCharacter = ' ' | '!' | %x23-7E ; #..~ (= all printable except ") quote = %x27 whiteSpace = ( blank | tab ) ( blank | tab )* blank = ' ' tab = %x0B comment = eolComment | longComment eolComment = '//' printable* newline ; comment till End of Line longComment = '/*' (printable | newline)* '*/' ; not nestable printable = %x20-7e newline = %x0D ; for *nix OS sytems ``` ## Jack 的完整編譯範例 * 輸入 (Jack 語言) -- https://github.com/cccnqu/sp106b/blob/master/more/nand2tetris/11/Average/Main.jack * Parser 輸出 (Xml 剖析樹) -- https://github.com/cccnqu/sp106b/blob/master/more/nand2tetris/11/Average/Main.xml * Compiler 輸出 (虛擬機中間碼) -- https://github.com/cccnqu/sp106b/blob/master/more/nand2tetris/11/Average/Main.vm ### Main.jack ```jack class Main { function void main() { var Array a; var int length; var int i, sum; let length = Keyboard.readInt("How many numbers? "); let a = Array.new(length); // constructs the array let i = 0; while (i < length) { let a[i] = Keyboard.readInt("Enter a number: "); let sum = sum + a[i]; let i = i + 1; } do Output.printString("The average is "); do Output.printInt(sum / length); return; } } ``` ### Main.xml ```xml class Main { function void main ( ) { var Array a ; var int length ; var int i , sum ; let length = Keyboard Keyboard . readInt ( How many numbers? ) ; let a = Array Array . new ( length ) ; let i = 0 ; while ( i < length ) { let a [ i ] = Keyboard Keyboard . readInt ( Enter a number: ) ; let sum = sum + a [ i ] ; let i = i + 1 ; } do Output . printString ( The average is ) ; do Output . printInt ( sum / length ) ; return ; } ``` ### Main.vm ```vm function Main.main 4 push constant 18 call String.new 1 push constant 72 call String.appendChar 2 push constant 111 call String.appendChar 2 push constant 119 call String.appendChar 2 push constant 32 call String.appendChar 2 push constant 109 call String.appendChar 2 push constant 97 call String.appendChar 2 push constant 110 call String.appendChar 2 push constant 121 call String.appendChar 2 push constant 32 call String.appendChar 2 push constant 110 call String.appendChar 2 push constant 117 call String.appendChar 2 push constant 109 call String.appendChar 2 push constant 98 call String.appendChar 2 push constant 101 call String.appendChar 2 push constant 114 call String.appendChar 2 push constant 115 call String.appendChar 2 push constant 63 call String.appendChar 2 push constant 32 call String.appendChar 2 call Keyboard.readInt 1 pop local 1 push local 1 call Array.new 1 pop local 0 push constant 0 pop local 2 label label1 push local 2 push local 1 lt not if-goto label2 push local 0 push local 2 add push constant 16 call String.new 1 push constant 69 call String.appendChar 2 push constant 110 call String.appendChar 2 push constant 116 call String.appendChar 2 push constant 101 call String.appendChar 2 push constant 114 call String.appendChar 2 push constant 32 call String.appendChar 2 push constant 97 call String.appendChar 2 push constant 32 call String.appendChar 2 push constant 110 call String.appendChar 2 push constant 117 call String.appendChar 2 push constant 109 call String.appendChar 2 push constant 98 call String.appendChar 2 push constant 101 call String.appendChar 2 push constant 114 call String.appendChar 2 push constant 58 call String.appendChar 2 push constant 32 call String.appendChar 2 call Keyboard.readInt 1 pop temp 1 pop pointer 1 push temp 1 pop that 0 push local 3 push local 0 push local 2 add pop pointer 1 push that 0 add pop local 3 push local 2 push constant 1 add pop local 2 goto label1 label label2 push constant 15 call String.new 1 push constant 84 call String.appendChar 2 push constant 104 call String.appendChar 2 push constant 101 call String.appendChar 2 push constant 32 call String.appendChar 2 push constant 97 call String.appendChar 2 push constant 118 call String.appendChar 2 push constant 101 call String.appendChar 2 push constant 114 call String.appendChar 2 push constant 97 call String.appendChar 2 push constant 103 call String.appendChar 2 push constant 101 call String.appendChar 2 push constant 32 call String.appendChar 2 push constant 105 call String.appendChar 2 push constant 115 call String.appendChar 2 push constant 32 call String.appendChar 2 call Output.printString 1 pop temp 0 push local 3 push local 1 call Math.divide 2 call Output.printInt 1 pop temp 0 push constant 0 return ```