I've been learning about trees again to better understand them.
I came up with the following solution in C++ to see how it might work:

#include <iostream>
#include <vector>

using namespace std;

class TreeNode {
	public:
	TreeNode( string v ) { value = v; };
	string value;
	vector<TreeNode*> children;	
};

void traverse(TreeNode *t)
{
	cout << t->value << endl;
	vector<TreeNode*>::iterator c;
	for ( c = t->children.begin(); c != t->children.end(); c++)
		traverse(*c);	
}

main()
{
	TreeNode *root = new TreeNode("Root");
	TreeNode *branchA = new TreeNode("BranchA");
	TreeNode *childA = new TreeNode("   ChildA");
	TreeNode *branchB = new TreeNode("BranchB");
	TreeNode *childB = new TreeNode("   ChildB");

	branchA->children.push_back(childA);
	branchB->children.push_back(childB);

	root->children.push_back(branchA);
	root->children.push_back(branchB);

	traverse(root);

}

Root
BranchA
   ChildA
BranchB
   ChildB

A vector works nice as it keeps track of the nodes that are children of the current node.

This is obviously not useful, other than the fact that it helps me understand more how the recursive
algorithm goes through each node and respective children. I still want to create my own scripting language,
but I see the benefit in creating it in C, and not C++. I would like a similar solution in C to practice with, but
without the vector / list I cant figure out how to go about it.

Say I was to make the "children" variable a pointer to the "next" TreeNode? Say you have Node-A, which has 2 children:
Child-A and Child-B, both "A" and "B" are peers in a sense, they both have the same parent node. Well, if the list was just a C-Style linked list, then Child-B would in essence be Child-A's child, not Node-A's.

I thought about adding a pointer called "next" calling the next child in the subset, but haven't decided if that would make
the most sense.

Ok, heres the answer to my own question:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct tree_node {
	char* value;
	struct tree_node *children; /* head pointer of children list */
	struct tree_node *next;     /* next peer in child list */
}TreeNode;

/* local protos */

void traverse(TreeNode*);
TreeNode *talloc(const char*);

TreeNode *talloc(const char *value)
{
	TreeNode *t = (TreeNode*) malloc(sizeof(TreeNode));
	t->value = strdup(value);
	t->children = NULL;
	t->next = NULL;
	return t;
}

void traverse(TreeNode* t)
{
	puts(t->value);
	TreeNode *c;

	for ( c = t->children; c; c = c->next)
		traverse©;
}

int main(void) 
{
	TreeNode *root = talloc("Root");
	TreeNode *branch1 = talloc("BranchA");
	TreeNode *child1 = talloc("   ChildA");
	TreeNode *branch2 = talloc("BranchB");
	TreeNode *child2 = talloc("   ChildB");

	branch1->children = child1;
	branch2->children = child2;

	branch1->next = branch2;
	root->children = branch1;

	traverse(root);	
}

Root
BranchA
   ChildA
BranchB
   ChildB

Doing it in c++ gives you proper string handling and associative arrays, both of which are difficult to handle in C.

Ah, you do? And what is that benefit?

From the Lua manual:


Obviously C++ is much easier and better suited for the development process, but I would like to really
write a scripting language that is used by other people. If it takes me 10 years and noone uses it is for
another thread. I know the odds are against me, but who knows ;)

The wide variety of platforms they're talking about are things like embedded devices and hardware that hasn't had compiler upgrades for years. Recall that Lua is supposed to run on embedded devices – so this extreme degree of cross-platform compatibility is very important.

But if your target platforms are Linux from the past 10 years and similarly for Windows, then you have nothing to worry about, really.

Well, that's cool. I'm really starting to like C++ :smile:

My quick solution above uses recursion instead of a stack object to keep
track of the tree's state. I have seen some examples where a stack is used
instead. Perhaps someone could point out the benefit / usefulness of using a stack.

A stack lets you track the state explicitly, meaning that you can have a stack in your host program and a stack in your scripting language.

Using recursion in the host to track the hosted state means that you are using the host's stack, meaning that separating the two stacks of execution becomes quite difficult.

Consider what you would need to do in order to pause execution in your hosted language, go to the host language and muck around for a while, let some network ticks pass, and eventually return to the interpreted language. How would you restore the stack, when it was implicit in your host?

quick question on static variables:
In Lua, each function returns a static int. If you are passing the LuaState*, shouldn't that be enough?
If you have several LuaStates for example, why would you want the value returned static?

Ah, the joys of overloaded C keywords.

For a global function definition, the declaration

static int foo()

doesn't mean that the returned int is static. It means that the function identifier is static, i.e. visible to that compilation unit only. (In fact, any global identifier defined as static behaves this way. Local variables that are static have the behavior that you describe.)

haha, indeed.

TreeNode( const string& v ) { value = v; };

:-p, why hello all.

Long time no see. :tongue:

And yeah, you rarely want to pass around strings: passing a const ref is almost always a better idea. (It's more efficient, because you don't need to copy the string, and since it's const, the function can't mess with the caller's string.)

Sort of on the same topic, I've been playing around with Ruby to get the core concepts down.
I've found that the hardest part is not seeing it work while you learn it. I'm sure this will be much
longer and harder in C or even C++. This is my take on a quick Lexer in Ruby.

No it's not perfect, and it doesn't account for string literals yet but:

#!/usr/bin/ruby1.9

# Lexical Analyzer
#
class Lex

  def initialize()
	@list = []
	@tokens = {
	  'def'   => :define,
	  'if'    => :if,
	  'then'  => :then,
	  'end'   => :end,
	  'else'  => :else,
	  'do'    => :do,
	  'while' => :while,
	  'loop'  => :loop,
	  'case'  => :case,
	  'nil'   => :nil,
	  'null'  => :null,
	  'void'  => :void,
	  ?''     => :smallquote, # double '' and "" to humor the mudbytes syntax highlighter :)
	  ?""     => :quote,
	  ';'     => :semicol,
	  '{'     => :opencurley,
	  '}'     => :closecurley, 
	  '['     => :openbracket,
	  ']'     => :closebracket,
	  '('     => :openparen,
	  ')'     => :closeparen,
	  '+'     => :op_plus,
	  '-'     => :op_minus,
	  '*'     => :op_times,
	  '/'     => :op_divide,
	  '='     => :op_equals,
	  '=='    => :op_isequal,
	  '.'     => :op_deref_dot,
	  '->'    => :op_deref_arrow,
	  '::'    => :op_scope,
	}
  end

  def tokenize()	
	for s in @pile
	  if @tokens[s]
		@list << @tokens[s]
	  else
		@list << "identifier [#{s}]"
	  end
	end
  end

  def scan(str)
	[?(, ?), ?., ?{, ?}, ?[, ?], ?;, "'", "->", "::"].each {|c| str.gsub!(c, " #{c} ")}
	@pile = str.split(' ')
	tokenize()
	output()
  end

  def output()
	puts "\nLexemes:\n__________________"
	@list.each {|s| puts ":#{s}"}
  end

end

code =  "def main(ch)\n"
code << "{\n"
code << "   if ch.level = 34\n"
code << "   {\n"
code << "      Server::sendGreeting(ch.name());\n"
code << "   }\n"
code << "}"


puts "Original Code:\n\n" + code

Lex.new.scan(code)

Original Code:

def main(ch)
{
   if ch.level = 34
   {
      Server::sendGreeting(ch.name());
   }
}

Lexemes:
__________________
:define
:identifier [main]
:openparen
:identifier [ch]
:closeparen
:opencurley
:if
:identifier [ch]
:op_deref_dot
:identifier [level]
:op_equals
:identifier [34]
:opencurley
:identifier [Server]
:op_scope
:identifier [sendGreeting]
:openparen
:identifier [ch]
:op_deref_dot
:identifier [name]
:openparen
:closeparen
:closeparen
:semicol
:closecurley
:closecurley

Next, it's on to the parser. So far, I'm going to iterate through the list and create an AST.
Then, on with the semantic analysis.