Ինտերպրետատոր։ Համեմատում, ճյուղավորում, կրկնություն

Այս գրառումը իմ երեք նախորդ գրառումների շարունակությունն է («Հաշվարկիչ կամ արտահայտությունների ինտերպրետատոր», «Հաշվարկիչ վերագրման և արտածման հրամաններով», «Հաշվարկիչից դեպի լեզվի ինտերպրետատոր»), որոնցում ես սկսեցի պատմել, թե ինչպես իրականացնել թվաբանական չորս գործողություններ կատարող հաշվարկիչ, ապա նրա հիման վրա կառուցել ծրագրավորման լեզվի ինտերպրետատոր։

* * *

Ինտերպրետատորի զարգացման այս քայլում ես պլանավորել էի իրականացնել ճյուղավորման և կրկնման հրամանները։ Բայց, քանի որ համեմատման գործողությունները սերտորեն կապված են դրանց հետ, ես նախ ընդլայնեցի արտահայտություններն այնպես, որ նրանք ընդգրկեն համեմատման վեց գործողություններ, ապա նոր միայն ընդլայնեցի հրամանների համակարգը ճյուղավորման և կրկնման հրամաններով։

Համեմատման գործողություններ

Երկու թվերի համեմատման գործողությունների համար ես ընտրել եմ հետևյալ նշանակումները․

1. = – հավասար է,
2. <> – հավասար չէ,
3. > – մեծ է,
4. >= – մեծ է կամ հավասար,
5. < – փոքր է,
6. <= – փոքր է կամ հավասար:

Արտահայտությունների քերականությունն ընդլայնվում է և ստանում է այսպիսի տեսք․

Relation = Expr [RelOper Expr].
RelOper = '=' | '<>' | '>' | '>=' | '<' | '<='.
Expr = Term {('+' | '-') Term}.
Term = Factor {('*' | '/') Factor}.
Factor = 'Number'
       | 'Ident'
       | '-' Factor
       | '(' Expr ')'.

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

Թոքենների ցուցակում ավելացել են հաստատուններ վերը նշված համեմատման գործողությունների համար․

const (
  None byte = iota
  ...
  Equal       // '='
  NotEq       // '<>'
  Great       // '>'
  GrEq        // '>='
  Less        // '<'
  LsEq        // '<='
  ...
)

Քանի որ սրանով թվաբանական ու համեմատման գործողությունների քանակն իրար հետ վերցրած հասավ տասի, ես որոշեցի լեքսեմներին թոքեններ համապատասխանեցնելու համար սահմանել մի հեշ աղյուսակ․

var operations = map[string]byte{
  "+":  Add,
  "-":  Sub,
  "*":  Mul,
  "/":  Div,
  "=":  Equal,
  "<>": NotEq,
  ">":  Great,
  ">=": GrEq,
  "<":  Less,
  "<=": LsEq,
}

Իսկ գործողություններ կազմող սիմվոլները ճանաչելու համար սահմանեցի isOpChar ֆունկցիան, որպեսզի հնարավորություն ունենամ գործողությունների նշաններ կարդալ scanWith մեթոդով․

func isOpChar(r rune) bool {
  return strings.ContainsRune("+-*/=><", r)
}

Համապատախանաբար Next մեթոդի մարմնում ավելացավ մի նոր ճյուղ, որը կարդում և ճանաչում թվաբանական ու համեմատման գործողությունների նշանները․

func (s *Scanner) Next() (string, byte) {
  ...
  // operations
  if isOpChar(ch) {
    str := s.scanWith(isOpChar)
    tok, iskey := operations[str]
    if !iskey {
      tok = None
    }
    return str, tok
  }
  ...
}

Աբստրակտ քերականական ծառի փոփոխությունները

Քանի որ համեմատումները բինար գործողություններ են, նրանց համապատասխան ծառի հանգույցներ կստեղծենք NewBinary կոնստրուկտորով։ Փոփոխություններ կատարվել են միայն Evaluate մեթոդում։ big փաթեթի Int կառուցվածքի համար սահմանված Cmp մեթոդը համեմատում է երկու Big թվեր և վերադարձնում է -1, 0, 1, երբ առաջին թիվը համապատասխանաբար փոքր է, հավասար է կամ մեծ է երկրորդ թվից։

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

  switch e.class {
    ...
    case binary:
      exo := e.first.Evaluate(env)
      exi := e.second.Evaluate(env)
      switch e.operation {
        ...
        case "=":
          u := exo.Cmp(exi)
          res.SetInt64(toInt64(u == 0))
        case "<>":
          u := exo.Cmp(exi)
          res.SetInt64(toInt64(u != 0))
        case ">":
          u := exo.Cmp(exi)
          res.SetInt64(toInt64(u > 0))
        case ">=":
          u := exo.Cmp(exi)
          res.SetInt64(toInt64(u >= 0))
        case "<":
          u := exo.Cmp(exi)
          res.SetInt64(toInt64(u < 0))
        case "<=":
          u := exo.Cmp(exi)
          res.SetInt64(toInt64(u <= 0))
      }
  }
  return res
}

Քերականական անալիզատորի փոփոխությունները

Քերականական անալիզատորում ավելացել է relation մեթոդը, որը տառացիորեն համընկնում է քերականության հետևյալ կանոնին.

Relation = Expr [RelOper Expr].
RelOper = '=' | '<>' | '>' | '>=' | '<' | '<='.

func (p *Parser) relation() *asteval.Expression {
  ex := p.expr()
  if p.look >= scanner.Equal && p.look <= scanner.LsEq {
    op := p.lexeme
    p.match(p.look)
    ex = asteval.Binary(op, ex, p.expr())
  }
  return ex
}

Ճյուղավորման և կրկնման կառուցվածքներ

Երկու նոր հրամանները, որոնք անհրաժեշտ են քիչ թե շատ կարգին ալգորիթմներ գրելու համար դրանք ճյուղավորման ու կրկնման հրամաններն են։ Քերականական տեսակետից նրանք ունեն այսպիսի տեսք.

Statement = ... 
          | Branching
          | Looping.
Branching = 'if' Relation 'then'
              Sequence
           {'elseif' Relation 'then'
              Sequence}
           ['else'
              Sequence]
            'end'.
Looping = 'while' Relation 'do'
            Sequence
          'end'.

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

Թոքենների ցուցակում պետք է հաստատուններ ավելացնել if, then, elseif, else, while, do և end ծառայողական բառերի համար։

const (
  None   byte = iota
  ...
  If          // 'if'
  Then        // 'then'
  ElseIf      // 'elseif'
  Else        // 'else'
  While       // 'while'
  Do          // 'do'
  End         // 'end'
  ...
)

Ծառայողական բառերը թոքենների արտապատկերող հեշ աղյուսակը նույնպես պետք է ընդլայնել հետևյալ կերպ.

var keywords = map[string]byte{
  ...
  "if":     If,
  "then":   Then,
  "elseif": ElseIf,
  "else":   Else,
  "while":  While,
  "do":     Do,
  "end":    End,
}

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

astexec փաթեթում ավելանում են Branching և Looping կառուցվածքներն իրենց կոնստրուկտորներով ու Execute մեթոդներով։

Branching կառուցվածքը, որ նախատեսված է ճյուղավորման հրամանի համար, պարունակում է cond դաշտը որպես պայմանի արտահայտություն, thenpart դաշտը որպես հրամանների հաջորդականություն, որոնք պիտի կատարվեն այն դեպքում, երբ cond արտահայտության արժեքը հաշվարկվել է զրոյից տարբեր, և elsepart դաշտը որպես հարմանների հաջորդականություն, որոնք կատարվում են cond արտահայտության զրո հաշվարկված արժեքի դեպքում։

type Branching struct {
  cond *asteval.Expression
  thenpart, elsepart Statement
}

Կոնստրուկտորը ստանում է միայն երկու արգումենտ՝ cond և thenpart դաշտերի համար, իսկ elsepart դաշտն արժեքավորվում է առանձին SetElse մեթոդով։

func NewBranching(cd *asteval.Expression, tp Statement) *Branching {
  return &Branching{cond: cd, thenpart: tp, elsepart: nil}
}

func (b *Branching) SetElse(e Statement) {
  b.elsepart = e
}

Ճյուղավորման հրամանի կատարումը շատ պարզ է։ Նախ հաշվարկվում է cond արտահայտության արժեքը, ապա, եթե այն տարբեր է զրոյից՝ կատարվում է thenpart հրամանների հաջորդականությունը, հակառակ դեպքում՝ elsepart հաջորդականությունը։

func (b *Branching) Execute(env *environ.Environment) {
  ex := b.cond.Evaluate(env)
  if 0 != ex.Cmp(big.NewInt(0)) {
    b.thenpart.Execute(env)
  } else {
    b.elsepart.Execute(env)
  }
}

Կրկնման հրամանը մոդելավորող Looping կառուցվածքում cond դաշտը ցիկլի կատարման պայմանն է, իսկ body դաշտը՝ ցիկլի մարմինը։ Կոնստրուկտորը պարզապես արժեքավորում է այդ դաշտերը։

type Looping struct {
  cond *asteval.Expression
  body Statement
}

func NewLooping(cd *asteval.Expression, bd Statement) *Looping {
  return &Looping{cd, bd}
}

Կրկնման հրամանը կատարելու համար նախ հաշվվում է cond արտահայտությունը։ Եթե նրա արժեքը զրոյից տարբեր է, ապա կատարվում է body հրամանների հաջորդականությունը։ Նույնը կրկնվում է այնքան ժամանակ, քանի դեռ cond արտահայտության արժեքը տարբեր է զրոյից։

func (w *Looping) Execute(env *environ.Environment) {
  zr := big.NewInt(0)
  ex := w.cond.Evaluate(env)
  for 0 != ex.Cmp(zr) {
    w.body.Execute(env)
    ex = w.cond.Evaluate(env)
  }
}

Քերականական անալիզատորի ընդլայնումը

Ճյուղավորման հրամանի քերականական կանոնը պահանջում է, որ հրամանը սկսվի if ծառայողական բառով, որին հետևում է պայմանը ներկայացնող արտահայտությունը, ապա then ծառայողական բառը, որին հետևում են այն հրամանները, որոնք կատարվելու են, երբ պայմանի արտահայտության արժեքը հաշվարկվի զրոյից տարբեր։

func (p *Parser) branching() astexec.Statement {
  p.match(scanner.If)
  ex := p.relation()
  p.match(scanner.Then)
  st := p.sequence()
  res := astexec.NewBranching(ex, st)

Ճյուղավորման հրամանի առաջին պայմանին կարող են հաջորդել անսահմանափակ քանակով elseif կառուցվածքներ՝ իրենց համապատասխան հրամանների հաջորդականություններով։

  t := res
  for p.look == scanner.ElseIf {
    p.match(scanner.ElseIf)
    ex = p.relation()
    p.match(scanner.Then)
    st = p.sequence()
    v := astexec.NewBranching(ex, st)
    t.SetElse(v)
    t = v
  }

Եվ հրամանը կարող է ունենալ միակ else ճյուղ, որում թվարկված հրամանները կկատարվեն, եթե մինչև իրեն նշված բոլոր պայմանների արտահայտությունների հաշվարկը վերադարձրել զրոյական արժեք։

  if p.look == scanner.Else {
    p.match(scanner.Else)
    se := p.sequence()
    t.SetElse(se)
  }

Ճյուղավորման հրամանն ավարտվում է end ծառայողական բառով։

  p.match(scanner.End)
  return res
}

Կրկնման հրամանը սկսվում է while ծառայողական բառով, որին հետևում են կրկնման պայմանի արտահայտությունը, do բառը, հրամանի մարմնի հրամանների հաջորդականությունը և ապա end բառը։

func (p *Parser) looping() astexec.Statement {
  p.match(scanner.While)
  ex := p.relation()
  p.match(scanner.Do)
  st := p.sequence()
  p.match(scanner.End)
  return astexec.NewLooping(ex, st)
}

Բնականաբար branching և looping մեթոդներն իրականացնելուց հետո պետք է statement մեթոդում ավելացնել նրանց համապատասխան ճյուղերը։

Օրինակներ

Հետևյալ երկու օրինակները ցուցադրում են ճյուղավորման ու կրկնման հրամանների օգտագործումը։

Առաջին օգտագործողից հարցնում է ինչ-որ թիվ և ամեն մի թվի համար արտածում է պատասխան։

input x;
if x = 1 then
  print 100
elseif x = 2 then 
  print 200
elseif x = 3 then
  print 300
elseif x = 4 then
  print 400
else
  print 100000
end.

Երկրորդ օրինակը հաշվում է 10-ի ֆակտորիալը։

i = 10;
r = 1;
while i <> 0 do 
  print i;
  r = r * i;
  i = i - 1
end;
print r.

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

Կոդը։ http://code.google.com/p/calculator-with-big-integers/source/checkout

Թեգը։ calc-iii

Նշագրեր: go, Parser, Scanner, կրկնություն, ճյուղավորում

Բաժին: Go, Կոմպիլյատորներ