aboutsummaryrefslogtreecommitdiff
path: root/driver/parser
diff options
context:
space:
mode:
Diffstat (limited to 'driver/parser')
-rw-r--r--driver/parser/conflict_test.go524
-rw-r--r--driver/parser/lac_test.go120
-rw-r--r--driver/parser/parser.go412
-rw-r--r--driver/parser/parser_test.go833
-rw-r--r--driver/parser/semantic_action.go366
-rw-r--r--driver/parser/semantic_action_test.go227
-rw-r--r--driver/parser/spec.go73
-rw-r--r--driver/parser/syntax_error_test.go306
-rw-r--r--driver/parser/template.go531
-rw-r--r--driver/parser/token_stream.go61
10 files changed, 3453 insertions, 0 deletions
diff --git a/driver/parser/conflict_test.go b/driver/parser/conflict_test.go
new file mode 100644
index 0000000..21b829a
--- /dev/null
+++ b/driver/parser/conflict_test.go
@@ -0,0 +1,524 @@
+package parser
+
+import (
+ "strings"
+ "testing"
+
+ "github.com/nihei9/vartan/grammar"
+ "github.com/nihei9/vartan/spec/grammar/parser"
+)
+
+func TestParserWithConflicts(t *testing.T) {
+ tests := []struct {
+ caption string
+ specSrc string
+ src string
+ cst *Node
+ }{
+ {
+ caption: "when a shift/reduce conflict occurred, we prioritize the shift action",
+ specSrc: `
+#name test;
+
+expr
+ : expr assign expr
+ | id
+ ;
+
+id: "[A-Za-z0-9_]+";
+assign: '=';
+`,
+ src: `foo=bar=baz`,
+ cst: nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "foo"),
+ ),
+ termNode("assign", "="),
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "bar"),
+ ),
+ termNode("assign", "="),
+ nonTermNode("expr",
+ termNode("id", "baz"),
+ ),
+ ),
+ ),
+ },
+ {
+ caption: "when a reduce/reduce conflict occurred, we prioritize the production defined earlier in the grammar",
+ specSrc: `
+#name test;
+
+s
+ : a
+ | b
+ ;
+a
+ : id
+ ;
+b
+ : id
+ ;
+
+id: "[A-Za-z0-9_]+";
+`,
+ src: `foo`,
+ cst: nonTermNode("s",
+ nonTermNode("a",
+ termNode("id", "foo"),
+ ),
+ ),
+ },
+ {
+ caption: "left associativities defined earlier in the grammar have higher precedence",
+ specSrc: `
+#name test;
+
+#prec (
+ #left mul
+ #left add
+);
+
+expr
+ : expr add expr
+ | expr mul expr
+ | id
+ ;
+
+id: "[A-Za-z0-9_]+";
+add: '+';
+mul: '*';
+`,
+ src: `a+b*c*d+e`,
+ cst: nonTermNode("expr",
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "a"),
+ ),
+ termNode("add", "+"),
+ nonTermNode("expr",
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "b"),
+ ),
+ termNode("mul", "*"),
+ nonTermNode("expr",
+ termNode("id", "c"),
+ ),
+ ),
+ termNode("mul", "*"),
+ nonTermNode("expr",
+ termNode("id", "d"),
+ ),
+ ),
+ ),
+ termNode("add", "+"),
+ nonTermNode("expr",
+ termNode("id", "e"),
+ ),
+ ),
+ },
+ {
+ caption: "left associativities defined in the same line have the same precedence",
+ specSrc: `
+#name test;
+
+#prec (
+ #left add sub
+);
+
+expr
+ : expr add expr
+ | expr sub expr
+ | id
+ ;
+
+id: "[A-Za-z0-9_]+";
+add: '+';
+sub: '-';
+`,
+ src: `a-b+c+d-e`,
+ cst: nonTermNode("expr",
+ nonTermNode("expr",
+ nonTermNode("expr",
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "a"),
+ ),
+ termNode("sub", "-"),
+ nonTermNode("expr",
+ termNode("id", "b"),
+ ),
+ ),
+ termNode("add", "+"),
+ nonTermNode("expr",
+ termNode("id", "c"),
+ ),
+ ),
+ termNode("add", "+"),
+ nonTermNode("expr",
+ termNode("id", "d"),
+ ),
+ ),
+ termNode("sub", "-"),
+ nonTermNode("expr",
+ termNode("id", "e"),
+ ),
+ ),
+ },
+ {
+ caption: "right associativities defined earlier in the grammar have higher precedence",
+ specSrc: `
+#name test;
+
+#prec (
+ #right r1
+ #right r2
+);
+
+expr
+ : expr r2 expr
+ | expr r1 expr
+ | id
+ ;
+
+whitespaces #skip
+ : "[\u{0009}\u{0020}]+";
+r1
+ : 'r1';
+r2
+ : 'r2';
+id
+ : "[A-Za-z0-9_]+";
+`,
+ src: `a r2 b r1 c r1 d r2 e`,
+ cst: nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "a"),
+ ),
+ termNode("r2", "r2"),
+ nonTermNode("expr",
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "b"),
+ ),
+ termNode("r1", "r1"),
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "c"),
+ ),
+ termNode("r1", "r1"),
+ nonTermNode("expr",
+ termNode("id", "d"),
+ ),
+ ),
+ ),
+ termNode("r2", "r2"),
+ nonTermNode("expr",
+ termNode("id", "e"),
+ ),
+ ),
+ ),
+ },
+ {
+ caption: "right associativities defined in the same line have the same precedence",
+ specSrc: `
+#name test;
+
+#prec (
+ #right r1 r2
+);
+
+expr
+ : expr r2 expr
+ | expr r1 expr
+ | id
+ ;
+
+whitespaces #skip
+ : "[\u{0009}\u{0020}]+";
+r1
+ : 'r1';
+r2
+ : 'r2';
+id
+ : "[A-Za-z0-9_]+";
+`,
+ src: `a r2 b r1 c r1 d r2 e`,
+ cst: nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "a"),
+ ),
+ termNode("r2", "r2"),
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "b"),
+ ),
+ termNode("r1", "r1"),
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "c"),
+ ),
+ termNode("r1", "r1"),
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "d"),
+ ),
+ termNode("r2", "r2"),
+ nonTermNode("expr",
+ termNode("id", "e"),
+ ),
+ ),
+ ),
+ ),
+ ),
+ },
+ {
+ caption: "terminal symbols with an #assign directive defined earlier in the grammar have higher precedence",
+ specSrc: `
+#name test;
+
+#prec (
+ #assign a1
+ #assign a2
+);
+
+expr
+ : expr a2 expr
+ | expr a1 expr
+ | id
+ ;
+
+whitespaces #skip
+ : "[\u{0009}\u{0020}]+";
+a1
+ : 'a1';
+a2
+ : 'a2';
+id
+ : "[A-Za-z0-9_]+";
+`,
+ src: `a a2 b a1 c a1 d a2 e`,
+ cst: nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "a"),
+ ),
+ termNode("a2", "a2"),
+ nonTermNode("expr",
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "b"),
+ ),
+ termNode("a1", "a1"),
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "c"),
+ ),
+ termNode("a1", "a1"),
+ nonTermNode("expr",
+ termNode("id", "d"),
+ ),
+ ),
+ ),
+ termNode("a2", "a2"),
+ nonTermNode("expr",
+ termNode("id", "e"),
+ ),
+ ),
+ ),
+ },
+ {
+ caption: "terminal symbols with an #assign directive defined in the same line have the same precedence",
+ specSrc: `
+#name test;
+
+#prec (
+ #assign a1 a2
+);
+
+expr
+ : expr a2 expr
+ | expr a1 expr
+ | id
+ ;
+
+whitespaces #skip
+ : "[\u{0009}\u{0020}]+";
+a1
+ : 'a1';
+a2
+ : 'a2';
+id
+ : "[A-Za-z0-9_]+";
+`,
+ src: `a a2 b a1 c a1 d a2 e`,
+ cst: nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "a"),
+ ),
+ termNode("a2", "a2"),
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "b"),
+ ),
+ termNode("a1", "a1"),
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "c"),
+ ),
+ termNode("a1", "a1"),
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "d"),
+ ),
+ termNode("a2", "a2"),
+ nonTermNode("expr",
+ termNode("id", "e"),
+ ),
+ ),
+ ),
+ ),
+ ),
+ },
+ {
+ caption: "#left, #right, and #assign can be mixed",
+ specSrc: `
+#name test;
+
+#prec (
+ #left mul div
+ #left add sub
+ #assign else
+ #assign then
+ #right assign
+);
+
+expr
+ : expr add expr
+ | expr sub expr
+ | expr mul expr
+ | expr div expr
+ | expr assign expr
+ | if expr then expr
+ | if expr then expr else expr
+ | id
+ ;
+
+ws #skip: "[\u{0009}\u{0020}]+";
+if: 'if';
+then: 'then';
+else: 'else';
+id: "[A-Za-z0-9_]+";
+add: '+';
+sub: '-';
+mul: '*';
+div: '/';
+assign: '=';
+`,
+ src: `x = y = a + b * c - d / e + if f then if g then h else i`,
+ cst: nonTermNode(
+ "expr",
+ nonTermNode("expr",
+ termNode("id", "x"),
+ ),
+ termNode("assign", "="),
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "y"),
+ ),
+ termNode("assign", "="),
+ nonTermNode("expr",
+ nonTermNode("expr",
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "a"),
+ ),
+ termNode("add", "+"),
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "b"),
+ ),
+ termNode("mul", "*"),
+ nonTermNode("expr",
+ termNode("id", "c"),
+ ),
+ ),
+ ),
+ termNode("sub", "-"),
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("id", "d"),
+ ),
+ termNode("div", "/"),
+ nonTermNode("expr",
+ termNode("id", "e"),
+ ),
+ ),
+ ),
+ termNode("add", "+"),
+ nonTermNode("expr",
+ termNode("if", "if"),
+ nonTermNode("expr",
+ termNode("id", "f"),
+ ),
+ termNode("then", "then"),
+ nonTermNode("expr",
+ termNode("if", "if"),
+ nonTermNode("expr",
+ termNode("id", "g"),
+ ),
+ termNode("then", "then"),
+ nonTermNode("expr",
+ termNode("id", "h"),
+ ),
+ termNode("else", "else"),
+ nonTermNode("expr",
+ termNode("id", "i"),
+ ),
+ ),
+ ),
+ ),
+ ),
+ ),
+ },
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.caption, func(t *testing.T) {
+ ast, err := parser.Parse(strings.NewReader(tt.specSrc))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ b := grammar.GrammarBuilder{
+ AST: ast,
+ }
+ cg, _, err := b.Build()
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ toks, err := NewTokenStream(cg, strings.NewReader(tt.src))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ gram := NewGrammar(cg)
+ tb := NewDefaultSyntaxTreeBuilder()
+ p, err := NewParser(toks, gram, SemanticAction(NewCSTActionSet(gram, tb)))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ err = p.Parse()
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ if tt.cst != nil {
+ testTree(t, tb.Tree(), tt.cst)
+ }
+ })
+ }
+}
diff --git a/driver/parser/lac_test.go b/driver/parser/lac_test.go
new file mode 100644
index 0000000..14bd2cf
--- /dev/null
+++ b/driver/parser/lac_test.go
@@ -0,0 +1,120 @@
+package parser
+
+import (
+ "strings"
+ "testing"
+
+ "github.com/nihei9/vartan/grammar"
+ "github.com/nihei9/vartan/spec/grammar/parser"
+)
+
+func TestParserWithLAC(t *testing.T) {
+ specSrc := `
+#name test;
+
+s
+ : t t
+ ;
+t
+ : c t
+ | d
+ ;
+
+c: 'c';
+d: 'd';
+`
+
+ src := `ccd`
+
+ actLogWithLAC := []string{
+ "shift/c",
+ "shift/c",
+ "shift/d",
+ "miss",
+ }
+
+ actLogWithoutLAC := []string{
+ "shift/c",
+ "shift/c",
+ "shift/d",
+ "reduce/t",
+ "reduce/t",
+ "reduce/t",
+ "miss",
+ }
+
+ ast, err := parser.Parse(strings.NewReader(specSrc))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ b := grammar.GrammarBuilder{
+ AST: ast,
+ }
+ gram, _, err := b.Build()
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ t.Run("LAC is enabled", func(t *testing.T) {
+ semAct := &testSemAct{
+ gram: gram,
+ }
+
+ toks, err := NewTokenStream(gram, strings.NewReader(src))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ p, err := NewParser(toks, NewGrammar(gram), SemanticAction(semAct))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ err = p.Parse()
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ if len(semAct.actLog) != len(actLogWithLAC) {
+ t.Fatalf("unexpected action log; want: %+v, got: %+v", actLogWithLAC, semAct.actLog)
+ }
+
+ for i, e := range actLogWithLAC {
+ if semAct.actLog[i] != e {
+ t.Fatalf("unexpected action log; want: %+v, got: %+v", actLogWithLAC, semAct.actLog)
+ }
+ }
+ })
+
+ t.Run("LAC is disabled", func(t *testing.T) {
+ semAct := &testSemAct{
+ gram: gram,
+ }
+
+ toks, err := NewTokenStream(gram, strings.NewReader(src))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ p, err := NewParser(toks, NewGrammar(gram), SemanticAction(semAct), DisableLAC())
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ err = p.Parse()
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ if len(semAct.actLog) != len(actLogWithoutLAC) {
+ t.Fatalf("unexpected action log; want: %+v, got: %+v", actLogWithoutLAC, semAct.actLog)
+ }
+
+ for i, e := range actLogWithoutLAC {
+ if semAct.actLog[i] != e {
+ t.Fatalf("unexpected action log; want: %+v, got: %+v", actLogWithoutLAC, semAct.actLog)
+ }
+ }
+ })
+}
diff --git a/driver/parser/parser.go b/driver/parser/parser.go
new file mode 100644
index 0000000..05f7d38
--- /dev/null
+++ b/driver/parser/parser.go
@@ -0,0 +1,412 @@
+package parser
+
+import (
+ "fmt"
+)
+
+type Grammar interface {
+ // InitialState returns the initial state of a parser.
+ InitialState() int
+
+ // StartProduction returns the start production of grammar.
+ StartProduction() int
+
+ // Action returns an ACTION entry corresponding to a (state, terminal symbol) pair.
+ Action(state int, terminal int) int
+
+ // GoTo returns a GOTO entry corresponding to a (state, non-terminal symbol) pair.
+ GoTo(state int, lhs int) int
+
+ // ErrorTrapperState returns true when a state can shift the error symbol.
+ ErrorTrapperState(state int) bool
+
+ // LHS returns a LHS symbol of a production.
+ LHS(prod int) int
+
+ // AlternativeSymbolCount returns a symbol count of p production.
+ AlternativeSymbolCount(prod int) int
+
+ // RecoverProduction returns true when a production has the recover directive.
+ RecoverProduction(prod int) bool
+
+ // NonTerminal retuns a string representaion of a non-terminal symbol.
+ NonTerminal(nonTerminal int) string
+
+ // TerminalCount returns a terminal symbol count of grammar.
+ TerminalCount() int
+
+ // SkipTerminal returns true when a terminal symbol must be skipped on syntax analysis.
+ SkipTerminal(terminal int) bool
+
+ // EOF returns the EOF symbol.
+ EOF() int
+
+ // Error returns the error symbol.
+ Error() int
+
+ // Terminal retuns a string representaion of a terminal symbol.
+ Terminal(terminal int) string
+
+ // ASTAction returns an AST action entries.
+ ASTAction(prod int) []int
+}
+
+type VToken interface {
+ // TerminalID returns a terminal ID.
+ TerminalID() int
+
+ // Lexeme returns a lexeme.
+ Lexeme() []byte
+
+ // EOF returns true when a token represents EOF.
+ EOF() bool
+
+ // Invalid returns true when a token is invalid.
+ Invalid() bool
+
+ // Position returns (row, column) pair.
+ Position() (int, int)
+}
+
+type TokenStream interface {
+ Next() (VToken, error)
+}
+
+type SyntaxError struct {
+ Row int
+ Col int
+ Message string
+ Token VToken
+ ExpectedTerminals []string
+}
+
+type ParserOption func(p *Parser) error
+
+// DisableLAC disables LAC (lookahead correction). LAC is enabled by default.
+func DisableLAC() ParserOption {
+ return func(p *Parser) error {
+ p.disableLAC = true
+ return nil
+ }
+}
+
+func SemanticAction(semAct SemanticActionSet) ParserOption {
+ return func(p *Parser) error {
+ p.semAct = semAct
+ return nil
+ }
+}
+
+type Parser struct {
+ toks TokenStream
+ gram Grammar
+ stateStack *stateStack
+ semAct SemanticActionSet
+ disableLAC bool
+ onError bool
+ shiftCount int
+ synErrs []*SyntaxError
+}
+
+func NewParser(toks TokenStream, gram Grammar, opts ...ParserOption) (*Parser, error) {
+ p := &Parser{
+ toks: toks,
+ gram: gram,
+ stateStack: &stateStack{},
+ }
+
+ for _, opt := range opts {
+ err := opt(p)
+ if err != nil {
+ return nil, err
+ }
+ }
+
+ return p, nil
+}
+
+func (p *Parser) Parse() error {
+ p.stateStack.push(p.gram.InitialState())
+ tok, err := p.nextToken()
+ if err != nil {
+ return err
+ }
+
+ACTION_LOOP:
+ for {
+ act := p.lookupAction(tok)
+
+ switch {
+ case act < 0: // Shift
+ nextState := act * -1
+
+ recovered := false
+ if p.onError {
+ p.shiftCount++
+
+ // When the parser performs shift three times, the parser recovers from the error state.
+ if p.shiftCount >= 3 {
+ p.onError = false
+ p.shiftCount = 0
+ recovered = true
+ }
+ }
+
+ p.shift(nextState)
+
+ if p.semAct != nil {
+ p.semAct.Shift(tok, recovered)
+ }
+
+ tok, err = p.nextToken()
+ if err != nil {
+ return err
+ }
+ case act > 0: // Reduce
+ prodNum := act
+
+ recovered := false
+ if p.onError && p.gram.RecoverProduction(prodNum) {
+ p.onError = false
+ p.shiftCount = 0
+ recovered = true
+ }
+
+ accepted := p.reduce(prodNum)
+ if accepted {
+ if p.semAct != nil {
+ p.semAct.Accept()
+ }
+
+ return nil
+ }
+
+ if p.semAct != nil {
+ p.semAct.Reduce(prodNum, recovered)
+ }
+ default: // Error
+ if p.onError {
+ tok, err = p.nextToken()
+ if err != nil {
+ return err
+ }
+ if tok.EOF() {
+ if p.semAct != nil {
+ p.semAct.MissError(tok)
+ }
+
+ return nil
+ }
+
+ continue ACTION_LOOP
+ }
+
+ row, col := tok.Position()
+ p.synErrs = append(p.synErrs, &SyntaxError{
+ Row: row,
+ Col: col,
+ Message: "unexpected token",
+ Token: tok,
+ ExpectedTerminals: p.searchLookahead(p.stateStack.top()),
+ })
+
+ count, ok := p.trapError()
+ if !ok {
+ if p.semAct != nil {
+ p.semAct.MissError(tok)
+ }
+
+ return nil
+ }
+
+ p.onError = true
+ p.shiftCount = 0
+
+ act, err := p.lookupActionOnError()
+ if err != nil {
+ return err
+ }
+
+ p.shift(act * -1)
+
+ if p.semAct != nil {
+ p.semAct.TrapAndShiftError(tok, count)
+ }
+ }
+ }
+}
+
+// validateLookahead validates whether `term` is a valid lookahead in the current context. When `term` is valid,
+// this method returns `true`.
+func (p *Parser) validateLookahead(term int) bool {
+ p.stateStack.enableExploratoryMode()
+ defer p.stateStack.disableExploratoryMode()
+
+ for {
+ act := p.gram.Action(p.stateStack.topExploratorily(), term)
+
+ switch {
+ case act < 0: // Shift
+ return true
+ case act > 0: // Reduce
+ prodNum := act
+
+ lhs := p.gram.LHS(prodNum)
+ if lhs == p.gram.LHS(p.gram.StartProduction()) {
+ return true
+ }
+ n := p.gram.AlternativeSymbolCount(prodNum)
+ p.stateStack.popExploratorily(n)
+ state := p.gram.GoTo(p.stateStack.topExploratorily(), lhs)
+ p.stateStack.pushExploratorily(state)
+ default: // Error
+ return false
+ }
+ }
+}
+
+func (p *Parser) nextToken() (VToken, error) {
+ for {
+ // We don't have to check whether the token is invalid because the kind ID of the invalid token is 0,
+ // and the parsing table doesn't have an entry corresponding to the kind ID 0. Thus we can detect
+ // a syntax error because the parser cannot find an entry corresponding to the invalid token.
+ tok, err := p.toks.Next()
+ if err != nil {
+ return nil, err
+ }
+
+ if p.gram.SkipTerminal(tok.TerminalID()) {
+ continue
+ }
+
+ return tok, nil
+ }
+}
+
+func (p *Parser) tokenToTerminal(tok VToken) int {
+ if tok.EOF() {
+ return p.gram.EOF()
+ }
+
+ return tok.TerminalID()
+}
+
+func (p *Parser) lookupAction(tok VToken) int {
+ if !p.disableLAC {
+ term := p.tokenToTerminal(tok)
+ if !p.validateLookahead(term) {
+ return 0
+ }
+ }
+
+ return p.gram.Action(p.stateStack.top(), p.tokenToTerminal(tok))
+}
+
+func (p *Parser) lookupActionOnError() (int, error) {
+ act := p.gram.Action(p.stateStack.top(), p.gram.Error())
+ if act >= 0 {
+ return 0, fmt.Errorf("an entry must be a shift action by the error symbol; entry: %v, state: %v, symbol: %v", act, p.stateStack.top(), p.gram.Terminal(p.gram.Error()))
+ }
+
+ return act, nil
+}
+
+func (p *Parser) shift(nextState int) {
+ p.stateStack.push(nextState)
+}
+
+func (p *Parser) reduce(prodNum int) bool {
+ lhs := p.gram.LHS(prodNum)
+ if lhs == p.gram.LHS(p.gram.StartProduction()) {
+ return true
+ }
+ n := p.gram.AlternativeSymbolCount(prodNum)
+ p.stateStack.pop(n)
+ nextState := p.gram.GoTo(p.stateStack.top(), lhs)
+ p.stateStack.push(nextState)
+ return false
+}
+
+func (p *Parser) trapError() (int, bool) {
+ count := 0
+ for {
+ if p.gram.ErrorTrapperState(p.stateStack.top()) {
+ return count, true
+ }
+
+ if p.stateStack.top() != p.gram.InitialState() {
+ p.stateStack.pop(1)
+ count++
+ } else {
+ return 0, false
+ }
+ }
+}
+
+func (p *Parser) SyntaxErrors() []*SyntaxError {
+ return p.synErrs
+}
+
+func (p *Parser) searchLookahead(state int) []string {
+ kinds := []string{}
+ termCount := p.gram.TerminalCount()
+ for term := 0; term < termCount; term++ {
+ if p.disableLAC {
+ if p.gram.Action(p.stateStack.top(), term) == 0 {
+ continue
+ }
+ } else {
+ if !p.validateLookahead(term) {
+ continue
+ }
+ }
+
+ // We don't add the error symbol to the look-ahead symbols because users cannot input the error symbol
+ // intentionally.
+ if term == p.gram.Error() {
+ continue
+ }
+
+ kinds = append(kinds, p.gram.Terminal(term))
+ }
+
+ return kinds
+}
+
+type stateStack struct {
+ items []int
+ itemsExp []int
+}
+
+func (s *stateStack) enableExploratoryMode() {
+ s.itemsExp = make([]int, len(s.items))
+ copy(s.itemsExp, s.items)
+}
+
+func (s *stateStack) disableExploratoryMode() {
+ s.itemsExp = nil
+}
+
+func (s *stateStack) top() int {
+ return s.items[len(s.items)-1]
+}
+
+func (s *stateStack) topExploratorily() int {
+ return s.itemsExp[len(s.itemsExp)-1]
+}
+
+func (s *stateStack) push(state int) {
+ s.items = append(s.items, state)
+}
+
+func (s *stateStack) pushExploratorily(state int) {
+ s.itemsExp = append(s.itemsExp, state)
+}
+
+func (s *stateStack) pop(n int) {
+ s.items = s.items[:len(s.items)-n]
+}
+
+func (s *stateStack) popExploratorily(n int) {
+ s.itemsExp = s.itemsExp[:len(s.itemsExp)-n]
+}
diff --git a/driver/parser/parser_test.go b/driver/parser/parser_test.go
new file mode 100644
index 0000000..b1b9e4f
--- /dev/null
+++ b/driver/parser/parser_test.go
@@ -0,0 +1,833 @@
+package parser
+
+import (
+ "fmt"
+ "strings"
+ "testing"
+
+ "github.com/nihei9/vartan/grammar"
+ "github.com/nihei9/vartan/spec/grammar/parser"
+)
+
+func termNode(kind string, text string, children ...*Node) *Node {
+ return &Node{
+ Type: NodeTypeTerminal,
+ KindName: kind,
+ Text: text,
+ Children: children,
+ }
+}
+
+func errorNode() *Node {
+ return &Node{
+ Type: NodeTypeError,
+ KindName: "error",
+ }
+}
+
+func nonTermNode(kind string, children ...*Node) *Node {
+ return &Node{
+ Type: NodeTypeNonTerminal,
+ KindName: kind,
+ Children: children,
+ }
+}
+
+func TestParser_Parse(t *testing.T) {
+ tests := []struct {
+ specSrc string
+ src string
+ synErr bool
+ cst *Node
+ ast *Node
+ }{
+ {
+ specSrc: `
+#name test;
+
+expr
+ : expr add term
+ | term
+ ;
+term
+ : term mul factor
+ | factor
+ ;
+factor
+ : l_paren expr r_paren
+ | id
+ ;
+
+add
+ : '+';
+mul
+ : '*';
+l_paren
+ : '(';
+r_paren
+ : ')';
+id
+ : "[A-Za-z_][0-9A-Za-z_]*";
+`,
+ src: `(a+(b+c))*d+e`,
+ cst: nonTermNode("expr",
+ nonTermNode("expr",
+ nonTermNode("term",
+ nonTermNode("term",
+ nonTermNode("factor",
+ termNode("l_paren", "("),
+ nonTermNode("expr",
+ nonTermNode("expr",
+ nonTermNode("term",
+ nonTermNode("factor",
+ termNode("id", "a"),
+ ),
+ ),
+ ),
+ termNode("add", "+"),
+ nonTermNode("term",
+ nonTermNode("factor",
+ termNode("l_paren", "("),
+ nonTermNode("expr",
+ nonTermNode("expr",
+ nonTermNode("term",
+ nonTermNode("factor",
+ termNode("id", "b"),
+ ),
+ ),
+ ),
+ termNode("add", "+"),
+ nonTermNode("term",
+ nonTermNode("factor",
+ termNode("id", "c"),
+ ),
+ ),
+ ),
+ termNode("r_paren", ")"),
+ ),
+ ),
+ ),
+ termNode("r_paren", ")"),
+ ),
+ ),
+ termNode("mul", "*"),
+ nonTermNode("factor",
+ termNode("id", "d"),
+ ),
+ ),
+ ),
+ termNode("add", "+"),
+ nonTermNode("term",
+ nonTermNode("factor",
+ termNode("id", "e"),
+ ),
+ ),
+ ),
+ },
+ // Fragments (\f{}), code point expressions (\u{}), and character property expressions (\p{}) are
+ // not allowed in string literals.
+ {
+ specSrc: `
+#name test;
+
+s
+ : a b c
+ ;
+
+a
+ : '\f{foo}';
+b
+ : '\u{0000}';
+c
+ : '\p{gc=Letter}';
+`,
+ src: `\f{foo}\u{0000}\p{gc=Letter}`,
+ cst: nonTermNode("s",
+ termNode("a", `\f{foo}`),
+ termNode("b", `\u{0000}`),
+ termNode("c", `\p{gc=Letter}`),
+ ),
+ },
+ // The driver can reduce productions that have the empty alternative and can generate a CST (and AST) node.
+ {
+ specSrc: `
+#name test;
+
+s
+ : foo bar
+ ;
+foo
+ :
+ ;
+bar
+ : bar_text
+ |
+ ;
+bar_text: "bar";
+`,
+ src: ``,
+ cst: nonTermNode("s",
+ nonTermNode("foo"),
+ nonTermNode("bar"),
+ ),
+ },
+ // The driver can reduce productions that have the empty alternative and can generate a CST (and AST) node.
+ {
+ specSrc: `
+#name test;
+
+s
+ : foo bar
+ ;
+foo
+ :
+ ;
+bar
+ : bar_text
+ |
+ ;
+
+bar_text
+ : "bar";
+`,
+ src: `bar`,
+ cst: nonTermNode("s",
+ nonTermNode("foo"),
+ nonTermNode("bar",
+ termNode("bar_text", "bar"),
+ ),
+ ),
+ },
+ // A production can have multiple alternative productions.
+ {
+ specSrc: `
+#name test;
+
+#prec (
+ #assign $uminus
+ #left mul div
+ #left add sub
+);
+
+expr
+ : expr add expr
+ | expr sub expr
+ | expr mul expr
+ | expr div expr
+ | int
+ | sub int #prec $uminus // This 'sub' means the unary minus symbol.
+ ;
+
+int
+ : "0|[1-9][0-9]*";
+add
+ : '+';
+sub
+ : '-';
+mul
+ : '*';
+div
+ : '/';
+`,
+ src: `-1*-2+3-4/5`,
+ ast: nonTermNode("expr",
+ nonTermNode("expr",
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("sub", "-"),
+ termNode("int", "1"),
+ ),
+ termNode("mul", "*"),
+ nonTermNode("expr",
+ termNode("sub", "-"),
+ termNode("int", "2"),
+ ),
+ ),
+ termNode("add", "+"),
+ nonTermNode("expr",
+ termNode("int", "3"),
+ ),
+ ),
+ termNode("sub", "-"),
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("int", "4"),
+ ),
+ termNode("div", "/"),
+ nonTermNode("expr",
+ termNode("int", "5"),
+ ),
+ ),
+ ),
+ },
+ // A lexical production can have multiple production directives.
+ {
+ specSrc: `
+#name test;
+
+s
+ : push_a push_b pop pop
+ ;
+
+push_a #mode default #push a
+ : '->a';
+push_b #mode a #push b
+ : '->b';
+pop #mode a b #pop
+ : '<-';
+`,
+ src: `->a->b<-<-`,
+ ast: nonTermNode("s",
+ termNode("push_a", "->a"),
+ termNode("push_b", "->b"),
+ termNode("pop", "<-"),
+ termNode("pop", "<-"),
+ ),
+ },
+ {
+ specSrc: `
+#name test;
+
+mode_tran_seq
+ : mode_tran_seq mode_tran
+ | mode_tran
+ ;
+mode_tran
+ : push_m1
+ | push_m2
+ | pop_m1
+ | pop_m2
+ ;
+
+push_m1 #push m1
+ : "->";
+push_m2 #mode m1 #push m2
+ : "-->";
+pop_m1 #mode m1 #pop
+ : "<-";
+pop_m2 #mode m2 #pop
+ : "<--";
+whitespace #mode default m1 m2 #skip
+ : "\u{0020}+";
+`,
+ src: ` -> --> <-- <- `,
+ },
+ {
+ specSrc: `
+#name test;
+
+s
+ : foo bar
+ ;
+
+foo
+ : "foo";
+bar #mode default
+ : "bar";
+`,
+ src: `foobar`,
+ },
+ // When #push and #pop are applied to the same symbol, #pop will run first, then #push.
+ {
+ specSrc: `
+#name test;
+
+s
+ : foo bar baz
+ ;
+
+foo #push m1
+ : 'foo';
+bar #mode m1 #pop #push m2
+ : 'bar';
+baz #mode m2
+ : 'baz';
+`,
+ src: `foobarbaz`,
+ ast: nonTermNode("s",
+ termNode("foo", "foo"),
+ termNode("bar", "bar"),
+ termNode("baz", "baz"),
+ ),
+ },
+ // When #push and #pop are applied to the same symbol, #pop will run first, then #push, even if #push appears first
+ // in a definition. That is, the order in which #push and #pop appear in grammar has nothing to do with the order in which
+ // they are executed.
+ {
+ specSrc: `
+#name test;
+
+s
+ : foo bar baz
+ ;
+
+foo #push m1
+ : 'foo';
+bar #mode m1 #push m2 #pop
+ : 'bar';
+baz #mode m2
+ : 'baz';
+`,
+ src: `foobarbaz`,
+ ast: nonTermNode("s",
+ termNode("foo", "foo"),
+ termNode("bar", "bar"),
+ termNode("baz", "baz"),
+ ),
+ },
+ // The parser can skips specified tokens.
+ {
+ specSrc: `
+#name test;
+
+s
+ : foo bar
+ ;
+
+foo
+ : "foo";
+bar
+ : "bar";
+white_space #skip
+ : "[\u{0009}\u{0020}]+";
+`,
+ src: `foo bar`,
+ },
+ // A grammar can contain fragments.
+ {
+ specSrc: `
+#name test;
+
+s
+ : tagline
+ ;
+tagline
+ : "\f{words} IS OUT THERE.";
+fragment words
+ : "[A-Za-z\u{0020}]+";
+`,
+ src: `THE TRUTH IS OUT THERE.`,
+ },
+ // A grammar can contain ast actions.
+ {
+ specSrc: `
+#name test;
+
+list
+ : l_bracket elems r_bracket #ast elems...
+ ;
+elems
+ : elems comma id #ast elems... id
+ | id
+ ;
+
+whitespace #skip
+ : "\u{0020}+";
+l_bracket
+ : '[';
+r_bracket
+ : ']';
+comma
+ : ',';
+id
+ : "[A-Za-z]+";
+`,
+ src: `[Byers, Frohike, Langly]`,
+ cst: nonTermNode("list",
+ termNode("x_1", "["),
+ nonTermNode("elems",
+ nonTermNode("elems",
+ nonTermNode("elems",
+ termNode("id", "Byers"),
+ ),
+ termNode("x_3", ","),
+ termNode("id", "Frohike"),
+ ),
+ termNode("x_3", ","),
+ termNode("id", "Langly"),
+ ),
+ termNode("x_2", "]"),
+ ),
+ ast: nonTermNode("list",
+ termNode("id", "Byers"),
+ termNode("id", "Frohike"),
+ termNode("id", "Langly"),
+ ),
+ },
+ // The '...' operator can expand child nodes.
+ {
+ specSrc: `
+#name test;
+
+s
+ : a #ast a...
+ ;
+a
+ : a comma foo #ast a... foo
+ | foo
+ ;
+
+comma
+ : ',';
+foo
+ : 'foo';
+`,
+ src: `foo,foo,foo`,
+ ast: nonTermNode("s",
+ termNode("foo", "foo"),
+ termNode("foo", "foo"),
+ termNode("foo", "foo"),
+ ),
+ },
+ // The '...' operator also can applied to an element having no children.
+ {
+ specSrc: `
+#name test;
+
+s
+ : a semi_colon #ast a...
+ ;
+a
+ :
+ ;
+
+semi_colon
+ : ';';
+`,
+ src: `;`,
+ ast: nonTermNode("s"),
+ },
+ // A label can be a parameter of #ast directive.
+ {
+ specSrc: `
+#name test;
+
+#prec (
+ #left add sub
+);
+
+expr
+ : expr@lhs add expr@rhs #ast add lhs rhs
+ | expr@lhs sub expr@rhs #ast sub lhs rhs
+ | num
+ ;
+
+add
+ : '+';
+sub
+ : '-';
+num
+ : "0|[1-9][0-9]*";
+`,
+ src: `1+2-3`,
+ ast: nonTermNode("expr",
+ termNode("sub", "-"),
+ nonTermNode("expr",
+ termNode("add", "+"),
+ nonTermNode("expr",
+ termNode("num", "1"),
+ ),
+ nonTermNode("expr",
+ termNode("num", "2"),
+ ),
+ ),
+ nonTermNode("expr",
+ termNode("num", "3"),
+ ),
+ ),
+ },
+ // An AST can contain a symbol name, even if the symbol has a label. That is, unused labels are allowed.
+ {
+ specSrc: `
+#name test;
+
+s
+ : foo@x semi_colon #ast foo
+ ;
+
+semi_colon
+ : ';';
+foo
+ : 'foo';
+`,
+ src: `foo;`,
+ ast: nonTermNode("s",
+ termNode("foo", "foo"),
+ ),
+ },
+ // A production has the same precedence and associativity as the right-most terminal symbol.
+ {
+ specSrc: `
+#name test;
+
+#prec (
+ #left add
+);
+
+expr
+ : expr add expr // This alternative has the same precedence and associativiry as 'add'.
+ | int
+ ;
+
+ws #skip
+ : "[\u{0009}\u{0020}]+";
+int
+ : "0|[1-9][0-9]*";
+add
+ : '+';
+`,
+ // This source is recognized as the following structure because the production `expr → expr add expr` has the same
+ // precedence and associativity as the symbol 'add'.
+ //
+ // ((1+2)+3)
+ //
+ // If the symbol doesn't have the precedence and left associativity, the production also doesn't have the precedence
+ // and associativity and this source will be recognized as the following structure.
+ //
+ // (1+(2+3))
+ src: `1+2+3`,
+ ast: nonTermNode("expr",
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("int", "1"),
+ ),
+ termNode("add", "+"),
+ nonTermNode("expr",
+ termNode("int", "2"),
+ ),
+ ),
+ termNode("add", "+"),
+ nonTermNode("expr",
+ termNode("int", "3"),
+ ),
+ ),
+ },
+ // The 'prec' directive can set precedence of a production.
+ {
+ specSrc: `
+#name test;
+
+#prec (
+ #assign $uminus
+ #left mul div
+ #left add sub
+);
+
+expr
+ : expr add expr
+ | expr sub expr
+ | expr mul expr
+ | expr div expr
+ | int
+ | sub int #prec $uminus // This 'sub' means a unary minus symbol.
+ ;
+
+ws #skip
+ : "[\u{0009}\u{0020}]+";
+int
+ : "0|[1-9][0-9]*";
+add
+ : '+';
+sub
+ : '-';
+mul
+ : '*';
+div
+ : '/';
+`,
+ // This source is recognized as the following structure because the production `expr → sub expr`
+ // has the `#prec mul` directive and has the same precedence of the symbol `mul`.
+ //
+ // (((-1) * 20) / 5)
+ //
+ // If the production doesn't have the `#prec` directive, this source will be recognized as
+ // the following structure.
+ //
+ // (- ((1 * 20) / 5))
+ src: `-1*20/5`,
+ cst: nonTermNode("expr",
+ nonTermNode("expr",
+ nonTermNode("expr",
+ termNode("sub", "-"),
+ termNode("int", "1"),
+ ),
+ termNode("mul", "*"),
+ nonTermNode("expr",
+ termNode("int", "20"),
+ ),
+ ),
+ termNode("div", "/"),
+ nonTermNode("expr",
+ termNode("int", "5"),
+ ),
+ ),
+ },
+ // The grammar can contain the 'error' symbol.
+ {
+ specSrc: `
+#name test;
+
+s
+ : id id id semi_colon
+ | error semi_colon
+ ;
+
+ws #skip
+ : "[\u{0009}\u{0020}]+";
+semi_colon
+ : ';';
+id
+ : "[A-Za-z_]+";
+`,
+ src: `foo bar baz ;`,
+ },
+ // The 'error' symbol can appear in an #ast directive.
+ {
+ specSrc: `
+#name test;
+
+s
+ : foo semi_colon
+ | error semi_colon #ast error
+ ;
+
+semi_colon
+ : ';';
+foo
+ : 'foo';
+`,
+ src: `bar;`,
+ synErr: true,
+ ast: nonTermNode("s",
+ errorNode(),
+ ),
+ },
+ // The 'error' symbol can have a label, and an #ast can reference it.
+ {
+ specSrc: `
+#name test;
+
+s
+ : foo semi_colon
+ | error@e semi_colon #ast e
+ ;
+
+semi_colon
+ : ';';
+foo
+ : 'foo';
+`,
+ src: `bar;`,
+ synErr: true,
+ ast: nonTermNode("s",
+ errorNode(),
+ ),
+ },
+ // The grammar can contain the 'recover' directive.
+ {
+ specSrc: `
+#name test;
+
+seq
+ : seq elem
+ | elem
+ ;
+elem
+ : id id id semi_colon
+ | error semi_colon #recover
+ ;
+
+ws #skip
+ : "[\u{0009}\u{0020}]+";
+semi_colon
+ : ';';
+id
+ : "[A-Za-z_]+";
+`,
+ src: `a b c ; d e f ;`,
+ },
+ // The same label can be used between different alternatives.
+ {
+ specSrc: `
+#name test;
+
+s
+ : foo@x bar
+ | foo@x
+ ;
+
+foo: 'foo';
+bar: 'bar';
+`,
+ src: `foo`,
+ },
+ }
+
+ for i, tt := range tests {
+ t.Run(fmt.Sprintf("#%v", i), func(t *testing.T) {
+ ast, err := parser.Parse(strings.NewReader(tt.specSrc))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ b := grammar.GrammarBuilder{
+ AST: ast,
+ }
+ cg, _, err := b.Build()
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ toks, err := NewTokenStream(cg, strings.NewReader(tt.src))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ gram := NewGrammar(cg)
+ tb := NewDefaultSyntaxTreeBuilder()
+ var opt []ParserOption
+ switch {
+ case tt.ast != nil:
+ opt = append(opt, SemanticAction(NewASTActionSet(gram, tb)))
+ case tt.cst != nil:
+ opt = append(opt, SemanticAction(NewCSTActionSet(gram, tb)))
+ }
+ p, err := NewParser(toks, gram, opt...)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ err = p.Parse()
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ if !tt.synErr && len(p.SyntaxErrors()) > 0 {
+ for _, synErr := range p.SyntaxErrors() {
+ t.Fatalf("unexpected syntax errors occurred: %v", synErr)
+ }
+ }
+
+ switch {
+ case tt.ast != nil:
+ testTree(t, tb.Tree(), tt.ast)
+ case tt.cst != nil:
+ testTree(t, tb.Tree(), tt.cst)
+ }
+ })
+ }
+}
+
+func testTree(t *testing.T, node, expected *Node) {
+ t.Helper()
+
+ if node.Type != expected.Type || node.KindName != expected.KindName || node.Text != expected.Text {
+ t.Fatalf("unexpected node; want: %+v, got: %+v", expected, node)
+ }
+ if len(node.Children) != len(expected.Children) {
+ t.Fatalf("unexpected children; want: %v, got: %v", len(expected.Children), len(node.Children))
+ }
+ for i, c := range node.Children {
+ testTree(t, c, expected.Children[i])
+ }
+}
diff --git a/driver/parser/semantic_action.go b/driver/parser/semantic_action.go
new file mode 100644
index 0000000..f709d4f
--- /dev/null
+++ b/driver/parser/semantic_action.go
@@ -0,0 +1,366 @@
+package parser
+
+import (
+ "encoding/json"
+ "fmt"
+ "io"
+ "strconv"
+)
+
+// SemanticActionSet is a set of semantic actions a parser calls.
+type SemanticActionSet interface {
+ // Shift runs when the parser shifts a symbol onto a state stack. `tok` is a token corresponding to the symbol.
+ // When the parser recovered from an error state by shifting the token, `recovered` is true.
+ Shift(tok VToken, recovered bool)
+
+ // Reduce runs when the parser reduces an RHS of a production to its LHS. `prodNum` is a number of the production.
+ // When the parser recovered from an error state by reducing the production, `recovered` is true.
+ Reduce(prodNum int, recovered bool)
+
+ // Accept runs when the parser accepts an input.
+ Accept()
+
+ // TrapAndShiftError runs when the parser traps a syntax error and shifts a error symbol onto the state stack.
+ // `cause` is a token that caused a syntax error. `popped` is the number of frames that the parser discards
+ // from the state stack.
+ // Unlike `Shift` function, this function doesn't take a token to be shifted as an argument because a token
+ // corresponding to the error symbol doesn't exist.
+ TrapAndShiftError(cause VToken, popped int)
+
+ // MissError runs when the parser fails to trap a syntax error. `cause` is a token that caused a syntax error.
+ MissError(cause VToken)
+}
+
+var _ SemanticActionSet = &SyntaxTreeActionSet{}
+
+// SyntaxTreeNode is a node of a syntax tree. A node type used in SyntaxTreeActionSet must implement SyntaxTreeNode interface.
+type SyntaxTreeNode interface {
+ // ChildCount returns a child count of a node. A parser calls this method to know the child count to be expanded by an `#ast`
+ // directive with `...` operator.
+ ChildCount() int
+
+ // ExpandChildren returns children of a node. A parser calls this method to fetch the children to be expanded by an `#ast`
+ // directive with `...` operator.
+ ExpandChildren() []SyntaxTreeNode
+}
+
+var _ SyntaxTreeNode = &Node{}
+
+// SyntaxTreeBuilder allows you to construct a syntax tree containing arbitrary user-defined node types.
+// The parser uses SyntaxTreeBuilder interface as a part of semantic actions via SyntaxTreeActionSet interface.
+type SyntaxTreeBuilder interface {
+ Shift(kindName string, text string, row, col int) SyntaxTreeNode
+ ShiftError(kindName string) SyntaxTreeNode
+ Reduce(kindName string, children []SyntaxTreeNode) SyntaxTreeNode
+ Accept(f SyntaxTreeNode)
+}
+
+var _ SyntaxTreeBuilder = &DefaulSyntaxTreeBuilder{}
+
+// DefaulSyntaxTreeBuilder is a implementation of SyntaxTreeBuilder.
+type DefaulSyntaxTreeBuilder struct {
+ tree *Node
+}
+
+// NewDefaultSyntaxTreeBuilder returns a new DefaultSyntaxTreeBuilder.
+func NewDefaultSyntaxTreeBuilder() *DefaulSyntaxTreeBuilder {
+ return &DefaulSyntaxTreeBuilder{}
+}
+
+// Shift is a implementation of SyntaxTreeBuilder.Shift.
+func (b *DefaulSyntaxTreeBuilder) Shift(kindName string, text string, row, col int) SyntaxTreeNode {
+ return &Node{
+ Type: NodeTypeTerminal,
+ KindName: kindName,
+ Text: text,
+ Row: row,
+ Col: col,
+ }
+}
+
+// ShiftError is a implementation of SyntaxTreeBuilder.ShiftError.
+func (b *DefaulSyntaxTreeBuilder) ShiftError(kindName string) SyntaxTreeNode {
+ return &Node{
+ Type: NodeTypeError,
+ KindName: kindName,
+ }
+}
+
+// Reduce is a implementation of SyntaxTreeBuilder.Reduce.
+func (b *DefaulSyntaxTreeBuilder) Reduce(kindName string, children []SyntaxTreeNode) SyntaxTreeNode {
+ cNodes := make([]*Node, len(children))
+ for i, c := range children {
+ cNodes[i] = c.(*Node)
+ }
+ return &Node{
+ Type: NodeTypeNonTerminal,
+ KindName: kindName,
+ Children: cNodes,
+ }
+}
+
+// Accept is a implementation of SyntaxTreeBuilder.Accept.
+func (b *DefaulSyntaxTreeBuilder) Accept(f SyntaxTreeNode) {
+ b.tree = f.(*Node)
+}
+
+// Tree returns a syntax tree when the parser has accepted an input. If a syntax error occurs, the return value is nil.
+func (b *DefaulSyntaxTreeBuilder) Tree() *Node {
+ return b.tree
+}
+
+// SyntaxTreeActionSet is a implementation of SemanticActionSet interface and constructs a syntax tree.
+type SyntaxTreeActionSet struct {
+ gram Grammar
+ builder SyntaxTreeBuilder
+ semStack *semanticStack
+ disableASTAction bool
+}
+
+// NewASTActionSet returns a new SyntaxTreeActionSet that constructs an AST (Abstract Syntax Tree).
+// When grammar `gram` contains `#ast` directives, the new SyntaxTreeActionSet this function returns interprets them.
+func NewASTActionSet(gram Grammar, builder SyntaxTreeBuilder) *SyntaxTreeActionSet {
+ return &SyntaxTreeActionSet{
+ gram: gram,
+ builder: builder,
+ semStack: newSemanticStack(),
+ }
+}
+
+// NewCSTTActionSet returns a new SyntaxTreeActionSet that constructs a CST (Concrete Syntax Tree).
+// Even if grammar `gram` contains `#ast` directives, the new SyntaxTreeActionSet this function returns ignores them.
+func NewCSTActionSet(gram Grammar, builder SyntaxTreeBuilder) *SyntaxTreeActionSet {
+ return &SyntaxTreeActionSet{
+ gram: gram,
+ builder: builder,
+ semStack: newSemanticStack(),
+ disableASTAction: true,
+ }
+}
+
+// Shift is a implementation of SemanticActionSet.Shift method.
+func (a *SyntaxTreeActionSet) Shift(tok VToken, recovered bool) {
+ term := a.tokenToTerminal(tok)
+ row, col := tok.Position()
+ a.semStack.push(a.builder.Shift(a.gram.Terminal(term), string(tok.Lexeme()), row, col))
+}
+
+// Reduce is a implementation of SemanticActionSet.Reduce method.
+func (a *SyntaxTreeActionSet) Reduce(prodNum int, recovered bool) {
+ lhs := a.gram.LHS(prodNum)
+
+ // When an alternative is empty, `n` will be 0, and `handle` will be empty slice.
+ n := a.gram.AlternativeSymbolCount(prodNum)
+ handle := a.semStack.pop(n)
+
+ var astAct []int
+ if !a.disableASTAction {
+ astAct = a.gram.ASTAction(prodNum)
+ }
+ var children []SyntaxTreeNode
+ if astAct != nil {
+ // Count the number of children in advance to avoid frequent growth in a slice for children.
+ {
+ l := 0
+ for _, e := range astAct {
+ if e > 0 {
+ l++
+ } else {
+ offset := e*-1 - 1
+ l += handle[offset].ChildCount()
+ }
+ }
+
+ children = make([]SyntaxTreeNode, l)
+ }
+
+ p := 0
+ for _, e := range astAct {
+ if e > 0 {
+ offset := e - 1
+ children[p] = handle[offset]
+ p++
+ } else {
+ offset := e*-1 - 1
+ for _, c := range handle[offset].ExpandChildren() {
+ children[p] = c
+ p++
+ }
+ }
+ }
+ } else {
+ // If an alternative has no AST action, a driver generates
+ // a node with the same structure as a CST.
+ children = handle
+ }
+
+ a.semStack.push(a.builder.Reduce(a.gram.NonTerminal(lhs), children))
+}
+
+// Accept is a implementation of SemanticActionSet.Accept method.
+func (a *SyntaxTreeActionSet) Accept() {
+ top := a.semStack.pop(1)
+ a.builder.Accept(top[0])
+}
+
+// TrapAndShiftError is a implementation of SemanticActionSet.TrapAndShiftError method.
+func (a *SyntaxTreeActionSet) TrapAndShiftError(cause VToken, popped int) {
+ a.semStack.pop(popped)
+ a.semStack.push(a.builder.ShiftError(a.gram.Terminal(a.gram.Error())))
+}
+
+// MissError is a implementation of SemanticActionSet.MissError method.
+func (a *SyntaxTreeActionSet) MissError(cause VToken) {
+}
+
+func (a *SyntaxTreeActionSet) tokenToTerminal(tok VToken) int {
+ if tok.EOF() {
+ return a.gram.EOF()
+ }
+
+ return tok.TerminalID()
+}
+
+type semanticStack struct {
+ frames []SyntaxTreeNode
+}
+
+func newSemanticStack() *semanticStack {
+ return &semanticStack{
+ frames: make([]SyntaxTreeNode, 0, 100),
+ }
+}
+
+func (s *semanticStack) push(f SyntaxTreeNode) {
+ s.frames = append(s.frames, f)
+}
+
+func (s *semanticStack) pop(n int) []SyntaxTreeNode {
+ fs := s.frames[len(s.frames)-n:]
+ s.frames = s.frames[:len(s.frames)-n]
+
+ return fs
+}
+
+type NodeType int
+
+const (
+ NodeTypeError = 0
+ NodeTypeTerminal = 1
+ NodeTypeNonTerminal = 2
+)
+
+// Node is a implementation of SyntaxTreeNode interface.
+type Node struct {
+ Type NodeType
+ KindName string
+ Text string
+ Row int
+ Col int
+ Children []*Node
+}
+
+func (n *Node) MarshalJSON() ([]byte, error) {
+ switch n.Type {
+ case NodeTypeError:
+ return json.Marshal(struct {
+ Type NodeType `json:"type"`
+ KindName string `json:"kind_name"`
+ }{
+ Type: n.Type,
+ KindName: n.KindName,
+ })
+ case NodeTypeTerminal:
+ if n.KindName == "" {
+ return json.Marshal(struct {
+ Type NodeType `json:"type"`
+ Text string `json:"text"`
+ Row int `json:"row"`
+ Col int `json:"col"`
+ }{
+ Type: n.Type,
+ Text: n.Text,
+ Row: n.Row,
+ Col: n.Col,
+ })
+ }
+ return json.Marshal(struct {
+ Type NodeType `json:"type"`
+ KindName string `json:"kind_name"`
+ Text string `json:"text"`
+ Row int `json:"row"`
+ Col int `json:"col"`
+ }{
+ Type: n.Type,
+ KindName: n.KindName,
+ Text: n.Text,
+ Row: n.Row,
+ Col: n.Col,
+ })
+ case NodeTypeNonTerminal:
+ return json.Marshal(struct {
+ Type NodeType `json:"type"`
+ KindName string `json:"kind_name"`
+ Children []*Node `json:"children"`
+ }{
+ Type: n.Type,
+ KindName: n.KindName,
+ Children: n.Children,
+ })
+ default:
+ return nil, fmt.Errorf("invalid node type: %v", n.Type)
+ }
+}
+
+// ChildCount is a implementation of SyntaxTreeNode.ChildCount.
+func (n *Node) ChildCount() int {
+ return len(n.Children)
+}
+
+// ExpandChildren is a implementation of SyntaxTreeNode.ExpandChildren.
+func (n *Node) ExpandChildren() []SyntaxTreeNode {
+ fs := make([]SyntaxTreeNode, len(n.Children))
+ for i, n := range n.Children {
+ fs[i] = n
+ }
+ return fs
+}
+
+// PrintTree prints a syntax tree whose root is `node`.
+func PrintTree(w io.Writer, node *Node) {
+ printTree(w, node, "", "")
+}
+
+func printTree(w io.Writer, node *Node, ruledLine string, childRuledLinePrefix string) {
+ if node == nil {
+ return
+ }
+
+ switch node.Type {
+ case NodeTypeError:
+ fmt.Fprintf(w, "%v%v\n", ruledLine, node.KindName)
+ case NodeTypeTerminal:
+ fmt.Fprintf(w, "%v%v %v\n", ruledLine, node.KindName, strconv.Quote(node.Text))
+ case NodeTypeNonTerminal:
+ fmt.Fprintf(w, "%v%v\n", ruledLine, node.KindName)
+
+ num := len(node.Children)
+ for i, child := range node.Children {
+ var line string
+ if num > 1 && i < num-1 {
+ line = "├─ "
+ } else {
+ line = "└─ "
+ }
+
+ var prefix string
+ if i >= num-1 {
+ prefix = " "
+ } else {
+ prefix = "│ "
+ }
+
+ printTree(w, child, childRuledLinePrefix+line, childRuledLinePrefix+prefix)
+ }
+ }
+}
diff --git a/driver/parser/semantic_action_test.go b/driver/parser/semantic_action_test.go
new file mode 100644
index 0000000..c98a12f
--- /dev/null
+++ b/driver/parser/semantic_action_test.go
@@ -0,0 +1,227 @@
+package parser
+
+import (
+ "fmt"
+ "strings"
+ "testing"
+
+ "github.com/nihei9/vartan/grammar"
+ spec "github.com/nihei9/vartan/spec/grammar"
+ "github.com/nihei9/vartan/spec/grammar/parser"
+)
+
+type testSemAct struct {
+ gram *spec.CompiledGrammar
+ actLog []string
+}
+
+func (a *testSemAct) Shift(tok VToken, recovered bool) {
+ t := a.gram.Syntactic.Terminals[tok.TerminalID()]
+ if recovered {
+ a.actLog = append(a.actLog, fmt.Sprintf("shift/%v/recovered", t))
+ } else {
+ a.actLog = append(a.actLog, fmt.Sprintf("shift/%v", t))
+ }
+}
+
+func (a *testSemAct) Reduce(prodNum int, recovered bool) {
+ lhsSym := a.gram.Syntactic.LHSSymbols[prodNum]
+ lhsText := a.gram.Syntactic.NonTerminals[lhsSym]
+ if recovered {
+ a.actLog = append(a.actLog, fmt.Sprintf("reduce/%v/recovered", lhsText))
+ } else {
+ a.actLog = append(a.actLog, fmt.Sprintf("reduce/%v", lhsText))
+ }
+}
+
+func (a *testSemAct) Accept() {
+ a.actLog = append(a.actLog, "accept")
+}
+
+func (a *testSemAct) TrapAndShiftError(cause VToken, popped int) {
+ a.actLog = append(a.actLog, fmt.Sprintf("trap/%v/shift/error", popped))
+}
+
+func (a *testSemAct) MissError(cause VToken) {
+ a.actLog = append(a.actLog, "miss")
+}
+
+func TestParserWithSemanticAction(t *testing.T) {
+ specSrcWithErrorProd := `
+#name test;
+
+seq
+ : seq elem semicolon
+ | elem semicolon
+ | error star star semicolon
+ | error semicolon #recover
+ ;
+elem
+ : char char char
+ ;
+
+ws #skip
+ : "[\u{0009}\u{0020}]+";
+semicolon
+ : ';';
+star
+ : '*';
+char
+ : "[a-z]";
+`
+
+ specSrcWithoutErrorProd := `
+#name test;
+
+seq
+ : seq elem semicolon
+ | elem semicolon
+ ;
+elem
+ : char char char
+ ;
+
+ws #skip
+ : "[\u{0009}\u{0020}]+";
+semicolon
+ : ';';
+char
+ : "[a-z]";
+`
+
+ tests := []struct {
+ caption string
+ specSrc string
+ src string
+ actLog []string
+ }{
+ {
+ caption: "when an input contains no syntax error, the driver calls `Shift`, `Reduce`, and `Accept`.",
+ specSrc: specSrcWithErrorProd,
+ src: `a b c; d e f;`,
+ actLog: []string{
+ "shift/char",
+ "shift/char",
+ "shift/char",
+ "reduce/elem",
+ "shift/semicolon",
+ "reduce/seq",
+
+ "shift/char",
+ "shift/char",
+ "shift/char",
+ "reduce/elem",
+ "shift/semicolon",
+ "reduce/seq",
+
+ "accept",
+ },
+ },
+ {
+ caption: "when a grammar has `error` symbol, the driver calls `TrapAndShiftError`.",
+ specSrc: specSrcWithErrorProd,
+ src: `a; b !; c d !; e ! * *; h i j;`,
+ actLog: []string{
+ "shift/char",
+ "trap/1/shift/error",
+ "shift/semicolon",
+ "reduce/seq/recovered",
+
+ "shift/char",
+ "trap/2/shift/error",
+ "shift/semicolon",
+ "reduce/seq/recovered",
+
+ "shift/char",
+ "shift/char",
+ "trap/3/shift/error",
+ "shift/semicolon",
+ "reduce/seq/recovered",
+
+ "shift/char",
+ "trap/2/shift/error",
+ "shift/star",
+ "shift/star",
+ // When the driver shifts three times, it recovers from an error.
+ "shift/semicolon/recovered",
+ "reduce/seq",
+
+ "shift/char",
+ "shift/char",
+ "shift/char",
+ "reduce/elem",
+ "shift/semicolon",
+ "reduce/seq",
+
+ // Even if the input contains syntax errors, the driver calls `Accept` when the input is accepted
+ // according to the error production.
+ "accept",
+ },
+ },
+ {
+ caption: "when the input doesn't meet the error production, the driver calls `MissError`.",
+ specSrc: specSrcWithErrorProd,
+ src: `a !`,
+ actLog: []string{
+ "shift/char",
+ "trap/1/shift/error",
+
+ "miss",
+ },
+ },
+ {
+ caption: "when a syntax error isn't trapped, the driver calls `MissError`.",
+ specSrc: specSrcWithoutErrorProd,
+ src: `a !`,
+ actLog: []string{
+ "shift/char",
+
+ "miss",
+ },
+ },
+ }
+ for _, tt := range tests {
+ t.Run(tt.caption, func(t *testing.T) {
+ ast, err := parser.Parse(strings.NewReader(tt.specSrc))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ b := grammar.GrammarBuilder{
+ AST: ast,
+ }
+ gram, _, err := b.Build()
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ toks, err := NewTokenStream(gram, strings.NewReader(tt.src))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ semAct := &testSemAct{
+ gram: gram,
+ }
+ p, err := NewParser(toks, NewGrammar(gram), SemanticAction(semAct))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ err = p.Parse()
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ if len(semAct.actLog) != len(tt.actLog) {
+ t.Fatalf("unexpected action log; want: %+v, got: %+v", tt.actLog, semAct.actLog)
+ }
+
+ for i, e := range tt.actLog {
+ if semAct.actLog[i] != e {
+ t.Fatalf("unexpected action log; want: %+v, got: %+v", tt.actLog, semAct.actLog)
+ }
+ }
+ })
+ }
+}
diff --git a/driver/parser/spec.go b/driver/parser/spec.go
new file mode 100644
index 0000000..1d57bae
--- /dev/null
+++ b/driver/parser/spec.go
@@ -0,0 +1,73 @@
+package parser
+
+import spec "github.com/nihei9/vartan/spec/grammar"
+
+type grammarImpl struct {
+ g *spec.CompiledGrammar
+}
+
+func NewGrammar(g *spec.CompiledGrammar) *grammarImpl {
+ return &grammarImpl{
+ g: g,
+ }
+}
+
+func (g *grammarImpl) InitialState() int {
+ return g.g.Syntactic.InitialState
+}
+
+func (g *grammarImpl) StartProduction() int {
+ return g.g.Syntactic.StartProduction
+}
+
+func (g *grammarImpl) RecoverProduction(prod int) bool {
+ return g.g.Syntactic.RecoverProductions[prod] != 0
+}
+
+func (g *grammarImpl) Action(state int, terminal int) int {
+ return g.g.Syntactic.Action[state*g.g.Syntactic.TerminalCount+terminal]
+}
+
+func (g *grammarImpl) GoTo(state int, lhs int) int {
+ return g.g.Syntactic.GoTo[state*g.g.Syntactic.NonTerminalCount+lhs]
+}
+
+func (g *grammarImpl) AlternativeSymbolCount(prod int) int {
+ return g.g.Syntactic.AlternativeSymbolCounts[prod]
+}
+
+func (g *grammarImpl) TerminalCount() int {
+ return g.g.Syntactic.TerminalCount
+}
+
+func (g *grammarImpl) SkipTerminal(terminal int) bool {
+ return g.g.Syntactic.TerminalSkip[terminal] == 1
+}
+
+func (g *grammarImpl) ErrorTrapperState(state int) bool {
+ return g.g.Syntactic.ErrorTrapperStates[state] != 0
+}
+
+func (g *grammarImpl) NonTerminal(nonTerminal int) string {
+ return g.g.Syntactic.NonTerminals[nonTerminal]
+}
+
+func (g *grammarImpl) LHS(prod int) int {
+ return g.g.Syntactic.LHSSymbols[prod]
+}
+
+func (g *grammarImpl) EOF() int {
+ return g.g.Syntactic.EOFSymbol
+}
+
+func (g *grammarImpl) Error() int {
+ return g.g.Syntactic.ErrorSymbol
+}
+
+func (g *grammarImpl) Terminal(terminal int) string {
+ return g.g.Syntactic.Terminals[terminal]
+}
+
+func (g *grammarImpl) ASTAction(prod int) []int {
+ return g.g.ASTAction.Entries[prod]
+}
diff --git a/driver/parser/syntax_error_test.go b/driver/parser/syntax_error_test.go
new file mode 100644
index 0000000..71175be
--- /dev/null
+++ b/driver/parser/syntax_error_test.go
@@ -0,0 +1,306 @@
+package parser
+
+import (
+ "fmt"
+ "sort"
+ "strings"
+ "testing"
+
+ "github.com/nihei9/vartan/grammar"
+ "github.com/nihei9/vartan/spec/grammar/parser"
+)
+
+func TestParserWithSyntaxErrors(t *testing.T) {
+ tests := []struct {
+ caption string
+ specSrc string
+ src string
+ synErrCount int
+ }{
+ {
+ caption: "the parser can report a syntax error",
+ specSrc: `
+#name test;
+
+s
+ : foo
+ ;
+
+foo
+ : 'foo';
+`,
+ src: `bar`,
+ synErrCount: 1,
+ },
+ {
+ caption: "when the parser reduced a production having the reduce directive, the parser will recover from an error state",
+ specSrc: `
+#name test;
+
+seq
+ : seq elem semi_colon
+ | elem semi_colon
+ | error semi_colon #recover
+ ;
+elem
+ : a b c
+ ;
+
+ws #skip
+ : "[\u{0009}\u{0020}]+";
+semi_colon
+ : ';';
+a
+ : 'a';
+b
+ : 'b';
+c
+ : 'c';
+`,
+ src: `!; a!; ab!;`,
+ synErrCount: 3,
+ },
+ {
+ caption: "After the parser shifts the error symbol, symbols are ignored until a symbol the parser can perform shift appears",
+ specSrc: `
+#name test;
+
+seq
+ : seq elem semi_colon
+ | elem semi_colon
+ | error semi_colon #recover
+ ;
+elem
+ : a b c
+ ;
+
+ws #skip
+ : "[\u{0009}\u{0020}]+";
+semi_colon
+ : ';';
+a
+ : 'a';
+b
+ : 'b';
+c
+ : 'c';
+`,
+ // After the parser trasits to the error state reading the first invalid symbol ('!'),
+ // the second and third invalid symbols ('!') are ignored.
+ src: `! ! !; a!; ab!;`,
+ synErrCount: 3,
+ },
+ {
+ caption: "when the parser performs shift three times, the parser recovers from the error state",
+ specSrc: `
+#name test;
+
+seq
+ : seq elem semi_colon
+ | elem semi_colon
+ | error star star semi_colon
+ ;
+elem
+ : a b c
+ ;
+
+ws #skip
+ : "[\u{0009}\u{0020}]+";
+semi_colon
+ : ';';
+star
+ : '*';
+a
+ : 'a';
+b
+ : 'b';
+c
+ : 'c';
+`,
+ src: `!**; a!**; ab!**; abc!`,
+ synErrCount: 4,
+ },
+ }
+ for i, tt := range tests {
+ t.Run(fmt.Sprintf("#%v", i), func(t *testing.T) {
+ ast, err := parser.Parse(strings.NewReader(tt.specSrc))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ b := grammar.GrammarBuilder{
+ AST: ast,
+ }
+ gram, _, err := b.Build()
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ toks, err := NewTokenStream(gram, strings.NewReader(tt.src))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ p, err := NewParser(toks, NewGrammar(gram))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ err = p.Parse()
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ synErrs := p.SyntaxErrors()
+ if len(synErrs) != tt.synErrCount {
+ t.Fatalf("unexpected syntax error; want: %v error(s), got: %v error(s)", tt.synErrCount, len(synErrs))
+ }
+ })
+ }
+}
+
+func TestParserWithSyntaxErrorAndExpectedLookahead(t *testing.T) {
+ tests := []struct {
+ caption string
+ specSrc string
+ src string
+ cause string
+ expected []string
+ }{
+ {
+ caption: "the parser reports an expected lookahead symbol",
+ specSrc: `
+#name test;
+
+s
+ : foo
+ ;
+
+foo
+ : 'foo';
+`,
+ src: `bar`,
+ cause: `bar`,
+ expected: []string{
+ "foo",
+ },
+ },
+ {
+ caption: "the parser reports expected lookahead symbols",
+ specSrc: `
+#name test;
+
+s
+ : foo
+ | bar
+ ;
+
+foo
+ : 'foo';
+bar
+ : 'bar';
+`,
+ src: `baz`,
+ cause: `baz`,
+ expected: []string{
+ "foo",
+ "bar",
+ },
+ },
+ {
+ caption: "the parser may report the EOF as an expected lookahead symbol",
+ specSrc: `
+#name test;
+
+s
+ : foo
+ ;
+
+foo
+ : 'foo';
+`,
+ src: `foobar`,
+ cause: `bar`,
+ expected: []string{
+ "<eof>",
+ },
+ },
+ {
+ caption: "the parser may report the EOF and others as expected lookahead symbols",
+ specSrc: `
+#name test;
+
+s
+ : foo
+ |
+ ;
+
+foo
+ : 'foo';
+`,
+ src: `bar`,
+ cause: `bar`,
+ expected: []string{
+ "foo",
+ "<eof>",
+ },
+ },
+ }
+ for i, tt := range tests {
+ t.Run(fmt.Sprintf("#%v", i), func(t *testing.T) {
+ ast, err := parser.Parse(strings.NewReader(tt.specSrc))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ b := grammar.GrammarBuilder{
+ AST: ast,
+ }
+ gram, _, err := b.Build()
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ toks, err := NewTokenStream(gram, strings.NewReader(tt.src))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ p, err := NewParser(toks, NewGrammar(gram))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ err = p.Parse()
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ synErrs := p.SyntaxErrors()
+ if synErrs == nil {
+ t.Fatalf("expected one syntax error, but it didn't occur")
+ }
+ if len(synErrs) != 1 {
+ t.Fatalf("too many syntax errors: %v errors", len(synErrs))
+ }
+ synErr := synErrs[0]
+ if string(synErr.Token.Lexeme()) != tt.cause {
+ t.Fatalf("unexpected lexeme: want: %v, got: %v", tt.cause, string(synErr.Token.Lexeme()))
+ }
+ if len(synErr.ExpectedTerminals) != len(tt.expected) {
+ t.Fatalf("unexpected lookahead symbols: want: %v, got: %v", tt.expected, synErr.ExpectedTerminals)
+ }
+ sort.Slice(tt.expected, func(i, j int) bool {
+ return tt.expected[i] < tt.expected[j]
+ })
+ sort.Slice(synErr.ExpectedTerminals, func(i, j int) bool {
+ return synErr.ExpectedTerminals[i] < synErr.ExpectedTerminals[j]
+ })
+ for i, e := range tt.expected {
+ if synErr.ExpectedTerminals[i] != e {
+ t.Errorf("unexpected lookahead symbol: want: %v, got: %v", e, synErr.ExpectedTerminals[i])
+ }
+ }
+ })
+ }
+}
diff --git a/driver/parser/template.go b/driver/parser/template.go
new file mode 100644
index 0000000..96eb71f
--- /dev/null
+++ b/driver/parser/template.go
@@ -0,0 +1,531 @@
+package parser
+
+import (
+ "bytes"
+ _ "embed"
+ "fmt"
+ "go/ast"
+ "go/format"
+ "go/parser"
+ "go/token"
+ goToken "go/token"
+ "strconv"
+ "strings"
+ "text/template"
+
+ spec "github.com/nihei9/vartan/spec/grammar"
+)
+
+//go:embed parser.go
+var parserCoreSrc string
+
+//go:embed semantic_action.go
+var semActSrc string
+
+func GenParser(cgram *spec.CompiledGrammar, pkgName string) ([]byte, error) {
+ var parserSrc string
+ {
+ fset := goToken.NewFileSet()
+ f, err := parser.ParseFile(fset, "parser.go", parserCoreSrc, parser.ParseComments)
+ if err != nil {
+ return nil, err
+ }
+
+ var b strings.Builder
+ err = format.Node(&b, fset, f)
+ if err != nil {
+ return nil, err
+ }
+
+ parserSrc = b.String()
+ }
+
+ var grammarSrc string
+ {
+ t, err := template.New("").Funcs(genGrammarTemplateFuncs(cgram)).Parse(grammarSrcTmplate)
+ if err != nil {
+ return nil, err
+ }
+
+ var b strings.Builder
+ err = t.Execute(&b, map[string]interface{}{
+ "initialState": cgram.Syntactic.InitialState,
+ "startProduction": cgram.Syntactic.StartProduction,
+ "terminalCount": cgram.Syntactic.TerminalCount,
+ "nonTerminalCount": cgram.Syntactic.NonTerminalCount,
+ "eofSymbol": cgram.Syntactic.EOFSymbol,
+ "errorSymbol": cgram.Syntactic.ErrorSymbol,
+ })
+ if err != nil {
+ return nil, err
+ }
+
+ grammarSrc = b.String()
+ }
+
+ var lexerSrc string
+ {
+ t, err := template.New("").Funcs(genLexerTemplateFuncs(cgram)).Parse(lexerSrcTmplate)
+ if err != nil {
+ return nil, err
+ }
+
+ var b strings.Builder
+ err = t.Execute(&b, nil)
+ if err != nil {
+ return nil, err
+ }
+
+ lexerSrc = b.String()
+ }
+
+ var src string
+ {
+ tmpl := `// Code generated by vartan-go. DO NOT EDIT.
+{{ .parserSrc }}
+
+{{ .grammarSrc }}
+
+{{ .lexerSrc }}
+`
+ t, err := template.New("").Parse(tmpl)
+ if err != nil {
+ return nil, err
+ }
+
+ var b strings.Builder
+ err = t.Execute(&b, map[string]string{
+ "parserSrc": parserSrc,
+ "grammarSrc": grammarSrc,
+ "lexerSrc": lexerSrc,
+ })
+ if err != nil {
+ return nil, err
+ }
+
+ src = b.String()
+ }
+
+ fset := goToken.NewFileSet()
+ f, err := parser.ParseFile(fset, "", src, parser.ParseComments)
+ if err != nil {
+ return nil, err
+ }
+
+ f.Name = ast.NewIdent(pkgName)
+
+ // Complete an import statement.
+ for _, d := range f.Decls {
+ gd, ok := d.(*ast.GenDecl)
+ if !ok || gd.Tok != token.IMPORT {
+ continue
+ }
+ gd.Specs = append(gd.Specs, &ast.ImportSpec{
+ Path: &ast.BasicLit{
+ Value: `"io"`,
+ },
+ })
+ break
+ }
+
+ var b bytes.Buffer
+ err = format.Node(&b, fset, f)
+ if err != nil {
+ return nil, err
+ }
+
+ return b.Bytes(), nil
+}
+
+const grammarSrcTmplate = `
+type grammarImpl struct {
+ recoverProductions []int
+ action []int
+ goTo []int
+ alternativeSymbolCounts []int
+ errorTrapperStates []int
+ nonTerminals []string
+ lhsSymbols []int
+ terminals []string
+ terminalSkip []int
+ astActions [][]int
+}
+
+func NewGrammar() *grammarImpl {
+ return &grammarImpl{
+ recoverProductions: {{ genRecoverProductions }},
+ action: {{ genAction }},
+ goTo: {{ genGoTo }},
+ alternativeSymbolCounts: {{ genAlternativeSymbolCounts }},
+ errorTrapperStates: {{ genErrorTrapperStates }},
+ nonTerminals: {{ genNonTerminals }},
+ lhsSymbols: {{ genLHSSymbols }},
+ terminals: {{ genTerminals }},
+ terminalSkip: {{ genTerminalSkip }},
+ astActions: {{ genASTActions }},
+ }
+}
+
+func (g *grammarImpl) InitialState() int {
+ return {{ .initialState }}
+}
+
+func (g *grammarImpl) StartProduction() int {
+ return {{ .startProduction }}
+}
+
+func (g *grammarImpl) RecoverProduction(prod int) bool {
+ return g.recoverProductions[prod] != 0
+}
+
+func (g *grammarImpl) Action(state int, terminal int) int {
+ return g.action[state*{{ .terminalCount }}+terminal]
+}
+
+func (g *grammarImpl) GoTo(state int, lhs int) int {
+ return g.goTo[state*{{ .nonTerminalCount }}+lhs]
+}
+
+func (g *grammarImpl) AlternativeSymbolCount(prod int) int {
+ return g.alternativeSymbolCounts[prod]
+}
+
+func (g *grammarImpl) TerminalCount() int {
+ return {{ .terminalCount }}
+}
+
+func (g *grammarImpl) SkipTerminal(terminal int) bool {
+ return g.terminalSkip[terminal] == 1
+}
+
+func (g *grammarImpl) ErrorTrapperState(state int) bool {
+ return g.errorTrapperStates[state] != 0
+}
+
+func (g *grammarImpl) NonTerminal(nonTerminal int) string {
+ return g.nonTerminals[nonTerminal]
+}
+
+func (g *grammarImpl) LHS(prod int) int {
+ return g.lhsSymbols[prod]
+}
+
+func (g *grammarImpl) EOF() int {
+ return {{ .eofSymbol }}
+}
+
+func (g *grammarImpl) Error() int {
+ return {{ .errorSymbol }}
+}
+
+func (g *grammarImpl) Terminal(terminal int) string {
+ return g.terminals[terminal]
+}
+
+func (g *grammarImpl) ASTAction(prod int) []int {
+ return g.astActions[prod]
+}
+`
+
+func genGrammarTemplateFuncs(cgram *spec.CompiledGrammar) template.FuncMap {
+ return template.FuncMap{
+ "genRecoverProductions": func() string {
+ var b strings.Builder
+ fmt.Fprintf(&b, "[]int{\n")
+ c := 1
+ for _, v := range cgram.Syntactic.RecoverProductions {
+ fmt.Fprintf(&b, "%v, ", v)
+ if c == 20 {
+ fmt.Fprintf(&b, "\n")
+ c = 1
+ } else {
+ c++
+ }
+ }
+ if c > 1 {
+ fmt.Fprintf(&b, "\n")
+ }
+ fmt.Fprintf(&b, "}")
+ return b.String()
+ },
+ "genAction": func() string {
+ var b strings.Builder
+ fmt.Fprintf(&b, "[]int{\n")
+ c := 1
+ for _, v := range cgram.Syntactic.Action {
+ fmt.Fprintf(&b, "%v, ", v)
+ if c == 20 {
+ fmt.Fprintf(&b, "\n")
+ c = 1
+ } else {
+ c++
+ }
+ }
+ if c > 1 {
+ fmt.Fprintf(&b, "\n")
+ }
+ fmt.Fprintf(&b, "}")
+ return b.String()
+ },
+ "genGoTo": func() string {
+ var b strings.Builder
+ fmt.Fprintf(&b, "[]int{\n")
+ c := 1
+ for _, v := range cgram.Syntactic.GoTo {
+ fmt.Fprintf(&b, "%v, ", v)
+ if c == 20 {
+ fmt.Fprintf(&b, "\n")
+ c = 1
+ } else {
+ c++
+ }
+ }
+ if c > 1 {
+ fmt.Fprintf(&b, "\n")
+ }
+ fmt.Fprintf(&b, "}")
+ return b.String()
+ },
+ "genAlternativeSymbolCounts": func() string {
+ var b strings.Builder
+ fmt.Fprintf(&b, "[]int{\n")
+ c := 1
+ for _, v := range cgram.Syntactic.AlternativeSymbolCounts {
+ fmt.Fprintf(&b, "%v, ", v)
+ if c == 20 {
+ fmt.Fprintf(&b, "\n")
+ c = 1
+ } else {
+ c++
+ }
+ }
+ if c > 1 {
+ fmt.Fprintf(&b, "\n")
+ }
+ fmt.Fprintf(&b, "}")
+ return b.String()
+ },
+ "genErrorTrapperStates": func() string {
+ var b strings.Builder
+ fmt.Fprintf(&b, "[]int{\n")
+ c := 1
+ for _, v := range cgram.Syntactic.ErrorTrapperStates {
+ fmt.Fprintf(&b, "%v, ", v)
+ if c == 20 {
+ fmt.Fprintf(&b, "\n")
+ c = 1
+ } else {
+ c++
+ }
+ }
+ if c > 1 {
+ fmt.Fprintf(&b, "\n")
+ }
+ fmt.Fprintf(&b, "}")
+ return b.String()
+ },
+ "genNonTerminals": func() string {
+ var b strings.Builder
+ fmt.Fprintf(&b, "[]string{\n")
+ for _, v := range cgram.Syntactic.NonTerminals {
+ fmt.Fprintf(&b, "%v,\n", strconv.Quote(v))
+ }
+ fmt.Fprintf(&b, "}")
+ return b.String()
+ },
+ "genLHSSymbols": func() string {
+ var b strings.Builder
+ fmt.Fprintf(&b, "[]int{\n")
+ c := 1
+ for _, v := range cgram.Syntactic.LHSSymbols {
+ fmt.Fprintf(&b, "%v, ", v)
+ if c == 20 {
+ fmt.Fprintf(&b, "\n")
+ c = 1
+ } else {
+ c++
+ }
+ }
+ if c > 1 {
+ fmt.Fprintf(&b, "\n")
+ }
+ fmt.Fprintf(&b, "}")
+ return b.String()
+ },
+ "genTerminals": func() string {
+ var b strings.Builder
+ fmt.Fprintf(&b, "[]string{\n")
+ for _, v := range cgram.Syntactic.Terminals {
+ fmt.Fprintf(&b, "%v,\n", strconv.Quote(v))
+ }
+ fmt.Fprintf(&b, "}")
+ return b.String()
+ },
+ "genTerminalSkip": func() string {
+ var b strings.Builder
+ fmt.Fprintf(&b, "[]int{\n")
+ c := 1
+ for _, v := range cgram.Syntactic.TerminalSkip {
+ fmt.Fprintf(&b, "%v, ", v)
+ if c == 20 {
+ fmt.Fprintf(&b, "\n")
+ c = 1
+ } else {
+ c++
+ }
+ }
+ if c > 1 {
+ fmt.Fprintf(&b, "\n")
+ }
+ fmt.Fprintf(&b, "}")
+ return b.String()
+ },
+ "genASTActions": func() string {
+ var b strings.Builder
+ fmt.Fprintf(&b, "[][]int{\n")
+ for _, entries := range cgram.ASTAction.Entries {
+ if len(entries) == 0 {
+ fmt.Fprintf(&b, "nil,\n")
+ continue
+ }
+
+ fmt.Fprintf(&b, "{\n")
+ c := 1
+ for _, v := range entries {
+ fmt.Fprintf(&b, "%v, ", v)
+ if c == 20 {
+ fmt.Fprintf(&b, "\n")
+ c = 1
+ } else {
+ c++
+ }
+ }
+ if c > 1 {
+ fmt.Fprintf(&b, "\n")
+ }
+ fmt.Fprintf(&b, "},\n")
+ }
+ fmt.Fprintf(&b, "}")
+ return b.String()
+ },
+ }
+}
+
+const lexerSrcTmplate = `
+type vToken struct {
+ terminalID int
+ tok *Token
+}
+
+func (t *vToken) TerminalID() int {
+ return t.terminalID
+}
+
+func (t *vToken) Lexeme() []byte {
+ return t.tok.Lexeme
+}
+
+func (t *vToken) EOF() bool {
+ return t.tok.EOF
+}
+
+func (t *vToken) Invalid() bool {
+ return t.tok.Invalid
+}
+
+func (t *vToken) Position() (int, int) {
+ return t.tok.Row, t.tok.Col
+}
+
+var kindToTerminal = {{ genKindToTerminal }}
+
+type tokenStream struct {
+ lex *Lexer
+ kindToTerminal []int
+}
+
+func NewTokenStream(src io.Reader) (*tokenStream, error) {
+ lex, err := NewLexer(NewLexSpec(), src)
+ if err != nil {
+ return nil, err
+ }
+
+ return &tokenStream{
+ lex: lex,
+ }, nil
+}
+
+func (t *tokenStream) Next() (VToken, error) {
+ tok, err := t.lex.Next()
+ if err != nil {
+ return nil, err
+ }
+ return &vToken{
+ terminalID: kindToTerminal[tok.KindID],
+ tok: tok,
+ }, nil
+}
+`
+
+func genLexerTemplateFuncs(cgram *spec.CompiledGrammar) template.FuncMap {
+ return template.FuncMap{
+ "genKindToTerminal": func() string {
+ var b strings.Builder
+ fmt.Fprintf(&b, "[]int{\n")
+ c := 1
+ for _, v := range cgram.Syntactic.KindToTerminal {
+ fmt.Fprintf(&b, "%v, ", v)
+ if c == 20 {
+ fmt.Fprintf(&b, "\n")
+ c = 1
+ } else {
+ c++
+ }
+ }
+ if c > 1 {
+ fmt.Fprintf(&b, "\n")
+ }
+ fmt.Fprintf(&b, "}")
+ return b.String()
+ },
+ }
+}
+
+func GenSemanticAction(pkgName string) ([]byte, error) {
+ var src string
+ {
+ tmpl := `// Code generated by vartan-go. DO NOT EDIT.
+{{ .semActSrc }}
+`
+ t, err := template.New("").Parse(tmpl)
+ if err != nil {
+ return nil, err
+ }
+
+ var b strings.Builder
+ err = t.Execute(&b, map[string]string{
+ "semActSrc": semActSrc,
+ })
+ if err != nil {
+ return nil, err
+ }
+
+ src = b.String()
+ }
+
+ fset := goToken.NewFileSet()
+ f, err := parser.ParseFile(fset, "", src, parser.ParseComments)
+ if err != nil {
+ return nil, err
+ }
+
+ f.Name = ast.NewIdent(pkgName)
+
+ var b bytes.Buffer
+ err = format.Node(&b, fset, f)
+ if err != nil {
+ return nil, err
+ }
+
+ return b.Bytes(), nil
+}
diff --git a/driver/parser/token_stream.go b/driver/parser/token_stream.go
new file mode 100644
index 0000000..0bc9e32
--- /dev/null
+++ b/driver/parser/token_stream.go
@@ -0,0 +1,61 @@
+package parser
+
+import (
+ "io"
+
+ "github.com/nihei9/vartan/driver/lexer"
+ spec "github.com/nihei9/vartan/spec/grammar"
+)
+
+type vToken struct {
+ terminalID int
+ tok *lexer.Token
+}
+
+func (t *vToken) TerminalID() int {
+ return t.terminalID
+}
+
+func (t *vToken) Lexeme() []byte {
+ return t.tok.Lexeme
+}
+
+func (t *vToken) EOF() bool {
+ return t.tok.EOF
+}
+
+func (t *vToken) Invalid() bool {
+ return t.tok.Invalid
+}
+
+func (t *vToken) Position() (int, int) {
+ return t.tok.Row, t.tok.Col
+}
+
+type tokenStream struct {
+ lex *lexer.Lexer
+ kindToTerminal []int
+}
+
+func NewTokenStream(g *spec.CompiledGrammar, src io.Reader) (TokenStream, error) {
+ lex, err := lexer.NewLexer(lexer.NewLexSpec(g.Lexical), src)
+ if err != nil {
+ return nil, err
+ }
+
+ return &tokenStream{
+ lex: lex,
+ kindToTerminal: g.Syntactic.KindToTerminal,
+ }, nil
+}
+
+func (l *tokenStream) Next() (VToken, error) {
+ tok, err := l.lex.Next()
+ if err != nil {
+ return nil, err
+ }
+ return &vToken{
+ terminalID: l.kindToTerminal[tok.KindID],
+ tok: tok,
+ }, nil
+}
generated by cgit v1.2.3 (git 2.49.0) at 2025-07-12 23:30:25 +0000