Brainf*ck Compiler

• Download demo - 23.06 KB
• Download source - 40.69 KB

Introduction

Brainf*ck is a simple Turing-complete language which only has eight commands. Structure of brainf*ck program is simple, it consists of certain number of cells for storing program data and data pointer (dataptr) that is used for referencing data by program's commands. Size of a cell is not defined but it is usually a single byte or a word for easier handling of EOF marker when dealing with I/O commands.

Converting a brainf*ck source code to C# equivalent is an easy task using the following mappings:

Once the brainf*ck program is converted to C# code, C# compiler can be invoked dynamically to produce executable file.

Generating C# Code using CodeDOM

CodeDOM is part of .NET Framework and allows programmers to build source code tree dynamically. Unlike Expression Trees and Lambda Expressions, code models built using CodeDOM can be used to feed compiler and produce assembly files at run-time.

C# code template that is used for converting looks like this:

namespace BfApplication {
  using System;


  public class Program {

    public static void Main() {
      short[] cells = new short[1000];
      int ptr = 0;
      System.IO.Stream @in = Console.OpenStandardInput();
      System.IO.Stream @out = Console.OpenStandardOutput();

      /* brainf*ck */

    }
  }
}

cells array represents cells used for storing data by brainf*ck program, ptr is data pointer, @in and @out are standard input and output streams which are used by , and . commands.

To represent this template as CodeDOM graph, we need to create compilation unit which will store namespaces, imports and classes. Template building is done in Compile method of Compiler class.

CodeCompileUnit unit = new CodeCompileUnit();

/* creates BfApplication namespace and adds it to compile unit */
CodeNamespace ns = new CodeNamespace("BfApplication");
unit.Namespaces.Add(ns);

/* adds using directive for System namespace */
ns.Imports.Add(new CodeNamespaceImport("System"));

/* create Program class and adds it to namespace */
CodeTypeDeclaration cs = new CodeTypeDeclaration("Program");
ns.Types.Add(cs);

/* creates Main method and adds it to class */
CodeEntryPointMethod main = new CodeEntryPointMethod();
cs.Members.Add(main);

/* creates cells array and data pointer variables */
main.Statements.Add(new CodeVariableDeclarationStatement(typeof(short[]),
  "cells", new CodeArrayCreateExpression(typeof(short), cellCount)));
main.Statements.Add(new CodeVariableDeclarationStatement(typeof(int),
  "ptr", new CodePrimitiveExpression(0)));

/* create stream variables */
main.Statements.Add(new CodeVariableDeclarationStatement(typeof(Stream),
  "in", new CodeMethodInvokeExpression(ConAcc("OpenStandardInput"))));
main.Statements.Add(new CodeVariableDeclarationStatement(typeof(Stream),
  "out", new CodeMethodInvokeExpression(ConAcc("OpenStandardOutput"))));

/* keeps track of nested loops */
Stack<codestatementcollection> blocks = new Stack<codestatementcollection />();
blocks.Push(main.Statements);

CSharpCodeProvider class gives the programmer access to C# compiler. GenerateCodeFromCompileUnit method generates C# code from CodeDOM graph of compilation unit and CompileAssemblyFromDom method produces assembly file.

/* produces C# source code */
if (codeGen != null)
  provider.GenerateCodeFromCompileUnit(unit, codeGen,
  new CodeGeneratorOptions());

/* sets compiler options */
CompilerParameters p = new CompilerParameters(new string[] { "System.dll" },
  outputFileName);
p.GenerateExecutable = true;

/* compiles CodeDOM graph and produces assembly file */
CompilerResults results = provider.CompileAssemblyFromDom(p, unit);

CodeGeneratorOptions and CompilerParameters classes are used to sets various parameters for code generation and compilation.

Brainf*ck Parser

Parsing is implemented by Parse method and it is using mappings that are described earlier:

for (int i = 0; i < code.Length; i++)
{
  if (char.IsWhiteSpace(code[i])) continue;

  switch (code[i])
  {
    /* increments dataptr */
    case '>': blocks.Peek().Add(IncSt(typeof(int), PtrAcc())); break;

    /* decrements dataptr */
    case '<': blocks.Peek().Add(DecSt(typeof(int), PtrAcc())); break;

    /* increments cell referenced by dataptr */
    case '+': blocks.Peek().Add(IncSt(typeof(byte), CellAcc())); break;

    /* decrements cell referenced by dataptr */
    case '-': blocks.Peek().Add(DecSt(typeof(byte), CellAcc())); break;

    /* outputs content of referenced cell to the output */
    case '.': blocks.Peek().Add(OutExp()); break;

    /* reads byt from input and stores it to the cell
       referenced by dataptr */
    case ',':
      blocks.Peek().Add(new CodeAssignStatement(CellAcc(), InExp()));
      break;

    case '[':
      /* creates for loop that check cell referenced by dataptr for 0 */
      CodeIterationStatement loop = new CodeIterationStatement(
        new CodeSnippetStatement(), new CodeBinaryOperatorExpression(
        CellAcc(), CodeBinaryOperatorType.IdentityInequality,
        new CodePrimitiveExpression(0)), new CodeSnippetStatement());

      /* new commands goes to new loop's body */
      blocks.Peek().Add(loop);
      blocks.Push(loop.Statements);
      break;
    case ']':
      blocks.Pop();
      break;

      default: break;
  }
}

/* creates expression that references specified static method of
   Console class */
private static CodeMethodReferenceExpression ConAcc(string method)
{
  return new CodeMethodReferenceExpression(
    new CodeTypeReferenceExpression("Console"), method);
}

/* creates expression that calls ReadByte method of Console class */
private static CodeExpression InExp()
{
  return new CodeCastExpression(typeof(short),
    new CodeMethodInvokeExpression(
    new CodeMethodReferenceExpression(
    new CodeVariableReferenceExpression("in"), "ReadByte")));
}

/* creates expression that calls WriteByte method of Console class */
private static CodeExpression OutExp()
{
  return new CodeMethodInvokeExpression(
    new CodeMethodReferenceExpression(
    new CodeVariableReferenceExpression("out"), "WriteByte"),
    new CodeCastExpression(typeof(byte), CellAcc()));
}

/* creates expression that references variable that stores dataptr */
private static CodeExpression PtrAcc()
{
  return new CodeVariableReferenceExpression("ptr");
}

/* creates expression that references cell pointed by dataptr */
private static CodeExpression CellAcc()
{
  return new CodeArrayIndexerExpression(
    new CodeVariableReferenceExpression("cells"), PtrAcc());
}

/* creates expression that cast an expression to specified type */
private static CodeExpression CastExp(Type type, CodeExpression exp)
{
  return new CodeCastExpression(type, exp);
}

/* creates expression that increments provided expression */
private static CodeStatement IncSt(Type type, CodeExpression exp)
{
  return new CodeAssignStatement(exp, CastExp(type,
    new CodeBinaryOperatorExpression(exp, CodeBinaryOperatorType.Add,
    new CodePrimitiveExpression(1))));
}

/* creates expression that decrements provided expression */
private static CodeStatement DecSt(Type type, CodeExpression exp)
{
  return new CodeAssignStatement(exp, CastExp(type,
    new CodeBinaryOperatorExpression(exp, CodeBinaryOperatorType.Subtract,
    new CodePrimitiveExpression(1))));
}

Error/warning reporting is removed from the code sample.

OnReport event is used for notification about compiler events like compile errors, warnings and state of compilation process.

History

• 15^th November, 2011: Initial post