大事なのはLookup力

Sublinear-space evaluation algorithms for attribute grammars という論文を見つける．1987年もの．attribute grammar というのは死に絶えた技術なんだろうか，それはさておき

ROOT -> exp
  exp.env = φ
exp -> exp + exp
  exp1.val = exp2.val + exp3.val
  exp2 .env = exp1 .env
  exp3.env = exp1 .env
exp -> exp - exp
  exp1 .val = exp2 .val - exp3 .val
  exp2 .env = exp1 .env
  exp3 .env = exp1 .env
exp -> let id = exp in exp ni
  exp1 .val = exp3 .val
  exp2 .env = exp1 .env
  exp3 .env = exp1 .env U ( (id, exp2 .val) )
exp -> id
  exp.val= LookUp(id, exp.env)
exp -> integer
  exp.val = ValueOf(integer)

これは典型的なattribute grammarの例としてこの論文に載っている．この中にある LookUp という関数はid と 環境（スコープ）をもとに値を探してくるものだが，その実装はAttribute Grammarでは規定されていない，というか書きにくい？このへんにAttribute Grammarの限界があるのかもしれない．