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

Objective:

In a team of three or four students, 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:

function char decimal_to_hex_digit (int number)
{
  char hex_digit;

  if ((number >= 0) && (number <= 9))
  {
    hex_digit = number + '0';
  }
  else
  {
    if ((number >= 10) && (number <= 15))
    {
      hex_digit = number - 10 + 'a';
    }
    else
    {
      hex_digit = '\x0'; // return a NULL character when an error occurs.
    }
  }
  return hex_digit;
}

procedure main (void)
{
  char hex_number_string[9], reversed_hex_number_string[9], hex_digit_character;
  int i, number, temp_number, hex_digit, num_hex_digits;
  bool error_occurred;

  error_occurred = FALSE;
  for (i = 0; i < 9; i = i + 1)
  {
    hex_number_string[i] = '\x0';
    reversed_hex_number_string[i] = '\x0';
  }
  number = 2147483647; // largest positive 32-bit signed integer.
  temp_number = number;
  num_hex_digits = 0;
  while ((temp_number > 0) && (!error_occurred))
  {
    hex_digit = temp_number % 16;
    hex_digit_character = decimal_to_hex_digit (hex_digit);
    if (hex_digit_character != '\x0')
    {
      reversed_hex_number_string[num_hex_digits] = hex_digit_character;
       num_hex_digits = num_hex_digits + 1;
    }
    else
    {
      error_occurred = TRUE;
    }
    temp_number = temp_number / 16;
  }
  if (!error_occurred)
  {
    for (i = 0; i <= num_hex_digits; i = i + 1)
    {
      hex_number_string[i] = reversed_hex_number_string[num_hex_digits - i - 1];
    }
    printf ("The non-negative integer, %d equals 0x%s\n", number, hex_number_string);
  }
}

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 6b: Creating an Abstract Syntax Tree"".

Exercise 6b 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