दममीज़ के लिए प्रैट पर्सर्स

पुनरावर्ती वंश कार्य आदर्श रूप से तब होता है जब आप वर्तमान संदर्भ और टोकन का उपयोग करके कोड के एक टुकड़े के बारे में निर्णय कर सकते हैं।

भाव चित्र को खराब करते हैं : पोस्टफ़िक्स, इन्फिक्स और अन्य। समस्या: आप समझ नहीं सकते हैं कि जब तक आप इसकी पहली छमाही को पार्स नहीं करते हैं तब तक आप किस प्रकार की अभिव्यक्ति कर रहे हैं। अक्सर ऑपरेशन की प्राथमिकता और इसकी सहयोगीता आपके लिए भी महत्वपूर्ण है ताकि निर्मित एएसटी में सही संरचना हो।

इस लेख में, हम गो बोली के लिए एक पार्सर लिखेंगे, जिन विशेषताओं पर हम थोड़ी देर बाद विचार करेंगे। जैसा कि आप देख सकते हैं, प्रैट एल्गोरिथ्म हमारी अधिकांश समस्याओं को हल करता है।

गो ++ और ++ गो

शाब्दिक विश्लेषण पर समय बर्बाद न करने के लिए , हम मानक पुस्तकालय से अपनी जरूरत की हर चीज लेंगे:

• गो / स्कैनर आपको पाठ से टोकन का एक सेट प्राप्त करने की अनुमति देता है
• go/token , scanner

, , :

type Token struct {
    kind  token.Token //  () , INT/IDENT/ADD
    value string      //   
}

scanner.Scanner lexer, :

• Peek() — ,
• Consume() — ,

go/ast, , .

Go right-associative , .

Go — statement, expression. . , .

. , , .

. , README : github.com/richardjennings/prattparser.

, .

// exprNode     AST.
type exprNode interface {
    expr()
}

type nameExpr struct {
    Value string
}

type prefixExpr struct {
    Op  token.Token //  , , '+'  '-'
    Arg exprNode    //   
}

func (e *nameExpr) expr()   {}
func (e *prefixExpr) expr() {}

, parseExpr(), :

func (p *exprParser) parseExpr() exprNode {
    tok := p.lexer.Consume()
    switch tok.kind {
    case token.IDENT:
        return p.parseName(tok)
    case token.ADD, token.SUB:
        return p.parsePrefixExpr(tok)
    case token.LPAREN:
        return p.parseParenExpr(tok)
    // ...   
    }
}

func (p *exprParser) parseName(tok Token) exprNode {
    return &nameExpr{Value: tok.value}
}

func (p *exprParser) parsePrefixExpr(tok Token) exprNode {
    arg := p.parseExpr()
    return &prefixExpr{Op: tok.kind, Arg: arg}
}

- .

, . , -, parsePrefixExpr(), map , . , , map.

, prefixParselet:

type prefixParselet func(Token) exprNode

map[token.Token]prefixParselet. :

func newExprParser() *exprParser {
    p := &exprParser{
        prefixParselets: make(map[token.Token]prefixParselet),
    }

    prefixExpr := func(kinds ...token.Token) {
        for _, kind := range kinds {
            p.prefixParselets[kind] = p.parsePrefixExpr
        }
    }

    p.prefixParselets[token.IDENT] = p.parseName
    prefixExpr(token.ADD, token.SUB)

    return p
}

prefixExpr() . , (. ).

func (p *exprParser) parseExpr() exprNode {
  tok := p.lexer.consume()
  prefix, ok := p.prefixParselets[tok.kind]
  if !ok {
    // Parse error: unexpected token
  }
  return prefix(tok)
}

, x+y.

nameExpr{Value:"x"}, +. , .

infixParselet, prefixParselet , Expr, . x+y x.

type infixParselet func(left exprNode, tok Token) exprNode

map. , .

, + - binaryExpr:

func (p *exprParser) parseBinaryExpr(left exprNode, tok token) exprNode {
    right := p.parseExpr()
    return &binaryExpr{Op: tok.kind, Left: left, Right: right}
}

parseExpr() :

func (p *exprParser) parseExpr() exprNode {
    tok := p.lexer.Consume()
    prefix, ok := p.prefixParselets[tok.kind]
    if !ok {
        // Parse error: unexpected token
    }
    left := prefix(tok)
    tok = p.lexer.Peek()
    infix, ok := p.infixParselets[tok.kind]
    if !ok {
        return left
    }
    p.lexer.Consume() //  skip/discard  
    return infix(left, tok)
}

:

1. -: x-y-z => x-(y-z)
2. : x*y+z => x*(y+z)

, .

{token.Token => precedence}. , , :

p.prefixPrecedenceTab = map[token.Token]int{
    token.ADD: 4,
    token.SUB: 4,
}

p.infixPrecedenceTab = map[token.Token]int{
    token.ADD: 2,
    token.SUB: 2,
    token.MUL: 3,
    token.QUO: 3,
    // ...   
}

parseExpr() precedence:

func (p *exprParser) parseExpr(precedence int) exprNode {
    tok := p.lexer.Consume()
    prefix, ok := p.prefixParselets[tok.kind]
    if !ok {
        // Parse error: unexpected token
    }
    left := prefix(tok)

    for precedence < p.infixPrecedenceTab[p.lexer.Peek().kind] {
        tok := p.lexer.Consume()
        infix := p.infixParselets[tok.kind]
        left = infix(left, tok)
    }

    return left
}

, , , AST.

precedence () parseExpr():

func (p *exprParser) parseBinaryExpr(left exprNode, tok Token) exprNode {
    right := p.parseExpr(p.infixPrecedenceTab[tok.kind])
    return &binaryExpr{Op: tok.kind, Left: left, Right: right}
}

parseBinaryExpr() -. - , 1 :

func (p *exprParser) rparseBinaryExpr(left exprNode, tok Token) exprNode {
    right := p.parseExpr(p.infixPrecedenceTab[tok.kind] - 1)
    return &binaryExpr{Op: tok.kind, Left: left, Right: right}
}

, << -, rparseBinaryExpr().

— infixParselet, '(' parseExpr(0) , ')'.

() — prefixParselet, '(' parseExpr(0), ')'.

func (p *exprParser) parseParenExpr(tok Token) exprNode {
    x := p.parseExpr(0)
    p.expect(token.RPAREN)
    return x
}

— infixParselet:

func (p *exprParser) parsePostfixExpr(left exprNode, tok Token) exprNode {
    return &postfixExpr{Op: tok.kind, Arg: left}
}

, , .

, , , helper- precedence:

prefixExpr := func(precedence int, kinds ...token.Token) {
    for _, kind := range kinds {
        p.prefixParselets[kind] = p.parsePrefixExpr
        p.prefixPrecedenceTab[kind] = precedence
    }
}

:

addPrefixParselet(token.LPAREN, 0, p.parseParenExpr)
addPrefixParselet(token.IDENT, 0, p.parseNameExpr)
leftAssocBinaryExpr(1, token.LOR)  // ||
leftAssocBinaryExpr(2, token.LAND) // &&
leftAssocBinaryExpr(3,
    token.EQL, // ==
    token.NEQ, // !=
)
rightAssocBinaryExpr(4,
    token.SHL, // <<
)
leftAssocBinaryExpr(4,
    token.ADD, // +
    token.SUB, // -
    token.SHR, // >>
)
leftAssocBinaryExpr(5,
    token.MUL, // *
    token.QUO, // /
    token.REM, // %
)
prefixExpr(6,
    token.ADD, // +
    token.SUB, // -
    token.INC, // ++
    token.DEC, // --
)
postfixExpr(7,
    token.INC, // ++
    token.DEC, // --
)
addInfixParselet(token.LPAREN, 8, p.parseCallExpr)

, , PrecAdd=3, PrecMult=4 .

map.

, , newExprParser . prefixParselet infixParslet , — *exprParser.

, , . , : , — .

Pratt Parsers: Expression Parsing Made Easy (Bob Nystrom). , , , , ", ".

, .

github.com/quasilyte/pratt-parsers-go.

: github.com/richardjennings/prattparser.

:

• JavaScript