aboutsummaryrefslogtreecommitdiff
path: root/src/urubu/grammar/parsing_table.go
diff options
context:
space:
mode:
Diffstat (limited to 'src/urubu/grammar/parsing_table.go')
-rw-r--r--src/urubu/grammar/parsing_table.go553
1 files changed, 553 insertions, 0 deletions
diff --git a/src/urubu/grammar/parsing_table.go b/src/urubu/grammar/parsing_table.go
new file mode 100644
index 0000000..48ea9fe
--- /dev/null
+++ b/src/urubu/grammar/parsing_table.go
@@ -0,0 +1,553 @@
+package grammar
+
+import (
+ "fmt"
+ "sort"
+
+ "urubu/grammar/symbol"
+ spec "urubu/spec/grammar"
+)
+
+type ActionType string
+
+const (
+ ActionTypeShift = ActionType("shift")
+ ActionTypeReduce = ActionType("reduce")
+ ActionTypeError = ActionType("error")
+)
+
+type actionEntry int
+
+const actionEntryEmpty = actionEntry(0)
+
+func newShiftActionEntry(state stateNum) actionEntry {
+ return actionEntry(state * -1)
+}
+
+func newReduceActionEntry(prod productionNum) actionEntry {
+ return actionEntry(prod)
+}
+
+func (e actionEntry) isEmpty() bool {
+ return e == actionEntryEmpty
+}
+
+func (e actionEntry) describe() (ActionType, stateNum, productionNum) {
+ if e == actionEntryEmpty {
+ return ActionTypeError, stateNumInitial, productionNumNil
+ }
+ if e < 0 {
+ return ActionTypeShift, stateNum(e * -1), productionNumNil
+ }
+ return ActionTypeReduce, stateNumInitial, productionNum(e)
+}
+
+type GoToType string
+
+const (
+ GoToTypeRegistered = GoToType("registered")
+ GoToTypeError = GoToType("error")
+)
+
+type goToEntry uint
+
+const goToEntryEmpty = goToEntry(0)
+
+func newGoToEntry(state stateNum) goToEntry {
+ return goToEntry(state)
+}
+
+func (e goToEntry) describe() (GoToType, stateNum) {
+ if e == goToEntryEmpty {
+ return GoToTypeError, stateNumInitial
+ }
+ return GoToTypeRegistered, stateNum(e)
+}
+
+type conflictResolutionMethod int
+
+func (m conflictResolutionMethod) Int() int {
+ return int(m)
+}
+
+const (
+ ResolvedByPrec conflictResolutionMethod = 1
+ ResolvedByAssoc conflictResolutionMethod = 2
+ ResolvedByShift conflictResolutionMethod = 3
+ ResolvedByProdOrder conflictResolutionMethod = 4
+)
+
+type conflict interface {
+ conflict()
+}
+
+type shiftReduceConflict struct {
+ state stateNum
+ sym symbol.Symbol
+ nextState stateNum
+ prodNum productionNum
+ resolvedBy conflictResolutionMethod
+}
+
+func (c *shiftReduceConflict) conflict() {
+}
+
+type reduceReduceConflict struct {
+ state stateNum
+ sym symbol.Symbol
+ prodNum1 productionNum
+ prodNum2 productionNum
+ resolvedBy conflictResolutionMethod
+}
+
+func (c *reduceReduceConflict) conflict() {
+}
+
+var (
+ _ conflict = &shiftReduceConflict{}
+ _ conflict = &reduceReduceConflict{}
+)
+
+type ParsingTable struct {
+ actionTable []actionEntry
+ goToTable []goToEntry
+ stateCount int
+ terminalCount int
+ nonTerminalCount int
+
+ // errorTrapperStates's index means a state number, and when `errorTrapperStates[stateNum]` is `1`,
+ // the state has an item having the following form. The `α` and `β` can be empty.
+ //
+ // A → α・error β
+ errorTrapperStates []int
+
+ InitialState stateNum
+}
+
+func (t *ParsingTable) getAction(state stateNum, sym symbol.SymbolNum) (ActionType, stateNum, productionNum) {
+ pos := state.Int()*t.terminalCount + sym.Int()
+ return t.actionTable[pos].describe()
+}
+
+func (t *ParsingTable) getGoTo(state stateNum, sym symbol.SymbolNum) (GoToType, stateNum) {
+ pos := state.Int()*t.nonTerminalCount + sym.Int()
+ return t.goToTable[pos].describe()
+}
+
+func (t *ParsingTable) readAction(row int, col int) actionEntry {
+ return t.actionTable[row*t.terminalCount+col]
+}
+
+func (t *ParsingTable) writeAction(row int, col int, act actionEntry) {
+ t.actionTable[row*t.terminalCount+col] = act
+}
+
+func (t *ParsingTable) writeGoTo(state stateNum, sym symbol.Symbol, nextState stateNum) {
+ pos := state.Int()*t.nonTerminalCount + sym.Num().Int()
+ t.goToTable[pos] = newGoToEntry(nextState)
+}
+
+type lrTableBuilder struct {
+ automaton *lr0Automaton
+ prods *productionSet
+ termCount int
+ nonTermCount int
+ symTab *symbol.SymbolTableReader
+ precAndAssoc *precAndAssoc
+
+ conflicts []conflict
+}
+
+func (b *lrTableBuilder) build() (*ParsingTable, error) {
+ var ptab *ParsingTable
+ {
+ initialState := b.automaton.states[b.automaton.initialState]
+ ptab = &ParsingTable{
+ actionTable: make([]actionEntry, len(b.automaton.states)*b.termCount),
+ goToTable: make([]goToEntry, len(b.automaton.states)*b.nonTermCount),
+ stateCount: len(b.automaton.states),
+ terminalCount: b.termCount,
+ nonTerminalCount: b.nonTermCount,
+ errorTrapperStates: make([]int, len(b.automaton.states)),
+ InitialState: initialState.num,
+ }
+ }
+
+ for _, state := range b.automaton.states {
+ if state.isErrorTrapper {
+ ptab.errorTrapperStates[state.num] = 1
+ }
+
+ for sym, kID := range state.next {
+ nextState := b.automaton.states[kID]
+ if sym.IsTerminal() {
+ b.writeShiftAction(ptab, state.num, sym, nextState.num)
+ } else {
+ ptab.writeGoTo(state.num, sym, nextState.num)
+ }
+ }
+
+ for prodID := range state.reducible {
+ reducibleProd, ok := b.prods.findByID(prodID)
+ if !ok {
+ return nil, fmt.Errorf("reducible production not found: %v", prodID)
+ }
+
+ var reducibleItem *lrItem
+ for _, item := range state.items {
+ if item.prod != reducibleProd.id {
+ continue
+ }
+
+ reducibleItem = item
+ break
+ }
+ if reducibleItem == nil {
+ for _, item := range state.emptyProdItems {
+ if item.prod != reducibleProd.id {
+ continue
+ }
+
+ reducibleItem = item
+ break
+ }
+ if reducibleItem == nil {
+ return nil, fmt.Errorf("reducible item not found; state: %v, production: %v", state.num, reducibleProd.num)
+ }
+ }
+
+ for a := range reducibleItem.lookAhead.symbols {
+ b.writeReduceAction(ptab, state.num, a, reducibleProd.num)
+ }
+ }
+ }
+
+ return ptab, nil
+}
+
+// writeShiftAction writes a shift action to the parsing table. When a shift/reduce conflict occurred,
+// we prioritize the shift action.
+func (b *lrTableBuilder) writeShiftAction(tab *ParsingTable, state stateNum, sym symbol.Symbol, nextState stateNum) {
+ act := tab.readAction(state.Int(), sym.Num().Int())
+ if !act.isEmpty() {
+ ty, _, p := act.describe()
+ if ty == ActionTypeReduce {
+ act, method := b.resolveSRConflict(sym.Num(), p)
+ b.conflicts = append(b.conflicts, &shiftReduceConflict{
+ state: state,
+ sym: sym,
+ nextState: nextState,
+ prodNum: p,
+ resolvedBy: method,
+ })
+ if act == ActionTypeShift {
+ tab.writeAction(state.Int(), sym.Num().Int(), newShiftActionEntry(nextState))
+ }
+ return
+ }
+ }
+ tab.writeAction(state.Int(), sym.Num().Int(), newShiftActionEntry(nextState))
+}
+
+// writeReduceAction writes a reduce action to the parsing table. When a shift/reduce conflict occurred,
+// we prioritize the shift action, and when a reduce/reduce conflict we prioritize the action that reduces
+// the production with higher priority. Productions defined earlier in the grammar file have a higher priority.
+func (b *lrTableBuilder) writeReduceAction(tab *ParsingTable, state stateNum, sym symbol.Symbol, prod productionNum) {
+ act := tab.readAction(state.Int(), sym.Num().Int())
+ if !act.isEmpty() {
+ ty, s, p := act.describe()
+ switch ty {
+ case ActionTypeReduce:
+ if p == prod {
+ return
+ }
+
+ b.conflicts = append(b.conflicts, &reduceReduceConflict{
+ state: state,
+ sym: sym,
+ prodNum1: p,
+ prodNum2: prod,
+ resolvedBy: ResolvedByProdOrder,
+ })
+ if p < prod {
+ tab.writeAction(state.Int(), sym.Num().Int(), newReduceActionEntry(p))
+ } else {
+ tab.writeAction(state.Int(), sym.Num().Int(), newReduceActionEntry(prod))
+ }
+ case ActionTypeShift:
+ act, method := b.resolveSRConflict(sym.Num(), prod)
+ b.conflicts = append(b.conflicts, &shiftReduceConflict{
+ state: state,
+ sym: sym,
+ nextState: s,
+ prodNum: prod,
+ resolvedBy: method,
+ })
+ if act == ActionTypeReduce {
+ tab.writeAction(state.Int(), sym.Num().Int(), newReduceActionEntry(prod))
+ }
+ }
+ return
+ }
+ tab.writeAction(state.Int(), sym.Num().Int(), newReduceActionEntry(prod))
+}
+
+func (b *lrTableBuilder) resolveSRConflict(sym symbol.SymbolNum, prod productionNum) (ActionType, conflictResolutionMethod) {
+ symPrec := b.precAndAssoc.terminalPrecedence(sym)
+ prodPrec := b.precAndAssoc.productionPredence(prod)
+ if symPrec == 0 || prodPrec == 0 {
+ return ActionTypeShift, ResolvedByShift
+ }
+ if symPrec == prodPrec {
+ assoc := b.precAndAssoc.productionAssociativity(prod)
+ if assoc != assocTypeLeft {
+ return ActionTypeShift, ResolvedByAssoc
+ }
+ return ActionTypeReduce, ResolvedByAssoc
+ }
+ if symPrec < prodPrec {
+ return ActionTypeShift, ResolvedByPrec
+ }
+ return ActionTypeReduce, ResolvedByPrec
+}
+
+func (b *lrTableBuilder) genReport(tab *ParsingTable, gram *Grammar) (*spec.Report, error) {
+ var terms []*spec.Terminal
+ {
+ termSyms := b.symTab.TerminalSymbols()
+ terms = make([]*spec.Terminal, len(termSyms)+1)
+
+ for _, sym := range termSyms {
+ name, ok := b.symTab.ToText(sym)
+ if !ok {
+ return nil, fmt.Errorf("failed to generate terminals: symbol not found: %v", sym)
+ }
+
+ term := &spec.Terminal{
+ Number: sym.Num().Int(),
+ Name: name,
+ }
+
+ prec := b.precAndAssoc.terminalPrecedence(sym.Num())
+ if prec != precNil {
+ term.Precedence = prec
+ }
+
+ assoc := b.precAndAssoc.terminalAssociativity(sym.Num())
+ switch assoc {
+ case assocTypeLeft:
+ term.Associativity = "l"
+ case assocTypeRight:
+ term.Associativity = "r"
+ }
+
+ terms[sym.Num()] = term
+ }
+ }
+
+ var nonTerms []*spec.NonTerminal
+ {
+ nonTermSyms := b.symTab.NonTerminalSymbols()
+ nonTerms = make([]*spec.NonTerminal, len(nonTermSyms)+1)
+ for _, sym := range nonTermSyms {
+ name, ok := b.symTab.ToText(sym)
+ if !ok {
+ return nil, fmt.Errorf("failed to generate non-terminals: symbol not found: %v", sym)
+ }
+
+ nonTerms[sym.Num()] = &spec.NonTerminal{
+ Number: sym.Num().Int(),
+ Name: name,
+ }
+ }
+ }
+
+ var prods []*spec.Production
+ {
+ ps := gram.productionSet.getAllProductions()
+ prods = make([]*spec.Production, len(ps)+1)
+ for _, p := range ps {
+ rhs := make([]int, len(p.rhs))
+ for i, e := range p.rhs {
+ if e.IsTerminal() {
+ rhs[i] = e.Num().Int()
+ } else {
+ rhs[i] = e.Num().Int() * -1
+ }
+ }
+
+ prod := &spec.Production{
+ Number: p.num.Int(),
+ LHS: p.lhs.Num().Int(),
+ RHS: rhs,
+ }
+
+ prec := b.precAndAssoc.productionPredence(p.num)
+ if prec != precNil {
+ prod.Precedence = prec
+ }
+
+ assoc := b.precAndAssoc.productionAssociativity(p.num)
+ switch assoc {
+ case assocTypeLeft:
+ prod.Associativity = "l"
+ case assocTypeRight:
+ prod.Associativity = "r"
+ }
+
+ prods[p.num.Int()] = prod
+ }
+ }
+
+ var states []*spec.State
+ {
+ srConflicts := map[stateNum][]*shiftReduceConflict{}
+ rrConflicts := map[stateNum][]*reduceReduceConflict{}
+ for _, con := range b.conflicts {
+ switch c := con.(type) {
+ case *shiftReduceConflict:
+ srConflicts[c.state] = append(srConflicts[c.state], c)
+ case *reduceReduceConflict:
+ rrConflicts[c.state] = append(rrConflicts[c.state], c)
+ }
+ }
+
+ states = make([]*spec.State, len(b.automaton.states))
+ for _, s := range b.automaton.states {
+ kernel := make([]*spec.Item, len(s.items))
+ for i, item := range s.items {
+ p, ok := b.prods.findByID(item.prod)
+ if !ok {
+ return nil, fmt.Errorf("failed to generate states: production of kernel item not found: %v", item.prod)
+ }
+
+ kernel[i] = &spec.Item{
+ Production: p.num.Int(),
+ Dot: item.dot,
+ }
+ }
+
+ sort.Slice(kernel, func(i, j int) bool {
+ if kernel[i].Production < kernel[j].Production {
+ return true
+ }
+ if kernel[i].Production > kernel[j].Production {
+ return false
+ }
+ return kernel[i].Dot < kernel[j].Dot
+ })
+
+ var shift []*spec.Transition
+ var reduce []*spec.Reduce
+ var goTo []*spec.Transition
+ {
+ TERMINALS_LOOP:
+ for _, t := range b.symTab.TerminalSymbols() {
+ act, next, prod := tab.getAction(s.num, t.Num())
+ switch act {
+ case ActionTypeShift:
+ shift = append(shift, &spec.Transition{
+ Symbol: t.Num().Int(),
+ State: next.Int(),
+ })
+ case ActionTypeReduce:
+ for _, r := range reduce {
+ if r.Production == prod.Int() {
+ r.LookAhead = append(r.LookAhead, t.Num().Int())
+ continue TERMINALS_LOOP
+ }
+ }
+ reduce = append(reduce, &spec.Reduce{
+ LookAhead: []int{t.Num().Int()},
+ Production: prod.Int(),
+ })
+ }
+ }
+
+ for _, n := range b.symTab.NonTerminalSymbols() {
+ ty, next := tab.getGoTo(s.num, n.Num())
+ if ty == GoToTypeRegistered {
+ goTo = append(goTo, &spec.Transition{
+ Symbol: n.Num().Int(),
+ State: next.Int(),
+ })
+ }
+ }
+
+ sort.Slice(shift, func(i, j int) bool {
+ return shift[i].State < shift[j].State
+ })
+ sort.Slice(reduce, func(i, j int) bool {
+ return reduce[i].Production < reduce[j].Production
+ })
+ sort.Slice(goTo, func(i, j int) bool {
+ return goTo[i].State < goTo[j].State
+ })
+ }
+
+ sr := []*spec.SRConflict{}
+ rr := []*spec.RRConflict{}
+ {
+ for _, c := range srConflicts[s.num] {
+ conflict := &spec.SRConflict{
+ Symbol: c.sym.Num().Int(),
+ State: c.nextState.Int(),
+ Production: c.prodNum.Int(),
+ ResolvedBy: c.resolvedBy.Int(),
+ }
+
+ ty, s, p := tab.getAction(s.num, c.sym.Num())
+ switch ty {
+ case ActionTypeShift:
+ n := s.Int()
+ conflict.AdoptedState = &n
+ case ActionTypeReduce:
+ n := p.Int()
+ conflict.AdoptedProduction = &n
+ }
+
+ sr = append(sr, conflict)
+ }
+
+ sort.Slice(sr, func(i, j int) bool {
+ return sr[i].Symbol < sr[j].Symbol
+ })
+
+ for _, c := range rrConflicts[s.num] {
+ conflict := &spec.RRConflict{
+ Symbol: c.sym.Num().Int(),
+ Production1: c.prodNum1.Int(),
+ Production2: c.prodNum2.Int(),
+ ResolvedBy: c.resolvedBy.Int(),
+ }
+
+ _, _, p := tab.getAction(s.num, c.sym.Num())
+ conflict.AdoptedProduction = p.Int()
+
+ rr = append(rr, conflict)
+ }
+
+ sort.Slice(rr, func(i, j int) bool {
+ return rr[i].Symbol < rr[j].Symbol
+ })
+ }
+
+ states[s.num.Int()] = &spec.State{
+ Number: s.num.Int(),
+ Kernel: kernel,
+ Shift: shift,
+ Reduce: reduce,
+ GoTo: goTo,
+ SRConflict: sr,
+ RRConflict: rr,
+ }
+ }
+ }
+
+ return &spec.Report{
+ Terminals: terms,
+ NonTerminals: nonTerms,
+ Productions: prods,
+ States: states,
+ }, nil
+}
generated by cgit v1.2.3 (git 2.49.0) at 2025-07-13 14:11:39 +0000