lambdaclass / lambdaclass/lambda_compiler_kit
Integrate Glushkov NFA engine into lck-grep CLI utility
Nessuno ha ancora preso questa issue.
- Lingua principale
- Lean
- Stelle
- 2
- Fork
- 1
- Metriche di merge delle PR
- Nessuna PR unita negli ultimi 30g
Descrizione
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/)
Guida per i contributori
Nessuna guida per i contributori indicizzata per questo repository
Come iniziare
- Leggi tutta la issue e poi la guida ai contributi del progetto.
- Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
- Fai un fork del repository e lavora su un branch.
- Apri una pull request che faccia riferimento al numero della issue.
Direzione di ricerca
Inizia da cli/Lck.Grep.lean, Lck/Regex.lean e dal motore Glushkov in Lck/Regex/Glushkov/. Esponi Glushkov.build, sostituisci le chiamate a Thompson NFA ed esegui gli esempi o test esistenti in test/ per confrontare il comportamento di grep. Il lavoro è completato quando la CLI utilizza il motore verificato e le proprietà verificate formalmente sono documentate.
Scritto dal modello di indicizzazione a partire dal testo della issue.
Valutazione
- Ambito
- cli, compilers
- Tipo di issue
- Refactoring
- Difficoltà
- 4/5
- Tempo stimato
- 3-5 giorni
- Stato di attività
- Ferma
- Chiarezza
- Abbastanza chiara
- Idoneità per principianti
- 38/100