lean-parsing-completeness

Prove parsing completeness theorems for Lean 4 parsers.

112|9|Updated Feb 17, 2026

Search Tags:#formal verification #theorem proving #completeness #proofs #parsing #lean4

Ready to run

npx skills add https://github.com/kim-em/lean-zip --skill lean-parsing-completeness

💬 Prompt for ChatGPT / Claude Chat▼

Please help me install this Agent Skill.
Skill: lean-parsing-completeness
Source: https://github.com/kim-em/lean-zip/tree/main/.claude/skills/lean-parsing-completeness
Command: npx skills add https://github.com/kim-em/lean-zip --skill lean-parsing-completeness

SYSTEM DOCUMENTATION & REQUIREMENTS

💡 This Skill includes references (resource) components.

What problem does it solve?

This Skill helps developers prove that their parsing functions correctly handle all valid inputs, ensuring robustness and reliability in data processing.

Core Features & Use Cases

Parsing Completeness Proofs: Generate proofs that spec-level success implies native parser success.
Eliminator Lemmas: Prove properties about results when the native parser succeeds.
Use Case: When implementing a complex data format parser, use this Skill to formally verify that any input conforming to the format specification will be parsed without error by your native implementation.

Quick Start

Use the lean-parsing-completeness skill to prove that parseHeader correctly handles all valid inputs.

Frequently Asked Questions about lean-parsing-completeness

High-intent search queries and answers about installing and using this skill.

FAQPage Schema

How do I prove parsing completeness for a function in Lean 4?▼

To prove parsing completeness in Lean 4, you demonstrate that spec-level success implies native parser success. This involves verifying position bounds, applying eliminator lemmas, and validating monadic parsing steps within Except or Option monads.

What is parsing completeness in formal verification?▼

Parsing completeness in formal verification ensures that parsing functions correctly return success for all well-formed inputs. It confirms that any input conforming to a format specification will be parsed without error by the native implementation.

What's the best way to verify a complex data format parser handles all valid inputs?▼

The best way to verify a complex data format parser is using theorem proving to generate completeness proofs. This verifies that any well-formed input conforming to your format specification will be parsed without error by your native implementation.

Do I need theorem proving experience to verify parser correctness in Lean 4?▼

Yes, verifying parser correctness in Lean 4 requires familiarity with theorem proving and formal verification concepts. You need to understand eliminator lemmas, position bounds, and monadic parsing steps in Except and Option to use these structured proof patterns.

Why does my native Lean 4 parser fail on well-formed inputs despite passing tests?▼

Your native Lean 4 parser might fail due to unproven position bounds or incorrect monadic steps in Except or Option. Applying formal verification and eliminator lemmas helps prove spec-level success implies native success for all well-formed inputs.

Can I use formal verification for parsing functions returning Option or Except in Lean 4?▼

Yes, you can use formal verification for parsing functions returning Option or Except in Lean 4. The Skill provides structured proof patterns to validate monadic parsing steps and prove completeness theorems for these specific monadic contexts.