lambdaclass / lambdaclass/lambda_compiler_kit

Integrate Glushkov NFA engine into lck-grep CLI utility

Aperta
#11 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

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.build to compile regexes to NFAs
  • Verify that the Glushkov engine produces equivalent results
  • Validate against existing test cases in cli/

Implementation steps

  1. Expose Glushkov.build in Lck/Regex.lean
  2. Replace Thompson NFA calls with Glushkov.build
  3. Run existing grep tests to confirm behavior equivalence
  4. 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

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. 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

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.