RPN Compiler for PIC Microcontroller Evaluation Engine 1.4

• Download RPN_Compiler1_4 - 1.07 MB

Introduction

This is an update to a great article Evaluation Engine by Donald Snowdy.

There are some changes that I made to the article that makes it a typical C-Compiler. It is a good starting point for making a compiler. With a few changes, you can complete it as a real C-Compiler !! and with some changes you can make AVR Compiler for ATMega32 , ATMega64 family ICs or PIC Compiler for PIC16F , PIC17 , PIC24 , PIC32 Compiler

FOR Evaluation System :

when you open a new Console project and write a simple FOR block and add a breakpoint and run the project -

<code>
<p>for (int i=iii; i <= 5; i++) <br />{ iii++; <br />}</p>
<code>

in debug mode if you right click on the for block and click on GO To Disassembly you see the code and corresponding assembly codes in a "For" block you see on the end of block there is another "for" declarative : for(int i = iii ; i<= 5; i++)

for ( int i=iii; i <= 5 ; i++; )

Compiler just Cut and paste other two sentence i <= 5 ; i++; to the end of the "FOR" block but in reverse order i++; i <= 5 ; and there are two sensitive keywords

1. ending function parantesis ')' for "FOR" keyword with TokenType=Token_For_InitializeEnd that runtime pointer at this poing jumps to the end of inrement sentence and begining of "for condition" means after initialization of FOR - int i = 0; the condition will bechecked .

2. End of condition checking : at this point compiler check the result of condition if it was true so runtime pointer should jump back to the begining of for-code-block on the other hand if the result was false continue its way.

if(eval.Count != 0) 
    if(eval.Peek().TokenName_Boolean == true) 
    {
        index = item.FOR_FirstLevel.StartTokenBlock.Position+1;
    }

you can see the procedure in image below:

Parsing "FOR" in Token.cs

picture below shows the detection map of parsing code

Background

RPN-Reverse Polish Notation "if" Evalution Parsing

The "if" keyword checks the true or false state of a statement and decides where the runtime pointer should jump. This compiler needs specific characters to use them as flags as you see in figure 1. "if" has three set of states:

1. Token_if_True: Refers to end of "if" statement which is ')' at this point if the statement was True runtime pointer continues on its journey until it meets its End Point and jumps to End Point.
2. Token_IF_False: If the statement failed, runtime Pointer jumps to Fail Point.
3. Token_IF_END: If statement finished its True Block or Fail Block, runtime jump to EndPoint

IF / FOR Handling after Making RPN_Queue

I add some codes to the Article article Evaluation Engine by Donald Snowdy for making it more c-Compiler like

at this point the queue is ready but we need to specify where should we check statement and where should compiler pointer jump and also position of some FOR tokens must chenge as i mentioned earlier remeber when a loop is searching through a list its dangerus to change items but i just did ! but i make them safe a change just move tokens from the searched token to point after curser in list which are not explored.

Stack<TokenItem> IF = new Stack<TokenItem>(); // list of found IF
Stack<TokenItem> IF_FOR_FUNC_CLASS = new Stack<TokenItem>(); //list of found IF or FOR or Function or Class Tokens to see the owning current position
Stack<bool> EncloseInBrackets = new Stack<bool>();// bool value to see weather the opening block is Embeded in brackets or just a one line and ends with semicolon

FOR = new Stack<TokenItem>(); //list of founded FOR
Stack<TokenItem> Else = new Stack<TokenItem>(); //list of founded Else
Stack<TokenItem> Element = new Stack<TokenItem>(); // list of all usefull element throughout search
Stack<TokenItem> CurlyBracket = new Stack<TokenItem>(); //list of founded bracket left / right


Stack<bool> isTrueBlock = new Stack<bool>();// this is useful for IF statement to see if we are at the True block of IF or we passed Else of an IF
bool readFOR2sentense = false ; // this indicate when should we start reading two sentence of FOR for CUT and paste them
Stack<EvaluationEngine.Support.ExQueue<TokenItem>> readedFOR2sentences = new Stack<EvaluationEngine.Support.ExQueue<TokenItem>>();//this is a stack full of queues of readed pair FOR sentences i added them to a stack for FORs that are embeded in a FOR
TokenItem NextTok = null;
for (int i = 0; i < rpn_queue.Count; i++)
{
    TokenItem tok = rpn_queue[i];

    if (i + 1 < rpn_queue.Count)
        NextTok = rpn_queue[i + 1];
    else
        NextTok = null;


    tok.Position = i;

    if (tok.TokenName == "if(")                                                               ///   if
    {
        //tok.TokenType = TokenType.Token_if;
        isTrueBlock.Push(true);
        Element.Push(tok);
        tok.Usage = TokenItem.UsageType.IF_Related;
        IF.Push(tok);
        IF_FOR_FUNC_CLASS.Push(tok);


    }
    if (tok.TokenName == "for")                                                               ///   for
    {
        FOR.Push(tok);
        Element.Push(tok);
        IF_FOR_FUNC_CLASS.Push(tok);
        readedFOR2sentences.Push(new EvaluationEngine.Support.ExQueue<TokenItem>());

    }
    if (tok.TokenName == ";")
    {
        if (Element.Count > 0 && Element.Peek().TokenName == "for")
        {

            readFOR2sentense = true;

        }
    }

    if (tok.TokenName == "{")                                                                  ///   {
    {
        if ((Element.Peek().TokenName == "]" && Element.Peek().IF_FirstLevel != null) || (Element.Peek().TokenName == "else" && Element.Peek().IF_FirstLevel != null))
            tok.Usage = TokenItem.UsageType.IF_Related;
        if (Element.Peek().TokenName == "]" && Element.Peek().FOR_FirstLevel != null)
            tok.Usage = TokenItem.UsageType.FOR_Related;
        CurlyBracket.Push(tok);


        Element.Push(tok);
        tok.TokenType = TokenType.LeftCurlyBracket;

    }
    if (tok.TokenName == "]")                                                                ///   ]
    {
        if (readFOR2sentense == true)
        {
            readFOR2sentense = false;
            //readedFOR2sentences.Enqueue(new TokenItem(";", TokenType.Token_Assignment_Stop, TokenDataType.Token_DataType_None,false  ));
        }
        if (tok.IF_FirstLevel != null && isTrueBlock.Peek() && !(isTrueBlock.Peek() == true && tok.TokenName == "{"))
        {
            tok.TokenType = TokenType.Token_if_True;
            tok.Usage = TokenItem.UsageType.IF_Related;
            tok.IF_FirstLevel.IF_TruePosition = i;
            Element.Push(tok);
            if (NextTok != null && NextTok.TokenName == "{")
                tok.IF_TrueIsWithinBracket = true;
        }
        if (tok.FOR_FirstLevel != null)
        {
            //tok.TokenType = TokenType.Token_if_True;
           // tok.FOR_FirstLevel.FOR_CondithionToken = tok;
            Element.Push(tok);
            tok.FOR_FirstLevel.StartTokenBlock = tok;
            tok.TokenType = TokenType.Token_FOR_InitializeEnd;
        }
        if (tok.FOR_FirstLevel != null || tok.IF_FirstLevel != null)
            if (NextTok!=null && NextTok.TokenName == "{") EncloseInBrackets.Push(true); else EncloseInBrackets.Push(false);
    }


    if (readFOR2sentense)
        readedFOR2sentences.Peek().Enqueue(tok);



    if (tok.TokenName == "else")                                                               ///   else
    {
        Element.Push(tok);
        Else.Push(tok);
        tok.Usage = TokenItem.UsageType.IF_Related;
        tok.IF_FirstLevel = IF.Peek();
        isTrueBlock.Pop();
        isTrueBlock.Push(false);
        IF.Peek().FalseToken = tok;
        tok.TokenType = TokenType.Token_IF_False;
        if (tok.FOR_FirstLevel != null || tok.IF_FirstLevel != null)
            if (NextTok!=null && NextTok.TokenName == "{") EncloseInBrackets.Push(true); else EncloseInBrackets.Push(false);

    }





    if (tok.TokenName == ";" || tok.TokenName == "}")   ///E                                                               ///   ;
    {
        //if (isTrueBlock.Count > 0 && CurlyBracket.Count != 0 && CurlyBracket.Peek().Usage == TokenItem.UsageType.IF_Related)

        if (Element.Count > 0)
            if (tok.TokenName == ";" && (Element.Peek().TokenName == "]" || Element.Peek().TokenName == "else") || (tok.TokenName == "}"  && CurlyBracket.Count != 0))
            {
                //if (IF_FOR_FUNC_CLASS.Peek().TokenName == "if(")
                //{

                #region GoUp IF
                while (IF_FOR_FUNC_CLASS.Count > 0)
                {
                    if (IF_FOR_FUNC_CLASS.Peek().Usage == TokenItem.UsageType.IF_Related)
                    {
                        if (EncloseInBrackets.Peek() == true && tok.TokenName == ";") break;
                            if (isTrueBlock.Peek() == true)
                            {
                                    IF.Peek().EndTokenBlock = tok;
                                    IF.Peek().FalseToken = tok;
                                    if (NextTok == null || NextTok.TokenName != "else")
                                    {
                                        IF.Pop();
                                        IF_FOR_FUNC_CLASS.Pop();
                                        isTrueBlock.Pop();
                                    }
                                    if (EncloseInBrackets.Peek() == true )
                                        CurlyBracket.Pop();
                                    EncloseInBrackets.Pop();
                                    if (EncloseInBrackets.Peek() == true) break;
                            }
                            else
                            {
                                isTrueBlock.Pop();
                                IF.Peek().EndTokenBlock = tok;
                                IF.Pop();
                                IF_FOR_FUNC_CLASS.Pop();

                                if (EncloseInBrackets.Peek() == true )
                                    CurlyBracket.Pop();
                                EncloseInBrackets.Pop();
                                if (EncloseInBrackets.Peek() == true) break;
                            }
                    }
                    else
                        if (IF_FOR_FUNC_CLASS.Count > 0 && IF_FOR_FUNC_CLASS.Peek().Usage == TokenItem.UsageType.FOR_Related)
                        {





                            FOR.Peek().EndTokenBlock = tok;
                            tok.FOR_FirstLevel = FOR.Peek();
                            FOR.Pop();

                            IF_FOR_FUNC_CLASS.Pop();
                            readedFOR2sentences.Peek().Dequeue();

                            bool found = false;
                            for (int ii = 0; ii < readedFOR2sentences.Peek().Count; ii++) ///for(;;i++)
                            {
                                if (found == true)
                                {
                                    ///
                                    rpn_queue.Insert(i, readedFOR2sentences.Peek()[ii]);
                                    ///
                                }
                                if (readedFOR2sentences.Peek()[ii].TokenName == ";")
                                {
                                    if (found == true)
                                    {
                                        tok.FOR_FirstLevel.FOR_ConditionToken = readedFOR2sentences.Peek()[ii];
                                        break;
                                    }
                                    found = true;
                                    //break;
                                }
                            }
                            found = false;
                            for (int ii = 0; ii < readedFOR2sentences.Peek().Count; ii++)///for(;i>3;)
                            {
                                ///
                                rpn_queue.Insert(i, readedFOR2sentences.Peek()[ii]);
                                ///
                                if (readedFOR2sentences.Peek()[ii].TokenName == ";")
                                {
                                    readedFOR2sentences.Peek()[ii].TokenType = TokenType.Token_FOR_ConditionEnd;
                                    readedFOR2sentences.Peek()[ii].FOR_FirstLevel = tok.FOR_FirstLevel;
                                    tok.FOR_FirstLevel.TrueToken = readedFOR2sentences.Peek()[ii];
                                    break;
                                }
                            }

                            while (readedFOR2sentences.Peek().Count > 0) readedFOR2sentences.Peek().Dequeue().Usage = TokenItem.UsageType.FOR_Related;
                            readedFOR2sentences.Pop();


                            if (EncloseInBrackets.Peek() == true)
                                CurlyBracket.Pop();
                            EncloseInBrackets.Pop();
                            if (EncloseInBrackets.Count ==0 || EncloseInBrackets.Peek() == true)
                                break;






                        }

                }
                #endregion


                Element.Push(tok);

            }

    }




}
for (int i = 0; i < rpn_queue.Count; i++)
{
    rpn_queue[i].Position = i ;
}

History

Points of Interest

for get list of Elsectronic software available in my website click here