Skip to main content
GameDev.net gamedev.net
🔒 Locked

Critique my basic scripting language code

Started by Narf the Mouse Oct 1, 2009 at 7:28 PM 6 replies 1.8k views
Original Post
Narf the Mouse
Narf the Mouse
I've just written my first Lexer, Parser, Compiler and Interpreter. It's not anywhere near complex, but it does confirm that 2 + 2 = 4. I'm looking for, specifically, critique of the basic concepts and base code I'm using. Best to make sure the foundation isn't cracked and all that. Any comments about 'highly incomplete' will be fed to the dragons. Thanks for any and all help. Lexer

    public class Lexer
    {
        public Lexer()
        {
            tokenConverter.Add("+", "+");
            tokenConverter.Add(" +", "+");
            tokenConverter.Add(" + ", "+");
            tokenConverter.Add("+ ", "+");
        }


        public string Lexigate(string script)
        {
            foreach (KeyValuePair<string, string> kvp in tokenConverter)
            {
                script = script.Replace(kvp.Key, kvp.Value);
            }
            return script;
        }


        protected Dictionary<string, string> tokenConverter =
            new Dictionary<string,string>();
    }



Parser (With Rules)

    public class Parser
    {
        public PTNode Parse(string script)
        {
            int t = 0,
                count = script.Length;
            bool found = false,
                check = false;
            PTNode root = new PTNode(),
                checkForNode;

            do
            {
                foreach (Rule rule in baseRules)
                {
                    if (tokens.Contains(script[t]))
                    {
                        if (rule.CheckFor(script, ref t, 1, out checkForNode))
                        {
                            check = true;
                            root.Add(checkForNode);
                        }
                    }
                    else
                    {
                        ++t;
                        check = true;
                    }
                }
                found = check;
            }while(found == true && t < count);


            return root;
        }


        public List<char> tokens = new List<char>(
            new char[]
            {
                '+'
            }
        );


        public List<Rule> baseRules = new List<Rule>(
            new Rule[]
            {
                new RuleAddition()
            }
        );
    }

    public abstract class Rule
    {
        public abstract bool CheckFor(string text, ref int pointer, int scanDir, out PTNode ret);
    }


    public class RuleAddition : Rule
    {
        public override bool CheckFor(string text, ref int pointer, int scanDir, out PTNode ret)
        {
            if (text[pointer] == '+')
            {
                PTNode left;
                PTNode right;
                if (ruleInteger.CheckFor(text, ref pointer, -1, out left) &&
                ruleInteger.CheckFor(text, ref pointer, 1, out right))
                    ret = new PTNodeAdd(left, right);
                else throw new InvalidOperationException("Difficulty finding things to add.");
                pointer += scanDir;
                return true;
            }
            ret = null;
            return false;
        }


        protected RuleInteger ruleInteger = new RuleInteger();
    }


    public class RuleInteger : Rule
    {
        public override bool CheckFor(string text, ref int pointer, int scanDir, out PTNode ret)
        {
            string subString;
            bool success = false;
            int value = 0;
            int from = pointer;
            if (scanDir < 0)
            {
                do
                {
                    from += scanDir;
                    subString = text.Substring(from, (pointer - from));
                    success = int.TryParse(subString, out value);
                } while (!success && pointer - scanDir <= 13);
            }
            else if (scanDir > 0)
            {
                do
                {
                    from += scanDir;
                    subString = text.Substring(pointer + 1, from - (pointer));
                    success = int.TryParse(subString, out value);
                } while (!success && scanDir - (pointer + 1) <= 13);
                if (success)
                    pointer = from;
            }
            if (success)
                ret = new PTNodeAssign(value);
            else
                ret = null;
            return success;
        }
    }



Compiler and PTNode and derivatives. Yes, I've stuck the compilation function in the PTNode class. It makes sense to me. If there's some reason not to, please tell me - This is my first real compiler (My first two, I had no idea what I was doing. Now I have a slight clue)

    public class PTNode
    {
        protected PTNodeType nodeType;


        protected List<PTNode> subNodes;
        public int? value;


        public void Add(PTNode node) { if (subNodes == null) subNodes = new List<PTNode>(); subNodes.Add(node); }


        public Stack<int> Compile()
        {
            Stack<int> stack = new Stack<int>();
            foreach (PTNode node in subNodes)
            {
                node.Compile(stack);
            }
            return stack;
        }


        public virtual void Compile(Stack<int> stack)
        {
            if (subNodes != null)
                foreach (PTNode node in subNodes)
                {
                    node.Compile(stack);
                }
        }


        public override string ToString()
        {
            string toString = "Root: ";
            foreach (PTNode node in subNodes)
                toString += node.ToString();
            return toString;
        }
    }


    public class PTNodeAdd : PTNode
    {
        public PTNodeAdd(PTNode left, PTNode right) { Add(left); Add(right); nodeType = PTNodeType.Binary; }


        public override void Compile(Stack<int> stack)
        {
            stack.Push((int)FuncCodes.Add);
            base.Compile(stack);
        }


        public override string ToString()
        {
            return subNodes[0].ToString() + " + " + subNodes[1].ToString() + ", ";
        }
    }


    public class PTNodeAssign : PTNode
    {
        public PTNodeAssign(int value) { this.value = value; nodeType = PTNodeType.Assignary; }


        public override void Compile(Stack<int> stack)
        {
            if (value.HasValue)
                stack.Push(value.Value);
            base.Compile(stack);
        }


        public override string ToString()
        {
            return value.ToString();
        }
    }



And interpreter.

    public class Interpreter
    {
        public Interpreter()
        {
            operationLookupTable.Add(FuncCodes.Add, Add);
        }


        public Stack<int> Run(Stack<int> stack)
        {
            Stack<int> stack2 = new Stack<int>(stack);
            pointer = 0;
            while (pointer < operationLookupTable.Count)
                operationLookupTable[(FuncCodes)stack2.Pop()](stack2);
            return stack2;
        }


        protected int pointer;


        protected List<FuncCodes> program = new List<FuncCodes>(
            new FuncCodes[]
            {
                FuncCodes.Add
            }
        );


        protected delegate void Op(Stack<int> stackList);
        protected Dictionary<FuncCodes, Op> operationLookupTable =
            new Dictionary<FuncCodes,Op>();


        protected void Add(Stack<int> stack)
        {
            stack.Push(stack.Pop() + stack.Pop());
            ++pointer;
        }
    }


    public enum FuncCodes
    {
        Add
    }



[Edited by - Narf the Mouse on October 1, 2009 7:52:24 PM]
Kylotan
Kylotan
You shouldn't be explicitly adding white-space into your tokens. What would you do if there were 2 spaces before an operator? Or a tab? Instead, you should have a routine that consumes and discards whitespace. (Or tokenises it separately, and lets the parser decide whether it's relevant or not.)

It also appears that your Lexer isn't doing its job and that you're actually lexing integers in your Parser. Personally, when hand-writing parsers I do it all in the parser and skip the lexer entirely. But if you are going to have both, you should really do it properly so that it's consistent. Stuff like int.TryParse should be in the lexer, returning a token of Integer type. The idea of the lexer is that the parser then has a ready-made list of valid tokens, and all it has to do is ensure they're in a valid order.

I haven't looked too much at your compiler or interpreter as I don't usually write those as standalone objects.
Narf the Mouse
Narf the Mouse
Quote:
Original post by Kylotan
You shouldn't be explicitly adding white-space into your tokens. What would you do if there were 2 spaces before an operator? Or a tab? Instead, you should have a routine that consumes and discards whitespace. (Or tokenises it separately, and lets the parser decide whether it's relevant or not.)

That, actually, would be a crude method of eliminating spaces. The right side replaces the left.
Quote:
Original post by Kylotan
It also appears that your Lexer isn't doing its job and that you're actually lexing integers in your Parser. Personally, when hand-writing parsers I do it all in the parser and skip the lexer entirely. But if you are going to have both, you should really do it properly so that it's consistent. Stuff like int.TryParse should be in the lexer, returning a token of Integer type. The idea of the lexer is that the parser then has a ready-made list of valid tokens, and all it has to do is ensure they're in a valid order.

So a Token is an actual object? Containing, I suppose, a variable and a definition?
Quote:
Original post by Kylotan
I haven't looked too much at your compiler or interpreter as I don't usually write those as standalone objects.

Er...What do you write them as?
BFG
BFG

You might find this tutorial helpful.
Kylotan
Kylotan
Quote:
Original post by Narf the Mouse
Quote:
Original post by Kylotan
You shouldn't be explicitly adding white-space into your tokens. What would you do if there were 2 spaces before an operator? Or a tab? Instead, you should have a routine that consumes and discards whitespace. (Or tokenises it separately, and lets the parser decide whether it's relevant or not.)

That, actually, would be a crude method of eliminating spaces. The right side replaces the left.

I have no idea what you're trying to say here. But your approach of hard-coding several different versions of the same token is just bizarre. Tokenising the white-space and then dealing with it at the parser level is the most generally correct way.

Quote:
So a Token is an actual object? Containing, I suppose, a variable and a definition?

A token would normally comprise a type and a value. eg. (int_constant, 10), (string_literal, "abcdef"), (variable, 'some_var'), (relational_operator, '<'), (whitespace, ' \t '). These types are completely arbitrary, but usually correspond to the building blocks of your language's grammar. My rule of thumb is that the lexer does pretty much all the work that is possible without backtracking, ie. the unambiguous part.

Quote:
Quote:
Original post by Kylotan
I haven't looked too much at your compiler or interpreter as I don't usually write those as standalone objects.

Er...What do you write them as?

I've never needed a compiler, or a byte-code interpreter. For my needs I have been able to merge an interpreter into the parser, basically.
thre3dee
thre3dee
On a side note, Kylotan, do you have any open-source or public APIs for scripting libraries you have created? I would be interested in having a peak.

Thanks.
paul_nicholls
paul_nicholls
Hi Narf the Mouse,
There is a great tutorial on doing hand-written parsers/compilers/interpreters which I have used to make compilers/interpreters successfully in the past.

It is written in Pascal, but it shows the basics of taking a EBNF grammer for a programming language, and creating a top-down recursive-descent parser, etc. for that grammer.

It is old, but still very good (and relevant) IMHO :)

Let's build a compiler!

I think you could learn a lot from it even though it isn't in C/C++ :)
cheers,
Paul
Kylotan
Kylotan
Quote:
Original post by thre3dee
On a side note, Kylotan, do you have any open-source or public APIs for scripting libraries you have created? I would be interested in having a peak.

Sadly not. I was never very prolific when working on my own projects and these days most of my code is done at work. Where I have used scripting on home projects I've typically just embedded Python and/or Lua and used some templates to bind it to functions and methods.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.