chapter10

10. 編譯器 (I)

教學	主題	影片
PDF	Chapter 10. Compiler I: Syntax Analysis
範例	剖析數學運算式 (JavaScript)
範例	產生數學運算式 (C)
範例	數學運算式編譯器 (C)
影片	gcc 編譯器工具鏈的用法	影片

Lexer

範例

if (x < 153) {let city = ”Paris”;}

轉為 XML

<tokens>
  <keyword> if </keyword>
  <symbol> ( </symbol>
  <identifier> x </identifier>
  <symbol> &lt; </symbol>
  <integerConstant> 153 </integerConstant>
  <symbol> ) </symbol>
  <symbol> { </symbol>
  <keyword> let </keyword>
  <identifier> city </identifier>
  <symbol> = </symbol>
  <stringConstant> Paris </stringConstant>
  <symbol> ; </symbol>
  <symbol> } </symbol>
</tokens>

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
  }
}

典型的語法範例

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

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

<class>
<keyword> class </keyword>
<identifier> Main </identifier>
<symbol> { </symbol>
<subroutineDec>
<keyword> function </keyword>
<keyword> void </keyword>
<identifier> main </identifier>
<symbol> ( </symbol>
<symbol> ) </symbol>
<subroutineBody>
<symbol> { </symbol>
<varDec>
<keyword> var </keyword>
<identifier> Array </identifier>
<identifier> a </identifier>
<symbol> ; </symbol>
</varDec>
<varDec>
<keyword> var </keyword>
<keyword> int </keyword>
<identifier> length </identifier>
<symbol> ; </symbol>
</varDec>
<varDec>
<keyword> var </keyword>
<keyword> int </keyword>
<identifier> i </identifier>
<symbol> , </symbol>
<identifier> sum </identifier>
<symbol> ; </symbol>
</varDec>
<statements>
<letStatement>
<keyword> let </keyword>
<identifier> length </identifier>
<symbol> = </symbol>
<expression>
<term>
<identifier> Keyboard </identifier>
<identifier> Keyboard </identifier>
<symbol> . </symbol>
<identifier> readInt </identifier>
<symbol> ( </symbol>
<expressionList>
<expression>
<term>
<stringConstant> How many numbers?  </stringConstant>
</term>
</expression>
</expressionList>
<symbol> ) </symbol>
</term>
</expression>
<symbol> ; </symbol>
</letStatement>
<letStatement>
<keyword> let </keyword>
<identifier> a </identifier>
<symbol> = </symbol>
<expression>
<term>
<identifier> Array </identifier>
<identifier> Array </identifier>
<symbol> . </symbol>
<identifier> new </identifier>
<symbol> ( </symbol>
<expressionList>
<expression>
<term>
<identifier> length </identifier>
</term>
</expression>
</expressionList>
<symbol> ) </symbol>
</term>
</expression>
<symbol> ; </symbol>
</letStatement>
<letStatement>
<keyword> let </keyword>
<identifier> i </identifier>
<symbol> = </symbol>
<expression>
<term>
<integerConstant> 0 </integerConstant>
</term>
</expression>
<symbol> ; </symbol>
</letStatement>
<whileStatement>
<keyword> while </keyword>
<symbol> ( </symbol>
<expression>
<term>
<identifier> i </identifier>
</term>
<symbol> &lt; </symbol>
<term>
<identifier> length </identifier>
</term>
</expression>
<symbol> ) </symbol>
<symbol> { </symbol>
<statements>
<letStatement>
<keyword> let </keyword>
<identifier> a </identifier>
<symbol> [ </symbol>
<expression>
<term>
<identifier> i </identifier>
</term>
</expression>
<symbol> ] </symbol>
<symbol> = </symbol>
<expression>
<term>
<identifier> Keyboard </identifier>
<identifier> Keyboard </identifier>
<symbol> . </symbol>
<identifier> readInt </identifier>
<symbol> ( </symbol>
<expressionList>
<expression>
<term>
<stringConstant> Enter a number:  </stringConstant>
</term>
</expression>
</expressionList>
<symbol> ) </symbol>
</term>
</expression>
<symbol> ; </symbol>
</letStatement>
<letStatement>
<keyword> let </keyword>
<identifier> sum </identifier>
<symbol> = </symbol>
<expression>
<term>
<identifier> sum </identifier>
</term>
<symbol> + </symbol>
<term>
<identifier> a </identifier>
<symbol> [ </symbol>
<expression>
<term>
<identifier> i </identifier>
</term>
</expression>
<symbol> ] </symbol>
</term>
</expression>
<symbol> ; </symbol>
</letStatement>
<letStatement>
<keyword> let </keyword>
<identifier> i </identifier>
<symbol> = </symbol>
<expression>
<term>
<identifier> i </identifier>
</term>
<symbol> + </symbol>
<term>
<integerConstant> 1 </integerConstant>
</term>
</expression>
<symbol> ; </symbol>
</letStatement>
</statements>
<symbol> } </symbol>
</whileStatement>
<doStatement>
<keyword> do </keyword>
<identifier> Output </identifier>
<symbol> . </symbol>
<identifier> printString </identifier>
<symbol> ( </symbol>
<expressionList>
<expression>
<term>
<stringConstant> The average is  </stringConstant>
</term>
</expression>
</expressionList>
<symbol> ) </symbol>
<symbol> ; </symbol>
</doStatement>
<doStatement>
<keyword> do </keyword>
<identifier> Output </identifier>
<symbol> . </symbol>
<identifier> printInt </identifier>
<symbol> ( </symbol>
<expressionList>
<expression>
<term>
<identifier> sum </identifier>
</term>
<symbol> / </symbol>
<term>
<identifier> length </identifier>
</term>
</expression>
</expressionList>
<symbol> ) </symbol>
<symbol> ; </symbol>
</doStatement>
<returnStatement>
<keyword> return </keyword>
<symbol> ; </symbol>
</returnStatement>
</statements>
<symbol> } </symbol>
</subroutineBody>
</subroutineDec>
</class>

Main.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

陳鍾誠於金門大學資訊工程系

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

chapter10

10. 編譯器 (I)

Lexer

Jack 語言的結構

典型的語法範例

Jack 的設計原則

Jack 的 BNF

Jack 的完整編譯範例

Main.jack

Main.xml

Main.vm

課程內容

補充教材

Clone this wiki locally