DOC

rightParenthesis

By Danielle Young,2014-12-20 00:16
11 views 0
rightParenthesis

    /* COMPILER PROJECT by Prof. J. Chen, NCU, Taiwan 2011.06.04

This project contains 4 labs. Together, they compile source code, like Selection

    Sort below of a language specially designed for this course called myLang, to

    obtain the target code of the ARM assembly language for the mobile and embedded electronics products.

int[] array={3,1,4,2};

    int i=0; int j=0; int length=4; int min=0; int temp=0;

    {

    while (i<(length-1) ) {

    min=i; j=i+1;

     while (j

     if (array[j]

     j=j+1;

     };

     temp=array[i]; array[i]=array[min]; array[min]=temp;

     i=i+1;

    };

    }

    Next, we will briefly introduce the 4 labs:

    Lab1: getTheTokens: Get all the tokens from the source code on source file. Ex: get 3 tokens a, +, and b from source code a+b.

    Lab2: topDownParse: Use top-down approach to parse all the tokens. Ex: parse the tokens a, +, and b, returning whether the syntax is OK.

    Lab2&3: parseAndGenerateAST: Reduce the nodes of virtual parse tree during the top-down parse to generate abstract syntax tree (AST), returning whether it is a success.

    Ex: from source code a+b generates AST on the right: +

     a b Lab4: generateTargetCode: Traverse the AST to generate ARM target code, returning whether it is a success.

     Ex: from the AST: +

     a b

     generates LDR R1,a

     LDR R2,b

     ADD R1,R2

    */

    /* main program

    1. construct an object myCompiler out of class Compilers.

    2. call myCompiler to getTheTokens, return theTokens

     call myCompiler to parseAndGenerateAST, return Boolean 3.

    4. call myCompiler to generateTargetCode, return targetString end of main program */

    /*------------------------------------------------------------------------------------ Tokens class contains two attributes: type and value.

    Ex: token a and token 1 are two objects of Tokens class.

     token a is of identifier type with value a.

    token 1 is of integerConstant type with value 1.

    -------------------------------------------------------------------------------------*/

    class Tokens { private String type; private String value;

     this.type=type; this.value=value; } public Tokens (String type, String value){

     public String getValue( ) {return this.value;}

     public String getType( ) {return this.type;}

    }// end of Tokens

    /*---------------------------------------------------------------------------------- TreeNodes class contains a label such as a and 3 pointers to left-most child, right

    sibling, and parent, respectively.

    -----------------------------------------------------------------------------------*/ class TreeNodes

    { private String label;

    private int lmc; // left most child pointer

    private int rs; // right sibling pointer

    private int p; // parent pointer

public TreeNodes (label, lmc, rs, p)

    {this.label=label; this.lmc=lmc; this.rs=rs; this.p=p;}

    } // end of TreeNodes

class Symbols

    { private String label; /* it is the token value of an identifier*/

     private String type; // either integer (int) or array of integers

     private int intValue; /* the value of an integer, ex: a is 1*/

     private int [] arrayValues;/* the values of an array, ex: b is 3,1,4,2*/

     public Symbols {}

    } // end of Symbols

public class Compilers

    {

     //Lab1

    //the tokens scanned Tokens[] theTokens;

     int tokenBeginning; //the beginning position of the token being scanned

     int forward; //the forward pointer during scanning a token

     String line; //the current line being scanned

     //Lab2&3

     boolean syntaxOK; //flag to mark up weather syntaxOK or not

     boolean dclOK; //flag to mark weather dcl is OK or not

     int next; //next token position

     boolean success; // mark weather parse success or not

     TreeNodes[] AST; //the abstract syntax tree (AST) to generate

     Symbols[] symbolTable; //the symbol table to generate

     int root; //points to root of AST

     int available; //next available position to store a tree node

     boolean firstChild; // mark first child (first statement or declaration )

     //Lab4

     int labelNumber; //the next available label number

     int registerNumber; //the next available register number

     String result; //result of target code

    public Tokens[] getTheTokens (); //Lab 1 input: sourceFile

    public boolean parseAndGenerateAST(); //Lab 2&3 input: theTokens

    public String generateTargetCode(); // Lab 4 input: AST, symbolTable

}//end of Compilers

/*-------------------------------------------------------------------------------------------------

    getTheTokens scans the sourceFile to get and store all the tokens.

    myLang has 19 (0-18) token types as below:

     No. Token type Token value

     0 assign =

     1 comma ,

     2 elsePart else

     3 identifier letter (letterOrDigit)* (underscore (letterOrDigit) + )*

     4 ifStatement if

     5 integer int

     6 integerConstant digit +

     7 leftBrace {

     8 leftBracket [

     9 leftParenthesis (

     10 logOp (logical operator) && | ||

     11 loopStatement while

     12 mulOp (multiply operator) * | /

     13 plusOp (plus operator) + | -

     14 relOp (relational operator) > | < | ==

     15 rightBrace }

     16 rightBracket ]

     17 rightParenthesis )

     18 semicolon ;

    -------------------------------------------------------------------------------------------------*/

    public Tokens[] getTheTokens ( );

    Tokens aToken

    String line//the current line being scanned 1 open sourceFile. forward,tokenBeginning <= 0 2. read first line into line

    3. while (not endOfFile)

    1. tokenBeginning <= forward;

    2. call getNextToken() to get aToken

    (from tokenBeginning to forward in the line); increment forward 3.store it to theTokens

    4.if endOfLine then read next line

     end while

    4. return theTokens

// end of getTheTokens

private Tokens getNextToken ( ) {

    /* see the Deterministic Finite Automata (DFA) in Fig. 1

    state <= 0

    while (not endOfLine)

     switch (state)

    0: if next char is blank break

     else if it is a letter then state ? 1 break

     else if a digit then state ? 4 break

     else if a {, [, >, +, *”… then state ? 6 break

     else if a & then state ? 7 break

     else if a | then state ? 9 break

     else if a = then state ? 11 break

    1: if next char is a letter or a digit break

     else if underscore then state ? 2 break

     else state ? 3 break

    2: if next char is a letter or a digit then state ? 1 break

    3: if it is a keyword then return it else return identifier

    4: if next char is a digit break

     else state ? 5 break

    5: return an integerConstant token

    6: if it is a { return then return leftBrace

    else if it is a [ then return leftBracket

    else if it is a > or < then return relOp

    else if it is a + or - then return plusOp

    else if it is a * or / return mulOp token

    ..

    7: if next char is a & then state ? 8 break

    8: return logOp

    9: if next char is a | then state ? 10 break

    10: return logOp

    11: if next char a = then state ? 12 break

     else state ? 13 break

    12: return relOp

    13: return assign

end of while (not endOfLine)

}; //end of getNextToken

/*-------------------------------------------------------------------------------------

    topDownParse performs LL parse according to the 47 grammar rules of myLang. Write a method for each non-terminal based on predict set (first set,

    or follow set when null). MyLang provides the features below:

1. integer data type. Ex: int i = 0;

    2. integer array data structure. Ex: int[] array = {3,1,4,2}; 3. 3 kinds of statement:

    1. assignment statement. Ex: min=i;

    2. selection statement.Ex: if (array[j]

    3. iteration statement.Ex: while (j4. 3 kinds of expression:

     1. arithmetic expression.Ex: length-1

     2.relational expression.Ex: i<(length-1)

     3. logical expression.Ex: i<(length-1) && j>2 5. 2 kinds of operation:

     1. plus, minus operation.

     2. multiply, divide operation.

    ------------------------------------------------------------------------------------------------*/

    public boolean topDownParse ( ){ 1. syntaxOK ? true; 2. call program();}

private boolean program ( ) {

    // 1. ? { }

    1. if declarations() then

    if theTokens[next] is { then

    if statements() then

    if theTokens[next] is } then

    syntaxOK ? true

    else syntaxOK ? false

     else syntaxOK ? false

    else syntaxOK ? false

    else syntaxOK ? false

    2. if syntaxOK then print Great! The syntax is OK!

    else print Sorry! The syntax is incorrect.

    3. return syntaxOK

    } //end of program()

    An alternative design using exception handling private boolean program ( ) {

    // 1. ? { } 1. call declarations()

    2. call match ({ )

    3. call statements()

    4. call match (}”)

    5. if syntaxOK then print Great! The syntax is OK!

    6. return syntaxOK

    7. handle syntaxNotOK exception print Sorry! The syntax is incorrect.

    } //end of program()

    private boolean match (String theToken) {

    if theToken matches theTokens[next] then return syntaxOK ? true else throw syntaxNotOK exception } // end of match

private boolean declarations ( ) {

    //2 ? //3 | null

    Note that the predict set of rule 2 contains int, and that of rule 3 contains {. 1. if theTokens[next] is int then

     call declaration()

    if syntaxOK then call declarations()

     else syntaxOK ? false

     else if theTokens[next] is { then return syntaxOK? true

     else syntaxOK ? false

    2. return syntaxOK

    } //end of declarations ()

    (4) ? = ;

    (5) | = {} ;

    Note rules 4 and 5 has the same predict set {int}. So parser needs to look ahead

    one more token. If it is [ then go rule 5 else go 4. (6) ? ; (7) | null

    (8) ?

    (9) |

    (10) |

    (11) ? =

    (12) | = (13) ? if(){}else{}

    (14) ? while ( ) { } (15) ? [] (16) ?

    (17) ? (18) | null

    (19) ? (20) ? >

    (21) | <

    (22) | ==

    (23) ? &&

    (24) | ||

    (25) ? +

    (26) | -

    (27) ? *

    (28) | /

    (29) ?

    (30) ? (31) | null

    (32) ?

    (33) ? (34) | null

    (35) ? ( )

    (36) |

    (37) |

    (38) |

    (39) ? (40) -> ,

    (41) | null

    (42) ?

    (43) ? (44) ? [ ] (45) ?

    (46) | null

    (47) ? int

// end of topDownParse

Report this document

For any questions or suggestions please email
cust-service@docsford.com