再帰下降パーザー

最近、ボケ防止にいろんなコードを書いて、各社お客様の若手プログラマに取り残されないように注意しています。コードを見てフンフンと思うのと、実際にコードを書くのでは雲泥の差があるのです。（もちろん雲というのはホンワカしていていい加減であり、泥はしっかりとして現実、という意味です*1。）
というわけで、今日は Python で再帰下降パーザー（recursive descent parser）を書いてみました。この再帰処理は、ぱっと見、魔法のようなもので、どうしてこれで構文を解析できるのか不思議なものです。だから、ぱっと見ではなくて、自分で一から書いてみて初めて血肉となる、と考えたわけです。
何気なくコードを読んでいると分からないのですが、大抵の再帰下降パーザーでは先読みをしているようです。というか、次に解釈すべきトークンを sym とかいう広域変数に入れて、あちこち状態遷移するときにトークンを食べてしまわないようにしています。
私が今日書いたコードでは、get_token() という関数に加えて、unget_token() という「食べてしまったトークンを吐き出す」関数を作って対処してみました。というか、あとから参考書を読んだら、みんな前述の方法（広域変数 sym にトークン（シンボル）を残しておく）を使っていた、ということですが。
もう一つ。再帰下降パーザーで左再帰（left recursion）の構文を処理する方法が結局分からず、思わず参考書を盗みみてしまいました。左再帰というのは、例えば次のような構文です。

expr := term
      | expr '+' term
      | expr '-' term;

expr を解釈しようとすると、その定義の中に出てくる expr の解釈にいきなり再帰しようとするため、再帰が止まらなくなってしまうのでした。ここで、expr '+' term は左結合なので左右の順序を入れ替えてしまう訳にはいかないのです。
また思わず参考書を盗み見たら、みんな、ここを再帰ではなくてループで実現していました。つまり、次のような感じです。

def get_expr():
    term = get_term()
    op = get_token()
    while op == '+' or op == '-':
        ...
        next_term = get_term()
        op = get_token()
        ...

みたいな感じです。これって、再帰じゃ書けないのだろうか? もう少し考えてみよう。

*1:そうなのか?