diff options
Diffstat (limited to 'grammar')
| -rw-r--r-- | grammar/grammar.go | 148 | ||||
| -rw-r--r-- | grammar/parsing_table.go | 29 | ||||
| -rw-r--r-- | grammar/semantic_error.go | 2 |
3 files changed, 176 insertions, 3 deletions
diff --git a/grammar/grammar.go b/grammar/grammar.go index 85eedcc..450c526 100644 --- a/grammar/grammar.go +++ b/grammar/grammar.go @@ -16,6 +16,58 @@ type astActionEntry struct { expansion bool } +type assocType string + +const ( + assocTypeNil = assocType("") + assocTypeLeft = assocType("left") + assocTypeRight = assocType("right") +) + +const ( + precNil = 0 + precMin = 1 +) + +// precAndAssoc represents precedence and associativities of terminal symbols and productions. +// We use the priority of the production to resolve shift/reduce conflicts. +type precAndAssoc struct { + // termPrec represents the precedence of the terminal symbols. + termPrec map[symbolNum]int + + // prodPrec and prodAssoc represent the precedence and the associativities of the production. + // These values are inherited from the right-most symbols in the RHS of the productions. + prodPrec map[productionNum]int + prodAssoc map[productionNum]assocType +} + +func (pa *precAndAssoc) terminalPrecedence(sym symbolNum) int { + prec, ok := pa.termPrec[sym] + if !ok { + return precNil + } + + return prec +} + +func (pa *precAndAssoc) productionPredence(prod productionNum) int { + prec, ok := pa.prodPrec[prod] + if !ok { + return precNil + } + + return prec +} + +func (pa *precAndAssoc) productionAssociativity(prod productionNum) assocType { + assoc, ok := pa.prodAssoc[prod] + if !ok { + return assocTypeNil + } + + return assoc +} + type Grammar struct { lexSpec *mlspec.LexSpec skipLexKinds []mlspec.LexKindName @@ -24,6 +76,7 @@ type Grammar struct { augmentedStartSymbol symbol symbolTable *symbolTable astActions map[productionID][]*astActionEntry + precAndAssoc *precAndAssoc } type GrammarBuilder struct { @@ -43,6 +96,11 @@ func (b *GrammarBuilder) Build() (*Grammar, error) { return nil, err } + pa, err := b.genPrecAndAssoc(symTabAndLexSpec.symTab, prodsAndActs.prods) + if err != nil { + return nil, err + } + syms, err := findUsedAndUnusedSymbols(b.AST) if err != nil { return nil, err @@ -93,6 +151,7 @@ func (b *GrammarBuilder) Build() (*Grammar, error) { augmentedStartSymbol: prodsAndActs.augStartSym, symbolTable: symTabAndLexSpec.symTab, astActions: prodsAndActs.astActs, + precAndAssoc: pa, }, nil } @@ -130,7 +189,6 @@ func findUsedAndUnusedSymbols(root *spec.RootNode) (*usedAndUnusedSymbols, error markUsedSymbols(mark, map[string]bool{}, prods, start) } - // usedProds := make(map[string]*spec.ProductionNode, len(prods)) usedTerms := make(map[string]*spec.ProductionNode, len(lexProds)) unusedProds := map[string]*spec.ProductionNode{} unusedTerms := map[string]*spec.ProductionNode{} @@ -605,6 +663,93 @@ func (b *GrammarBuilder) genProductionsAndActions(root *spec.RootNode, symTabAnd }, nil } +func (b *GrammarBuilder) genPrecAndAssoc(symTab *symbolTable, prods *productionSet) (*precAndAssoc, error) { + termPrec := map[symbolNum]int{} + termAssoc := map[symbolNum]assocType{} + { + precN := precMin + for _, md := range b.AST.MetaData { + var assocTy assocType + switch md.Name { + case "left": + assocTy = assocTypeLeft + case "right": + assocTy = assocTypeRight + default: + return nil, &verr.SpecError{ + Cause: semErrMDInvalidName, + Row: md.Pos.Row, + } + } + + if len(md.Parameters) == 0 { + return nil, &verr.SpecError{ + Cause: semErrMDInvalidParam, + Detail: "associativity needs at least one symbol", + Row: md.Pos.Row, + } + } + + for _, p := range md.Parameters { + sym, ok := symTab.toSymbol(p.ID) + if !ok { + return nil, &verr.SpecError{ + Cause: semErrMDInvalidParam, + Detail: fmt.Sprintf("'%v' is undefined", p.ID), + Row: p.Pos.Row, + } + } + if !sym.isTerminal() { + return nil, &verr.SpecError{ + Cause: semErrMDInvalidParam, + Detail: fmt.Sprintf("associativity can take only terminal symbol ('%v' is a non-terminal)", p.ID), + Row: p.Pos.Row, + } + } + + termPrec[sym.num()] = precN + termAssoc[sym.num()] = assocTy + } + + precN++ + } + } + + prodPrec := map[productionNum]int{} + prodAssoc := map[productionNum]assocType{} + for _, prod := range prods.getAllProductions() { + mostRightTerm := symbolNil + for _, sym := range prod.rhs { + if !sym.isTerminal() { + continue + } + mostRightTerm = sym + } + if mostRightTerm.isNil() { + continue + } + + prec, ok := termPrec[mostRightTerm.num()] + if !ok { + continue + } + + assoc, ok := termAssoc[mostRightTerm.num()] + if !ok { + continue + } + + prodPrec[prod.num] = prec + prodAssoc[prod.num] = assoc + } + + return &precAndAssoc{ + termPrec: termPrec, + prodPrec: prodPrec, + prodAssoc: prodAssoc, + }, nil +} + type Class string const ( @@ -720,6 +865,7 @@ func Compile(gram *Grammar, opts ...CompileOption) (*spec.CompiledGrammar, error nonTermCount: len(nonTerms), symTab: gram.symbolTable, sym2AnonPat: gram.sym2AnonPat, + precAndAssoc: gram.precAndAssoc, } tab, err = b.build() if err != nil { diff --git a/grammar/parsing_table.go b/grammar/parsing_table.go index 903f95a..aee5963 100644 --- a/grammar/parsing_table.go +++ b/grammar/parsing_table.go @@ -136,6 +136,7 @@ type lrTableBuilder struct { nonTermCount int symTab *symbolTable sym2AnonPat map[symbol]string + precAndAssoc *precAndAssoc conflicts []conflict } @@ -222,6 +223,12 @@ func (b *lrTableBuilder) writeShiftAction(tab *ParsingTable, state stateNum, sym nextState: nextState, prodNum: p, }) + + if b.resolveConflict(sym.num(), p) == ActionTypeShift { + tab.writeAction(state.Int(), sym.num().Int(), newShiftActionEntry(nextState)) + } + + return } } @@ -230,7 +237,7 @@ func (b *lrTableBuilder) writeShiftAction(tab *ParsingTable, state stateNum, sym // 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 -// teh production with higher priority. Productions defined earlier in the grammar file have a higher priority. +// 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, prod productionNum) { act := tab.readAction(state.Int(), sym.num().Int()) if !act.isEmpty() { @@ -261,7 +268,9 @@ func (b *lrTableBuilder) writeReduceAction(tab *ParsingTable, state stateNum, sy prodNum: prod, }) - tab.writeAction(state.Int(), sym.num().Int(), newShiftActionEntry(s)) + if b.resolveConflict(sym.num(), prod) == ActionTypeReduce { + tab.writeAction(state.Int(), sym.num().Int(), newReduceActionEntry(prod)) + } } return @@ -270,6 +279,22 @@ func (b *lrTableBuilder) writeReduceAction(tab *ParsingTable, state stateNum, sy tab.writeAction(state.Int(), sym.num().Int(), newReduceActionEntry(prod)) } +func (b *lrTableBuilder) resolveConflict(sym symbolNum, prod productionNum) ActionType { + symPrec := b.precAndAssoc.terminalPrecedence(sym) + prodPrec := b.precAndAssoc.productionPredence(prod) + if symPrec < prodPrec { + return ActionTypeShift + } + if symPrec == prodPrec { + assoc := b.precAndAssoc.productionAssociativity(prod) + if assoc != assocTypeLeft { + return ActionTypeShift + } + } + + return ActionTypeReduce +} + func (b *lrTableBuilder) writeDescription(w io.Writer, tab *ParsingTable) { conflicts := map[stateNum][]conflict{} for _, con := range b.conflicts { diff --git a/grammar/semantic_error.go b/grammar/semantic_error.go index 2d722a8..28154e2 100644 --- a/grammar/semantic_error.go +++ b/grammar/semantic_error.go @@ -15,6 +15,8 @@ func (e *SemanticError) Error() string { } var ( + semErrMDInvalidName = newSemanticError("invalid meta data name") + semErrMDInvalidParam = newSemanticError("invalid parameter") semErrUnusedProduction = newSemanticError("unused production") semErrUnusedTerminal = newSemanticError("unused terminal") semErrTermCannotBeSkipped = newSemanticError("a terminal used in productions cannot be skipped") |