12 Replies - 717 Views - Last Post: 25 April 2015 - 04:15 PM Rate Topic: -----

#1 computersamurai  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 24-April 15

Recursively building a conscell structure via recursive descent.

Posted 25 April 2015 - 12:21 AM

I'm currently working on a Scheme Interpreter written in C. I'm trying to create a cons cell structure via recursive descent parsing, except instead of just having the car and cons, I also have a field that holds the token that I receive from the lexical analyzer (which was provided to us). The struct for what I'm describing is as such:

typdef struct node node;

typedef node* list;

struct node { 
    char* symbol;
    list car;
    list cdr;
};



Thus a cons cell would be (with a node represented as [symbol][car][cdr]), [null][car][cdr], while a symbol would be [symbol][null][null].

In the top answer for a similar question on Stack Overflow, one of the suggestions was to put the tokens into a stack as the input is recursively parsed, and then from that stack input it into the cons cell structure.

This is something that I'm working towards now, as it is easier for me to understand and I already have implemented a stack in C before, but I know that I can just build the structure recursively, I'm just not sure how. The following is code that I have:

list s_expression()
{	
	list local;
	list temp;

	if (strcmp(token, "(") == 0) {

		strcpy(token, getToken());

		local = createNode(NULL, NULL, NULL); 
		local -> car = s_expression();
		temp = local;

		while(strcmp(token, ")") != 0) {
			temp -> cdr = createNode(NULL, NULL, NULL);
			temp = temp -> cdr;
			temp -> car = s_expression();
		}

		temp -> cdr = NULL;
		strcpy(token, getToken());

	} else if (isSymbol(token) == 0) {

		strcpy(symbol, token);
		temp = createNode(symbol, NULL, NULL);
		return temp; 

    } else {
    	return local;
    }
    return local;
}



s_expression is supposed to return a pointer to a recursively built cons cell structure. I'm just having issues figuring out when to call getToken(), as I either call getToken in the wrong spot and unintentionally skip over a token, or I call getToken() when I'm done getting all of the tokens, thus causing my program to continue searching for a token from user input instead of continuing on with the rest of the program.

When should I be calling getToken()?

In addition, what would be better, recursively building the cons cell structure as you go through the user's input, or putting all of the tokens into a stack and then building the cons cell structure using that stack?

If needed, I can post the lexical analyzer that's been provided to us.

Also, sorry for S_expression(); showing up as S_exp<b></b>pression();, I'm not sure what happened there. I copied this post from my question on stack overflow.

Is This A Good Question/Topic? 0
  • +

Replies To: Recursively building a conscell structure via recursive descent.

#2 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3714
  • Posts: 13,467
  • Joined: 08-August 08

Re: Recursively building a conscell structure via recursive descent.

Posted 25 April 2015 - 05:23 AM

Start small, and confirm that things are working before moving on. Your recursion isn't working, so let's start with that. I assume you're parsing a string, right?
void Cons(list myList, char str[])
{
	if (str[0] == '(') {
		Cons(myList, &str[1]);
	}
}

int main()
{
	char cons[] = {"((1 . 2) . (3 . 4))"};
	list theList;
	Cons(theList, cons);

	return 0;
}


So the first two characters will have our function calling itself twice and the second call will be parsing 1 . 2) . (3 . 4)). What will happen with 1.2)?
Was This Post Helpful? 0
  • +
  • -

#3 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 6979
  • View blog
  • Posts: 14,600
  • Joined: 16-October 07

Re: Recursively building a conscell structure via recursive descent.

Posted 25 April 2015 - 07:12 AM

First, don't obfuscate pointers with typedef! Ever. Second, your node is too complex.

A cons list is pretty much just a stack. The node should just be a value and a pointer to a node. If you want to keep things generic, do something like:
typedef struct Node_s {
    void *value;
    struct Node_s *next;
} Node;

Node *cons(void *, Node *);
void *car(Node *);
Node *cdr(Node *);


Was This Post Helpful? 1
  • +
  • -

#4 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3714
  • Posts: 13,467
  • Joined: 08-August 08

Re: Recursively building a conscell structure via recursive descent.

Posted 25 April 2015 - 07:24 AM

View Postbaavgai, on 25 April 2015 - 10:12 AM, said:

First, don't obfuscate pointers with typedef! Ever. Second, your node is too complex.

True. I should have mentioned how difficult I found it to remember that theList and myList in my version of the OP's code are pointers.

Doesn't the struct need a left and right pointer? Isn't that what car and cdr are?
Was This Post Helpful? 1
  • +
  • -

#5 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 6979
  • View blog
  • Posts: 14,600
  • Joined: 16-October 07

Re: Recursively building a conscell structure via recursive descent.

Posted 25 April 2015 - 07:41 AM

View PostCTphpnwb, on 25 April 2015 - 10:24 AM, said:

Doesn't the struct need a left and right pointer? Isn't that what car and cdr are?


No, in spite of the confusing bloody name, car is actually the value. e.g.
list 1 2 3
is really
(cons 1 (cons 2 (cons 3 ())))
in C you might say
1 -> 2 -> 3 -> NULL



In the above, car will get you 1 and cdr will get you (cons 2 (cons 3 ())). What C structure does that suggest?

... crap, just found a wiki for this: they probably did a better job than I just did, though one example is strangely similar. http://en.wikipedia.org/wiki/Cons

When you see lispy trees, they're taking advantage of the fact that the value can be anything, including another cons list. Hence my suggestion of void* for a value.
Was This Post Helpful? 1
  • +
  • -

#6 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3714
  • Posts: 13,467
  • Joined: 08-August 08

Re: Recursively building a conscell structure via recursive descent.

Posted 25 April 2015 - 07:51 AM

Yes, but they also talk about using a tree, and that

Quote

Technically, the list (1 2 3) in the previous example is also a binary tree, one which happens to be particularly unbalanced.

Was This Post Helpful? 0
  • +
  • -

#7 computersamurai  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 24-April 15

Re: Recursively building a conscell structure via recursive descent.

Posted 25 April 2015 - 11:07 AM

View Postbaavgai, on 25 April 2015 - 07:12 AM, said:

First, don't obfuscate pointers with typedef! Ever. Second, your node is too complex.

A cons list is pretty much just a stack. The node should just be a value and a pointer to a node. If you want to keep things generic, do something like:
typedef struct Node_s {
    void *value;
    struct Node_s *next;
} Node;

Node *cons(void *, Node *);
void *car(Node *);
Node *cdr(Node *);



In the description of the assignment my professor suggests to make the nodes generic, so that [symbol][null][null] will just be a symbol node, while [null][car][cdr] will just be a conscell, but with what you're suggesting, then wouldn't a node pointing to a symbol will just have the value in it, correct? Attached to this post is how the conscell structure would be represented (by my professors specifications for node). The first one is a structure representing (a b c) and the second one is (a (b c) d). How would I use what you suggested for what I'm trying to do? Would it be something like this:

if the input is (a b c) then the first node will have value pointing to a, and next will point to the next cell, which will be pointing to b, and then finally that node will point to a node with value pointing to c and have next as null (since it's at the end of the list)?

Thank you so much for all the help by the way everyone! This is extremely helpful for me.

Attached image(s)

  • Attached Image
  • Attached Image

Was This Post Helpful? 0
  • +
  • -

#8 computersamurai  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 24-April 15

Re: Recursively building a conscell structure via recursive descent.

Posted 25 April 2015 - 11:23 AM

View Postbaavgai, on 25 April 2015 - 07:12 AM, said:

First, don't obfuscate pointers with typedef! Ever. Second, your node is too complex.

A cons list is pretty much just a stack. The node should just be a value and a pointer to a node. If you want to keep things generic, do something like:
typedef struct Node_s {
    void *value;
    struct Node_s *next;
} Node;

Node *cons(void *, Node *);
void *car(Node *);
Node *cdr(Node *);



Actually reviewing this more, I understand this much more and what you suggested makes a whole lot clearer. So for my understanding, cons will put the value into a node and return a new node (with that new value), car is just returning the value from the node passed to it, and cdr will return *next from the node passed to it?
Was This Post Helpful? 0
  • +
  • -

#9 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 6979
  • View blog
  • Posts: 14,600
  • Joined: 16-October 07

Re: Recursively building a conscell structure via recursive descent.

Posted 25 April 2015 - 12:56 PM

View PostCTphpnwb, on 25 April 2015 - 10:51 AM, said:

they also talk about using a tree, and that

Quote

Technically, the list (1 2 3) in the previous example is also a binary tree, one which happens to be particularly unbalanced.


This is what adds the the confusion, honestly. If you look at what they're showing, the are considering the value node the left branch, the next node the right. Since the value can also be a node, then sure, you can make a binary tree. However, only one part of the structure is explicitly a branch, the other is whatever you want.

In Lisp you'll see the tree thing, because value can be anything, but it's honestly just a linked list. In tighter functional languages like Haskell and ML a cons list IS just a list as the type of the value node must be explicit.
Was This Post Helpful? 0
  • +
  • -

#10 computersamurai  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 24-April 15

Re: Recursively building a conscell structure via recursive descent.

Posted 25 April 2015 - 02:06 PM

I'm still having trouble with recursively creating the conscell structure. Should I use a helper function, should I be calling s_expression over and over while passing it parameters? I'm not really sure what to do.
Was This Post Helpful? 0
  • +
  • -

#11 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 6979
  • View blog
  • Posts: 14,600
  • Joined: 16-October 07

Re: Recursively building a conscell structure via recursive descent.

Posted 25 April 2015 - 03:07 PM

What new have you tried?

Given your notes, you could do something like:
Cons *addSymbol(char symbol, Cons *);
Cons *addCons(Cons *, Cons *);

Cons *bc = addSymbol('B', addSymbol('C',NULL));
/* your first diagram */
Cons *abc = addSymbol('A', bc);
/* your second diagram */
Cons *abcd = addSymbol('A', addCons(bc, addSymbol('D',NULL)));



The nature of the Cons struct is still up to you.

You might also want:
int isList(Cons *);
int isSymbol(Cons *);



Hmm... perhaps:
Cons *atom(char);
Cons *cons(Cons *, Cons *);

Cons *bc = cons(atom('B'), cons(atom('C'), NULL));
Cons *abc = cons(atom('A'), bc);
Cons *abcd = cons(atom('A'), cons(bc, cons(atom('D'),NULL)));



Sorry, no overloads in C.

Hope this helps.
Was This Post Helpful? 0
  • +
  • -

#12 computersamurai  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 24-April 15

Re: Recursively building a conscell structure via recursive descent.

Posted 25 April 2015 - 03:29 PM

View Postbaavgai, on 25 April 2015 - 03:07 PM, said:

What new have you tried?

Given your notes, you could do something like:
Cons *addSymbol(char symbol, Cons *);
Cons *addCons(Cons *, Cons *);

Cons *bc = addSymbol('B', addSymbol('C',NULL));
/* your first diagram */
Cons *abc = addSymbol('A', bc);
/* your second diagram */
Cons *abcd = addSymbol('A', addCons(bc, addSymbol('D',NULL)));



The nature of the Cons struct is still up to you.

You might also want:
int isList(Cons *);
int isSymbol(Cons *);



Hmm... perhaps:
Cons *atom(char);
Cons *cons(Cons *, Cons *);

Cons *bc = cons(atom('B'), cons(atom('C'), NULL));
Cons *abc = cons(atom('A'), bc);
Cons *abcd = cons(atom('A'), cons(bc, cons(atom('D'),NULL)));



Sorry, no overloads in C.

Hope this helps.


http://pastebin.com/CwCsYe3y

This is currently what I have tried, and thanks for your response!

Also, I've gotten rid of the notion of symbol conscells, and instead just have the cells point to a symbol, as such:

Attached image(s)

  • Attached Image

Was This Post Helpful? 0
  • +
  • -

#13 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3714
  • Posts: 13,467
  • Joined: 08-August 08

Re: Recursively building a conscell structure via recursive descent.

Posted 25 April 2015 - 04:15 PM

View Postbaavgai, on 25 April 2015 - 03:56 PM, said:

In Lisp you'll see the tree thing, because value can be anything, but it's honestly just a linked list.

Honestly, I'm having trouble seeing it as anything other than a binary tree. In the first example, the left (or the right) nodes are null for all but the last value, where both left and right are null. I suppose this is just semantics, since a tree is just a twist on linked lists.

@OP: You should post your code here, and in code tags.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1