Սկիզբ » Ուսումնական նյութեր » Ծրագրավորում » Ծրագրավորման լեզուներ » Go » Հաշվարկիչ կամ արտահայտությունների ինտերպրետատոր

Հաշվարկիչ կամ արտահայտությունների ինտերպրետատոր

| Դեկտեմբեր 1, 2012 |

Ինչպե՞ս գրել տողով տրված մաթեմատիկական արտահայտությունը հաշվարկող ծրագիր։ Կարող է թվալ, թե ավելորդ է գրել այս թեմայով, քանի որ կարելի է գտնել բազմաթիվ ու բազմազան գրականություն՝ հարուստ տեսական ու գործնական նյութով։ Բայց ես որոշեցի սկսել մի շարք, որտեղ կպատմեմ, թե ինչպես նախ կառուցել մի քանի թվաբանական գործողություններ կատարող հաշվարկիչ, ապա դրա հենքի վրա՝ քիչ-քիչ ընդլայնելով, ստեղծել ծրագրավորման լեզվի ինտերպրետատոր։

Որպես իրականացման միջոց ընտրել եմ Go լեզուն՝ երկու պատճառով. ա) ես ուզում եմ ավելի խորն ուսումնասիրել այդ լեզուն, և բ) ուզում եմ իմ կուտակած փորձը կիսել նրանց հետ, ովքեր հետաքրքրվում են Go լեզվով։

Սահմանումներ

Ամենից առաջ պետք է որոշել, թե ի՞նչ ֆունկցիոնալությամբ է օժտված լինելու հաշվարկիչը։ Սկզբի համար ես ընտրել եմ թվաբանական չորս բինար գործողություններ՝ գումարում, հանում, բազմապատկում և բաժանում, մեկ ունար գործողություն՝ բացասում, խմբավորման փակագծեր՝ գործողություններ։ Հաշվարկիչն աշխատելու է մեծ (“անսահմանափակ” երկարությամբ) ամբողջ թվերի հետ։ Օգտագործողի տեսակետից հաշվարկիչը ստանալու է արտահայտության տեքստային ներկայացումը, հաշվելու է նրա արժեքը և վերադարձնելու է պատասխանը՝ նորից տեքստային ներկայացմամբ։

EBNF գրառմամբ հաշվարկիչի լեզուն ներկայացնող քերականությունը կունենա այսպիսի տեսք.

Factor = "Number"
       | "-" Factor
       | "(" Expression ")".
Term = Factor {("*" | "/") Factor}.
Expression = Term {("+" | "-") Term}.

Այս երեք կանոններն ամբողջությամբ նկարագրում են գործողությունների թե՛ առաջայնությունը և թե՛ ասոցիատիվությունը։

Աբստրակտ քերականական ծառ

Քերականությամբ նկարագրված արտահայտությունների մոդելը աբստրակտ քերականական ծառն է (abstract syntax tree, AST)։ Այդ ծառի հանգույցները ներկայացնում են արտահայտության գործողությունները, իսկ տերևները ներկայացնում են տվյալները։ Օրինակ, 123 + 45 * 6 արտահայտության համար պետք է կառուցել հետևյալ ծառը.

    +
   / \
  /   \
123    *
      / \
     45  6

Աբստրակտ քերականական ծառը կառուցվում է քերականական անալիզատորի (parser) կողմից, և օգտագործվում է արտահայտության ինտերպրետացիայի (կամ կոմպիլյացիայի) ժամանակ։

Go լեզվով սահմանենք asteval փաթեթը, որը տրամադրում է ծառի հանգույցների ստրուկտուրան, կոնստրուկտոր ֆունկցիաներ՝ հանգույցներ ու տերևներ ստեղծելու համար, ինչպես նաև ծառի ինտերպրետացիայի ֆունկցիան։ Պրոյեկտի src պանակում ստեղծենք asteval պանակ, իսկ նրա մեջ՝ asteval.go ֆայլը։

Հայտարարենք asteval փաթեթը.

package asteval

Քանի որ մեր արտահայտություններն օգտագործելու են մեծ ամբողջ թվեր, Go լեզվի գրադարանից ներմուծենք big փաթեթը.

import "math/big"

Սահմանենք number = 0, unary = 1, binary = 2 հաստատունները, որոնք ցույց են տալու ծառի հանգույցի տիպը.

const (
  number byte = iota
  unary
  binary
)

Ծառի հանգույցը սահմանենք որպես Expression անունով կառուցվածք։ Նրա class դաշտը ցույց է տալիս հանգույցի տիպը, value դաշտը ցույց է տալիս հանգույցի արժեքը, եթե տիպը number է, operation դաշտը ցույց է տալիս հանգույցում ներկայացված ունար կամ բինար գործողությունը, իսկ first և second դաշտերը ցույց են տալիս հանգույցի ենթածառերը։ Եթե class = unary, ապա second = nil։

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

Ինչպես նշվեց, մենք գործ ենք ունենալու երեք տիպի հանգույցների հետ՝ թիվ, ունար գործողություն և բինար գքործողություն։ Սահմանենք կոնստրուկտոր ֆունկցիաներ նրանց համար։

Թիվ (number) ներկայացնող կոնստրուկտերը արգումենտում ստանում է թվի տեքստային տեսքը, և վերադարձնում է Expression կառուցվածքի նոր ստեղծված նմուշի ցուցիչը, որի class դաշտին վերագրված է number հաստատունը, իսկ value դաշտին՝ big.Int օբյեկտի ցուցիչը։

func Number(num string) *Expression {
  nm := new(big.Int)
  nm.SetString(num, 10)
  return &Expression{class: number, value: nm}
}

ՈՒնար գործողությանը համապատասխանող հանգույց ստեղծելու համար պետք է տալ գործողության նիշը և ենթաարտահայտությունը։ Չնայաց, որ մեր դեպքում կա միայն մեկ ունար գործողություն՝ բացասումը, կոնստրուկտոր ֆունկցիան որպես առաջին արգումենտ ընդունում է նաև գործողության նշանը։

func Unary(op rune, ex *Expression) *Expression {
  return &Expression{class: unary, operation: op, first: ex}
}

Բինար գործողության հանգույցիա համար էլ պետք է ունենալ գործողության նշանը, աջ ու ձախ ենթաարտահայտությունները։

func Binary(op rune, exo, exi *Expression) *Expression {
  return &Expression{class: binary, operation: op, first: exo, second: exi}
}

Արտահայտության արժեքը հաշվելու համար պետք է անցում կատարել նրա համար կառուցած աբստրակտ քերականական ծառով՝ ըստ հետևյալ կանոնների.
1. եթե class = number, ապա վերադարձնել նրա value դաշտը,
2. եթե class = unary, ապա այս կանոնների կիրառմամբ հաշվել first ենթաարտահայտությունը և այդ արժեքի վրա կիրառել operation դաշտով որոշվող գործողությունը։
3. եթե class = binary, ապա այս կանոնների կիրառմամբ հաշվել first և second ենթաարտահայտությունները, ապա ստացված արժեքների նկատմամբ կիրառել operation դաշտով որոշվող գործողությունը։

Նշված կանոններն իրականացնելու համար Expression կառուցվածքի ցուցիչի համար սահմանենք Evaluate մեթոդը։

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

  switch e.class {
    case number:
      res.Set(e.value)
    case unary:
      res = e.first.Evaluate()
      if '-' == e.operation { res.Neg(res) }
    case binary:
      exo := e.first.Evaluate()
      exi := e.second.Evaluate()
      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
}

Ակնհայտ է, որ այս ֆունկցիան ունի թերություն. այն բաժանման գործողությունը կատարելուց առաջ չի ստուգում երկրորդ արգումենտի զրո լինելը։ Բայց այս անգամ անտեսենք այդ թերությունը՝ հետագայում ճշտելու պայմանով։

Ահա և վերջ, ամբողջությամբ սահմանված է asteval փաթեթը։ Այն տրամադրում է Expression կառուցվածքը, Number, Unary, Binary կոնստրուկտորները և Evaluate մեթոդը։

Լեքսիկսկան և քերականական վերլուծություն

Աբստրակտ քերականական ծառն արտահայտության ներքին, օգտագործողին չերևացող մասն է։ Տեքստային ներկայացումից այն ստանալու համար պետք է արտահայտությունը ենթարկել քերականական վերլուծության, և այդ վերլուծությունը պետք է կատարել վերը բերված կանոններով։ Բայց քերականական վերլուծության համար պետք է նախ արտահայտության տեքստը տրոհել տերմինալային տրամաբանական կտորների՝ լեքսեմների և ամենի մի լեքսեմի հետ կապել նրա տիպը (նշանակությունը) ցույց տվող հատկություն՝ թոքեն։ Օրինակ, 123 + 45 * 6 արտահայտության համար տրոհումը կարող է ունենալ այսպիսի տեսք.

Lexeme  Token
------- -------
"123"   Number 
"+"     Add
"45"    Number
"*"     Mul
"6"     Number

Լեքսիկական անալիզատորի խնդիրն է հենց այս տրոհումը։ Քերականական անալիզատորն օգտագործում է թոքենները քերականական կանոնն ընտրելու համար, իսկ լեքսեմներն օգտագործում է ծառի հանգույցների պարունակությունը լրացնելու համար։

scanner փաթեթը

Լեքսիկական անլիզատորն իրականացնենք scanner փաթեթում։

package scanner

Ընթերցվող սիմվոլների տիպը որոշելու համար ներմուծենք Go լեզվի գրադարանային unicode փաթեթը։

import "unicode"

Սահմանենք Scanner կառուցվածքը, որի text դաշտը արտահայտության տեքստի նիշերի զանգվածն է, իսկ pos ինդեքսը ցույց է տալիս հերթական ընթերցվող սիմվոլը։

type Scanner struct {
	text []rune
	pos int
}

Scanner կառուցվածքի կոնստրուկտորը ստանում է վերլուծության ենթակա արտահայտության տեքստը, նրա վերջից կցում է “;” նիշը որպես արտահայտության ավարտի նշան, ապա տողը վերածում է նիշերի վեկտորի և վերագրում text դաշտին։

func New(txt string) *Scanner {
  return &Scanner{[]rune(txt+";"), 0}
}

Թոքենների համար սահմանենք հաստատուններ.

const (
	None byte = iota
	Number  // Digit{Digit}
	Add     // '+'
	Sub     // '-'
	Mul     // '*'
	Div     // '/'
	LPar    // '('
	RPar    // ')'
	Eos     // ';'
)

Սահմանենք մի օգնական մեթոդ, որը արտահայտության նիշերի շարքից կարդում է տրված պրեդիկատին բավարարող նիշերի անընդհատ շարք և վերադարձնում է դրանցից կազմած տողը։

func (s* Scanner) scanWith(predicate func(r rune) bool) string {
    k := s.pos
    for predicate(s.text[s.pos]) { s.pos++ }
    return string(s.text[k:s.pos])
}

Scanner կառուցվածքի Next մեթոդը վերադարձնում է երկու արժեք՝ հերթական լեքսեմը և նրան համապատասխանող թոքենը։ Մեթոդը նախ կանչում է scanWith մեթոդը IsSpace պրեդիկատով, որպեսզի դեն նետի բացատնանիշերը։ Այնուհետև, եթե հերթական նիշը թվանշան է, ապա scanWith մեթոդը կանչում է IsDigit պրեդիկատով ստանում է ամբողջ թիվ կազմող թվանշանների շարք։ Այս դեպքում վերադարձվում է թվանշաններից կազմված տողը որպես լեքսեմ և Number հաստատունը որպես թոքեն։ Թվանշաններից բացի դիտարկվում են միայն ‘+’, ‘-‘, ‘*’, ‘/’, ‘(‘, ‘)’ և ‘;’ նիշերը և ամեն մեկի համար վերադարձվում է համապատասխան թոքենը։ Բոլոր այլ նիշերի համար վերադարձվում է None թոքենը։

func (s *Scanner) Next() (string, byte) {
  s.scanWith(unicode.IsSpace)

  ch := s.text[s.pos]

  if unicode.IsDigit(ch) {
    return s.scanWith(unicode.IsDigit), Number
  }

  var res byte = None
  s.pos++
  switch ch {
    case '+': res = Add
    case '-': res = Sub
    case '*': res = Mul
    case '/': res = Div
    case '(': res = LPar
    case ')': res = RPar
    case ';': res = Eos
  }

  return string(ch), res
}

Սա էլ լեքսիկական անալիզատորի փաթեթեը։ նորից ոչ մի սխալների մշակում չի կարարված զուտ պարզության համար։ Նախագծի հետագա զարգացումներում անպայմանորեն պետք է հաշվի առնել հնարավոր սխալները։

parser փաթեթը

Քերականական անալիզատորն իրականացված է parser փաթեթում։ Այն ըստ քերականական կանոնների վերլուծում է արտահայտության տեքստը և կառուցում է աբստրակտ քերականական ծառը։ Քերականական սխալները չեն մշակվում՝ նորից պարզության համար։

package parser

Ներմուծենք մեր նախապես ստեղծած երկու փաթեթները։

import (
  "scanner"
  "asteval"
)

Parser կառուցվածքը քերականական անալիզատորի մոդելն է։ Նրա look դաշտը ընթացիկ թոքենն է՝ look-a-head սիմվոլը, lexeme դաշտը ընթացիկ լեքսեմն է, scan դաշտը լեքսիկական անալիզատորի ցուցիչն է։

type Parser struct {
  look byte
  lexeme string
  scan *scanner.Scanner
}

Parser կառուցվածքի համար կոնստրուկտոր չենք գրել, քանի որ դրա կարիքը պարզապես չկա։

Միակ միջոցը, որով քերականական անալիզատորը շփվում է արտաքին աշխարհի հետ, դա Parse մեթոդն է։ Այն ստանում է արտահայտության տեքստը և վերադարձնում է աբստրակտ քերականական ծառի արմատը (եթե վերլուծության ընթացքում սխալներ չեն հայտնաբերվել)։

func (p* Parser) Parse(src string) *asteval.Expression {
  p.look = scanner.None
  p.scan = scanner.New(src)
  p.match(scanner.None)
  return p.expr()
}

Parser-ը լեքսիկական անալիզատորից հերթական լեքսեմ-թոքեն զույգը կարդում է match մեթոդի օգնությամբ։ Հետագայում այս մեթոդի մեջ է իրականացվելու որոշ քերականական սխալների մասին ազդարարումը։

func (p *Parser) match(tok byte) bool {
  if tok != p.look { return false }
  p.lexeme, p.look = p.scan.Next()
  return true
}

Դիտարկվող արտահայտություների քերականությունն ունի երեք արտածման կանոն, ըստ որոնց էլ կառուցել եմ քերականական անալիզատորի մեթոդները։

Առաջինը Factor կանոնն է, որն ունի արտածման երեք տարբերակ․

Factor = "Number".
Factor = "-" Factor.
Factor = "(" Expression ")".

ՈՒշադիր նայելով այս արտածման կանոններին տեսնում ենք, որ Factor կանոնը կարելի է կիրառել միայն այն դեպքում, երբ լեքսիկական անալիզատորի look-a-head սիմվոլը “Number”, “-“, “(” թոքեններից որևէ մեկն է։

Եթե look-a-head = “Number”, ապա ստեղծում և վերադարձնում ենք ծառի նոր տերև՝ ընթացիկ լեքսեմի արժեքով։ Եթե look-a-head = “-“, ապա հանդիպել ենք ունար գործողության։ Ռեկուրսիվ կանչով կառուցում ենք գործողության արգումենտի ծառը, ապա ստեղծում ենք ծառի ունար գործողության հանգույց։ Եթե look-a-head = “(“, ապա ռեկուրսիվ կանչով կառուցում ենք փակագծերի ներսում գրված արտահայտության ծառը, ապա match մեթոդի կանչով համոզվում ենք, որ առկա է փակվող փակագիծը։

func (p *Parser) factor() *asteval.Expression {
  // number
  if p.look == scanner.Number {
    num := p.lexeme
    p.match(scanner.Number)
    return asteval.Number(num)
  }

  // unary operation '-'
  if p.look == scanner.Sub {
    p.match(scanner.Sub)
    ex := p.factor()
    return asteval.Unary('-', ex)
  }

  // expression in parentheses
  if p.look == scanner.LPar {
    p.match(scanner.LPar)
    ex := p.expr()
    p.match(scanner.RPar)
    return ex
  }

  return nil
}

Քերականության հաջորդ կանոնը կառուցում է բազմապատկման ու բաժանման բինար գործողություններին համապատասխանող հանգույցները։ Ըստ քերականական երկրորդ կանոնի, Term-ը կարող է լինել կա՛մ Factor, կա՛մ “*” և “/” նիշերով իրար կցված Factor-ների հաջորդականություն․

Term = Factor {("*" | "/") Factor}.

Քերականական անալիզատորի term մեթոդը այս կանոնի տառացի իրականացումն է։

func (p *Parser) term() *asteval.Expression {
  ex1 := p.factor()
  for p.look == scanner.Mul || p.look == scanner.Div {
    op := rune(p.lexeme[0])
    p.match(p.look)
    ex2 := p.factor()
    ex1 = asteval.Binary(op, ex1, ex2)
  }
  return ex1
}

Երրորդ քերականական կանոնը կառուցում է գումարման ու հանման բինար գործողություններին համապատասխանող հանգույցները։ expr մեթոդը շատ նման է term մեթոդին։ Քանի որ մեր քննարկած արտահայտություններում գումարման ու հանման գործողություններն ունեն ամենացածր նախապատվությունը, հենց այս մեթոդն է կանչվում Parse մեթոդից։

func (p *Parser) expr() *asteval.Expression {
  ex1 := p.term()
  for p.look == scanner.Add || p.look == scanner.Sub {
    op := rune(p.lexeme[0])
    p.match(p.look)
    ex2 := p.term()
    ex1 = asteval.Binary(op, ex1, ex2)
  }
  return ex1
}

Երկխոսություն օգտագործողի հետ

Հաշվարկիչի և օգտագործողի շփումն իրականացված է հրամանային տողի օգնությամբ։ Գործարկումից հետո ծրագիրն արտածում է “>” սիմվոլը և սպասում է, որ օգտագործողը ներմուծի արտահայտության տեքստը։ Արտահայտության ներմուծումից և Enter ստեղնի սեղմումից հետո հաշվարկվում և արտածվում է արտահայտությունը արժեքը։

Փաթեթն անվանված է repl՝ (Read-Evaluate-Print-Loop)։

package repl

Ներմուծենք անհրաժեշտ փաթեթները։

import (
  "fmt"
  "os"
  "bufio"
  "parser"
)

Եվ միակ Run պրոցեդուրան, որը reader-ի միջոցով կարդում է օգտագործողի տված տեքստը, parser-ի միջոցով վերլուծում է այն ու կառուցում է աբստրակտ քերականական ծառ։ Այնուհետև ծառի արմատի համար կանչելով Evaluate մեթոդը՝ հաշվում է արտահայտության արժեքը։ Ցիկլը կատարվում է այնքան ժամանակ, քանի դեռ օգտագործողի ներածած տեքստի առաջին նիշը “.” (կետ) չէ։

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

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

    ast := parser.Parse(ex)
    res := ast.Evaluate()
    fmt.Println(">", res.String())
  }
}

Ծրագրի մուտքի կետը և գործարկումը

Go լեզվով գրված ծրագրերի մուտքի կետ է հանդիսանում main փաթեթի main ֆունկցիան։ Այն պարզապես կանչում է repl փաթեթի Run ֆունկցիան։

package main

import "repl"

func main() {
  repl.Run()
}

Պրոյեկտի կոդը գտնվում է․http://code.google.com/p/calculator-with-big-integers/

Հաշվարկիչ կամ արտահայտությունների ինտերպրետատոր, 10.0 out of 10 based on 10 ratings

Նշագրեր: , , , ,

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

Կիսվել , տարածել , պահպանել

VN:F [1.9.20_1166]
Rating: 10.0/10 (10 votes cast)

Մեկնաբանությունները փակված են

288