11
\$\begingroup\$

I have been working on making a transpiler from Brainfuck to C in C(11), here is the code:

#include <stdlib.h>
#include <stdio.h>

int main(int argc, char **argv) {
    size_t indentlevel = 1;
    size_t repetition = 1;
    FILE *fin, *fout;
    int c;

    if (argc != 3) {
        if (argc > 0 && argv[0][0] != '\0') // check if program name is available
            fprintf(stderr, "usage: %s [input] [output]\n", argv[0]);
        else
            fputs("usage: [input] [output]\n", stderr);
        return EXIT_FAILURE;
    }

    fin = fopen(argv[1], "r");
    if (fin == NULL) {
        perror(argv[1]);
        return EXIT_FAILURE;
    }

    fout = fopen(argv[2], "w");
    if (fout == NULL) {
        fclose(fin);
        perror(argv[2]);
        return EXIT_FAILURE;
    }

    fputs("#include <stdio.h>\nint main(void) {\n\tunsigned char cells[30000] = {0};\n\tunsigned char *cellptr = cells;\n", fout); // add initalization code to output file

    while ((c = getc(fin)) != EOF) {
        if (c == ']')
            --indentlevel;

        for (size_t i = 0; i < indentlevel; ++i)
            putc('\t', fout);

        switch (c) {
            case '>':
                while ((c = getc(fin)) == '>')
                    ++repetition;
                ungetc(c, fin);

                if (repetition == 1)
                    fputs("++cellptr;\n", fout);
                else
                    fprintf(fout, "cellptr += %zu;\n", repetition);

                repetition = 1;
                break;

            case '<':
                while ((c = getc(fin)) == '<')
                    ++repetition;
                ungetc(c, fin);

                if (repetition == 1)
                    fputs("--cellptr;\n", fout);
                else
                    fprintf(fout, "cellptr -= %zu;\n", repetition);

                repetition = 1;
                break;

            case '+':
                while ((c = getc(fin)) == '+')
                    ++repetition;
                ungetc(c, fin);

                if (repetition == 1)
                    fputs("++*cellptr;\n", fout);
                else
                    fprintf(fout, "*cellptr += %zu;\n", repetition);

                repetition = 1;
                break;

            case '-':
                while ((c = getc(fin)) == '-')
                    ++repetition;
                ungetc(c, fin);

                if (repetition == 1)
                    fputs("--*cellptr;\n", fout);
                else
                    fprintf(fout, "*cellptr -= %zu;\n", repetition);

                repetition = 1;
                break;

            case '.':
                fputs("putchar(*cellptr);\n", fout);
                break;

            case ',':
                fputs("*cellptr = getchar();\n", fout);
                break;

            case '[':
                fputs("while (*cellptr) {\n", fout);
                ++indentlevel;
                break;

            case ']':
                fputs("}\n", fout);
                break;
        }
    }

    fputs("return 0;\n}\n", fout); // add termination code to output file

    fclose(fin);
    fclose(fout);

    return EXIT_SUCCESS;
}

Any bugs or potential concerns with the code?

\$\endgroup\$

2 Answers 2

7
\$\begingroup\$

Advice I - roll your own my_basename

When you

fprintf(stderr, "usage: %s [input] [output]\n", argv[0]);

I suggest you roll this:

static char* my_basename(const char* const argv0) {
    char* ptr = strrchr(argv0, '/');

    if (ptr != NULL) {
        return ptr + 1;
    }

    ptr = strrchr(argv0, '\\');

    if (ptr != NULL) {
        return ptr + 1;
    } else {
        return argv0;
    }
}

and do the call as

fprintf(stderr, 
        "usage: %s [input] [output]\n", 
        my_basename(argv[0]));

That way, the usage message does not abuse the user with the entire path to the executable.

Advice II - validate your source language (Brainf_ck)

You could check that symbols [ and ] are well formed. The algorithm is:

static bool is_valid_brackets(char* seq) {
    size_t cnt = 0;

    for (char* pch = seq; *pch != '\0'; pch++) {
        if (*pch == '[') {
            cnt++;
        } else if (*pch == ']') {
            if (cnt == 0) {
                return false;
            }

            cnt--;
        }
        // Omit any other char but [ and ]
    }

    return cnt == 0;
}

Advice III - Consider using more functions

I suggest you separate the file logic in main() from the actual compilation to C.

\$\endgroup\$
13
  • 2
    \$\begingroup\$ @Harith But as you see, my_basename is portable. \$\endgroup\$
    – coderodde
    Feb 17 at 16:00
  • 2
    \$\begingroup\$ Except that Linux has two versions of basename() (POSIX and GNU), so this solution works best, and works on Windows too. \$\endgroup\$
    – Harith
    Feb 17 at 16:40
  • 6
    \$\begingroup\$ I think basenaming argv[0] is a terrible idea. If the user called it from the command line, argv[0] will be the command that they ran (typically not a full path). If the user specified the full path, it would make sense to give that back to them, because they probably did it for a reason (e.g. they have multiple versions of the program installed in different places). \$\endgroup\$ Feb 17 at 21:06
  • 3
    \$\begingroup\$ Bracket validation only needs a counter, not a stack. You only need a stack if you implement bracket validation for multiple types of brackets, eg if you want [{}] to be valid and [{]} to be invalid. If you use a stack you should only push opening brackets onto the stack; never push a character which is not an opening bracket onto the stack. Since in brainfuck the only type of opening bracket is [, your stack should only have [ in it, so you don't actually need a stack, just a counter that counts how many [ haven't been closed. \$\endgroup\$
    – Stef
    Feb 17 at 21:57
  • 4
    \$\begingroup\$ If you're going to roll your own my_basename, why modify the string, and why something as complex as strtok? Use last_slash = strrchr(name, '/') to find the last / if there is one. return last_slash ? last_slash+1 : name since the basename is the suffix of the existing zero-terminated string. \$\endgroup\$ Feb 18 at 2:02
4
\$\begingroup\$

There are some undefined/implementation-defined behaviors of Brainfuck that you can define.


  • The size of the cell array shall always contain at least 9999 cells. The behavior is undefined if:
    1. The program attempts to move the pointer below the first array cell, or beyond the last array cell.
    2. The program contains one or more unbalanced brackets.

For 1, you could choose to reset the pointer to cell 0 when it exceeds the upper bound of the array, and to cell n - 1 when it goes below the lower bound of the array. For 2, I'd suggest terminating the program with an EXIT_FAILURE status.


  • The value of a cell is implementation-defined if the program attempts to decrement the value below its documented minimum value, if any, or increment the value of a cell beyond its documented maximum value. (The range is implementation-defined, but shall always at least include the values 0 through 127, inclusive.)

For this, you could also implement wrap-around behavior. On underflow, wrap it to n - 1. On overflow, wrap it to 0.

(Or as it is implementation-defined, you could implement it by attempting to run some games like GCC 1.34 did back when it was opposed to the new pragma directive. But I wouldn't recommend that.)

There are also some other aspects you might be interested in, and this The Unofficial Constraints on Portable Brainfuck Implementations should prove helpful.


To reduce some duplication, you can define a wrapper around fopen():

static FILE *xfopen(const char *restrict pathname, const char *restrict mode)
{
    FILE *const fp = fopen(path, mode);
     
    /* Note that errno may not be set. */
    if (!fp) {
        perror(path);
        exit(EXIT_FAILURE);
    }
    
    return fp;
}

Now we can write:

fin = xfopen(argv[1], "r");
fout = xfopen(argv[2], "w");

Note that you don't need to declare all variables at the top of main(). I recommend declaring variables where they are first used.


You could define some symbolic names for all valid instructions:

enum {
    BF_INC, 
    BF_DEC,
    BF_GET, 
    BF_PUT, 
    BF_NEXT,
    BF_PREV,
    BF_LOOP_START,
    BF_LOOP_END
};

and replace the hardcoded values in the switch statement with them.


I suggest always using:

if (repetition == 1) {
    fputs("++cellptr;\n", fout);
} else {                 
    fprintf(fout, "cellptr += %zu;\n", repetition);
}

to

if (repetition == 1) 
    fputs("++cellptr;\n", fout);
else                
    fprintf(fout, "cellptr += %zu;\n", repetition);

The problem with the second version is that if you go back and add a second statement to the if or else clause without adding the curly braces, your code will break. See: Apple's SSL/TLS bug.


It would be nice if the program would accept its input on standard input stream if an argument was not provided (which should be trivial to implement, seeing that you'd only need to replace argv[1] with stdin. You could also choose to output directly to stdout, and take an output flag to redirect the output to a file).

\$\endgroup\$
7
  • \$\begingroup\$ @OP There are also countless other implementations of Brainfuck that have been posted and reviewed here. You may find them helpful. \$\endgroup\$
    – Harith
    Feb 17 at 16:33
  • 1
    \$\begingroup\$ Your xfopen function hardcodes the file mode to "r", read. Should it the mode as a parameter? \$\endgroup\$
    – TomG
    Feb 17 at 18:15
  • \$\begingroup\$ @TomG Good point, I overlooked that. \$\endgroup\$
    – Harith
    Feb 17 at 19:06
  • \$\begingroup\$ you could also implement wrap-around behavior. On underflow, wrap it to n - 1. On overflow, wrap it to 0. - The OP already did that, but declaring cells as an array of unsigned char. Being unsigned, C guarantees that decrement wraps to UCHAR_MAX. (Actually it guarantees that (unsigned char)0 - 1 is signed int -1 after integer promotion, but assigning that back to an unsigned char modulo-reduces into its value-range, becoming 1 less than the modulus.) The actual wrapping value depends on UCHAR_MAX and the corresponding CHAR_BIT. You could force it to be 8-bit with &= 0xFF. \$\endgroup\$ Feb 18 at 2:33
  • \$\begingroup\$ As for wrapping pointers, yes, uint16_t indexing could do wrapping somewhat cheaply, or just unsigned with &= 0xFFFF if you don't want to require the optional uint16_t in the target system. And use an array of 65536 cells. \$\endgroup\$ Feb 18 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.