05/11/16 10:49:28
>>307
解析する式は段々と小さな部分式になっていって
いつか変数か定数に帰着して終わるから無限再帰ではない。
つまり最終的に出来上がる構文木のすべての葉ノードまで
ノードを作成しながら"再帰"的に"下降"して終了する。
(これはプログラミング言語関係の各種の性質の数学的証明で
よく使われるテクニックである「式の長さによる帰納法」に対応してるわけだな。)
とはいえ実際問題としては演算子の優先順位や結合規則を文法的に表現する必要から
式を何種類か(代入式、条件式、論理和、論理積、単項式などなど)にわけて
その間を巡りながら再帰していくわけだけどな。
で、再帰を素朴に再帰呼び出しで書く(再帰降下法)と
大規模なプログラムに対しては
再帰が深くなりすぎて溢れたり実行効率が悪化したりするから
パーサ・ジェネレータは自前で管理するスタックとループで動くような
コードを生成することが多いわけですな。