aboutsummaryrefslogtreecommitdiff
path: root/grammar/parsing_table.go
diff options
context:
space:
mode:
Diffstat (limited to 'grammar/parsing_table.go')
-rw-r--r--grammar/parsing_table.go88
1 files changed, 53 insertions, 35 deletions
diff --git a/grammar/parsing_table.go b/grammar/parsing_table.go
index a908001..1e3930b 100644
--- a/grammar/parsing_table.go
+++ b/grammar/parsing_table.go
@@ -63,25 +63,40 @@ func (e goToEntry) describe() (GoToType, stateNum) {
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
- nextState stateNum
- prodNum productionNum
+ state stateNum
+ sym symbol
+ nextState stateNum
+ prodNum productionNum
+ resolvedBy conflictResolutionMethod
}
func (c *shiftReduceConflict) conflict() {
}
type reduceReduceConflict struct {
- state stateNum
- sym symbol
- prodNum1 productionNum
- prodNum2 productionNum
+ state stateNum
+ sym symbol
+ prodNum1 productionNum
+ prodNum2 productionNum
+ resolvedBy conflictResolutionMethod
}
func (c *reduceReduceConflict) conflict() {
@@ -218,21 +233,20 @@ func (b *lrTableBuilder) writeShiftAction(tab *ParsingTable, state stateNum, sym
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,
+ state: state,
+ sym: sym,
+ nextState: nextState,
+ prodNum: p,
+ resolvedBy: method,
})
-
- if b.resolveConflict(sym.num(), p) == ActionTypeShift {
+ if act == ActionTypeShift {
tab.writeAction(state.Int(), sym.num().Int(), newShiftActionEntry(nextState))
}
-
return
}
}
-
tab.writeAction(state.Int(), sym.num().Int(), newShiftActionEntry(nextState))
}
@@ -250,50 +264,52 @@ func (b *lrTableBuilder) writeReduceAction(tab *ParsingTable, state stateNum, sy
}
b.conflicts = append(b.conflicts, &reduceReduceConflict{
- state: state,
- sym: sym,
- prodNum1: p,
- prodNum2: prod,
+ 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,
+ state: state,
+ sym: sym,
+ nextState: s,
+ prodNum: prod,
+ resolvedBy: method,
})
-
- if b.resolveConflict(sym.num(), prod) == ActionTypeReduce {
+ 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) resolveConflict(sym symbolNum, prod productionNum) ActionType {
+func (b *lrTableBuilder) resolveSRConflict(sym symbolNum, prod productionNum) (ActionType, conflictResolutionMethod) {
symPrec := b.precAndAssoc.terminalPrecedence(sym)
prodPrec := b.precAndAssoc.productionPredence(prod)
- if symPrec < prodPrec {
- return ActionTypeShift
+ if symPrec == 0 || prodPrec == 0 {
+ return ActionTypeShift, ResolvedByShift
}
if symPrec == prodPrec {
assoc := b.precAndAssoc.productionAssociativity(prod)
if assoc != assocTypeLeft {
- return ActionTypeShift
+ return ActionTypeShift, ResolvedByAssoc
}
+ return ActionTypeReduce, ResolvedByAssoc
}
-
- return ActionTypeReduce
+ if symPrec < prodPrec {
+ return ActionTypeShift, ResolvedByPrec
+ }
+ return ActionTypeReduce, ResolvedByPrec
}
func (b *lrTableBuilder) genDescription(tab *ParsingTable, gram *Grammar) (*spec.Description, error) {
@@ -485,6 +501,7 @@ func (b *lrTableBuilder) genDescription(tab *ParsingTable, gram *Grammar) (*spec
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())
@@ -509,6 +526,7 @@ func (b *lrTableBuilder) genDescription(tab *ParsingTable, gram *Grammar) (*spec
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())