Skip to content

Instantly share code, notes, and snippets.

@dabrahams
Created July 12, 2022 01:41
Show Gist options
  • Save dabrahams/faa12e366c77489566893ee1356dd70c to your computer and use it in GitHub Desktop.
Save dabrahams/faa12e366c77489566893ee1356dd70c to your computer and use it in GitHub Desktop.
Example that would be better if we could create a mixin with additional stored members
extension Grammar {
/// Returns the set of nullable symbols (which sometimes derive 𝝐) and the subset of nulling
/// symbols (which always derive 𝝐) in a grammar that is not yet in nihilist normal form.
func nullSymbolSets(rulesByRHS: MultiMap<Symbol, Rule>)
-> (nullable: Set<Symbol>, nulling: Set<Symbol>)
{
// - Common setup.
// Mapping from symbol to the set of ruleIDs having that symbol as a LHS.
let rulesByLHS = MultiMap(grouping: ruleIDs, by: lhs)
// Mapping from symbol to ruleIDs in whose RHS which that symbol appears.
let rulesByRHS = self.rulesByRHS()
// Mapping from symbol x to the LHS symbols of rules having x on the rhs.
let lhsSymbolsByRHS = Dictionary<Symbol, Set<Symbol>>(
uniqueKeysWithValues: rulesByRHS.storage.lazy.map { (rhsSymbol, ruleIDs) in
(key: rhsSymbol, value: Set(ruleIDs.lazy.map { r in lhs(r) }))
})
var uniqueCount = UniqueCounter<Symbol>()
// - Nulling analysis.
var nulling = Set<Symbol>()
// For each nonterminal s, tracks the number of distinct symbols not yet known to be nulling
// that appear on the RHS of any rule with s on the LHS. Start by assuming all symbols are
// non-nulling.
var maybeNonNullingRHSCount = Dictionary(
uniqueKeysWithValues: rulesByLHS.storage.lazy.map { (lhs, lhsRuleIDs) in
(lhs, uniqueCount(lhsRuleIDs.lazy.map { r in rhs(r) }.joined()))
})
// A work queue for unprocessed discoveries,
var unprocessed: Array<Symbol>
// All trivially-nulling symbols (those that only appear on the LHS of rules with empty RHS).
= maybeNonNullingRHSCount.lazy.filter { (lhs, rhsCount) in rhsCount == 0 }.map(\.key)
while let s = unprocessed.popLast() {
let newlyAdded = nulling.insert(s).inserted
assert(newlyAdded, "expecting to only discover a nulling symbol once")
for lhs in lhsSymbolsByRHS[s]! {
if maybeNonNullingRHSCount[lhs]!.decrementIsZero() {
unprocessed.append(lhs)
}
}
}
// - Nullable analysis.
// Start with the trivially nullable symbols (those on the lhs of any rule with an empty RHS).
var nullable = Set(ruleIDs.lazy.filter { r in rhs(r).isEmpty }.map { r in lhs(r) })
// For each rule, tracks the number of distinct symbols not yet known to be nullable on its RHS.
var maybeNonNullableRHSCount: Array = rules.map { r in uniqueCount(r.rhs) }
// Reset work queue
unprocessed.append(contentsOf: nullable)
while let s = unprocessed.popLast() {
for r in rulesByRHS[s] {
let i = Int(r.ordinal)
if maybeNonNullableRHSCount[i].decrementIsZero() {
let s1 = lhs(r)
if nullable.insert(s1).inserted { unprocessed.append(s1) }
}
}
}
return (nullable: nullable, nulling: nulling)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment