Code crash in mpc_parse

[TheCrafter]

Hello! I am trying to write a parser for a simple scripting language. So I completed my grammar and I tried to run it but I mpc_parse runs for about 25 seconds and then crashes without reason.

The error I am getting is:

The biggest problem is that the error is not always on the same spot. Some times it is on mpc_error or on mpc_delete. I don't know. It's kind of random.

I will give you part of my code and I hope you can tell me if it is my code's problem or if I should start debuggin mpc!!

My code:

int main()
{
    mpc_parser_t* Int = mpc_new("int");
    mpc_parser_t* Char = mpc_new("char");
    mpc_parser_t* String = mpc_new("string");
    mpc_parser_t* Id = mpc_new("id");
    mpc_parser_t* Type = mpc_new("type");
    mpc_parser_t* Formal = mpc_new("formal");
    mpc_parser_t* Header = mpc_new("header");
    mpc_parser_t* FuncDecl = mpc_new("funcdecl");
    mpc_parser_t* VarDef = mpc_new("vardef");
    mpc_parser_t* Expr = mpc_new("expr");
    mpc_parser_t* Call = mpc_new("call");
    mpc_parser_t* Atom = mpc_new("atom");
    mpc_parser_t* Simple = mpc_new("simple");
    mpc_parser_t* SimpleList = mpc_new("simplelist");
    mpc_parser_t* Stmt = mpc_new("stmt");
    mpc_parser_t* FuncDef = mpc_new("funcdef");
    mpc_parser_t* Program = mpc_new("program");

    // Define them with the following Language 
    mpca_lang(MPCA_LANG_DEFAULT,
    "                                                                                        \
    int        : /-?[0-9]+/                                                                ; \
    char       : /'[a-zA-Z0-9!@#$%^&*()\\_+-,.\\/<>?;'|\"`~]'/                             ; \
    string     : /\"(\\\\.|[^\"])*\"/                                                      ; \
    id         : /[a-zA-Z][a-zA-Z0-9_-]*/                                                  ; \
    type       : \"int\" | \"bool\" | \"char\" | <type> '[' ']' | \"list\" '[' <type> ']'  ; \
    formal     : (\"ref\")? <type> <id> (',' <id>)*                                        ; \
    header     : <type>? <id> '(' (<formal> (';' <formal>)*)? ')'                          ; \
    funcdecl   : \"decl\" <header>                                                         ; \
    vardef     : <type> <id> (',' <id>)*                                                   ; \
    expr       : <atom> | <int> | <char> | '(' <expr> ')'                                    \
                 | ('+' | '-') <expr> | <expr> ('+' | '-' | '*' | '/' | \"mod\") <expr>      \
                 | <expr> ('=' | \"<>\" | '<' | '>' | \"<=\" | \">=\") <expr>                \
                 | \"true\" | \"false\" | \"not\" <expr> | <expr> (\"and\" | \"or\") <expr>  \
                 | \"new\" <type> '[' <expr> ']' | \"nil\" | \"nil?\" '(' <expr> ')'         \
                 | <expr> '#' <expr> | \"head\" '(' <expr> ')' | \"tail\" '(' <expr> ')'   ; \
    call       : <id> '(' (<expr> (',' <expr>)*)? ')'                                      ; \
    atom       : <id> | <string> | <atom> '[' <expr> ']' | <call>                          ; \
    simple     : \"skip\" | <atom> \":=\" <expr> | <call>                                  ; \
    simplelist : <simple> (',' <simple>)*                                                  ; \
    stmt       : <simple> | \"exit\" | \"return\" <expr>                                     \
                 | \"if\" <expr> ':' <stmt>+ (\"elif\" <expr> ':' <stmt>+)*                  \
                     (\"else\" ':' <stmt>+)? \"end\"                                         \
                 | \"for\" <simplelist> ';' <expr> ';' <simplelist> ':' <stmt>+ \"end\"    ; \
    funcdef    : \"def\" <header> ':' (<funcdef> | <funcdecl> | <vardef>)* <stmt>+ \"end\" ; \
    program    : /^/ <funcdef> /$/                                                         ; \
    ",
    Int, Char, String, Id, Type, Formal, Header, FuncDecl, VarDef, Expr,
    Call, Atom, Simple, SimpleList, Stmt, FuncDef, Program);

    mpc_result_t r;
    char* input = "def hey () : return 1 end";
    if(mpc_parse("input", input, Program, &r))
    {
        mpc_ast_print((mpc_ast_t*)r.output);
        mpc_ast_delete((mpc_ast_t*)r.output);
    }
    else
    {
        mpc_err_print(r.error);
        mpc_err_delete(r.error);
    }

    PAUSE("Press any key to continue . . .");

    // Undefine and Delete our Parsers 
    mpc_cleanup(17, Int, Char, String, Id, Type, Formal, Header, FuncDecl, VarDef, Expr,
                Call, Atom, Simple, SimpleList, Stmt, FuncDef, Program);
    return 0;
}

The grammar I used in a less obfuscated version (it's hard to read on code):

I am really sorry for the long post. I just thought it would be better if I post my error before spending hours over hours to fix it. Maybe you have seen it again and you can pinpoint the problem immediately.

Thanks for your hard work. Mpc is a great piece of code and very helpful.

[orangeduck]

Hey,

I can't see the problem immediately but it seems likely that your grammar is going into an infinite loop during parsing. This can happen in a couple of cases but most likely is due to Left Recursion:

https://github.com/orangeduck/mpc#the-parser-is-going-into-an-infinite-loop

I can't spot the left recursion in your grammar but I suspect it might be in the expr or atom rule.

• Dan

[TheCrafter]

Yeah I thought you might say that... Even if I remove that rule the problem still occurs though...
Maybe I will try to re-write my grammar.

[TheCrafter]

You were right. The problem was with left recursion!

[orangeduck]

Good to hear it is working now 👍