mini-WhileDB

This is the repo for CS2205 Fall Project, mini-WhileDB with string and array.

Usage

To get started, navigate to root dirctory.

cd while_ldb_parser 
make

To execute a source file a.jtl with our interpreter:

cd while_ldb_parser 
./main a.jtl

Introduction

In addition to the basic features of the WhileDB language, we introduce the following enhancements:

1. Array

For array, we support array declaration, initialization via C-style initializer list, subscript access, built-in length function, and dereference.

  var p = malloc(80), a[10], b;
  b = *(p + 8); // access 2nd int in p
  b = a[1]; // access 2nd int in a
  b = len(a) // b = 10

2. String String is built on top of array. We support string literal, char literal (including C-style escape characters), and string I/O.

var a = 'a';
var b[10] = "hello";
var c = '\n';

var a[10], b;
a = read_string();
b = read_char();
write_string(a);
write_char(a[5]);

Detailed Standard

1. Type Specification

• Integers, pointers, and characters are all treated as natural numbers. Differences between them only emerge at the level of function interpretation.
• Each identifier (and intermediate result) holds an attribute is_array to indicate whether it's an array pointer.

2. Array class (fixed length)

• Writable subscript access with range check.
• Initializer list for array initialization.
  • curly brackets + comma (C style)
  • copy initializer list to array, and remaining part of array (if any) is filled with zeros.
  • if initializer list is longer than array, raise error.

  var a[10];
  a[1] = 1; // correct
  a[10] = 1; // raise error, out of range
  var b[10] = {0, 1, 2, 3, 4, 5}

3. Pointer Arithmetic

• For array pointer ptr (is_array = true), arithmetic operations like *(ptr + n) are interpreted at the integer level.
• For non-array pointers (is_array = false), arithmetic operations like *(ptr + n) are interpreted at the byte level

  var p = malloc(80), a[10], b;
  b = *(p + 8); // access 2nd int in p
  b = a[1] // access 2nd int in a

4. String

• String Literal & Char Literal
  • double quote: string literal.
  • single quote: char literal.
  • support C-style escape characters.
• String literal can be assigned to array or used at initialization.
  • copy string to array, and remaining part of array(if any) is filled with zeros.
  • if string is longer then array, raise error.
  • by design, string literals do not include a terminating \0 character.
• Char literal is directly interpreted as a constant, and all its behavior comply with constant.

var a[10] = "abcd", b = '\n';

5. Extension of Variable Declaration

• Mulitple variable/array declaration in one line, separated by comma.
• Vairalbe/array initialization at declaration, via equal sign.

var a, b, c=1;
var d[10] = {0, 1, 2, 3, 4}, e[10] = "abcde";
var f = 0, g[5]

6. More Built-in Functions.

• EXPR len:
  • len(S : string literal) -> var
  • len(A : array) -> var
    • return the length of argument.
    • Note: When applied to an array containing a string, len(A) returns the array's fixed length, not the position of the first \0.
• EXPR read_string:
  • read_sring() -> string literal
    • read in a string deliminated by any white space, and return as string literal.
    • buffer will be automatically managed to avoid overflow while reading.
• CMD write_string :
  • write_string(S : string literal)
  • write_string(A : array)
    • interpret the argument as a sequence of ASCII char and write sequentially.
    • if any non-ASCII character encountered, raise error.

---

Verification

We have devised a comprehensive test suite to evaluate the correctness of our implementation.

Our test extensively examines every listed feature, including correctness and error capturing.

Test cases are located in /verification/cases, with 53 cases in total, organized into the following sub-modules::

• array
  • len
  • subscript access
  • write int
• basic
  • 9 general cases used as initial correctness test at development stage.
• decl
  • 4 cases for variable declaration initialization extension.
• pointer
  • 4 cases for pointer arithmetic and dereference.
• string
  • char literal
  • len
  • read string
  • string literal
  • write string
• tester_self_test
  • 4 cases to verify the correctness of tester itself.

The tester uses three methods to justify the correctness of our impelmentation:

1. method=cpp, compare output with equivalent C++ program on multiple inputs.
2. method=out, compare output with manually verified output.
3. method=error, expected to receive exception.

To run full test suite:

cd verification
./test_cases.py all_cases.json

if you encoutered "python not found", please change the shebang (first line) of test_cases.py and test_onecase.py to "!/usr/bin/python"

To run a subset of cases

cd verification
./test_cases.py cases/<sub-module>/<sub-module>.json

To run a single case:

cd verification
./test_onecase.py -n <case_path>

For detailed arguments and case setup, please refer to comments in test_cases.py and test_onecase.py.