aboutsummaryrefslogtreecommitdiff
path: root/compiler/ast.go
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--compiler/ast.go469
1 files changed, 0 insertions, 469 deletions
diff --git a/compiler/ast.go b/compiler/ast.go
deleted file mode 100644
index 046662e..0000000
--- a/compiler/ast.go
+++ /dev/null
@@ -1,469 +0,0 @@
-package compiler
-
-import (
- "fmt"
- "io"
-
- "github.com/nihei9/maleeni/spec"
-)
-
-type astNode interface {
- fmt.Stringer
- children() (astNode, astNode)
- nullable() bool
- first() *symbolPositionSet
- last() *symbolPositionSet
-}
-
-var (
- _ astNode = &symbolNode{}
- _ astNode = &endMarkerNode{}
- _ astNode = &concatNode{}
- _ astNode = &altNode{}
- _ astNode = &optionNode{}
- _ astNode = &fragmentNode{}
-)
-
-type symbolNode struct {
- byteRange
- pos symbolPosition
- firstMemo *symbolPositionSet
- lastMemo *symbolPositionSet
-}
-
-func newSymbolNode(value byte) *symbolNode {
- return &symbolNode{
- byteRange: byteRange{
- from: value,
- to: value,
- },
- pos: symbolPositionNil,
- }
-}
-
-func newRangeSymbolNode(from, to byte) *symbolNode {
- return &symbolNode{
- byteRange: byteRange{
- from: from,
- to: to,
- },
- pos: symbolPositionNil,
- }
-}
-
-func (n *symbolNode) String() string {
- return fmt.Sprintf("{type: symbol, value: %v - %v, pos: %v}", n.from, n.to, n.pos)
-}
-
-func (n *symbolNode) children() (astNode, astNode) {
- return nil, nil
-}
-
-func (n *symbolNode) nullable() bool {
- return false
-}
-
-func (n *symbolNode) first() *symbolPositionSet {
- if n.firstMemo == nil {
- n.firstMemo = newSymbolPositionSet()
- n.firstMemo.add(n.pos)
- }
- return n.firstMemo
-}
-
-func (n *symbolNode) last() *symbolPositionSet {
- if n.lastMemo == nil {
- n.lastMemo = newSymbolPositionSet()
- n.lastMemo.add(n.pos)
- }
- return n.lastMemo
-}
-
-type endMarkerNode struct {
- id spec.LexModeKindID
- pos symbolPosition
- firstMemo *symbolPositionSet
- lastMemo *symbolPositionSet
-}
-
-func newEndMarkerNode(id spec.LexModeKindID) *endMarkerNode {
- return &endMarkerNode{
- id: id,
- pos: symbolPositionNil,
- }
-}
-
-func (n *endMarkerNode) String() string {
- return fmt.Sprintf("{type: end, pos: %v}", n.pos)
-}
-
-func (n *endMarkerNode) children() (astNode, astNode) {
- return nil, nil
-}
-
-func (n *endMarkerNode) nullable() bool {
- return false
-}
-
-func (n *endMarkerNode) first() *symbolPositionSet {
- if n.firstMemo == nil {
- n.firstMemo = newSymbolPositionSet()
- n.firstMemo.add(n.pos)
- }
- return n.firstMemo
-}
-
-func (n *endMarkerNode) last() *symbolPositionSet {
- if n.lastMemo == nil {
- n.lastMemo = newSymbolPositionSet()
- n.lastMemo.add(n.pos)
- }
- return n.lastMemo
-}
-
-type concatNode struct {
- left astNode
- right astNode
- firstMemo *symbolPositionSet
- lastMemo *symbolPositionSet
-}
-
-func newConcatNode(left, right astNode) *concatNode {
- return &concatNode{
- left: left,
- right: right,
- }
-}
-
-func (n *concatNode) String() string {
- return fmt.Sprintf("{type: concat}")
-}
-
-func (n *concatNode) children() (astNode, astNode) {
- return n.left, n.right
-}
-
-func (n *concatNode) nullable() bool {
- return n.left.nullable() && n.right.nullable()
-}
-
-func (n *concatNode) first() *symbolPositionSet {
- if n.firstMemo == nil {
- n.firstMemo = newSymbolPositionSet()
- n.firstMemo.merge(n.left.first())
- if n.left.nullable() {
- n.firstMemo.merge(n.right.first())
- }
- n.firstMemo.sortAndRemoveDuplicates()
- }
- return n.firstMemo
-}
-
-func (n *concatNode) last() *symbolPositionSet {
- if n.lastMemo == nil {
- n.lastMemo = newSymbolPositionSet()
- n.lastMemo.merge(n.right.last())
- if n.right.nullable() {
- n.lastMemo.merge(n.left.last())
- }
- n.lastMemo.sortAndRemoveDuplicates()
- }
- return n.lastMemo
-}
-
-type altNode struct {
- left astNode
- right astNode
- firstMemo *symbolPositionSet
- lastMemo *symbolPositionSet
-}
-
-func newAltNode(left, right astNode) *altNode {
- return &altNode{
- left: left,
- right: right,
- }
-}
-
-func (n *altNode) String() string {
- return fmt.Sprintf("{type: alt}")
-}
-
-func (n *altNode) children() (astNode, astNode) {
- return n.left, n.right
-}
-
-func (n *altNode) nullable() bool {
- return n.left.nullable() || n.right.nullable()
-}
-
-func (n *altNode) first() *symbolPositionSet {
- if n.firstMemo == nil {
- n.firstMemo = newSymbolPositionSet()
- n.firstMemo.merge(n.left.first())
- n.firstMemo.merge(n.right.first())
- n.firstMemo.sortAndRemoveDuplicates()
- }
- return n.firstMemo
-}
-
-func (n *altNode) last() *symbolPositionSet {
- if n.lastMemo == nil {
- n.lastMemo = newSymbolPositionSet()
- n.lastMemo.merge(n.left.last())
- n.lastMemo.merge(n.right.last())
- n.lastMemo.sortAndRemoveDuplicates()
- }
- return n.lastMemo
-}
-
-type repeatNode struct {
- left astNode
- firstMemo *symbolPositionSet
- lastMemo *symbolPositionSet
-}
-
-func newRepeatNode(left astNode) *repeatNode {
- return &repeatNode{
- left: left,
- }
-}
-
-func (n *repeatNode) String() string {
- return fmt.Sprintf("{type: repeat}")
-}
-
-func (n *repeatNode) children() (astNode, astNode) {
- return n.left, nil
-}
-
-func (n *repeatNode) nullable() bool {
- return true
-}
-
-func (n *repeatNode) first() *symbolPositionSet {
- if n.firstMemo == nil {
- n.firstMemo = newSymbolPositionSet()
- n.firstMemo.merge(n.left.first())
- n.firstMemo.sortAndRemoveDuplicates()
- }
- return n.firstMemo
-}
-
-func (n *repeatNode) last() *symbolPositionSet {
- if n.lastMemo == nil {
- n.lastMemo = newSymbolPositionSet()
- n.lastMemo.merge(n.left.last())
- n.lastMemo.sortAndRemoveDuplicates()
- }
- return n.lastMemo
-}
-
-func newRepeatOneOrMoreNode(left astNode) *concatNode {
- return newConcatNode(
- left,
- &repeatNode{
- left: copyAST(left),
- })
-}
-
-type optionNode struct {
- left astNode
- firstMemo *symbolPositionSet
- lastMemo *symbolPositionSet
-}
-
-func newOptionNode(left astNode) *optionNode {
- return &optionNode{
- left: left,
- }
-}
-
-func (n *optionNode) String() string {
- return fmt.Sprintf("{type: option}")
-}
-
-func (n *optionNode) children() (astNode, astNode) {
- return n.left, nil
-}
-
-func (n *optionNode) nullable() bool {
- return true
-}
-
-func (n *optionNode) first() *symbolPositionSet {
- if n.firstMemo == nil {
- n.firstMemo = newSymbolPositionSet()
- n.firstMemo.merge(n.left.first())
- n.firstMemo.sortAndRemoveDuplicates()
- }
- return n.firstMemo
-}
-
-func (n *optionNode) last() *symbolPositionSet {
- if n.lastMemo == nil {
- n.lastMemo = newSymbolPositionSet()
- n.lastMemo.merge(n.left.last())
- n.lastMemo.sortAndRemoveDuplicates()
- }
- return n.lastMemo
-}
-
-type fragmentNode struct {
- symbol string
- left astNode
-}
-
-func newFragmentNode(symbol string, ast astNode) *fragmentNode {
- return &fragmentNode{
- symbol: symbol,
- left: ast,
- }
-}
-
-func (n *fragmentNode) String() string {
- return fmt.Sprintf("{type: fragment, symbol: %v}", n.symbol)
-}
-
-func (n *fragmentNode) children() (astNode, astNode) {
- return n.left, nil
-}
-
-func (n *fragmentNode) nullable() bool {
- return n.left.nullable()
-}
-
-func (n *fragmentNode) first() *symbolPositionSet {
- return n.left.first()
-}
-
-func (n *fragmentNode) last() *symbolPositionSet {
- return n.left.last()
-}
-
-func copyAST(src astNode) astNode {
- switch n := src.(type) {
- case *symbolNode:
- return newRangeSymbolNode(n.from, n.to)
- case *endMarkerNode:
- return newEndMarkerNode(n.id)
- case *concatNode:
- return newConcatNode(copyAST(n.left), copyAST(n.right))
- case *altNode:
- return newAltNode(copyAST(n.left), copyAST(n.right))
- case *repeatNode:
- return newRepeatNode(copyAST(n.left))
- case *optionNode:
- return newOptionNode(copyAST(n.left))
- case *fragmentNode:
- if n.left == nil {
- return newFragmentNode(n.symbol, nil)
- }
- return newFragmentNode(n.symbol, copyAST(n.left))
- }
- panic(fmt.Errorf("copyAST cannot handle %T type; AST: %v", src, src))
-}
-
-type followTable map[symbolPosition]*symbolPositionSet
-
-func genFollowTable(root astNode) followTable {
- follow := followTable{}
- calcFollow(follow, root)
- return follow
-}
-
-func calcFollow(follow followTable, ast astNode) {
- if ast == nil {
- return
- }
- left, right := ast.children()
- calcFollow(follow, left)
- calcFollow(follow, right)
- switch n := ast.(type) {
- case *concatNode:
- l, r := n.children()
- for _, p := range l.last().set() {
- if _, ok := follow[p]; !ok {
- follow[p] = newSymbolPositionSet()
- }
- follow[p].merge(r.first())
- }
- case *repeatNode:
- for _, p := range n.last().set() {
- if _, ok := follow[p]; !ok {
- follow[p] = newSymbolPositionSet()
- }
- follow[p].merge(n.first())
- }
- }
-}
-
-func positionSymbols(node astNode, n uint16) (uint16, error) {
- if node == nil {
- return n, nil
- }
-
- l, r := node.children()
- p := n
- p, err := positionSymbols(l, p)
- if err != nil {
- return p, err
- }
- p, err = positionSymbols(r, p)
- if err != nil {
- return p, err
- }
- switch n := node.(type) {
- case *symbolNode:
- n.pos, err = newSymbolPosition(p, false)
- if err != nil {
- return p, err
- }
- p++
- case *endMarkerNode:
- n.pos, err = newSymbolPosition(p, true)
- if err != nil {
- return p, err
- }
- p++
- }
- node.first()
- node.last()
- return p, nil
-}
-
-func printAST(w io.Writer, ast astNode, ruledLine string, childRuledLinePrefix string, withAttrs bool) {
- if ast == nil {
- return
- }
- fmt.Fprintf(w, ruledLine)
- fmt.Fprintf(w, "node: %v", ast)
- if withAttrs {
- fmt.Fprintf(w, ", nullable: %v, first: %v, last: %v", ast.nullable(), ast.first(), ast.last())
- }
- fmt.Fprintf(w, "\n")
- left, right := ast.children()
- children := []astNode{}
- if left != nil {
- children = append(children, left)
- }
- if right != nil {
- children = append(children, right)
- }
- num := len(children)
- for i, child := range children {
- line := "└─ "
- if num > 1 {
- if i == 0 {
- line = "├─ "
- } else if i < num-1 {
- line = "│ "
- }
- }
- prefix := "│ "
- if i >= num-1 {
- prefix = " "
- }
- printAST(w, child, childRuledLinePrefix+line, childRuledLinePrefix+prefix, withAttrs)
- }
-}
generated by cgit v1.2.3 (git 2.49.0) at 2025-07-13 04:14:58 +0000