arithy / packcc

A parser generator for C
Other
348 stars 29 forks source link

Simple grammar goes into an infinite loop instead of erroring #43

Closed decahedron1 closed 3 years ago

decahedron1 commented 3 years ago

I have a simple grammar like so:

root <- foo*
foo <- "foo"

If I give the parser something like 0, fo, or bar it goes into an infinite loop instead of exiting. I'm using the example main code like this:

int main() {
    pcc_context_t *ctx = pcc_create(NULL);
    while (pcc_parse(ctx, NULL));
    pcc_destroy(ctx);
    return 0;
}
AlbertoGP commented 1 year ago

For others that might wonder why this is happening, that’s a fundamental limitation described in the original PEG paper: “Parsing Expression Grammars: A Recognition-Based Syntactic Foundation

4.2.4 The Empty String Limitation To show that we have no hope of avoiding the restriction that the original grammar cannot accept the empty input string, we prove that any predicate-free grammar cannot accept the empty input string without accepting all input strings.

The grammar above accepts the empty string as input because of the * in the root rule.