Sonoma State University
Department of Computer Science
CS-460: Programming Languages
Exercise 6a: Creating an abstract syntax tree.

Objective:

In your team, convert the input program (below) into an Abstract Syntax Tree (AST). An Abstract Syntax Tree is not a clone of a Concrete Syntax Tree. The program below is defined by our C-like programming programming language.

How do I know what a token is?

Please use the BNF document for the C-like programming language. Since this is an in-class exercise, please ask me questions if you need any help.

Please use the following input program to create your Concrete Syntax Tree:

procedure main (void)
{
  char buffer[255];
  int i, num_bytes_read, half_num_bytes_read, is_palindrome, byte;

  printf ("Enter a string of characters. When finished, hit <return> then press <ctrl-d>\n");
  for (i = 0; i < 255; i++)
  {
    buffer[i] = '\x0';
  }
  num_bytes_read = -1;
  byte = getchar();
  while ((byte != -1) && (num_bytes_read < 253))
  {
    num_bytes_read++;
    buffer[num_bytes_read] = byte;
    byte = getchar();
  }
  for (i = 0; i <= num_bytes_read; i++)
  {
    if (buffer[i] == '\n')
    {
      buffer[i] = '\x0';
      if (i > 0)
      {
        num_bytes_read = i;
      }
      else
      {
        num_bytes_read = 0;
      }
    }
  }
  if (num_bytes_read >= 2)
  {
    half_num_bytes_read = (num_bytes_read - 1) / 2;
    i = 0;
    is_palindrome = TRUE;
    while ((i <= half_num_bytes_read) && is_palindrome)
    {
      is_palindrome = buffer[i] == buffer[num_bytes_read - 1 - i];
      i = i + 1;
    }
  }
  else
  {
    is_palindrome = FALSE;
  }
  if (num_bytes_read > 0)
  {
    if (is_palindrome)
    {
      printf ("%s is a palindrome.\n", buffer);
    }
    else
    {
      printf ("%s is not a palindrome.\n", buffer);
    }
  }
}

Submission Instructions:

Since this is a group assignment, please write the names of each member of your team on your assignment submission along with "Exercise 6a: Creating an Abstract Syntax Tree".

Exercise 6a Rubric

CRITERIA RATINGS POINTS
Abstract Syntax Tree: Proficient
10 points
A partial or complete Abstract Syntax Tree is created with a Left-Child, Right-Sibling binary tree. The tree resembles an Abstract Syntax Tree and is not a clone of a Concrete Syntax Tree.		 Below Expectation
0 points
No solution submitted.		 10 points
Total points: 10