FPRD LabShare an approach

← Claims

Definition and semantic contract

FPRD-D34

Finite ordinary complete-match PEG semantics

Exact statement

A finite ordinary complete-match parsing expression grammar has a finite input alphabet and a finite nonterminal carrier transported to Fin n; expressions use ordinary ordered-choice relational semantics, evaluation is total, and a word is recognized exactly when evaluation succeeds with empty remainder.

StatusDefined self-containedly and mechanically exercised
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

The scaffold theorem needs an exact target model. The definition fixes ordinary PEG syntax and relational semantics before any generated grammar is considered.

Definitions

  • Expressions have epsilon, failure, any symbol, terminals, nonterminals, sequence, ordered alternative, and negative lookahead; positive lookahead is double negation.
  • Recognition means successful evaluation with no unconsumed suffix, not prefix acceptance.
  • Membership uses finite grammar data and a literal Fin n nonterminal carrier after semantics-preserving transport.

Proof or evidence

Lean checks deterministic relational evaluation, totality, complete-match recognition, grammar transport, guarded anyStar, exhaustive end-of-input examples, and a sound rank-scheduled table evaluator with complete, partial, and rejecting outcomes.

PEG semantic target →

Verification notes

The accepted specification, syntax and semantic modules, table evaluator, examples, finite-carrier boundary, and generated-grammar use were reconciled against the pinned source. The executable evaluator is corroboration rather than the definition of PEG membership.

Limitations

  • This is a semantic definition, not a theorem that a particular language lies in PEG.
  • It does not formalize every alternative PEG convention or prove normalization of arbitrary grammars.

Open work

Seek specialist review of the semantic correspondence with ordinary complete-match PEG conventions.

Notes

The accepted specification fixed the target before construction. Lean now checks ordinary syntax, deterministic relational evaluation, complete-match recognition, finite grammar data, nonterminal transport, exhaustive end-of-input tests, guarded anyStar, and a sound executable rank-scheduled table evaluator with explicit complete, partial, and rejecting outcomes. FPRD-T110 separately checks the generated scaffold grammar, independent relational totality, and Theorem 16 sufficient direction. This definition opens no M34 and does not change the assurance status of FPRD-T90.