lambdaclass / lambdaclass/lambda_compiler_kit
Integrate Glushkov NFA engine into lck-grep CLI utility
Dieses Issue hat noch niemand übernommen.
- Vorherrschende Sprache
- Lean
- Sterne
- 2
- Forks
- 1
- PR-Merge-Kennzahlen
- Keine gemergten PRs in 30 T.
Beschreibung
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/)
Beitragsleitfaden
Für dieses Repository ist kein Beitragsleitfaden indexiert
Erste Schritte
- Lies das ganze Issue und danach den Beitragsleitfaden des Projekts.
- Schreib ins Issue, dass du es übernimmst — das erspart doppelte Arbeit.
- Forke das Repository und arbeite in einem Branch.
- Öffne einen Pull Request, der die Issue-Nummer nennt.
Rechercherichtung
Beginne mit cli/Lck.Grep.lean, Lck/Regex.lean und der Glushkov-Engine unter Lck/Regex/Glushkov/. Mache Glushkov.build verfügbar, ersetze die Aufrufe der Thompson NFA und führe die vorhandenen Beispiele oder Tests in test/ aus, um das grep-Verhalten zu vergleichen. Die Aufgabe ist erledigt, wenn die CLI die verifizierte Engine verwendet und die formal verifizierten Eigenschaften dokumentiert sind.
Vom Indexierungsmodell aus dem Issue-Text verfasst.
Bewertung
- Bereich
- cli, compilers
- Issue-Typ
- Refactoring
- Schwierigkeit
- 4/5
- Geschätzter Aufwand
- 3-5 Tage
- Aktivitätsstatus
- Veraltet
- Klarheit
- Größtenteils klar
- Anfängerfreundlichkeit
- 38/100