lambdaclass / lambdaclass/lambda_compiler_kit
Integrate Glushkov NFA engine into lck-grep CLI utility
Nobody has claimed this yet.
- Dominant language
- Lean
- Stars
- 2
- Forks
- 1
- PR merge metrics
- No merged PRs in 30d
Description
Summary
The cli/Lck.Grep.lean CLI utility currently has a hardcoded Thompson NFA implementation for proof-of-concept. We now have a verified Glushkov NFA engine with formal correctness proofs.
Goal
Replace the Thompson PoC with the verified Glushkov engine:
- Use
Glushkov.buildto compile regexes to NFAs - Verify that the Glushkov engine produces equivalent results
- Validate against existing test cases in
cli/
Implementation steps
- Expose
Glushkov.buildinLck/Regex.lean - Replace Thompson NFA calls with
Glushkov.build - Run existing grep tests to confirm behavior equivalence
- Document which properties are now formally verified
Related
- Glushkov NFA file:
Lck/Regex/Glushkov/ - CLI entry point:
cli/Lck.Grep.lean - Test suite: (existing example usage in
test/)
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with cli/Lck.Grep.lean, Lck/Regex.lean, and the Glushkov engine under Lck/Regex/Glushkov/. Expose Glushkov.build, replace the Thompson NFA calls, and run the existing examples or tests in test/ to compare grep behavior. Done means the CLI uses the verified engine and the formally verified properties are documented.
Written by the indexing model from the issue text.
Assessment
- Domain
- cli, compilers
- Issue type
- Refactor
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 38/100