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.