Click here to Skip to main content
Click here to Skip to main content

RPN Compiler for PIC Microcontroller Evaluation Engine 1.4

, 12 Jul 2009
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)

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

Comments and Discussions

 
GeneralMy vote of 5 PinmemberMazen el Senih29-Mar-13 5:39 
GeneralVery Important Question Pinmembersepehr101416-May-11 4:34 
GeneralRe: Very Important Question PinmemberArash Javadi13-Aug-11 3:11 
GeneralRe: Very Important Question PinmemberArash Javadi5-Mar-13 18:57 
GeneralRe: Very Important Question Pinmembersepehr101420-Sep-13 0:13 
GeneralMy vote of 5 Pinmembersepehr101417-Apr-11 20:30 
GeneralIncorrect category. Pinmemberzennie22-Apr-09 10:56 
GeneralRe: Incorrect category. PinmemberArash Javadi22-Apr-09 13:02 
GeneralRe: Incorrect category. Pinmemberzennie24-Apr-09 5:51 
GeneralRe: Incorrect category. [modified] PinmemberArash Javadi24-Apr-09 10:33 
GeneralRe: Incorrect category. PinmemberLeblanc 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 | Mobile
Web04 | 2.8.140718.1 | Last Updated 12 Jul 2009
Article Copyright 2009 by Arash Javadi
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid