/
DerivationLimits.kt
98 lines (82 loc) · 3.58 KB
/
DerivationLimits.kt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
package me.vzhilin.gr.parser
import kotlin.IllegalStateException
data class DerivationLimits(val min: Int, val max: Int)
class ComputeLimits(private val g: Grammar) {
private val revCache = mutableMapOf<Rule, List<Rule>>()
private fun reverse(r: Rule): List<Rule> {
return revCache.computeIfAbsent(r) {
g.prods.filter { it.components.contains(r) } + g.sums.filter { it.components.contains(r) }
}
}
fun computeTreeHeights(goal: NonTerm, inputLength: Int): DerivationLimits {
val lastRow = mutableMapOf<Rule, MutableSet<Int>>()
val curRow = mutableMapOf<Rule, MutableSet<Int>>()
val allSymbols = mutableMapOf<Rule, MutableSet<Int>>()
var minHeight: Int? = null
var maxHeight: Int? = null
fun addToCurRow(rule: Rule, vararg sizes: Int) {
curRow.computeIfAbsent(rule) { mutableSetOf() }.addAll(sizes.toList())
}
fun addToAllSymbols(rule: Rule, vararg sizes: Int) {
allSymbols.computeIfAbsent(rule) { mutableSetOf() }.addAll(sizes.toList())
}
fun sizes(r: Rule) =
if (r is Term) {
setOf(1)
} else {
(lastRow[r] ?: emptySet()) + (allSymbols[r] ?: emptySet())
}
for (term in g.terms) {
lastRow[term] = mutableSetOf(1)
}
var treeDepth = 1
while (!lastRow.contains(goal) || lastRow[goal]!!.min() <= inputLength) {
if (lastRow.isEmpty()) {
throw AssertionError("last row should never be empty")
}
for ((rule, sizes) in lastRow) {
val rr = reverse(rule)
for (revRule in rr) {
when (revRule) {
is Prod -> {
val components = revRule.components
if (components.all { it is Term || lastRow.contains(it) || allSymbols.contains(it) }) {
var ruleVisited = false
val minProdSize = components.sumOf { component ->
if (component == rule && !ruleVisited) {
ruleVisited = true
sizes.min()
} else {
sizes(component).min()
}
}
val maxProdSize = components.sumOf {
component -> sizes(component).max()
}
addToCurRow(revRule, minProdSize, maxProdSize)
}
}
is Sum -> addToCurRow(revRule, sizes.min(), sizes.max())
is Term -> throw IllegalStateException("not expected here: '$revRule'")
}
}
}
for ((rule, sizes) in curRow) {
val min = sizes.min()
val max = sizes.max()
if (rule == goal && minHeight == null && max >= inputLength) {
minHeight = treeDepth + 1
}
if (rule == goal && min <= inputLength) {
maxHeight = treeDepth + 1
}
addToAllSymbols(rule, min, max)
}
lastRow.clear()
lastRow.putAll(curRow)
curRow.clear()
++treeDepth
}
return DerivationLimits(minHeight!!, maxHeight!!)
}
}