再帰降下法

第 12章 の 12.2 節において, 後置記法(逆ポーランド記法)で書いた数式を計算するプログラムを 解説した. このプログラムはスタックの利用により後置記法の式の計算を実現している. この節では, 中置記法の数式を後置記法へ変換する プログラムを開発する. 中置記法は演算子を真中におく, おなじみの式の記述方法である. たとえば は中置記法の式であり, これを後置記法に変換すると, たとえば 2 3 45 2 + * + となる. 変換するプログラムを書く前にどのような ``文法'' の 中置記法の式を入力として認めるのか きちんと定義する必要がある. 計算機の世界で意味する文法というのは, 英文法の意味する文法とは違い, 曖昧さが入る余地はゆるしていないし, 人間が人工的に定義する. 文法は BNF (Bakus-Nauer) 形式や構文図を用いて定義する. われわれの, ``式''