Theorem. LΓΆb Induction for Grammars

For every grammar 𝐴 and every term πœ‘:β–·π΄βŠ’π΄, where β–· is the later on grammars, there is a unique global parse π—…ΓΆπ–»πœ‘:⊀⊒𝐴 with

π—…ΓΆπ–»πœ‘=πœ‘βˆ˜π—‡π–Ύπ—‘π—(π—…ΓΆπ–»πœ‘).

Here 𝗇𝖾𝗑𝗍𝑑:βŠ€βŠ’β–·π΄ restricts a global parse 𝑑 to every proper suffix.

The proof is recursion on the length of the string. At 𝑣, the parses already built at the proper suffixes of 𝑣 form an element of (▷𝐴)𝑣, and πœ‘ turns it into a parse at 𝑣. Uniqueness is LΓΆb for families over the proper-suffix order. In the Agda, lob in Grammar/Later/Base.agda is this recursion, done by well-founded induction on length.

To prove an entailment 𝐡⊒𝐢 this way, apply LΓΆb to 𝐴=𝐡⇒𝐢. The hypothesis β–·(𝐡⇒𝐢) is the induction hypothesis at every proper suffix. It becomes usable once a non-nullable grammar has been consumed. If πœ€&𝐡⊒βŠ₯, then

(π΅βŠ—βŠ€)&β–·π΄βŠ’π΅βŠ—π΄

because a parse of π΅βŠ—βŠ€ over 𝑣 splits 𝑣=π‘₯++𝑒 with π‘₯ non-empty, so π‘’βŠπ‘£. This is β–·-app-NE in Grammar/Later/Properties.agda. Induction on a Kleene star is the standard use.

grammar-lob theorem entries/parsing/grammar-lob.hel