1 files changed, 318 insertions, 0 deletions
diff --git a/src/urubu/grammar/lalr1.go b/src/urubu/grammar/lalr1.go
new file mode 100644
index 0000000..8373568
--- /dev/null
+++ b/src/urubu/grammar/lalr1.go
@@ -0,0 +1,318 @@
+package grammar
+
+import (
+	"fmt"
+
+	"urubu/grammar/symbol"
+)
+
+type stateAndLRItem struct {
+	kernelID kernelID
+	itemID   lrItemID
+}
+
+type propagation struct {
+	src  *stateAndLRItem
+	dest []*stateAndLRItem
+}
+
+type lalr1Automaton struct {
+	*lr0Automaton
+}
+
+func genLALR1Automaton(lr0 *lr0Automaton, prods *productionSet, first *firstSet) (*lalr1Automaton, error) {
+	// Set the look-ahead symbol <EOF> to the initial item: [S' → ・S, $]
+	iniState := lr0.states[lr0.initialState]
+	iniState.items[0].lookAhead.symbols = map[symbol.Symbol]struct{}{
+		symbol.SymbolEOF: {},
+	}
+
+	var props []*propagation
+	for _, state := range lr0.states {
+		for _, kItem := range state.items {
+			items, err := genLALR1Closure(kItem, prods, first)
+			if err != nil {
+				return nil, err
+			}
+
+			kItem.lookAhead.propagation = true
+
+			var propDests []*stateAndLRItem
+			for _, item := range items {
+				if item.reducible {
+					p, ok := prods.findByID(item.prod)
+					if !ok {
+						return nil, fmt.Errorf("production not found: %v", item.prod)
+					}
+
+					if p.isEmpty() {
+						var reducibleItem *lrItem
+						for _, it := range state.emptyProdItems {
+							if it.id != item.id {
+								continue
+							}
+
+							reducibleItem = it
+							break
+						}
+						if reducibleItem == nil {
+							return nil, fmt.Errorf("reducible item not found: %v", item.id)
+						}
+						if reducibleItem.lookAhead.symbols == nil {
+							reducibleItem.lookAhead.symbols = map[symbol.Symbol]struct{}{}
+						}
+						for a := range item.lookAhead.symbols {
+							reducibleItem.lookAhead.symbols[a] = struct{}{}
+						}
+
+						propDests = append(propDests, &stateAndLRItem{
+							kernelID: state.id,
+							itemID:   item.id,
+						})
+					}
+
+					continue
+				}
+
+				nextKID := state.next[item.dottedSymbol]
+				var nextItemID lrItemID
+				{
+					p, ok := prods.findByID(item.prod)
+					if !ok {
+						return nil, fmt.Errorf("production not found: %v", item.prod)
+					}
+					it, err := newLR0Item(p, item.dot+1)
+					if err != nil {
+						return nil, fmt.Errorf("failed to generate an item ID: %v", err)
+					}
+					nextItemID = it.id
+				}
+
+				if item.lookAhead.propagation {
+					propDests = append(propDests, &stateAndLRItem{
+						kernelID: nextKID,
+						itemID:   nextItemID,
+					})
+				} else {
+					nextState := lr0.states[nextKID]
+					var nextItem *lrItem
+					for _, it := range nextState.items {
+						if it.id != nextItemID {
+							continue
+						}
+						nextItem = it
+						break
+					}
+					if nextItem == nil {
+						return nil, fmt.Errorf("item not found: %v", nextItemID)
+					}
+
+					if nextItem.lookAhead.symbols == nil {
+						nextItem.lookAhead.symbols = map[symbol.Symbol]struct{}{}
+					}
+
+					for a := range item.lookAhead.symbols {
+						nextItem.lookAhead.symbols[a] = struct{}{}
+					}
+				}
+			}
+			if len(propDests) == 0 {
+				continue
+			}
+
+			props = append(props, &propagation{
+				src: &stateAndLRItem{
+					kernelID: state.id,
+					itemID:   kItem.id,
+				},
+				dest: propDests,
+			})
+		}
+	}
+
+	err := propagateLookAhead(lr0, props)
+	if err != nil {
+		return nil, fmt.Errorf("failed to propagate look-ahead symbols: %v", err)
+	}
+
+	return &lalr1Automaton{
+		lr0Automaton: lr0,
+	}, nil
+}
+
+func genLALR1Closure(srcItem *lrItem, prods *productionSet, first *firstSet) ([]*lrItem, error) {
+	items := []*lrItem{}
+	knownItems := map[lrItemID]map[symbol.Symbol]struct{}{}
+	knownItemsProp := map[lrItemID]struct{}{}
+	uncheckedItems := []*lrItem{}
+	items = append(items, srcItem)
+	uncheckedItems = append(uncheckedItems, srcItem)
+	for len(uncheckedItems) > 0 {
+		nextUncheckedItems := []*lrItem{}
+		for _, item := range uncheckedItems {
+			if item.dottedSymbol.IsTerminal() {
+				continue
+			}
+
+			p, ok := prods.findByID(item.prod)
+			if !ok {
+				return nil, fmt.Errorf("production not found: %v", item.prod)
+			}
+
+			var fstSyms []symbol.Symbol
+			var isFstNullable bool
+			{
+				fst, err := first.find(p, item.dot+1)
+				if err != nil {
+					return nil, err
+				}
+
+				fstSyms = make([]symbol.Symbol, len(fst.symbols))
+				i := 0
+				for s := range fst.symbols {
+					fstSyms[i] = s
+					i++
+				}
+				if fst.empty {
+					isFstNullable = true
+				}
+			}
+
+			ps, _ := prods.findByLHS(item.dottedSymbol)
+			for _, prod := range ps {
+				var lookAhead []symbol.Symbol
+				{
+					var lookAheadCount int
+					if isFstNullable {
+						lookAheadCount = len(fstSyms) + len(item.lookAhead.symbols)
+					} else {
+						lookAheadCount = len(fstSyms)
+					}
+
+					lookAhead = make([]symbol.Symbol, lookAheadCount)
+					i := 0
+					for _, s := range fstSyms {
+						lookAhead[i] = s
+						i++
+					}
+					if isFstNullable {
+						for a := range item.lookAhead.symbols {
+							lookAhead[i] = a
+							i++
+						}
+					}
+				}
+
+				for _, a := range lookAhead {
+					newItem, err := newLR0Item(prod, 0)
+					if err != nil {
+						return nil, err
+					}
+					if items, exist := knownItems[newItem.id]; exist {
+						if _, exist := items[a]; exist {
+							continue
+						}
+					}
+
+					newItem.lookAhead.symbols = map[symbol.Symbol]struct{}{
+						a: {},
+					}
+
+					items = append(items, newItem)
+					if knownItems[newItem.id] == nil {
+						knownItems[newItem.id] = map[symbol.Symbol]struct{}{}
+					}
+					knownItems[newItem.id][a] = struct{}{}
+					nextUncheckedItems = append(nextUncheckedItems, newItem)
+				}
+
+				if isFstNullable {
+					newItem, err := newLR0Item(prod, 0)
+					if err != nil {
+						return nil, err
+					}
+					if _, exist := knownItemsProp[newItem.id]; exist {
+						continue
+					}
+
+					newItem.lookAhead.propagation = true
+
+					items = append(items, newItem)
+					knownItemsProp[newItem.id] = struct{}{}
+					nextUncheckedItems = append(nextUncheckedItems, newItem)
+				}
+			}
+		}
+		uncheckedItems = nextUncheckedItems
+	}
+
+	return items, nil
+}
+
+func propagateLookAhead(lr0 *lr0Automaton, props []*propagation) error {
+	for {
+		changed := false
+		for _, prop := range props {
+			srcState, ok := lr0.states[prop.src.kernelID]
+			if !ok {
+				return fmt.Errorf("source state not found: %v", prop.src.kernelID)
+			}
+			var srcItem *lrItem
+			for _, item := range srcState.items {
+				if item.id != prop.src.itemID {
+					continue
+				}
+				srcItem = item
+				break
+			}
+			if srcItem == nil {
+				return fmt.Errorf("source item not found: %v", prop.src.itemID)
+			}
+
+			for _, dest := range prop.dest {
+				destState, ok := lr0.states[dest.kernelID]
+				if !ok {
+					return fmt.Errorf("destination state not found: %v", dest.kernelID)
+				}
+				var destItem *lrItem
+				for _, item := range destState.items {
+					if item.id != dest.itemID {
+						continue
+					}
+					destItem = item
+					break
+				}
+				if destItem == nil {
+					for _, item := range destState.emptyProdItems {
+						if item.id != dest.itemID {
+							continue
+						}
+						destItem = item
+						break
+					}
+					if destItem == nil {
+						return fmt.Errorf("destination item not found: %v", dest.itemID)
+					}
+				}
+
+				for a := range srcItem.lookAhead.symbols {
+					if _, ok := destItem.lookAhead.symbols[a]; ok {
+						continue
+					}
+
+					if destItem.lookAhead.symbols == nil {
+						destItem.lookAhead.symbols = map[symbol.Symbol]struct{}{}
+					}
+
+					destItem.lookAhead.symbols[a] = struct{}{}
+					changed = true
+				}
+			}
+		}
+		if !changed {
+			break
+		}
+	}
+
+	return nil
+}