go で parser を実装してみた ::

昨日の ldap スキーマ parser 実装の続き。parser generator は使わず自分で parser を実装してみることにした。go の標準ライブラリにある text/scanner を使って字句解析をしたら、次のカスタマイズを行うことでそれっぽく token に分解できた。

s.Mode ^= scanner.ScanFloats
s.IsIdentRune = func(ch rune, i int) bool {
	return ch == '.' ||
		unicode.IsLetter(ch) ||
		unicode.IsDigit(ch)
}

しかし、text/scanner はあくまで go のソースコードを字句解析するためのツールになる。ldap スキーマの字句解析も一応は意図したように分割できたが 'objectClass' のようなシングルクォートで文字列を囲むような構文を go のソースコードでは記述できないため、エラーをチェックすると invalid char literal として必ずエラーになってしまう。これでは字句解析のエラーチェックをできなくなってしまうため text/scanner の利用は断念した。

そこで bufio#Scanner を使って字句解析を実装した。字句解析を行うツールを lexer または tokenizer と呼ぶ。go ではこのツールを scanner と呼ぶ慣習になってるようにみえる。分割する token をカスタマイズするには SplitFunc を定義する。ldap スキーマの字句解析は次のように定義できた。

const (
	singleQuote byte = '\''
)

func tokenize(
	data []byte, atEOF bool,
) (
	advance int, token []byte, err error,
) {
	advance, token, err = bufio.ScanWords(data, atEOF)
	if err != nil {
		return
	}
	if len(token) > 0 && token[0] == singleQuote {
		since := 0
		if data[0] != singleQuote {
			since = bytes.IndexByte(data, singleQuote)
		}
		i := bytes.IndexByte(data[since+1:], singleQuote)
		if i == -1 {
			return 0, data, bufio.ErrFinalToken
		}
		pos := since + i + 2
		return pos, data[since:pos], nil
	}
	return
}

func NewScanner(src string) *bufio.Scanner {
	s := bufio.NewScanner(strings.NewReader(src))
	s.Split(tokenize)
	return s
}

次のような ldap スキーマの文字列は、

( 2.5.4.0 NAME 'objectClass' DESC 'RFC4512: object classes of the entity' EQUALITY objectIdentifierMatch SYNTAX 1.3.6.1.4.1.1466.115.121.1.38 )

次のように token として分割される。

(
2.5.4.0
NAME
'objectClass'
DESC
'RFC4512: object classes of the entity'
EQUALITY
objectIdentifierMatch
SYNTAX
1.3.6.1.4.1.1466.115.121.1.38
)

あとはこれらの token から構文解析を行う parser を実装するだけ。AttributeTypeDescription の文法は次になる。

AttributeTypeDescription = "(" whsp
      numericoid whsp              ; AttributeType identifier
    [ "NAME" qdescrs ]             ; name used in AttributeType
    [ "DESC" qdstring ]            ; description
    [ "OBSOLETE" whsp ]
    [ "SUP" woid ]                 ; derived from this other
                                   ; AttributeType
    [ "EQUALITY" woid              ; Matching Rule name
    [ "ORDERING" woid              ; Matching Rule name
    [ "SUBSTR" woid ]              ; Matching Rule name
    [ "SYNTAX" whsp noidlen whsp ] ; Syntax OID
    [ "SINGLE-VALUE" whsp ]        ; default multi-valued
    [ "COLLECTIVE" whsp ]          ; default not collective
    [ "NO-USER-MODIFICATION" whsp ]; default user modifiable
    [ "USAGE" whsp AttributeUsage ]; default userApplications
    whsp ")"

AttributeUsage =
    "userApplications"     /
    "directoryOperation"   /
    "distributedOperation" / ; DSA-shared
    "dSAOperation"          ; DSA-specific, value depends on server

字句解析する scanner と組み合わせて実装した parser は次のようになる。

func ParseAttributeTypeDescription(
	src string,
) (*AttributeTypeDescription, error) {
	var err error
	d := &AttributeTypeDescription{}
	s := NewScanner(src)
	for s.Scan() {
		token := s.Text()
		switch token {
		case leftParenthesis:
			if s.Scan() {
				d.OID = OID{Value: s.Text()}
			}
		case rightParenthesis:
			// do nothing
		case "NAME":
			if s.Scan() {
				d.Name = ParseNAME(s)
			}
		case "DESC":
			if s.Scan() {
				d.Desc = Unquote(s.Text())
			}
		case "OBSOLETE":
			d.Obsolete = true
		case "SUP":
			if s.Scan() {
				d.Sup = NewWOID(s.Text())
			}
		case "EQUALITY":
			if s.Scan() {
				d.Equality = NewWOID(s.Text())
			}
		case "ORDERING":
			if s.Scan() {
				d.Ordering = NewWOID(s.Text())
			}
		case "SUBSTR":
			if s.Scan() {
				d.SubStr = NewWOID(s.Text())
			}
		case "SYNTAX":
			if s.Scan() {
				d.Syntax, err = ParseNOIDLen(s.Text())
				if err != nil {
					return nil, fmt.Errorf("failed to parse SYNTAX: %w", err)
				}
			}
		case "SINGLE-VALUE":
			d.SingleValue = true
		case "COLLECTIVE":
			d.Collective = true
		case "NO-USER-MODIFICATION":
			d.NoUserModification = true
		case "USAGE":
			if s.Scan() {
				usage := GetAttributeTypeUsage(s.Text())
				d.Usage = &usage
			}
		default:
			if strings.HasPrefix(token, "X-") {
				if s.Scan() {
					if d.Extension == nil {
						d.Extension = make(map[string][]string)
					}
					d.Extension[token] = ParseQuotedStrings(s)
				}
				break
			}
			slog.Warn("unsupported", "token", token, "oid", d.OID, "name", d.Name)
		}
	}
	if err := s.Err(); err != nil {
		return nil, fmt.Errorf("failed to scan: %w", err)
	}
	return d, nil
}

昨日の調査で go 製の parser generator をあまりみつけられなかったことに気付いた。その理由を理解できた。go で初めて parser を実装してみて簡単に実装できることに気付いた。標準ライブラリにある text/scanner や bufio#Scanner を使うと簡単に字句解析できるため、自分で parser を実装する労力が小さい。したがって parser generator を使って実装するよりも、自分で parser を実装することを選ぶ開発者が多いのではないかと推測する。