Click here to Skip to main content
15,867,291 members
Articles / Programming Languages / C#

Brainf*ck Compiler

Rate me:
Please Sign up or sign in to vote.
4.98/5 (25 votes)
14 Nov 2011CPOL2 min read 47.2K   957   35   19
This article shows how to produce executable file from brainf*ck source code using CodeDOM
brainfuck.png

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.

brainf*ck commands:
>moves dataptr to the next cell
<moves dataptr to the previous cell
+increments cell referenced by dataptr
-decrements cell referenced by dataptr
[test value of cell referenced by dataptr if it is equal to 0, command moves execution forward to the command after the matching ] command.
]moves execution backward to the matching [ command
.writes single byte stored in a cell referenced by the data pointer to the standard output
,reads single byte from the standard input and stores it in a cell referenced by the data pointer

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

>dataptr = dataptr + 1;
<dataptr = dataptr - 1;
+cells[dataptr] = cells[dataptr] + 1;
-cells[dataptr] = cells[dataptr] - 1;
[for(; cells[dataptr] != 0;) {
]}
.Console.Write(cells[dataptr]);
,cells[dataptr] = Console.Read();

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:

C#
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.

C#
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.

C#
/* 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:

C#
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

  • 15th November, 2011: Initial post

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer
Serbia Serbia
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
GeneralMy vote of 4 Pin
jfriedman7-Jan-13 12:40
jfriedman7-Jan-13 12:40 
GeneralMy vote of 5 PinPopular
Keith Barrow7-Feb-12 11:50
professionalKeith Barrow7-Feb-12 11:50 
GeneralMy vote of 1 Pin
ZurdoDev7-Feb-12 4:28
professionalZurdoDev7-Feb-12 4:28 
GeneralMy vote of 1 on your vote of 1. Reasons PinPopular
Keith Barrow7-Feb-12 12:04
professionalKeith Barrow7-Feb-12 12:04 
GeneralRe: My vote of 1 PinPopular
Brady Kelly7-Feb-12 18:00
Brady Kelly7-Feb-12 18:00 
GeneralRemoved Pin
ZurdoDev8-Feb-12 1:59
professionalZurdoDev8-Feb-12 1:59 
GeneralRe: My vote of 1 Pin
egenis7-Feb-12 19:14
egenis7-Feb-12 19:14 
GeneralRe: My vote of 1 Pin
dave.dolan8-Feb-12 4:37
dave.dolan8-Feb-12 4:37 
GeneralRe: My vote of 1 Pin
Ivaylo Slavov6-Nov-12 22:39
Ivaylo Slavov6-Nov-12 22:39 
QuestionCorrection Pin
DaveX8615-Nov-11 5:47
DaveX8615-Nov-11 5:47 
AnswerRe: Correction Pin
Mladen Janković15-Nov-11 6:41
Mladen Janković15-Nov-11 6:41 
GeneralMy vote of 5 Pin
Wayne Gaylard15-Nov-11 2:14
professionalWayne Gaylard15-Nov-11 2:14 
GeneralRe: My vote of 5 Pin
Mladen Janković15-Nov-11 6:41
Mladen Janković15-Nov-11 6:41 
GeneralMy vote of 5 Pin
Manfred Rudolf Bihy15-Nov-11 2:13
professionalManfred Rudolf Bihy15-Nov-11 2:13 
GeneralRe: My vote of 5 Pin
Mladen Janković15-Nov-11 6:41
Mladen Janković15-Nov-11 6:41 
QuestionThat's really cool Pin
Sacha Barber14-Nov-11 23:52
Sacha Barber14-Nov-11 23:52 
AnswerRe: That's really cool Pin
Mladen Janković15-Nov-11 1:39
Mladen Janković15-Nov-11 1:39 
GeneralMy vote of 5 Pin
Dave Kerr14-Nov-11 23:41
mentorDave Kerr14-Nov-11 23:41 
GeneralRe: My vote of 5 Pin
Mladen Janković15-Nov-11 1:39
Mladen Janković15-Nov-11 1:39 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.