diff options
Diffstat (limited to 'src/urubu/grammar/lalr1.go')
-rw-r--r-- | src/urubu/grammar/lalr1.go | 318 |
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 +} |