Why does Python's PLY stop parsing at an $end token?

Question

I am running the PLY library for Python on my grammar. It seems to compile alright, and the library doesn't alert me to any shift/reduce or reduce/reduce errors. However, running on a very simple example throws an error.

Digging into the parser.out file reveals that the error occurs at the very end of the program:

State  : 113
Stack  : DEFN ID ARROW type invariants statement . $end
ERROR: Error  : DEFN ID ARROW type invariants statement . $end
Syntax error at: None

where state 113 is:

state 113

    (16) fn_def -> DEFN ID ARROW type invariants statement .
    (24) tilde_loop -> statement . TILDE constant TILDE

    SEMICOLON       reduce using rule 16 (fn_def -> DEFN ID ARROW type inva\
riants statement .)
    TILDE           shift and go to state 62

As far as I can tell, the parser should be reducing to a fn_def.

Why does the reduce not happen when reaching an $end token?

(I can paste my grammar if it helps, although it might be a bit long.)

Grammar

Rule 0     S' -> program
Rule 1     program -> statement_list
Rule 2     statement -> definition SEMICOLON
Rule 3     statement -> expression SEMICOLON
Rule 4     statement -> control_statement
Rule 5     statement -> compound_statement
Rule 6     statement -> comment
Rule 7     statement -> empty SEMICOLON
Rule 8     statement_list -> statement_list statement
Rule 9     statement_list -> statement
Rule 10    control_statement -> loop
Rule 11    control_statement -> if_statement
Rule 12    compound_statement -> CURLY_OPEN statement_list CURLY_CLOSE
Rule 13    compound_statement -> CURLY_OPEN CURLY_CLOSE
Rule 14    definition -> fn_def
Rule 15    definition -> var_def
Rule 16    fn_def -> DEFN ID ARROW type invariants statement
Rule 17    var_def -> type assignment
Rule 18    assignment -> ID ASSIGN expression
Rule 19    loop -> for_loop
Rule 20    loop -> foreach_loop
Rule 21    loop -> tilde_loop
Rule 22    for_loop -> FOR statement statement statement compound_statement
Rule 23    foreach_loop -> FOREACH ID IN expression compound_statement
Rule 24    tilde_loop -> statement TILDE constant TILDE
Rule 25    if_statement -> IF condition compound_statement
Rule 26    if_statement -> IF condition compound_statement elseif_list
Rule 27    if_statement -> IF condition compound_statement elseif_list else
Rule 28    if_statement -> ternary
Rule 29    elseif_list -> ELSEIF condition compound_statement
Rule 30    elseif_list -> ELSEIF condition compound_statement elseif_list
Rule 31    else -> ELSE compound_statement
Rule 32    ternary -> condition QUESTION_MARK expression COLON expression
Rule 33    invariants -> invariants invariant
Rule 34    invariants -> invariant
Rule 35    invariants -> NONE
Rule 36    invariant -> type ID COLON invariant_tests
Rule 37    invariant_tests -> invariant_tests COMMA test
Rule 38    invariant_tests -> test
Rule 39    test -> ID operator constant
Rule 40    test -> STAR
Rule 41    expression -> declarator
Rule 42    expression -> assignment
Rule 43    expression -> container
Rule 44    expression -> test
Rule 45    expression -> constant
Rule 46    type -> INT_T
Rule 47    type -> DBL_T
Rule 48    type -> STR_T
Rule 49    type -> list_type
Rule 50    operator -> GT_OP
Rule 51    operator -> LT_OP
Rule 52    operator -> GTE_OP
Rule 53    operator -> LTE_OP
Rule 54    operator -> EQ_OP
Rule 55    operator -> NEQ_OP
Rule 56    constant -> INT
Rule 57    constant -> DBL
Rule 58    constant -> STR
Rule 59    declarator -> ID L_PAREN fn_args R_PAREN
Rule 60    declarator -> ID
Rule 61    fn_args -> fn_args COMMA expression
Rule 62    fn_args -> expression
Rule 63    container -> list
Rule 64    list -> L_BRACE container_items R_BRACE
Rule 65    list_type -> L_BRACE type R_BRACE
Rule 66    container_items -> container_items COMMA container_item
Rule 67    container_items -> container_item
Rule 68    container_item -> expression
Rule 69    container_item -> empty
Rule 70    bool -> TRUE
Rule 71    bool -> FALSE
Rule 72    condition -> bool
Rule 73    comment -> single_comment
Rule 74    single_comment -> COMMENT_LINE
Rule 75    empty -> <empty>

Answer 1

Seems like it needs a semicolon, and it has end-of-input. It is hard to say more without seeing the grammar.

The relevant part of your grammar:

 (2) statement -> definition SEMICOLON
(14) definition -> fn_def

Those are the only productions in which fn_def and definition occur on a right-hand side.

Clearly definition can only be reduced to statement when the lookahead token is SEMICOLON. Since fn_def can only appear in a valid program in a place where it can be immediately reduced to definition (the only production is a unit production), fn_def must be followed by a SEMICOLON. So your parser was correct and your sample input was ungrammatical.

fn_def has only one production:

(16) fn_def -> DEFN ID ARROW type invariants statement

in which it is evident that the last item in fn_def is a statement. Some statements (definition and expression) must be terminated by a ;; if the fn_def's statement is one of those (presumably an expression, since it doesn't seem like a single definition makes for an interesting function body) then the fn_def will have to be written with two semicolons. I doubt whether that's what you wanted.

definition ends with either a statement (if it's a fn_def) or with an expression (if it's a var_def). You've attempted to define statement so that it's self-delimiting (i.e. it ends with a semicolon if it doesn't end with the } which terminates a compound_statement. So fn_def already either ends with a semicolon or a closing brace, and shouldn't require another semicolon. var_def, on the other hand, ends with an expression, and therefore does. So one solution would be to push the closing semicolon into the var_def.

Editorial comment, unrelated to the specific question being asked:

In fact, there's no obvious reason why you need to restrict loop or conditional bodies to compound statements, other than your own aesthetics; if you allow a lambda body to be a non-compound statement, there's no obvious reason why you would restrict a for loop. The grammar can be made to work either way.