Հաշվարկիչ վերագրման և արտածման հրամաններով

Այս անգամ ես ներկայացնում եմ հաշվարկիչի մի նոր զարգացում, որտեղ ավելացված են փոփոխականին արժեքի վերագրման և արտահայտության արժեքի արտածման հրամանները։ Ի տարբերություն միայն թվաբանական գործողություններ կատարող հաշվարկիչի, փոփոխականներով հաշվարկիչը հնարավորություն է տալիս պահպանել և կրկին օգտագործել հաշվարկման արդյունքները։ Օրինակ, կարելի է գրել հետևյալ հրամանները․

a = 5
b = 4
print a + 1 + b

որոնց կատարումից հետո հաշվարկիչը կարտածի 10 արդյունքը։

Պետք է նկատի ունենալ, որ վերագրման և արտածման գործողությունները հրամաններ են, այլ ոչ թե արտահայտություններ։

Նոր քերականությունը

Հրամանների ավելացմամբ հաշվարկիչի լեզվի քերականությունն ընդլայնվում է և ստանում է ահա այսպիսի տեսք։

Statement = Assignment 
          | Print.
Assignment = 'Ident' '=' Expr.
Print = 'print' Expr.
Expr = Term {('+' | '-') Term}.
Term = Factor {('*' | '/') Factor}.
Factor = '(' Expr ')'
       | '-' Factor
       | 'Number'
       | 'Ident'.

Կատարման միջավայր

Քանի որ հաշվարկիչը պետք է կարողանա հիշել փոփոխականների արժեքները, սահմանենք Environment կառուցվածքը, որը մասնակցելու է հրամանների կատարման և արտահայտությունների հաշվարկման պրոցեսին և որի միջոցով փոխանցվելու են փոփոխականների արժեքները։

package environ

import "math/big"

Environment կառուցվածքը պարունակում է data դաշտը, որը արտապատկերում է փոփոխականի անունները արժեքներին։ Արտապատկերումը կազմակերպելու համար օգտագործված է Go լեզվի map օբյեկտը։

type Environment struct {
  data map[string]*big.Int
}

Միջավայրի կոնստրուկտորը պարզապես ստեղծում և վերադարձնում է նոր Environment օբյեկտի ցուցիչ։

func New() *Environment {
  return &Environment{data: make(map[string]*big.Int)}
}

Փոփոխականների արժեքները միջավայրում ավելացվում կամ թարմացվում են Set մեթոդով։

func (e *Environment) Set(name string, value *big.Int) {
  e.data[name] = value
}

Որևէ փոփոխականի արժեքը միջավայրից ստանալու համար է նախատեսված Get մեթոդը։

func (e *Environment) Get(name string) *big.Int {
  value, _ := e.data[name]
  return value
}

Աբստրակտ քերականական ծառի ընդլայոնում

Քերականության Factor արտածման կանոնում ավելացել է նոր ճյուղ՝ 'Ident', որը ցույց է տալիս, որ փոփոխականները նույնպես արտահայտություն են։ Ընդլայնենք asteval փաթեթի Expression կառուցվածքն այնպես, որ այն սպասարկի նաև փոփոխականները։

type Expression struct {
  class byte
  value *big.Int
  varname string
  operation rune
  first, second *Expression
}

Իսկ արտահայտության տիպը որոշող հաստատունների ցուցակում ավելացնենք ևս մեկ հաստատուն՝ variable։

const (
  number byte = iota
  variable
  unary
  binary
)

Բնականաբար պետք է ունենալ նաև նոր կոնստրուկտոր, որը կառուցում է փոփոխականին համապատասխան հանգույց.

func Variable(nam string) *Expression {
  return &Expression{class: variable, varname: nam}
}

Փոփոխության է ենթարկվում նաև արտահայտության արժեքը հաշվարկող Evaluate մեթոդը։ Այժմ այն իր արգումենտում ստանում է հաշվարկման միջավայրը՝ Environment կառուցվածքի ցուցիչ, որից վերցնելու ենք փոփոխականի արժեքը։

func (e *Expression) Evaluate(env *environ.Environment) *big.Int {
  var res *big.Int = new(big.Int)

  switch e.class {
    case number:
      res.Set(e.value)
    case variable:
      res.Set(env.Get(e.varname))
    case unary:
      res = e.first.Evaluate(env)
      if '-' == e.operation { res.Neg(res) }
    case binary:
      exo := e.first.Evaluate(env)
      exi := e.second.Evaluate(env)
      switch e.operation {
        case '+': res.Add(exo, exi)
        case '-': res.Sub(exo, exi)
        case '*': res.Mul(exo, exi)
        case '/': res.Div(exo, exi)
      }
  }

  return res
}

Լեզվի քերականության մեջ ավելացել է հրամանի հասկացությունը՝ Statement, իր երկու ներկայացումներով՝ Assignment և Print։ Հրամանների աբստրակտ քերականական ծառը կառուցելու համար ստեղծենք նոր փաթեթ.

package astexec

import (
  "asteval"
  "fmt"
  "environ"
)

Սահմանենք Statement ինտերֆեյսը, որի Execute մեթոդով իրականացնելու ենք տարբեր հրամանների վարքը.

type Statement interface {
  Execute(env *environ.Environment)
}

Վերագրման հրամանն իրականացված է Assignment կառուցվածքով, որի name դաշտը փոփոխականի անունն է, իսկ expr դաշտը այն արտահայտությունն է, որի արժեքը միջավայրում պետք է կապել փոփոխականի հետ։

type Assignment struct {
  name string
  expr *asteval.Expression
}

Կոնստրուկտորը շատ պարզ է։

func NewAssignment(nm string, ex *asteval.Expression) *Assignment {
  return &Assignment{name: nm, expr: ex}
}

Execute մեթոդի իրականացումը նախ հաշվում է expr արտահայտության արժեքը, ապա միջավայրում ավելացնում է նոր համապատասխանություն։

func (a *Assignment) Execute(env *environ.Environment) {
  val := a.expr.Evaluate(env)
  env.Set(a.name, val)
}

Արտածման հրամանի միակ expr դաշտը այն արտահայտությունն է, որի արժեքը պետք է հաշվել ու արտածել։

type Print struct {
  expr *asteval.Expression
}

Print հրամանի կոնստրուկտորն է.

func NewPrint(ex *asteval.Expression) *Print {
  return &Print{expr: ex}
}

Իսկ արտածման հրամանի կատարման համար պետք է պարզապես հաշվել expr արտահայտության արժեքը և fmt.Println ֆունկցիայով արտածել ստանդարտ արտածման հոսքի վրա։

func (p *Print) Execute(env *environ.Environment) {
  val := p.expr.Evaluate(env)
  fmt.Println(val.String())
}

Փոփոխություններ լեքսիկական անալիզատորում

Քերականության մեջ ավելացել են երեք թոքեններ՝ “Ident”, “Print” և “=”։ Իդենտիֆիկատորը դա տառով սկսվող տառաթվային հաջորդականություն է։ ‘print’-ը արտածման հրամանի ծառայողական բառն է։ ‘=’ նիշը վերագրման հրամանի սիմվոլն է։

const (
  None byte = iota
  Number  // Digit{Digit}
  Ident   // Letter{Letter|Digit}
  Add     // '+'
  Sub     // '-'
  Mul     // '*'
  Div     // '/'
  LPar    // '('
  RPar    // ')'
  Equal   // '='
  Print   // 'print', '?'
  Eos     // '@'
)

Ծառայողական բառերի համար սահմանենք մի աղյուսակ, որում իդենտիֆիկատորին համապատասխանեցված է թոքեն։ Այս աղյուսակն օգտագործելու ենք, որպեսզի պարզենք արդոք կարդացած իդենտիֆիկատորը ծառայողական բառ է, թե՝ ոչ։

var keywords = map[string]byte {
  "print": Print }

Սահմանենք նաև մի օգնական ֆունկցիա, որը դրական պատասխան է տալիս այն դեպքում, երբ արգումենտում տրված սիմվոլը տառ է կամ թվանշան։

func isLetterOrDigit(r rune) bool {
  return unicode.IsLetter(r) || unicode.IsDigit(r)
}

Լեքսիկական անալիզատորի Next մեթոդում ավելացնենք մի բլոկ, որը կարդում է տառով սկսվող տառաթվային հաջորդականություն, որոնում է այն ծառայողական բառերի աղյուսակում և, եթե գտնվել է, ապա վերադարձնում է համապատասխան թոքենը, հակառակ դեպքում վերադարձնում է Ident թոքենը։

...
  if unicode.IsLetter(ch) {
    iden := s.scanWith(isLetterOrDigit)
    tok, iskey := keywords[iden]
    if !iskey { tok = Ident }
    return iden, tok
  }
...

Փոփոխություններ քերականական անալիզատորում

Նախ factor մեթոդում ավելացնենք մի ճյուղ, որը վերլուծում է փոփոխականի առկայությունը.

...
  if p.look == scanner.Ident {
    nam := p.lexeme
    p.match(scanner.Ident)
    return asteval.Variable(nam)
  }
...

Քերականական անալիզատորում ավելացնենք երեք նոր մեթոդ՝ քերականության հետևյալ երեք կանոնների համար.

Statement = Assignment 
          | Print.
Assignment = 'Ident' '=' Expr.
Print = 'print' Expr.

Այս պահին մեր հրամանները կարող են սկսվել կա՛մ իդենտիֆիկատորով, կա՛մ print ծառայողական բառով։ Ես ճյուղավորման համար ընտրել եմ switch կառուցվածքը, որպեսզի հետագայում հեշտ լինի նոր հրամանների վերլուծության ճյուղերն ավելացնելը։

func (p *Parser) statement() astexec.Statement {
  switch p.look {
    case scanner.Ident:
      return p.assignment()
    case scanner.Print:
      return p.printexpr()
  }
  return nil
}

Վերագրման հրամանը վերլուծելու համար հերթականությամբ պետք է ճանաչել իդենտիֆիկատորը, հավասարության նշանը և հաջորդող արտահայտությունը։ Ապա կառուցել և վերադարձնել նոր Assignment հանգույց։

func (p *Parser) assignment() astexec.Statement {
  nm := p.lexeme
  p.match(scanner.Ident)
  p.match(scanner.Equal)
  ex := p.expr()
  return astexec.NewAssignment(nm, ex)
}

Արտածման հրամանը վերլուծելիս պետք է ճանաչել print ծառայողական բառը, ապա վերլուծել նրան հաջորդող արտահայտությունը։

func (p *Parser) printexpr() astexec.Statement {
  p.match(scanner.Print)
  ex := p.expr()
  return astexec.NewPrint(ex)
}

Քանի որ նոր քերականության մեջ առաջինը Statement կանոնն է, փոփոխենք Parse մեթոդն այնպես, որ նախ՝ այն վերադարձնի astexec.Statement, ապա՝ վերլուծությունը սկսի ոչ թե expr մեթոդից, այլ statement մեթոդից։

func (p* Parser) Parse(src string) astexec.Statement {
  p.look = scanner.None
  p.scan = scanner.New(src)
  p.match(scanner.None)
  return p.statement()
}

Երկխոսության ցիկլը

Ձևափոխված երկխոսության ցիկլում ստեղծում ենք նոր Environment օբյեկտ, որում պահվելու են փոփոխականների արժեքները։ Երբ Parse մեթոդը վերադարձնում է հրամանին համապատասխան աբստրակտ քերականական ծառը, կանչում ենք նրա Execute մեթոդը՝ արգումենտում տալով env օբյեկտը որպես կատարման միջավայր։

func Run() {
  reader := bufio.NewReader(os.Stdin)
  parser := new(parser.Parser)
  env := environ.New()

  for {
    fmt.Printf("> ")
    sr, _ := reader.ReadString('\n')
    ex := string(sr)
    if '.' == ex[0] { break }

    ast := parser.Parse(ex)
    ast.Execute(env)
  }
}

Սկզբնաղբյուրը։ http://code.google.com/p/calculator-with-big-integers/wiki/CalculatorI

Ծրագրի կոդը։ http://code.google.com/p/calculator-with-big-integers/

Թեգը։ calc-i

Նշագրեր: AST, go, interpreter, parsing, հաշվարկիչ, վերլուծություն

Բաժին: Go, Ծրագրավորում, Կոմպիլյատորներ, Ուսումնական նյութեր