左再帰 - Wikipedia

左再帰（英: Left recursion）とは、言語（普通、形式言語について言うが、自然言語に対しても考えられ得る）の文法（構文規則）にあらわれる再帰的な規則（定義）の特殊な場合で、ある非終端記号を展開した結果、その先頭（最も左）にその非終端記号自身があらわれるような再帰のことである。 ナイーブに再帰下降構文解析の関数に変換すると、実行（ないし評価）すると無限再帰に陥る関数になるのだが、通常の算術の式のように左結合（結合法則#結合性を参照）の中置演算子式は一般に左再帰の構文規則になるため、プログラミング言語処理系の実装のために、実用的な観点から対策が検討されてきた。この関数における再帰を指すこともある。 定義[編集] 文法が左再帰であるとは、非終端記号からその非終端記号自身を左端に含む文字列が導出される、ということである[1]。 以下、ラテンアルファベットの大文字（, ,...）は任意の

[a1ghost]

左再帰は無限ループ

[sshi]

「間接左再帰も直接左再帰も多項式時間で扱える構文解析アルゴリズムとし、非常に曖昧な文法であっても指数関数的な数になる構文木を多項式サイズでコンパクトに表現できることを示した」のあたり興味深い