Stack overflows in deeply nested expressions

[rscarson]

My grammar is attached below

Deeply nested expressions such as (2*(2*(2*(2*(2*(2*(2*(2*(2*(2*(2*(2*(2*(2*(2*(2*(2*(2)))))))))))))))))) cause stack overflows very quickly
The expression above gets ~halfway down the tree and crashes at around 256kb of stack usage

I thought a {1,3} in int_literal may have been the culprit but breaking that down changed little

The grammar works fine, besides the nested expression crashes

Is there some issue in my grammar?

SCRIPT = {
    LINE* ~ EOI
}

LINE = {
    WHITESPACE* ~ EXPRESSION ~ "@" ~ identifier ~ (EOL | &EOI)
    | WHITESPACE* ~ EXPRESSION ~ (EOL | &EOI)
    | WHITESPACE* ~ (EOL)
}

EXPRESSION = {
    FUNCTION_ASSIGNMENT_EXPRESSION | INDEX_ASSIGNMENT_EXPRESSION | ASSIGNMENT_EXPRESSION
    | TOPLEVEL_EXPRESSION
}

//
// Tokenizer configuration
//

INLINE_COMMENT = @{"//" ~ (!EOL ~ ANY)* ~ EOL}
BLOCK_COMMENT = @{"/*" ~ (!"*/" ~ ANY)* ~ "*/"}
COMMENT = _{INLINE_COMMENT | BLOCK_COMMENT}

WHITESPACE = _{" " | "\t" | "\\\n" | COMMENT}
EOL = _{NEWLINE | ";"}

// 
// Assignment expressions
// 

FUNCTION_ASSIGNMENT_EXPRESSION = {
    identifier ~ "(" ~ ")" ~ "=" ~ TOPLEVEL_EXPRESSION |
    identifier ~ "(" ~ identifier ~ ("," ~ identifier)* ~ ")" ~ "=" ~ TOPLEVEL_EXPRESSION
}

ASSIGNMENT_EXPRESSION = {identifier ~ "=" ~ TOPLEVEL_EXPRESSION}

INDEX_ASSIGNMENT_EXPRESSION = {
    identifier ~ ("[" ~ TOPLEVEL_EXPRESSION ~ "]")+ ~ "=" ~ TOPLEVEL_EXPRESSION
}

//
// Top of expression tree
//

TOPLEVEL_EXPRESSION = { ARRAY_EXPRESSION | ATOMIC_VALUE }

//
// Arrays and objects
//

ARRAY_EXPRESSION = {
    "[" ~ TOPLEVEL_EXPRESSION ~ ("," ~ TOPLEVEL_EXPRESSION)* ~ "]"
    | OBJECT_EXPRESSION
}

OBJECT_EXPRESSION_PAIR = _{TOPLEVEL_EXPRESSION ~ ":" ~ TOPLEVEL_EXPRESSION}
OBJECT_EXPRESSION = {
    "{" ~ OBJECT_EXPRESSION_PAIR ~ ("," ~ OBJECT_EXPRESSION_PAIR)* ~ "}"
    | TERNARY_EXPRESSION
}

//
// Flow control expressions
//

TERNARY_EXPRESSION = {
    BOOLEAN_OR_EXPRESSION ~ ("?" ~ BOOLEAN_OR_EXPRESSION ~ ":" ~ BOOLEAN_OR_EXPRESSION)*
}

//
// Boolean infix expressions
//

BOOLEAN_OR_EXPRESSION = {
    BOOLEAN_AND_EXPRESSION ~ ("||" ~ BOOLEAN_AND_EXPRESSION)*
}

BOOLEAN_AND_EXPRESSION = {
    BOOLEAN_CMP_EXPRESSION ~ ("&&" ~ BOOLEAN_CMP_EXPRESSION)*
}

BOOLEAN_CMP_OPERATOR = {"<=" | ">=" | "==" | "!=" | "<" | ">"}
BOOLEAN_CMP_EXPRESSION = {
    BITWISE_OR_EXPRESSION ~ (BOOLEAN_CMP_OPERATOR ~ BITWISE_OR_EXPRESSION)*
}

//
// Bitwise infix expressions
//

BITWISE_OR_EXPRESSION = {
    BITWISE_XOR_EXPRESSION ~ ("|" ~ BITWISE_XOR_EXPRESSION)*
}

BITWISE_XOR_EXPRESSION = {
    BITWISE_AND_EXPRESSION ~ ("^" ~ BITWISE_AND_EXPRESSION)*
}

BITWISE_AND_EXPRESSION = {
    BITWISE_SHIFT_EXPRESSION ~ ("&" ~ BITWISE_SHIFT_EXPRESSION)*
}

BITWISE_SHIFT_OPERATOR = {"<<" | ">>"}
BITWISE_SHIFT_EXPRESSION = {
    ARITHMETIC_AS_EXPRESSION ~ (BITWISE_SHIFT_OPERATOR ~ ARITHMETIC_AS_EXPRESSION)*
}

//
// Arithmetic infix expressions
//

ARITHMETIC_AS_OPERATOR = {"+" | "-"}
ARITHMETIC_AS_EXPRESSION = {
    ARITHMETIC_MD_EXPRESSION ~ (ARITHMETIC_AS_OPERATOR ~ ARITHMETIC_MD_EXPRESSION)*
}

ARITHMETIC_MD_OPERATOR = {"*" | "/" | "%"}
ARITHMETIC_MD_EXPRESSION = {
    ARITHMETIC_IMPLICIT_MUL_EXPRESSION ~ (ARITHMETIC_MD_OPERATOR ~ ARITHMETIC_IMPLICIT_MUL_EXPRESSION)*
}

ARITHMETIC_IMPLICIT_MUL_EXPRESSION = {
    TERM ~ (TERM)*
    | ARITHMETIC_EXPONENTIATION_EXPRESSION ~ (!"-" ~ ARITHMETIC_EXPONENTIATION_EXPRESSION)*
}

ARITHMETIC_EXPONENTIATION_EXPRESSION = {
    FUNCTION_CALL_EXPRESSION ~ ("**" ~ FUNCTION_CALL_EXPRESSION)*
}

//
// Function call stuff
// 

FUNCTION_CALL_EXPRESSION = {
    identifier ~ "(" ~ ")" |
    identifier ~ "(" ~ TOPLEVEL_EXPRESSION ~ ("," ~ TOPLEVEL_EXPRESSION)* ~ ")"
    | BOOLEAN_NOT_EXPRESSION
}

//
// Prefix unary expressions
//

BOOLEAN_NOT_OPERATOR = {"!"}
BOOLEAN_NOT_EXPRESSION = {
    BOOLEAN_NOT_OPERATOR* ~ BITWISE_NOT_EXPRESSION
}

BITWISE_NOT_OPERATOR = {"~"}
BITWISE_NOT_EXPRESSION = {
    BITWISE_NOT_OPERATOR* ~ ARITHMETIC_NEG_EXPRESSION
}

ARITHMETIC_NEG_OPERATOR = {"-"}
ARITHMETIC_NEG_EXPRESSION = {
    ARITHMETIC_NEG_OPERATOR* ~ INDEXING_EXPRESSION
}

//
// Postfix indexing expression - for arrays and objects
//

INDEXING_EXPRESSION = {
    TERM ~ ("[" ~ TOPLEVEL_EXPRESSION ~ "]")*
}

//
// Value Literals
// And value-literal adjascent gubbins
// 

TERM = {
    | "(" ~ ATOMIC_VALUE ~ ")"
    | "(" ~ TOPLEVEL_EXPRESSION ~ ")"
    | ATOMIC_VALUE}

ATOMIC_VALUE = {
    currency_literal
    | sci_literal | float_literal
    | hex_literal | bin_literal | oct_literal | int_literal
    | bool_literal | string_literal
    | identifier
    | errors
}

// Fixed-point currency values
currency_symbol = @{"$" | "€" | "£" | "¥"}
currency_literal = {((float_literal | int_literal) ~ currency_symbol) | (currency_symbol ~ (float_literal | int_literal))}

// Floating-point literals
sci_literal = @{(float_literal | int_literal) ~ ^"e" ~ ("+"|"-")? ~ ('0'..'9')+}
float_literal = @{int_literal? ~ "." ~ ('0'..'9')+}

// Integer literals
int_literal = @{('0'..'9'){4,} | ((('0'..'9') | ('0'..'9'){2} | ('0'..'9'){3}) ~ ("," ~ ('0'..'9'){3})*)}
hex_literal = @{(^"0x") ~ ('a'..'f' | 'A'..'F' | '0'..'9')+}
bin_literal = @{(^"0b") ~ ('0'..'1')+}
oct_literal = @{(^"0o" | "0") ~ ('0'..'7')+}    

// Other literals
bool_literal = @{^"true" | ^"false"}
string_literal = @{("\"" ~ ("\\"~ANY | (!"\"" ~ ANY))* ~ "\"") | ("\'" ~ ("\\"~ANY | (!"\'" ~ ANY))* ~ "\'")}

identifier = @{('a'..'z' | 'A'..'Z' | "_") ~ ('a'..'z' | 'A'..'Z' | '0'..'9' | "_")*}

//
// Error Definitions
//

errors = {
    ERROR_UNTERMINATED_LITERAL | ERROR_UNTERMINATED_LINEBREAK | ERROR_UNTERMINATED_COMMENT
    | ERROR_UNTERMINATED_ARRAY | ERROR_UNTERMINATED_OBJECT | ERROR_UNTERMINATED_PAREN
    | ERROR_UNEXPECTED_DECORATOR
}

ERROR_UNTERMINATED_LITERAL = @{("\"" ~ ("\\"~ANY | (!"\"" ~ ANY))*) | ("\'" ~ ("\\"~ANY | (!"\'" ~ ANY))*)}
ERROR_UNTERMINATED_LINEBREAK = @{"\\" ~ EOI}
ERROR_UNTERMINATED_COMMENT = @{"/*" ~ ANY*}

ERROR_UNTERMINATED_ARRAY = @{"[" ~ ANY*}
ERROR_UNTERMINATED_OBJECT = @{"{" ~ ANY*}
ERROR_UNTERMINATED_PAREN = @{"(" ~ ANY*}

ERROR_UNEXPECTED_DECORATOR = @{"@" ~ identifier ~ WHITESPACE* ~ (!WHITESPACE ~ !EOL ~ ANY)+ | SOI ~ "@" ~ ANY*}

[rscarson]

Seems the queue in the Pairs object is over 700 elements long at the time of crash

Also (2*(2*2)) is enough to trigger the overflow

[tomtau]

You can try loading the grammar in a debugger and put breakpoints to all rules to see which rules are being applied/expanded: https://github.com/pest-parser/awesome-pest/blob/main/debugger.md

[rscarson]

I updated my grammar to dramatically simplify the output tree, and now Pest simply freezes indefinitely on any nested expression, such as 2*(2*2)

Running the updated grammar with breakpoints in the debugger reveals that it seems to be parsing each character as TERM, over and over...?

It seems to be looping around the whole tree from TOPLEVEL_EXPRESSION to ATOMIC_VALUE for some reason

Any ideas?

Grammar:

SCRIPT = {
    LINE* ~ EOI
}

LINE = {
    WHITESPACE* ~ EXPRESSION ~ "@" ~ identifier ~ (EOL | &EOI)
    | WHITESPACE* ~ EXPRESSION ~ (EOL | &EOI)
    | WHITESPACE* ~ (EOL | INLINE_COMMENT)
}

EXPRESSION = _{
    FUNCTION_ASSIGNMENT_EXPRESSION | INDEX_ASSIGNMENT_EXPRESSION | ASSIGNMENT_EXPRESSION
    | TOPLEVEL_EXPRESSION
}

//
// Tokenizer configuration
//

INLINE_COMMENT = @{"//" ~ (!EOL ~ ANY)* ~ (&EOL | &EOI)}
BLOCK_COMMENT = @{"/*" ~ (!"*/" ~ ANY)* ~ "*/"}
COMMENT = _{INLINE_COMMENT | BLOCK_COMMENT}

WHITESPACE = _{" " | "\t" | "\\\n" | COMMENT}
EOL = _{NEWLINE | ";"}

// 
// Assignment expressions
// 

FUNCTION_ASSIGNMENT_EXPRESSION = {
    identifier ~ "(" ~ ")" ~ "=" ~ TOPLEVEL_EXPRESSION |
    identifier ~ "(" ~ identifier ~ ("," ~ identifier)* ~ ")" ~ "=" ~ TOPLEVEL_EXPRESSION
}

ASSIGNMENT_EXPRESSION = {identifier ~ "=" ~ TOPLEVEL_EXPRESSION}

INDEX_ASSIGNMENT_EXPRESSION = {
    identifier ~ ("[" ~ TOPLEVEL_EXPRESSION ~ "]")+ ~ "=" ~ TOPLEVEL_EXPRESSION
}

//
// Top of expression tree
//

TOPLEVEL_EXPRESSION = _{ TRY_ARRAY_EXPRESSION }

//
// Arrays and objects
//

TRY_ARRAY_EXPRESSION = _{ARRAY_EXPRESSION | TRY_OBJECT_EXPRESSION}
ARRAY_EXPRESSION = {
    "[" ~ TOPLEVEL_EXPRESSION ~ ("," ~ TOPLEVEL_EXPRESSION)* ~ "]"
}

TRY_OBJECT_EXPRESSION = _{OBJECT_EXPRESSION | TRY_TERNARY_EXPRESSION}
OBJECT_EXPRESSION_PAIR = _{TOPLEVEL_EXPRESSION ~ ":" ~ TOPLEVEL_EXPRESSION}
OBJECT_EXPRESSION = {
    "{" ~ OBJECT_EXPRESSION_PAIR ~ ("," ~ OBJECT_EXPRESSION_PAIR)* ~ "}"
}

//
// Flow control expressions
//

TRY_TERNARY_EXPRESSION = _{TERNARY_EXPRESSION | TRY_BOOLEAN_OR_EXPRESSION}
TERNARY_EXPRESSION = {
    TRY_BOOLEAN_OR_EXPRESSION ~ ("?" ~ TRY_BOOLEAN_OR_EXPRESSION ~ ":" ~ TRY_BOOLEAN_OR_EXPRESSION)+
}

//
// Boolean infix expressions
//

TRY_BOOLEAN_OR_EXPRESSION = _{BOOLEAN_OR_EXPRESSION | TRY_BOOLEAN_AND_EXPRESSION}
BOOLEAN_OR_EXPRESSION = {
    TRY_BOOLEAN_AND_EXPRESSION ~ ("||" ~ TRY_BOOLEAN_AND_EXPRESSION)+
}

TRY_BOOLEAN_AND_EXPRESSION = _{BOOLEAN_AND_EXPRESSION | TRY_BOOLEAN_CMP_EXPRESSION}
BOOLEAN_AND_EXPRESSION = {
    TRY_BOOLEAN_CMP_EXPRESSION ~ ("&&" ~ TRY_BOOLEAN_CMP_EXPRESSION)+
}

TRY_BOOLEAN_CMP_EXPRESSION = _{BOOLEAN_CMP_EXPRESSION | TRY_BITWISE_OR_EXPRESSION}
BOOLEAN_CMP_OPERATOR = {"<=" | ">=" | "==" | "!=" | "<" | ">"}
BOOLEAN_CMP_EXPRESSION = {
    TRY_BITWISE_OR_EXPRESSION ~ (BOOLEAN_CMP_OPERATOR ~ TRY_BITWISE_OR_EXPRESSION)+
}

//
// Bitwise infix expressions
//

TRY_BITWISE_OR_EXPRESSION = _{BITWISE_OR_EXPRESSION | TRY_BITWISE_XOR_EXPRESSION}
BITWISE_OR_EXPRESSION = {
    TRY_BITWISE_XOR_EXPRESSION ~ ("|" ~ TRY_BITWISE_XOR_EXPRESSION)+
}

TRY_BITWISE_XOR_EXPRESSION = _{BITWISE_XOR_EXPRESSION | TRY_BITWISE_AND_EXPRESSION}
BITWISE_XOR_EXPRESSION = {
    TRY_BITWISE_AND_EXPRESSION ~ ("^" ~ TRY_BITWISE_AND_EXPRESSION)+
}

TRY_BITWISE_AND_EXPRESSION = _{BITWISE_AND_EXPRESSION | TRY_BITWISE_SHIFT_EXPRESSION}
BITWISE_AND_EXPRESSION = {
    TRY_BITWISE_SHIFT_EXPRESSION ~ ("&" ~ TRY_BITWISE_SHIFT_EXPRESSION)+
}

TRY_BITWISE_SHIFT_EXPRESSION = _{BITWISE_SHIFT_EXPRESSION | TRY_ARITHMETIC_AS_EXPRESSION}
BITWISE_SHIFT_OPERATOR = {"<<" | ">>"}
BITWISE_SHIFT_EXPRESSION = {
    ARITHMETIC_AS_EXPRESSION ~ (BITWISE_SHIFT_OPERATOR ~ ARITHMETIC_AS_EXPRESSION)+
}

//
// Arithmetic infix expressions
//

TRY_ARITHMETIC_AS_EXPRESSION = _{ARITHMETIC_AS_EXPRESSION | TRY_ARITHMETIC_MD_EXPRESSION}
ARITHMETIC_AS_OPERATOR = {"+" | "-"}
ARITHMETIC_AS_EXPRESSION = {
    TRY_ARITHMETIC_MD_EXPRESSION ~ (ARITHMETIC_AS_OPERATOR ~ TRY_ARITHMETIC_MD_EXPRESSION)+
}

TRY_ARITHMETIC_MD_EXPRESSION = _{ARITHMETIC_MD_EXPRESSION | TRY_ARITHMETIC_IMPLICIT_MUL_EXPRESSION}
ARITHMETIC_MD_OPERATOR = {"*" | "/" | "%"}
ARITHMETIC_MD_EXPRESSION = {
    TRY_ARITHMETIC_IMPLICIT_MUL_EXPRESSION ~ (ARITHMETIC_MD_OPERATOR ~ TRY_ARITHMETIC_IMPLICIT_MUL_EXPRESSION)+
}

TRY_ARITHMETIC_IMPLICIT_MUL_EXPRESSION = _{ARITHMETIC_IMPLICIT_MUL_EXPRESSION | TRY_ARITHMETIC_EXPONENTIATION_EXPRESSION}
ARITHMETIC_IMPLICIT_MUL_EXPRESSION = {
    TRY_ARITHMETIC_EXPONENTIATION_EXPRESSION ~ (!"-" ~ TRY_ARITHMETIC_EXPONENTIATION_EXPRESSION)+
}

TRY_ARITHMETIC_EXPONENTIATION_EXPRESSION = _{ARITHMETIC_EXPONENTIATION_EXPRESSION | TRY_FUNCTION_CALL_EXPRESSION}
ARITHMETIC_EXPONENTIATION_EXPRESSION = {
    TRY_FUNCTION_CALL_EXPRESSION ~ ("**" ~ TRY_FUNCTION_CALL_EXPRESSION)+
}

//
// Function call stuff
// 

TRY_FUNCTION_CALL_EXPRESSION = _{FUNCTION_CALL_EXPRESSION | TRY_BOOLEAN_NOT_EXPRESSION}
FUNCTION_CALL_EXPRESSION = {
    identifier ~ "(" ~ ")" |
    identifier ~ "(" ~ TOPLEVEL_EXPRESSION ~ ("," ~ TOPLEVEL_EXPRESSION)* ~ ")"
}

//
// Prefix unary expressions
//

TRY_BOOLEAN_NOT_EXPRESSION = _{BOOLEAN_NOT_EXPRESSION | TRY_BITWISE_NOT_EXPRESSION}
BOOLEAN_NOT_OPERATOR = {"!"}
BOOLEAN_NOT_EXPRESSION = {
    BOOLEAN_NOT_OPERATOR+ ~ TRY_BITWISE_NOT_EXPRESSION
}

TRY_BITWISE_NOT_EXPRESSION = _{BITWISE_NOT_EXPRESSION | TRY_ARITHMETIC_NEG_EXPRESSION}
BITWISE_NOT_OPERATOR = {"~"}
BITWISE_NOT_EXPRESSION = {
    BITWISE_NOT_OPERATOR+ ~ TRY_ARITHMETIC_NEG_EXPRESSION
}

TRY_ARITHMETIC_NEG_EXPRESSION = _{ARITHMETIC_NEG_EXPRESSION | TRY_INDEXING_EXPRESSION}
ARITHMETIC_NEG_OPERATOR = {"-"}
ARITHMETIC_NEG_EXPRESSION = {
    ARITHMETIC_NEG_OPERATOR+ ~ TRY_INDEXING_EXPRESSION
}

//
// Postfix indexing expression - for arrays and objects
//

TRY_INDEXING_EXPRESSION = _{INDEXING_EXPRESSION | TERM}
INDEXING_EXPRESSION = {
    TERM ~ ("[" ~ TOPLEVEL_EXPRESSION ~ "]")+
}

//
// Value Literals
// And value-literal adjascent gubbins
// 

TERM = _{
    | "(" ~ TOPLEVEL_EXPRESSION ~ ")"
    | ATOMIC_VALUE}

ATOMIC_VALUE = _{
    currency_literal
    | sci_literal | float_literal
    | hex_literal | bin_literal | oct_literal | int_literal
    | bool_literal | string_literal
    | identifier
    | errors
}

// Fixed-point currency values
currency_symbol = @{"$" | "€" | "£" | "¥"}
currency_literal = {((float_literal | int_literal) ~ currency_symbol) | (currency_symbol ~ (float_literal | int_literal))}

// Floating-point literals
sci_literal = @{(float_literal | int_literal) ~ ^"e" ~ ("+"|"-")? ~ ('0'..'9')+}
float_literal = @{int_literal? ~ "." ~ ('0'..'9')+}

// Integer literals
int_comma = _{('0'..'9'){1,3} ~ ("," ~ ('0'..'9'){3})+}
int_literal = @{int_comma | ('0'..'9')+}
hex_literal = @{(^"0x") ~ ('a'..'f' | 'A'..'F' | '0'..'9')+}
bin_literal = @{(^"0b") ~ ('0'..'1')+}
oct_literal = @{(^"0o" | "0") ~ ('0'..'7')+}    

// Other literals
bool_literal = @{^"true" | ^"false"}
string_literal = @{("\"" ~ ("\\"~ANY | (!"\"" ~ ANY))* ~ "\"") | ("\'" ~ ("\\"~ANY | (!"\'" ~ ANY))* ~ "\'")}

identifier = @{('a'..'z' | 'A'..'Z' | "_") ~ ('a'..'z' | 'A'..'Z' | '0'..'9' | "_")*}

//
// Error Definitions
//

errors = _{
    ERROR_UNTERMINATED_LITERAL | ERROR_UNTERMINATED_LINEBREAK | ERROR_UNTERMINATED_COMMENT
    | ERROR_UNTERMINATED_ARRAY | ERROR_UNTERMINATED_OBJECT | ERROR_UNTERMINATED_PAREN
    | ERROR_UNEXPECTED_DECORATOR
}

ERROR_UNTERMINATED_LITERAL = @{("\"" ~ ("\\"~ANY | (!"\"" ~ ANY))*) | ("\'" ~ ("\\"~ANY | (!"\'" ~ ANY))*)}
ERROR_UNTERMINATED_LINEBREAK = @{"\\" ~ EOI}
ERROR_UNTERMINATED_COMMENT = @{"/*" ~ ANY*}

ERROR_UNTERMINATED_ARRAY = @{"[" ~ ANY*}
ERROR_UNTERMINATED_OBJECT = @{"{" ~ ANY*}
ERROR_UNTERMINATED_PAREN = @{"(" ~ ANY*}

ERROR_UNEXPECTED_DECORATOR = @{"@" ~ identifier ~ WHITESPACE* ~ (!WHITESPACE ~ !EOL ~ ANY)+ | SOI ~ "@" ~ ANY*}

[rscarson]

I do agree with your analysis, but I even let the debugger go overnight last night
Even the try-it box in the website freezes on my grammar with 2*(2*2)

The web version even freezes at 2*(2, which is not even valid input

[Tartasprint]

I did some calculations, and found out that in order to parse the following expression with the SCRIPT rule, the number of character comparisons (eg is the next character )?) is

• 718915 (≈7e5) for the empty word
• 1489093 (≈1e6) for 2
• 1674955 (≈1e6) for 2*2
• 5850972432 (≈6e9) for (2*2)
• 2926439440 (≈3e9) for 2*(2*2)

I don't know how big these numbers are for other grammars, but they feel huge.

It took 1h56m for (2*2) to parse and 0h50m to parse 2*(2*2). To do this measurement I needed to change the debugger timeout, and I set it to 10 hours. The ratio in time is similar to the ratio in number of comparison, so I think my approximation of the amount of work by number of comparisons is valid.

You can find my calculations on this sheet.

By doing them I figured that this grammar is very inefficient: rules of the form TRY_, almost systematically double the workload. As an example, on input 2, the rule TRY_INDEXING_EXPRESSION tries at first to read a TERM, then fails to read a [, then reads TERM again.

The LINE rule has a similar problem.

Something funny is that reading 2*(2*2) is twice faster then reading (2*2). That's because the first one doesn't double at ARITHMETIC_MD_EXPRESSION.

I guess that this grammar could be refactored/optimized. Some changes are possible without changing the parse tree, some may not. I could give a look later, if you want.

[rscarson]

I'd appreciate that
The try_ rules were actually my attempt to fix the problem by reducing the depth of the final tree

Prior to that refactor, attempting to resolve those expressions would just stack overflow

[Tartasprint]

Yes, I realise that in your original grammar there shouldn't be as much "doubling" as in the revised one.
That just explains the long time but not the stack overflows.

[rscarson]

My assumption has been that in the original version, there were enough steps that the tree's depth overflowed in the code I wrote to consume it

[rscarson]

Also; I had to manually set the breakpoints on rules, as setting the ba break on all rules option freezes the debugger

[tomtau]

That is strange, I'll try to reproduce it (maybe this weekend)

[tomtau]

I didn't manage to reproduce debugger freezing after ba.

With the original grammar:

> g grammar1.pest
> ba
> l
Breakpoints: ARITHMETIC_AS_EXPRESSION, ARITHMETIC_AS_OPERATOR, ARITHMETIC_EXPONENTIATION_EXPRESSION, ARITHMETIC_IMPLICIT_MUL_EXPRESSION, ARITHMETIC_MD_EXPRESSION, ARITHMETIC_MD_OPERATOR, ARITHMETIC_NEG_EXPRESSION, ARITHMETIC_NEG_OPERATOR, ARRAY_EXPRESSION, ASSIGNMENT_EXPRESSION, ATOMIC_VALUE, BITWISE_AND_EXPRESSION, BITWISE_NOT_EXPRESSION, BITWISE_NOT_OPERATOR, BITWISE_OR_EXPRESSION, BITWISE_SHIFT_EXPRESSION, BITWISE_SHIFT_OPERATOR, BITWISE_XOR_EXPRESSION, BLOCK_COMMENT, BOOLEAN_AND_EXPRESSION, BOOLEAN_CMP_EXPRESSION, BOOLEAN_CMP_OPERATOR, BOOLEAN_NOT_EXPRESSION, BOOLEAN_NOT_OPERATOR, BOOLEAN_OR_EXPRESSION, COMMENT, EOL, ERROR_UNEXPECTED_DECORATOR, ERROR_UNTERMINATED_ARRAY, ERROR_UNTERMINATED_COMMENT, ERROR_UNTERMINATED_LINEBREAK, ERROR_UNTERMINATED_LITERAL, ERROR_UNTERMINATED_OBJECT, ERROR_UNTERMINATED_PAREN, EXPRESSION, FUNCTION_ASSIGNMENT_EXPRESSION, FUNCTION_CALL_EXPRESSION, INDEXING_EXPRESSION, INDEX_ASSIGNMENT_EXPRESSION, INLINE_COMMENT, LINE, OBJECT_EXPRESSION, OBJECT_EXPRESSION_PAIR, SCRIPT, TERM, TERNARY_EXPRESSION, TOPLEVEL_EXPRESSION, WHITESPACE, bin_literal, bool_literal, currency_literal, currency_symbol, errors, float_literal, hex_literal, identifier, int_literal, oct_literal, sci_literal, string_literal

With the updated grammar:

> g grammar2.pest
> ba
> l
Breakpoints: ARITHMETIC_AS_EXPRESSION, ARITHMETIC_AS_OPERATOR, ARITHMETIC_EXPONENTIATION_EXPRESSION, ARITHMETIC_IMPLICIT_MUL_EXPRESSION, ARITHMETIC_MD_EXPRESSION, ARITHMETIC_MD_OPERATOR, ARITHMETIC_NEG_EXPRESSION, ARITHMETIC_NEG_OPERATOR, ARRAY_EXPRESSION, ASSIGNMENT_EXPRESSION, ATOMIC_VALUE, BITWISE_AND_EXPRESSION, BITWISE_NOT_EXPRESSION, BITWISE_NOT_OPERATOR, BITWISE_OR_EXPRESSION, BITWISE_SHIFT_EXPRESSION, BITWISE_SHIFT_OPERATOR, BITWISE_XOR_EXPRESSION, BLOCK_COMMENT, BOOLEAN_AND_EXPRESSION, BOOLEAN_CMP_EXPRESSION, BOOLEAN_CMP_OPERATOR, BOOLEAN_NOT_EXPRESSION, BOOLEAN_NOT_OPERATOR, BOOLEAN_OR_EXPRESSION, COMMENT, EOL, ERROR_UNEXPECTED_DECORATOR, ERROR_UNTERMINATED_ARRAY, ERROR_UNTERMINATED_COMMENT, ERROR_UNTERMINATED_LINEBREAK, ERROR_UNTERMINATED_LITERAL, ERROR_UNTERMINATED_OBJECT, ERROR_UNTERMINATED_PAREN, EXPRESSION, FUNCTION_ASSIGNMENT_EXPRESSION, FUNCTION_CALL_EXPRESSION, INDEXING_EXPRESSION, INDEX_ASSIGNMENT_EXPRESSION, INLINE_COMMENT, LINE, OBJECT_EXPRESSION, OBJECT_EXPRESSION_PAIR, SCRIPT, TERM, TERNARY_EXPRESSION, TOPLEVEL_EXPRESSION, TRY_ARITHMETIC_AS_EXPRESSION, TRY_ARITHMETIC_EXPONENTIATION_EXPRESSION, TRY_ARITHMETIC_IMPLICIT_MUL_EXPRESSION, TRY_ARITHMETIC_MD_EXPRESSION, TRY_ARITHMETIC_NEG_EXPRESSION, TRY_ARRAY_EXPRESSION, TRY_BITWISE_AND_EXPRESSION, TRY_BITWISE_NOT_EXPRESSION, TRY_BITWISE_OR_EXPRESSION, TRY_BITWISE_SHIFT_EXPRESSION, TRY_BITWISE_XOR_EXPRESSION, TRY_BOOLEAN_AND_EXPRESSION, TRY_BOOLEAN_CMP_EXPRESSION, TRY_BOOLEAN_NOT_EXPRESSION, TRY_BOOLEAN_OR_EXPRESSION, TRY_FUNCTION_CALL_EXPRESSION, TRY_INDEXING_EXPRESSION, TRY_OBJECT_EXPRESSION, TRY_TERNARY_EXPRESSION, WHITESPACE, bin_literal, bool_literal, currency_literal, currency_symbol, errors, float_literal, hex_literal, identifier, int_comma, int_literal, oct_literal, sci_literal, string_literal

[rscarson]

Very odd
The 2nd one still freezes here

Ah well, I have rewritten the grammar again, and the new version no longer has any issue with the debugger

Thanks for trying to reproduce the issue!

[rscarson]

I got it working!! Rewrote the grammar again, removing the TRY_* rules, and instead solved the deep-nested trees issue like this

        // Bypass single-child nodes
        // They should not be parsed into a node directly
        // Except for the script and line nodes, which are allowed to be single-child
        while target.clone().into_inner().count() == 1
            && target.as_rule() != Rule::SCRIPT
            && target.as_rule() != Rule::LINE
        {
            target = target.into_inner().next().unwrap();
        }

While flattens out the long precedence chains, allowing me to parse 2*(2*(2*(2*(2*(2*(2*(2*(2*(2*(2*(2*(22*(2*(2*(2*(2)))))))))))))))) successfully