An (incomplete) solution to Assignment #1
                     Programming Languages Course
                       G22.2110-001 Spring 2000
                                 ---


Problem 1:
==========

Sethi 2.12: To be done.
----------

Sethi 2.19:
-----------

As explained during the course, here is a solution:

   S ::= if E then S
       | T

   T ::= if E then T else S

To be able to work out examples, one should complete the grammar with
(for instance) a basic token (say `x') for the non-terminal S, and `é
for non-terminal E as:

     E ::= e

     S ::= if E then S
         | T
   
      T ::= if E then T else S
          | x

You can then try to build a parse tree for:

    if e then if e then x else x
                        ^      ^
                        T      T
                               ^
                               S 
              ^^^^^^^^^^^^^^^^^^
                      T
       ^              ^
       E              S
     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                S
-------------------------------------------------------------------------

Problem 3:
==========
The substr function, with lots of comments. A full program (usable for
testing) can be found <a href="substr.c">here</a>.

int substr(char *pat, char *str) {
  char *patf = pat, *strf = str;
  /* We maintain one "finger" patf on pat, and another one strf on str */
  int index = 0;
  if (!(*pat)) return 0; /* We consider that the empty pattern always matches */
  while (*pat && *str) {
    /* We superpose pat and str, and move the "fingers" on pat and str
       as long as they are on two equal chars */
    while (*patf && *strf && (*patf == *strf)) {
      ++patf; ++strf;
    }
    if (*patf) /* We did not reach the end of pat: no match yet */
      if (*strf) { /* Not yet at the end of str: we can continue */
        strf = ++str;
        patf = pat;
        ++index;
      } else /* We are at the end of the string: no chance to get a match */
        return -1;
    else /* We are at the end of the pattern: we got a match */
      return index;
  }
  return -1;
}

---------------------------------------------------------------------------

Problem 4:
==========
A full program is <a href="bstree.c">here</a>.

Type definition:
----------------
typedef struct node {
  int val;
  struct node *left, *right;
} *bstree;

It is always a good idea to have an allocation/initialization function
for our dynamic data structures:

bstree mknode(int v, bstree l, bstree r) {
  bstree tmp;
  tmp = (bstree) malloc(sizeof(struct node));
  if (tmp == NULL) {
    fprintf(stderr, "Fatal error: memory allocation failed\n");
    exit(1);
  }
  tmp->val = v; tmp->left = l; tmp->right=r;
  return tmp;
}


Adding an integer to the bs-tree:
---------------------------------
bstree add(int v, bstree t) {
  if (t == NULL)
    return mknode(v, NULL, NULL);
  if (v < t->val)
    t->left = add(v, t->left);
  else if (v > t->val)
    t->right = add(v, t->right);
  return t;
}

Deleting an integer from a bstree:
----------------------------------
bstree delete(int v, bstree t) {
  if (t == NULL)
    return t;
  if (v < t->val) {
    t->left = delete(v, t->left);
    return t;
  }
  if (v > t->val) {
    t->right = delete(v, t->right);
    return t;
  }
  /* We are on the node that we want to delete */
  if (t->right == NULL)
    return t->left;
  if (t->right->left == NULL) {
    bstree tmp = t->right;
    t->val = tmp->val;
    t->right = tmp->right;
    free(tmp);
    return t;
  }
  /* General case */
  { /* We know that the right subtree exists, and that it
       has a left branch: wo go down that branch to get
       the leftmost node
    */
    bstree tmp, ptr = t->right;
    while (ptr->left->left != NULL)
      ptr = ptr->left;
    tmp = ptr->left;
    ptr->left = tmp->right;
    t->val = tmp->val;
    free(tmp);
    return t;
  }
}

Listing in increasing order the elements:
-----------------------------------------

void list(bstree t) {
  if (t == NULL)
    return;
  list(t->left);
  printf("%d ", t->val);
  list(t->right);
}

===========================================================================