SQLite Forum

lemon: optimize empty reduction chains
Login

lemon: optimize empty reduction chains

(1) By terpstra on 2021-08-17 18:55:36 [source]

When one needs precise control over the precedence rules, you can end up with a bunch of rules like this:

    top ::= expr_inequal.

    expr_inequal ::= expr_ltgt.
    expr_inequal ::= expr_inequal EQ expr_ltgt.
    expr_inequal ::= expr_inequal NE expr_ltgt.

    expr_ltgt ::= expr_sum.
    expr_ltgt ::= expr_ltgt LT expr_sum.
    expr_ltgt ::= expr_ltgt GT expr_sum.

    expr_sum ::= expr_mul.
    expr_sum ::= expr_sum PLUS expr_mul.
    expr_sum ::= expr_sum MINUS expr_mul.

    expr_mul ::= expr_exp.
    expr_mul ::= expr_mul MUL expr_exp.

    expr_exp ::= expr_term.
    expr_exp ::= expr_term EXP expr_exp. // right-associative

    expr_term ::= ID.
    expr_term ::= OPEN expr_inequal CLOSE.

This works fine, but if you have an expression like "a != b", to get from ID(a) to an expr_inequal you have to run 6 no-op reductions before you can shift the NE token. In a language with more precedence levels, this cost starts to add up. As long as the reduction rules have a matching type and no code inside {}s, this multi-level reduction is a complete waste of time. The parser could have gone from a stack of [ID] with a token NE and reduced directly to expr_inequal.

For the parser I'm working on, here is a trace to demonstrate the potential savings:

Return. Stack=[top global export KW_DEF pattern P_EQUALS INDENT blockdefs KW_DEF pattern P_EQUALS KW_MATCH expression_term INDENT pattern KW_IF expression_op_inequal expression_binary_app ID]
Input 'P_EQUALS' in state 135
Reduce 118 [expression_nodot ::= ID], pop back to state 71.
... then shift 'expression_nodot', go to state 134
Reduce 220 [expression_term ::= expression_nodot] without external action, pop back to state 71.
... then shift 'expression_term', go to state 142
Reduce 143 [expression_binary_app ::= expression_binary_app expression_term], pop back to state 52.
... then shift 'expression_binary_app', go to state 71
Reduce 195 [expression_unary_quant ::= expression_binary_app] without external action, pop back to state 52.
... then shift 'expression_unary_quant', go to state 166
Reduce 194 [expression_binary_quant ::= expression_unary_quant] without external action, pop back to state 52.
... then shift 'expression_binary_quant', go to state 89
Reduce 197 [expression_unary_exp ::= expression_binary_quant] without external action, pop back to state 52.
... then shift 'expression_unary_exp', go to state 90
Reduce 196 [expression_binary_exp ::= expression_unary_exp] without external action, pop back to state 52.
... then shift 'expression_binary_exp', go to state 173
Reduce 199 [expression_unary_muldiv ::= expression_binary_exp] without external action, pop back to state 52.
... then shift 'expression_unary_muldiv', go to state 172
Reduce 198 [expression_binary_muldiv ::= expression_unary_muldiv] without external action, pop back to state 52.
... then shift 'expression_binary_muldiv', go to state 91
Reduce 201 [expression_unary_addsub ::= expression_binary_muldiv] without external action, pop back to state 52.
... then shift 'expression_unary_addsub', go to state 178
Reduce 200 [expression_binary_addsub ::= expression_unary_addsub] without external action, pop back to state 52.
... then shift 'expression_binary_addsub', go to state 92
Reduce 203 [expression_unary_compare ::= expression_binary_addsub] without external action, pop back to state 52.
... then shift 'expression_unary_compare', go to state 182
Reduce 202 [expression_binary_compare ::= expression_unary_compare] without external action, pop back to state 52.
... then shift 'expression_binary_compare', go to state 94
Reduce 205 [expression_unary_inequal ::= expression_binary_compare] without external action, pop back to state 52.
... then shift 'expression_unary_inequal', go to state 186
Reduce 95 [expression_unary_inequal ::= expression_op_inequal expression_unary_inequal], pop back to state 39.
... then shift 'expression_unary_inequal', go to state 185
Reduce 204 [expression_binary_inequal ::= expression_unary_inequal] without external action, pop back to state 39.
... then shift 'expression_binary_inequal', go to state 96
Reduce 207 [expression_unary_and ::= expression_binary_inequal] without external action, pop back to state 39.
... then shift 'expression_unary_and', go to state 189
Reduce 206 [expression_binary_and ::= expression_unary_and] without external action, pop back to state 39.
... then shift 'expression_binary_and', go to state 98
Reduce 209 [expression_unary_or ::= expression_binary_and] without external action, pop back to state 39.
... then shift 'expression_unary_or', go to state 193
Reduce 208 [expression_binary_or ::= expression_unary_or] without external action, pop back to state 39.
... then shift 'expression_binary_or', go to state 99
Reduce 211 [expression_unary_dollar ::= expression_binary_or] without external action, pop back to state 39.
... then shift 'expression_unary_dollar', go to state 101
Reduce 210 [expression_binary_dollar ::= expression_unary_dollar] without external action, pop back to state 39.
... then shift 'expression_binary_dollar', go to state 201
Reduce 213 [expression_unary_colon ::= expression_binary_dollar] without external action, pop back to state 39.
... then shift 'expression_unary_colon', go to state 104
Reduce 212 [expression_binary_colon ::= expression_unary_colon] without external action, pop back to state 39.
... then shift 'expression_binary_colon', go to state 221
Reduce 215 [expression_unary_lrarrow ::= expression_binary_colon] without external action, pop back to state 39.
... then shift 'expression_unary_lrarrow', go to state 220
Reduce 214 [expression_binary_lrarrow ::= expression_unary_lrarrow] without external action, pop back to state 39.
... then shift 'expression_binary_lrarrow', go to state 105
Reduce 217 [expression_unary_eqarrow ::= expression_binary_lrarrow] without external action, pop back to state 39.
... then shift 'expression_unary_eqarrow', go to state 231
Reduce 216 [expression_binary_eqarrow ::= expression_unary_eqarrow] without external action, pop back to state 39.
... then shift 'expression_binary_eqarrow', go to state 106
Reduce 219 [expression_unary_comma ::= expression_binary_eqarrow] without external action, pop back to state 39.
... then shift 'expression_unary_comma', go to state 108
Reduce 218 [expression_binary_comma ::= expression_unary_comma] without external action, pop back to state 39.
... then shift 'expression_binary_comma', go to state 246
Reduce 222 [expression ::= expression_binary_comma] without external action, pop back to state 39.
... then shift 'expression', go to state 328
Reduce 162 [guard ::= KW_IF expression], pop back to state 116.
... then shift 'guard', go to state 342
Shift 'P_EQUALS', go to state 34
Return. Stack=[top global export KW_DEF pattern P_EQUALS INDENT blockdefs KW_DEF pattern P_EQUALS KW_MATCH expression_term INDENT pattern guard P_EQUALS]