lambdaclass / lambdaclass/lambda_compiler_kit

refactor: deduplicate Symbol.matches / charMatchesClass in Glushkov

Open
#19 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Lean
Stars
2
Forks
1
PR merge metrics
No merged PRs in 30d

Description

Problem

Symbol.matches (Construction.lean:138) reimplements the same character-class matching logic already present in charMatchesClass (Syntax.lean:74). This duplication has been noticed in a correctness proof: CompositionCorrectness.lean even contains an explicit bridging lemma:

have h_eq : Symbol.matches ... = charMatchesClass c ranges.ranges ...

Proposed fix

Rewrite Symbol.matches to delegate to charMatchesClass, eliminating the duplication:

def Symbol.matches (sym : Symbol) (c : Char) : Bool :=
  match sym with
  | Symbol.charClass ranges negated => charMatchesClass c ranges.ranges negated

The bridging have h_eq lemma in CompositionCorrectness becomes trivial (or can be removed via rfl/simp).

Impact

Low risk. Symbol.matches is called internally by the Glushkov matcher. The semantics are identical by construction — the existing bridge lemma proves this. No API change.

Scope

  • Lck/Regex/Glushkov/Construction.lean
  • Lck/Regex/Glushkov/CompositionCorrectness.lean (remove/simplify bridge lemma)

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start in Lck/Regex/Glushkov/Construction.lean at Symbol.matches and compare it with charMatchesClass in Syntax.lean. Then inspect the bridging have h_eq in Lck/Regex/Glushkov/CompositionCorrectness.lean; done means the duplication is removed and the proof is simplified without changing matching behavior.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Refactor
Difficulty
2/5
Estimated time
1-3 hours
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
55/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.