title: Creating a cons cell structure via recursive descent parsing
body: <p>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 <code>struct</code> for what I'm describing is as such: </p>
  
  <pre><code>typdef struct node node;
  
  typedef node* list;
  
  struct node { 
      char* symbol;
      list car;
      list cdr;
  };
  </code></pre>
  
  <p>Thus a cons cell would be (with a node represented as <code>[symbol][car][cdr]</code>), <code>[null][car][cdr]</code>, while a symbol would be <code>[symbol][null][null]</code>.</p>
  
  <p>For example, <code>(a b c)</code> would be represented as:
  <img src="https://i.stack.imgur.com/YJFRp.png" alt="enter image description here"></p>
  
  <p>And <code>(a (b c) d)</code>, would be represented as:
  <img src="https://i.stack.imgur.com/sgcY7.png" alt="enter image description here"></p>
  
  <p>This previous post on stack overflow: <a href="https://stackoverflow.com/questions/6115562/cons-cell-data-structure-in-c">Cons Cell data structure in C</a> is pretty much dealing with the same assignment. In the top answer by Jason for that post, one of his suggestions is 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. </p>
  
  <p>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 pseudo code that I have: </p>
  
  <pre><code>list s_expression() {
      list local;
      list temp;
  
      if (token == "(") {
          token = getToken();
          local = new node;
          local -&gt; car = s_expression()
          temp = local;
  
          while (token != ")") {
              temp -&gt; rest = new node;
              temp = temp -&gt; rest;
              temp -&gt; first = s_expression()
          }
  
          temp -&gt; rest = NULL;
          token = getToken();
      } else if (token == symbol) {
          list symbolNode = new node;
          symbolNode -&gt; symbol = token;
          token = getToken()
          return symbolNode;
      } else {
          return local;
      }
  }
  </code></pre>
  
  <p><code>s_expression</code> is supposed to return a pointer to a recursively built cons cell structure. I'm just having issues figuring out when to call <code>getToken()</code>, as I either call <code>getToken</code> in the wrong spot and unintentionally skip over a token, or I call <code>getToken()</code> 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.</p>
  
  <p>When should I be calling <code>getToken()</code>? </p>
  
  <p>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?</p>
  
  <p>If needed, I can post the lexical analyzer that's been provided to us. </p>