JohnnyStarr
Wizard
Group: Members
Posts: 953
Joined: Feb 14, 2009
|
#1 id:46769 Posted Jun 6, 2010, 4:15 pm
|
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:
Code (c++): 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 |
#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);
}
|
Code (output): 1
2
3
4
5
6
7
8
9 |
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.
|
Last edited Jun 6, 2010, 4:17 pm by JohnnyStarr
|
|
JohnnyStarr
Wizard
Group: Members
Posts: 953
Joined: Feb 14, 2009
|
#2 id:46770 Posted Jun 6, 2010, 6:04 pm
|
Ok, heres the answer to my own question:
Code (C): 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53 |
#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(c);
}
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);
}
|
Code (output): 1
2
3
4
5
6
7
8
9 |
Root
BranchA
ChildA
BranchB
ChildB
|
|
Last edited Jun 6, 2010, 6:05 pm by JohnnyStarr
|
|
|
|
David Haley
Wizard
Group: Members
Posts: 7,783
Joined: Jun 30, 2007
|
#4 id:46776 Posted Jun 6, 2010, 7:31 pm
|
Quote:but I see the benefit in creating it in C, and not C++.
Ah, you do? And what is that benefit?
|
|
|
JohnnyStarr
Wizard
Group: Members
Posts: 953
Joined: Feb 14, 2009
|
#5 id:46777 Posted Jun 6, 2010, 7:50 pm
|
From the Lua manual:
Lua said:
Compiling Lua is straightforward. Lua, including the language processor and its core libraries, is written
in plain vanilla C so that it can be built on a wide variety of platforms with any ANSI-compliant C com-
piler. The advantage is that the resulting libraries and interpreter program are compatible with the sys-
tem on which it’s built. This is one of the principal advantages of open-source software in general. As
long as the target platform supports the tools and libraries needed to compile the source code — in Lua’s
case, this is a standard C compiler — the resulting binary program is compatible with the platform.
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 ;)
|
|
|
|
|
|
|
JohnnyStarr
Wizard
Group: Members
Posts: 953
Joined: Feb 14, 2009
|
#8 id:46957 Posted Jun 8, 2010, 12:50 pm
|
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.
|
|
|
David Haley
Wizard
Group: Members
Posts: 7,783
Joined: Jun 30, 2007
|
#9 id:46960 Posted Jun 8, 2010, 1:10 pm
|
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?
|
|
|
JohnnyStarr
Wizard
Group: Members
Posts: 953
Joined: Feb 14, 2009
|
#10 id:46980 Posted Jun 8, 2010, 8:43 pm
|
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?
|
|
|
|
|
JohnnyStarr
Wizard
Group: Members
Posts: 953
Joined: Feb 14, 2009
|
#12 id:46995 Posted Jun 9, 2010, 6:09 am
|
David Haley said:Ah, the joys of overloaded C keywords.
haha, indeed.
|
|
|
Noplex
Conjurer
Group: Members
Posts: 107
Joined: May 20, 2006
|
#13 id:47000 Posted Jun 9, 2010, 11:16 am
|
Code (text): 1
2
3
4
5 |
TreeNode( const string& v ) { value = v; };
|
:-p, why hello all.
|
|
.........................
jb
|
|
|
|
JohnnyStarr
Wizard
Group: Members
Posts: 953
Joined: Feb 14, 2009
|
#15 id:47013 Posted Jun 9, 2010, 6:44 pm
|
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:
Code (Ruby): 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82 |
#!/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)
|
Code (output): 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 |
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.
|
Last edited Jun 9, 2010, 6:55 pm by JohnnyStarr
|
|
