Brainf*ck 编译器

• 下载演示 - 23.06 KB
• 下载源代码 - 40.69 KB

引言

Brainf*ck 是一种简单的图灵完备语言，仅包含八条指令。 Brainf*ck 程序的结构很简单，它由用于存储程序数据的特定数量的单元格和数据指针（dataptr）组成，该指针用于通过程序的指令引用数据。 单元格的大小未定义，但通常为单个字节或字，以便更容易处理处理 I/O 命令时的 EOF 标记。

Brainf*ck 指令
>	将 dataptr 移动到下一个单元格
<	将 dataptr 移动到上一个单元格
+	增加 dataptr 引用单元格的值
-	减少 dataptr 引用单元格的值
[	测试 dataptr 引用单元格的值是否等于 0，如果相等，则将执行移动到与匹配的 ] 指令之后的指令。
]	将执行移动到匹配的 [ 指令
.	将存储在数据指针引用的单元格中的单个字节写入标准输出
,	从标准输入读取单个字节并将其存储到数据指针引用的单元格中

使用以下映射将 Brainf*ck 源代码转换为 C# 等效代码是一项简单的任务

>	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();

一旦 Brainf*ck 程序被转换为 C# 代码，就可以动态调用 C# 编译器来生成可执行文件。

使用 CodeDOM 生成 C# 代码

CodeDOM 是 .NET Framework 的一部分，允许程序员动态构建源代码树。 与表达式树和 Lambda 表达式不同，使用 CodeDOM 构建的代码模型可用于馈送编译器并在运行时生成程序集文件。

用于转换的 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 数组表示 Brainf*ck 程序用于存储数据的单元格，ptr 是数据指针，@in 和 @out 是标准输入和输出流，由 , 和 . 指令使用。

为了将此模板表示为 CodeDOM 图，我们需要创建一个编译单元，它将存储命名空间、导入和类。 模板构建在 Compiler 类的 Compile 方法中完成。

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 类使程序员可以访问 C# 编译器。 GenerateCodeFromCompileUnit 方法从编译单元的 CodeDOM 图生成 C# 代码，而 CompileAssemblyFromDom 方法生成程序集文件。

/* 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 和 CompilerParameters 类用于设置各种代码生成和编译参数。

Brainf*ck 解析器

解析由 Parse 方法实现，它使用前面描述的映射

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))));
}

错误/警告报告已从代码示例中删除。

OnReport 事件用于通知编译器事件，例如编译错误、警告和编译过程的状态。

历史

• 2011年11月15日：初始发布