Testing Circuits(AOJ 2348) と演算子順位解析

概要

論理式が与えられるので,その式を真にするような変数の値の組合せが何通りあるか計算する.
ただし,同じ変数は1回しか登場しない.

解法

同じ変数は1回しか登場しないという制限により,式をいくつかの区間(演算)に分けて考えることができる.

組合せの計算方法は難しくないので,あとは構文解析をするだけ....なのだが,入力がやたらと長い.したがって再帰を使っていると(... ( (x1) ) ...)みたいな入力が与えられたときにStackOverFlowで死ぬ.

LL(1)パーサを使ってやるのもいいけど,再帰をスタック使って書き直すのが面倒くさい.

与えられた文法は演算子順位文法だから演算子順位解析使えばいいじゃない!!

ってノリで(うろ覚えの知識で)演算子順位解析を書いて通した.


演算子順位解析の知識を復習する.

演算子順位文法とは,生成規則に非終端記号が隣接する規則がない文法である.つまり,A→...BC...のような規則は存在しない.

この時,各演算子間に順序>,<,=のうち高々1つが成り立つ.(本当は・を付けて表すらしい.)

この順序がわかれば,次のアルゴリズムを用いて構文解析が行える.


入力される文字列S(終端は適当な記号,例えば'$'で表される)
スタックT(文字列の開始を表す記号,例えば'^'を突っ込む)
p=0

  1. もしTの先頭が$なら解析を終了する.
  2. T.top > S[p]である限り,スタックの先頭から演算子を取り出し還元する
  3. TにS[p]をプッシュする.
  4. p++

ただし,^と$は優先順位最弱(^=$)

優先順位表の求め方は,

  1. A→...st...または.A→..sAt...なる生成規則が存在すればs=t
  2. A→...sB...となる生成規則が存在し,B⇒t...またはB⇒Ctとなる生成規則が導かれるならばs
  3. A→...Bt...となる生成規則が存在し,B⇒...sまたはB⇒sCとなる生成規則が導かれるならばs>t

これを自動で求める方法があった気がするけど,資料とかが今手元にないので後日.

次のBNFに対して優先順位を求めると下の表のようになる.

  • A ::= B | A"|"B
  • B ::= A | A"&"B
  • C ::= D | "~"C | "("A")"

Dは変数とかで字句解析などで既に還元されているものと考える...(Testing Circuitで与えられた規則の文字だけ変更)

id ( ) ~ & |
id > > > > >
( < < = < < <
) < > > >
~ < < > > > >
& < < > > > >
| < < > < > >

idは非終端記号のこと.

何となく覚えておけばいいことは,

  • (が右側に来たら最強.)が右側に来たらそれより左側のものを(が出てくるまで還元する.
  • 優先順位が高いほうが強い(+より*のほうが強いとか)
  • 左結合の時は自身に対して>,右結合の時は<

ぐらいだろうか.
なお上の表の確認はしていないもよう