式の構文解析
文字で書いた式を、計算する順序がわかる木に組み立てる処理です。同じ式でも演算子の順位の決まりが変わると、木の形と答えが変わります。
式の構文解析
0 / 0 手順
速さ 速さ
回/秒
| 決まり | 答え | 手順 | 比較 | スタックの最大 | 読み直した字句 | 木の段数 |
|---|
比較の対象
| 順位 | 演算子 | 結合 | 入れ替え |
|---|
- 答え
- –
- 手順
- 0
- 比較
- 0
- スタックの最大
- 0
- 読み直した字句
- 0
- 字句
- 0
- 木の段数
- –
音量 音量
dB
動作原理と式
式から答えまで
式は 3 つの工程で計算します [1]。
- 字句解析: 文字の並びを数と記号に分ける。
12は 2 文字でも 1 つの数 - 構文解析: 字句の並びから木を組む。下の丸ほど先に計算する
- 計算: 葉から順に、子の値を親の演算子で計算する。根の値が答え
括弧は木の形を決めたら役目を終えるので、木には残りません。
順位と結合
木の形は、隣り合う 2 つの演算子のどちらを先に計算するかで決まります [3]。
- 順位が違う: 順位の高い演算子を先に計算する。
1 + 2 × 3は × が先で 7 - 順位が同じで左結合: 左を先に計算する。
8 − 3 − 2は (8 − 3) − 2 で 3 - 順位が同じで右結合: 右を先に計算する。
2 ^ 3 ^ 2は 2 ^ (3 ^ 2) で 512
決まりが変わると答えが変わる
順位と結合は式を書く側の約束なので、道具ごとに違います。
| 内容 | 例 | |
|---|---|---|
| 数学の慣習 | ^ → 符号 → × ÷ → + − | -2 ^ 2 = −4 |
| 省略した × を優先 | 2(3) の × を ÷ より先に計算 | 6 / 2(1 + 2) = 1 |
| Excel [8] | 符号 → ^ → × ÷ → + −、同じ順位は左から | -2 ^ 2 = 4、2 ^ 3 ^ 2 = 64 |
| 標準の電卓 [9] | 入力した順に計算 | 1 + 2 * 3 = 9 |
| APL [10] | 順位なし、右から計算 | 8 - 3 - 2 = 7 |
手法
同じ決まりなら、どの手法でも同じ木になります。違うのは読み方と手順の数です。n は字句の数です。
| 読み方 | 手順の増え方 | 出典 | |
|---|---|---|---|
| 操車場 | 記号のスタックと木の列 | n に比例 | [2] |
| シフト還元 | 数も記号も 1 本のスタック | n に比例 | [4] |
| 再帰下降 | 順位の数だけ処理を呼ぶ | n × 順位の数に比例 | [1] |
| Pratt | 順位の下限を渡して呼ぶ | n に比例 | [5] |
| バックトラック | 失敗すると戻って読み直す | 括弧の深さに対して指数的 | [6] |
| パックラット | 読んだ結果を覚える | n に比例 | [7] |
- 操車場: 来た演算子とスタックの一番上を比べる。一番上が先なら木に足し、来た演算子が先なら積む
- シフト還元: 字句を積むのがシフト、一番上の組を 1 つの式 E にまとめるのが還元
- 再帰下降: 順位の低い処理から呼ぶので、数を 1 つ読むにも順位の数だけ呼び出しが深くなる
- Pratt: 「この順位以上だけ読む」と伝えて呼ぶので、演算子があるときだけ深くなる
- バックトラック: 「A 演算子 A」を試し、だめなら戻って「A」を読み直す。読み直す間にも同じ式を読むので、括弧が深いと手順が急に増える
- パックラット: バックトラックと同じ順に試し、位置ごとの結果を覚えて再利用する
音
音の高さは深さで決めます。深いほど高い音です。音階はペンタトニックです。
- 字句解析: 字句ができた位置が右へ行くほど高い
- 構文解析: スタックが深いほど高い。比較は 2 音、木に足すと下がる 2 音、読み直しとエラーは最も低い音
- 計算: 木の中で深い演算子ほど高い。根に近づくと下がる
出典
- 字句解析と構文解析の役割、再帰下降、シフト還元A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman, Compilers: Principles, Techniques, and Tools, 2nd ed., Addison-Wesley, 2006, Chapters 3–4
- 操車場アルゴリズムE. W. Dijkstra, Algol 60 translation: An Algol 60 translator for the X1 and making a translator for Algol 60, MR 35/61, Mathematisch Centrum, Amsterdam, 1961
- 演算子の順位による構文解析R. W. Floyd, Syntactic Analysis and Operator Precedence, Journal of the ACM, Vol. 10, No. 3, pp. 316–333, 1963
- シフトと還元で左から読む構文解析（LR）D. E. Knuth, On the translation of languages from left to right, Information and Control, Vol. 8, No. 6, pp. 607–639, 1965
- Pratt の方法V. R. Pratt, Top down operator precedence, Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL '73), pp. 41–51, 1973
- 順序付きの選択で読む文法B. Ford, Parsing expression grammars: a recognition-based syntactic foundation, Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '04), pp. 111–122, 2004
- パックラットB. Ford, Packrat parsing: simple, powerful, lazy, linear time, Proceedings of the 7th ACM SIGPLAN International Conference on Functional Programming (ICFP '02), pp. 36–47, 2002
- Excel の順位Microsoft, Calculation operators and precedence in Excel, Microsoft Support
- 標準の電卓の計算順Microsoft, Windows Calculator, README, GitHub
- APL の計算順K. E. Iverson, A Programming Language, Wiley, 1962
このツールで決めたこと
- 使える演算子は + − × ÷ ^ と符号の −、括弧。関数と変数は扱わない
- 数と括弧、括弧と括弧の間の × は補う。Excel の決まりでは省略を書けないのでエラーにする
- 標準の電卓に ^ と括弧はないが、ほかの決まりと比べるために同じ順位で扱う
- APL は本来 × ÷ ^ に別の記号を使うが、同じ記号で順序だけを再現する
- 「数学の慣習」は省略した × を ÷ と同じ順位とする。「省略した × を優先」は ÷ より先にする。どちらも使われる書き方の例で、正解を決めるものではない
- 「+ − を先に」は順位の違いを見るための決まりで、実在の道具の決まりではない
- 手順は図の 1 コマで数える。手順の数は手法の実装の速さではない
- 比較は順位を確かめた回数で、再帰下降とバックトラックでは次の字句が今の処理の演算子かを調べた回数を含める
- 読み直した字句は、戻した字句の数の合計
- 再生できるのは最初の 2,500 手順までで、数えるのは 300,000 手順まで。超えると打ち切り
- ÷ 0 はエラーにする