Programming Language in Lex and Yacc

I designed and implemented a small programming language for the Bilkent CS315 compiler design course using Lex and Yacc. The language has a C-like syntax with a few deliberate simplifications: begin/end blocks instead of braces, := for assignment, explicit display statements instead of printf, and function definitions that name their return value directly.

The toolchain is classic: Lex tokenizes the source, Yacc defines the grammar and builds the parse tree, and the code generator walks the tree to produce executable output.

Language Features

Null input rejection. The language forces input validation at the syntax level. Any variable read from user input must handle the zero/empty case before the program can proceed:

x := input "Enter value for x: ";
while (x == 0) begin
  display "Please enter a non-zero value for x";
  x := input "Enter value for x again: ";
end

Named return values. Function definitions name the return variable in the signature, so there’s no ambiguity about what gets returned:

foo(p, q) : largest begin
  display "Function foo with parameters", p, "and", q;
  if (p > q) then largest := p else largest := q;
  return largest;
end

Arrays and iteration. Standard array literals with length-based iteration:

a := [12, 13, 14, 15, 16, 17];
sum := 0;
for (i := 0; i < length(a); i := i + 1) begin
  sum := sum + a[i];
end
display "Sum of array:", sum;

Example Programs

Program 1: Input Validation

x := input "enter value for x: ";
while (x == 0) begin
  display "please enter a non-zero value for x";
  x := input "enter value for x again: ";
end else begin
  display "value of x was correct in inital input";
end

y := input "enter value for y: ";
while (y == 0) begin
  display "please enter a non-zero value for y";
  y := input "enter value for y again: ";
end else begin
  display "value of y was correct in inital input";
end

z := input "enter value for z: ";
while (z == 0) begin
  display "please enter a non-zero value for z";
  z := input "enter value for z again: ";
end else begin
  display "value of z was correct in inital input";
end

display x, " times ", y, " times ", z;

Program 2: Function Calls and Nested Loops

foo(p,q) : largest begin
  display "my name is foo and my parameters are\n";
  display "p = ", p, ", q =", q, "\n";
  if (p>q) begin
    largest := p;
  end else begin
    largest := q;
  end
  return largest;
end

a := [5,0,3,-7];
b := [9,-2,-1];
for (i := 0, i < a.length(), i := i + 1) begin
  for (j := 0, j < b.length(), j := j + 1) begin
    c := foo(a[i],b[j]);
    display "c = ", c, ", a = ", a[i], ", b = ", b[j];
  end
end

Program 3: Array Summation

a := [12,13,14,15,16,17];
sum := 0;
for (i := 0, i < a.length(), i := i + 1) begin
  sum := sum + a[i];
end

display "sum of array is: ", sum;

Program 4: Selection Sort

get_max(a,b):largest begin
  if (a > b) begin
    largest := a;
  end else begin
    largest := b;
  end
  return largest;
end

arr := [25,6,36,2,425,26,13];
for (i := 0, i < arr.length(), i := i + 1) begin
  for (j := i + 1, j < arr.length(), j := j + 1) begin
    if ( max(arr[i], arr[j]) != arr[j] ) begin
      temp := arr[i];
      arr[i] := arr[j];
      arr[j] := temp;
    end
  end
end

display "[ ";
for (i := 0, i < arr.length(), i := i + 1) begin
  display arr[i], ", ";
end
display " ]\n";

Program 5: Inline Functions and Mixed Expressions

get(a):d begin

  d := input "calculating d";  /* inline*/
  display "value of d: ", d;
  return d; /* inline */
end

b := a + 2 + get(5) * 10; /* inline */
a := input "enter a value for a: ";
arr := [12,13,14];
b := arr.size();
c := arr[2];
while (a > 12) begin
  a := a - 1;
end else begin
  display "a was greater than 12";
end
for (i := 1, i < 10, i := i + 1) begin
  display "test";
end

Source code on GitHub.

← back to writing