Click here to Skip to main content
11,705,753 members (53,358 online)
Click here to Skip to main content

RPN Compiler for PIC Microcontroller Evaluation Engine 1.4

, 12 Jul 2009 CPOL 20.8K 275 26
Rate this:
Please Sign up or sign in to vote.
The Evaluation Engine is a opensource C-Compiler , parser and interpreter that can be used to build a Business Rules Engine. It allows for mathematical and boolean expressions, operand functions, variables, variable assignment, comments, and short-circuit evaluation. for PIC Microcontrollers

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++) 
{ iii++; 
}</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:

RPN_Compiler_FOR_doodle.gif

Parsing "FOR" in Token.cs

picture below shows the detection map of parsing code

RPN_Compiler1_4

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

Version Description Status
1.1 Using parenthesis for functions sin[3*3.14] -- > sin(3*3.14) and free square brackets for further uses

Done/TestedOK

1.2 Changing equation from = to == more C# like and changing assignment operator from := to =

Done/TestedOK

1.3 Adding if( statement as a function of comparison and related handling

Done/TestedOK

1.4 Adding for( statement as a function and related handling

Done/Testing

1.5 Adding Function Declarative and block handling with all parameters push and pops to add for execution In Progress
1.6 Converting RPN Qeue to PIC assembly Codes

To Do

Points of Interest

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

and you can chat with me online :

consult.gif

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Arash Javadi
Software Developer (Junior)
Iran (Islamic Republic Of) Iran (Islamic Republic Of)
he studied MCSD (C# based 2003) and MCDBA (2005) CWNA, CWNP at Sematech
IC Programming with 8051, AVR , IC desighn with FPGA and board desigh at Contronic Co

He also worked on Wireless Low level TCP/IP Programmable Module and video motion Detection algorithm
he is student of Industrial engineering in University of Payam e noor Tehran learning about PMBOK and management systems.
He has Certificate in Advanced English (CAE) and also he studied German language in ökf österreichisches Kulturforum

You may also be interested in...

Comments and Discussions

 
GeneralMy vote of 5 Pin
Mazen el Senih29-Mar-13 5:39
memberMazen el Senih29-Mar-13 5:39 
GeneralVery Important Question Pin
sepehr101416-May-11 4:34
membersepehr101416-May-11 4:34 
GeneralRe: Very Important Question Pin
Arash Javadi13-Aug-11 3:11
memberArash Javadi13-Aug-11 3:11 
GeneralRe: Very Important Question Pin
Arash Javadi5-Mar-13 18:57
memberArash Javadi5-Mar-13 18:57 
GeneralRe: Very Important Question Pin
sepehr101420-Sep-13 0:13
membersepehr101420-Sep-13 0:13 
GeneralMy vote of 5 Pin
sepehr101417-Apr-11 20:30
membersepehr101417-Apr-11 20:30 
GeneralIncorrect category. Pin
zennie22-Apr-09 10:56
memberzennie22-Apr-09 10:56 
GeneralRe: Incorrect category. Pin
Arash Javadi22-Apr-09 13:02
memberArash Javadi22-Apr-09 13:02 
GeneralRe: Incorrect category. Pin
zennie24-Apr-09 5:51
memberzennie24-Apr-09 5:51 
GeneralRe: Incorrect category. [modified] Pin
Arash Javadi24-Apr-09 10:33
memberArash Javadi24-Apr-09 10:33 
GeneralRe: Incorrect category. Pin
Leblanc Meneses28-Apr-09 21:07
memberLeblanc Meneses28-Apr-09 21:07 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.150819.1 | Last Updated 12 Jul 2009
Article Copyright 2009 by Arash Javadi
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid