Pre type checking possible?

[joagre]

I tried to build a simple PEG grammar that should accept these:

1+1;
a*1;
1*a;
true&&true;
a&&true;

But fail on these:

1+true;
2&&1;
1&&true;

Below is my latest approach. It is almost there but fails on, for example, a*1;
I'm starting to believe that it's impossible and that I just should let my compiler do type analysis in a later state. It would be nice to catch these errors early on though.

Cheers
/J

%prefix "test"
Program <- Statement+
Statement <- Assignment / Expression ';'
Assignment <- Variable '=' Expression

# Expressions
Expression <- LogicalExpr / ArithmeticExpr

# Logical expressions
LogicalExpr <- OrExpr
OrExpr <- AndExpr ('||' AndExpr)*
AndExpr <- NotExpr ('&&' NotExpr)*
NotExpr <- '!' LogicalPrimary / LogicalPrimary
LogicalPrimary <- BooleanLiteral / NonArithmetic / Variable / FunctionCall
NonArithmetic <- (Variable / FunctionCall) !NumberLiteral

# Arithmetic expressions
ArithmeticExpr <- AdditiveExpr
AdditiveExpr <- MultiplicativeExpr (('+' / '-') MultiplicativeExpr)*
MultiplicativeExpr <- UnaryExpr (('*' / '/') UnaryExpr)*
UnaryExpr <- ('+' / '-')? ArithmeticPrimary
ArithmeticPrimary <- NumberLiteral / NonLogical / Variable/ FunctionCall
NonLogical <- (Variable / FunctionCall) !BooleanLiteral

# Handling of literals and variables
NumberLiteral <- [0-9]+ ('.' [0-9]+)?
BooleanLiteral <- 'true' / 'false'
Variable <- [a-zA-Z_][a-zA-Z0-9_]*
FunctionCall <- Variable '(' (Expression (',' Expression)*)? ')'

%%
int main() {
test_context_t *context = test_create(NULL);
test_parse(context, NULL);
test_destroy(context);
return 0;
}

[dolik-rce]

Hi @joagre,

I noticed two small problems:

1. the negative matches should be done before you parse Variable or FunctionCall
2. true and false can be parsed as variable name, which breaks some type checks

If you change it like this, it should be much better:

NonArithmetic <- !NumberLiteral (Variable / FunctionCall)
NonLogical <- !BooleanLiteral (Variable / FunctionCall)
Variable <- !BooleanLiteral [a-zA-Z_][a-zA-Z0-9_]*

[joagre]

Thanks for the input! Invaluable. It works much better now but a*1; is still invalid. A few tests that show the wanted behavior:

$ echo "1+1;" | ./foo
$ echo "true&&false;" | ./foo
$ echo "1+a;" | ./foo
$ echo "true&&1;" | ./foo
Syntax error
$ echo "1&&true;" | ./foo
Syntax error
$ echo "true+1;" | ./foo
Syntax error
$ echo "1*a;" | ./foo

and then the culprit:

$ echo "a*1;" | ./foo
Syntax error

Melts my brain. :-)

Thanks!
/J

[joagre]

New version:

%prefix "test"

Program            <- Statement+
Statement          <- Assignment / Expression ';'
Assignment         <- Variable '=' Expression

# Expressions
Expression         <- LogicalExpr / ArithmeticExpr

# Logical expressions
LogicalExpr        <- OrExpr
OrExpr             <- AndExpr ('||' AndExpr)*
AndExpr            <- NotExpr ('&&' NotExpr)*
NotExpr            <- '!' LogicalPrimary / LogicalPrimary
LogicalPrimary     <- BooleanLiteral / NonArithmetic / Variable / FunctionCall
NonArithmetic      <- !NumberLiteral (Variable / FunctionCall)

# Arithmetic expressions
ArithmeticExpr     <- AdditiveExpr
AdditiveExpr       <- MultiplicativeExpr (('+' / '-') MultiplicativeExpr)*
MultiplicativeExpr <- UnaryExpr (('*' / '/') UnaryExpr)*
UnaryExpr          <- ('+' / '-')? ArithmeticPrimary
ArithmeticPrimary  <- NumberLiteral / NonLogical / Variable/ FunctionCall
NonLogical         <- !BooleanLiteral (Variable / FunctionCall)

# Handling of literals and variables
NumberLiteral      <- [0-9]+ ('.' [0-9]+)?
BooleanLiteral     <- 'true' / 'false'
Variable           <- !BooleanLiteral [a-zA-Z_][a-zA-Z0-9_]*
FunctionCall       <- Variable '(' (Expression (',' Expression)*)? ')'

%%
int main() {
    test_context_t *context = test_create(NULL);
    test_parse(context, NULL);
    test_destroy(context);
    return 0;
}

[dolik-rce]

Melts my brain. :-)

I know that feeling, it happens often with peg grammars :-)

I strongly suggest to add PCC_DEBUG macro to your grammar. It will show you what is happening inside, which makes it much easier to locate the problems. Basic implementation can look like this:

%earlysource {
    static const char *dbg_str[] = { "Evaluating rule", "Matched rule", "Abandoning rule" };
    #define PCC_DEBUG(auxil, event, rule, level, pos, buffer, length) \
        fprintf(stderr, "%*s%s %s @%zu [%.*s]\n", (int)((level) * 2), "", dbg_str[event], rule, pos, (int)(length), buffer)
}

More details can be found in README.md section on macros.

Now to the problem with a*1: It fails, because it parses a as a valid logical expression and then it doesn't know what to do with the rest. Unfortunately, this is not easy to fix within you grammar. At least I don't see any easy way to do it. You could enforce that logical and arithmetic expressions must end with ;, which would solve this particular case. But that would mean you than would have tu use semicolon in FunctionCall as well, which you probably don't want to.

You might also try this:

LogicalExpr        <- OrExpr &[;,)]
ArithmeticExpr     <- AdditiveExpr &[;,)]

This should ensure that the expression is always parsed in full. It might cause you some headache later though :-)

Also I think you are missing parentheses in Statement:

Statement          <- (Assignment / Expression) ';'

Unless it is your intention to allow assignments not followed by semicolon - which would break the suggestion above.

[joagre]

The PCC_DEBUG macro gave me a better understanding about PEG parser's way of working. I was on a failed cause. I'll move the type checking alltogether to Hindley Milner.

Thanks
/J