aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRyo Nihei <nihei.dev@gmail.com>2021-08-29 23:40:10 +0900
committerRyo Nihei <nihei.dev@gmail.com>2021-08-29 23:40:10 +0900
commitbb85dcc57cc3c0fff6cc9dc09540d58fef400d6f (patch)
tree2fc6a20d0c644a79d454a48c49baa26423fbd10d
parentAdd describe command to print a description file (diff)
downloadurubu-bb85dcc57cc3c0fff6cc9dc09540d58fef400d6f.tar.gz
urubu-bb85dcc57cc3c0fff6cc9dc09540d58fef400d6f.tar.xz
Add precedences and associativities to the description file
-rw-r--r--cmd/vartan/describe.go34
-rw-r--r--grammar/grammar.go15
-rw-r--r--grammar/parsing_table.go30
-rw-r--r--spec/description.go20
4 files changed, 85 insertions, 14 deletions
diff --git a/cmd/vartan/describe.go b/cmd/vartan/describe.go
index d9c3b01..c2cde93 100644
--- a/cmd/vartan/describe.go
+++ b/cmd/vartan/describe.go
@@ -153,12 +153,40 @@ func writeDescription(w io.Writer, desc *spec.Description) error {
return "No conflict was detected."
},
"printTerminal": func(term spec.Terminal) string {
+ var prec string
+ if term.Precedence != 0 {
+ prec = fmt.Sprintf("%2v", term.Precedence)
+ } else {
+ prec = " -"
+ }
+
+ var assoc string
+ if term.Associativity != "" {
+ assoc = term.Associativity
+ } else {
+ assoc = "-"
+ }
+
if term.Alias != "" {
- return fmt.Sprintf("%4v %v (%v)", term.Number, term.Name, term.Alias)
+ return fmt.Sprintf("%4v %v %v %v (%v)", term.Number, prec, assoc, term.Name, term.Alias)
}
- return fmt.Sprintf("%4v %v", term.Number, term.Name)
+ return fmt.Sprintf("%4v %v %v %v", term.Number, prec, assoc, term.Name)
},
"printProduction": func(prod spec.Production) string {
+ var prec string
+ if prod.Precedence != 0 {
+ prec = fmt.Sprintf("%2v", prod.Precedence)
+ } else {
+ prec = " -"
+ }
+
+ var assoc string
+ if prod.Associativity != "" {
+ assoc = prod.Associativity
+ } else {
+ assoc = "-"
+ }
+
var b strings.Builder
fmt.Fprintf(&b, "%v →", nonTermName(prod.LHS))
if len(prod.RHS) > 0 {
@@ -173,7 +201,7 @@ func writeDescription(w io.Writer, desc *spec.Description) error {
fmt.Fprintf(&b, " ε")
}
- return fmt.Sprintf("%4v %v", prod.Number, b.String())
+ return fmt.Sprintf("%4v %v %v %v", prod.Number, prec, assoc, b.String())
},
"printItem": func(item spec.Item) string {
prod := desc.Productions[item.Production]
diff --git a/grammar/grammar.go b/grammar/grammar.go
index edfb6af..b87d368 100644
--- a/grammar/grammar.go
+++ b/grammar/grammar.go
@@ -33,8 +33,9 @@ const (
// 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
+ // termPrec and termAssoc represent the precedence of the terminal symbols.
+ termPrec map[symbolNum]int
+ termAssoc map[symbolNum]assocType
// 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.
@@ -51,6 +52,15 @@ func (pa *precAndAssoc) terminalPrecedence(sym symbolNum) int {
return prec
}
+func (pa *precAndAssoc) terminalAssociativity(sym symbolNum) assocType {
+ assoc, ok := pa.termAssoc[sym]
+ if !ok {
+ return assocTypeNil
+ }
+
+ return assoc
+}
+
func (pa *precAndAssoc) productionPredence(prod productionNum) int {
prec, ok := pa.prodPrec[prod]
if !ok {
@@ -896,6 +906,7 @@ func (b *GrammarBuilder) genPrecAndAssoc(symTab *symbolTable, prods *productionS
return &precAndAssoc{
termPrec: termPrec,
+ termAssoc: termAssoc,
prodPrec: prodPrec,
prodAssoc: prodAssoc,
}, nil
diff --git a/grammar/parsing_table.go b/grammar/parsing_table.go
index fe5a619..a82ef60 100644
--- a/grammar/parsing_table.go
+++ b/grammar/parsing_table.go
@@ -347,6 +347,19 @@ func (b *lrTableBuilder) genDescription(tab *ParsingTable, gram *Grammar) (*spec
term.Pattern = pat
}
+ 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
}
}
@@ -382,11 +395,26 @@ func (b *lrTableBuilder) genDescription(tab *ParsingTable, gram *Grammar) (*spec
}
}
- prods[p.num.Int()] = &spec.Production{
+ 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
}
}
diff --git a/spec/description.go b/spec/description.go
index d2b6d3b..08b037e 100644
--- a/spec/description.go
+++ b/spec/description.go
@@ -1,11 +1,13 @@
package spec
type Terminal struct {
- Number int `json:"number"`
- Name string `json:"name"`
- Anonymous bool `json:"anonymous"`
- Alias string `json:"alias"`
- Pattern string `json:"pattern"`
+ Number int `json:"number"`
+ Name string `json:"name"`
+ Anonymous bool `json:"anonymous"`
+ Alias string `json:"alias"`
+ Pattern string `json:"pattern"`
+ Precedence int `json:"prec"`
+ Associativity string `json:"assoc"`
}
type NonTerminal struct {
@@ -14,9 +16,11 @@ type NonTerminal struct {
}
type Production struct {
- Number int `json:"number"`
- LHS int `json:"lhs"`
- RHS []int `json:"rhs"`
+ Number int `json:"number"`
+ LHS int `json:"lhs"`
+ RHS []int `json:"rhs"`
+ Precedence int `json:"prec"`
+ Associativity string `json:"assoc"`
}
type Item struct {