左再帰

コンピュータサイエンスの形式言語理論では、左再帰は再帰の特殊なケースであり、文字列は同じ言語の文字列（左側）と接尾辞（右側）に分解されるという事実によって言語の一部として認識されます。たとえば、 は、同じく和である と適切な接尾辞に分解できるため、和として認識できます。 ${\displaystyle 1+2+3}$${\displaystyle 1+2}$${\displaystyle {}+3}$

文脈自由文法の観点から、非終端記号は、その生成規則の 1 つにおける最も左の記号がそれ自身である場合 (直接左再帰の場合)、または何らかの置換シーケンスによってそれ自身にできる場合 (間接左再帰の場合)、左再帰的である。

文法が左再帰的であるためには、非終端記号が存在し、その非終端記号自体を左端の記号として文法形式に導くことができる必要がある。 ^[1]記号的に言えば、 ${\displaystyle A}$

${\displaystyle A\Rightarrow ^{+}A\alpha }$、

ここで、 は1 つ以上の置換を行う操作を示し、終端記号と非終端記号の任意のシーケンスです。 ${\displaystyle \Rightarrow^{+}}$${\displaystyle \alpha }$

直接左再帰は、定義が1つの置換だけで満たされる場合に発生します。次の形式の規則が必要です。

${\displaystyle A\to A\alpha }$

ここで、は非終端記号と終端記号の列です。たとえば、次の規則 ${\displaystyle \alpha }$

${\displaystyle {\mathit {Expression}}\to {\mathit {Expression}}+{\mathit {Term}}}$

は直接左再帰です。この規則の左から右への再帰下降パーサは次のようになります。

void Expression () { Expression (); match ( '+' ); Term (); }  
  
  
  

このようなコードは実行されると無限再帰に陥ります。

間接左再帰は、左再帰の定義がいくつかの置換によって満たされるときに発生します。これは、パターンに従う一連の規則を伴います。

${\displaystyle A_{0}\to \beta _{0}A_{1}\alpha _{0}}$

${\displaystyle A_{1}\to \beta _{1}A_{2}\alpha _{1}}$

${\displaystyle \cdots }$

${\displaystyle A_{n}\to \beta _{n}A_{0}\alpha _{n}}$

ここで、 はそれぞれ空文字列 を生成するシーケンスであり、 は終端記号と非終端記号の任意のシーケンスである可能性がある。これらのシーケンスは空である可能性があることに注意してください。導出 ${\displaystyle \beta _{0},\beta _{1},\ldots ,\beta _{n}}$${\displaystyle \alpha _{0},\alpha _{1},\ldots ,\alpha _{n}}$

${\displaystyle A_{0}\Rightarrow \beta _{0}A_{1}\alpha _{0}\Rightarrow ^{+}A_{1}\alpha _{0}\Rightarrow \beta _{1}A_{2}\alpha _{1}\alpha _{0}\Rightarrow ^{+}\cdots \Rightarrow ^{+}A_{0}\alpha _{n}\dots \alpha _{1}\alpha _{0}}$

すると、最終的な文の形式では左端として与えられます。 ${\displaystyle A_{0}}$

左再帰は、演算を左結合的にするための慣用句としてよく使用されます。つまり、式はa+b-c-d+e次のように評価されます(((a+b)-c)-d)+e。この場合、その評価順序は、3つの文法規則によって構文的に実現できます。

${\displaystyle {\mathit {Expression}}\to {\mathit {Term}}}$

${\displaystyle {\mathit {Expression}}\to {\mathit {Expression}}+{\mathit {Term}}}$

${\displaystyle {\mathit {Expression}}\to {\mathit {Expression}}-{\mathit {Term}}}$

これらにより、が およびで構成され、 がおよび で構成され、 がおよびで構成される、などとして 解析することのみが可能になります。${\displaystyle {\mathit {Expression}}}$ a+b-c-d+e${\displaystyle {\mathit {Expression}}}$ a+b-c-d${\displaystyle {\mathit {Term}}}$ ea+b-c-d${\displaystyle {\mathit {Expression}}}$ a+b-c${\displaystyle {\mathit {Term}}}$ da+b-c${\displaystyle {\mathit {Expression}}}$ a+b${\displaystyle {\mathit {Term}}}$ c

左再帰は、パーサーにとってしばしば問題を引き起こします。これは、左再帰が無限再帰につながる (ほとんどのトップダウン パーサーの場合のように) か、または、左再帰を禁止する通常の形式のルールをパーサーが期待する (多くのボトムアップ パーサーの場合のように^{[説明が必要]} ) ためです。したがって、文法は左再帰を排除するために前処理されることがよくあります。

直接左再帰を除去するための一般的なアルゴリズムは以下のとおりです。この方法にはいくつかの改良が加えられています。^[2] 左再帰非終端記号の場合、形式の規則をすべて破棄し、残っている規則を検討します。 ${\displaystyle A}$${\displaystyle A\rightarrow A}$

${\displaystyle A\rightarrow A\alpha _{1}\mid \ldots \mid A\alpha _{n}\mid \beta _{1}\mid \ldots \mid \beta _{m}}$

どこ：

• それぞれは非終端記号と終端記号の空でない列であり、${\displaystyle \alpha }$
• それぞれは、で始まらない非終端記号と終端記号のシーケンスです。${\displaystyle \beta }$${\displaystyle A}$

これらを 2 つの生成セットに置き換えます。1 つは 用です。 ${\displaystyle A}$

${\displaystyle A\rightarrow \beta _{1}A^{\prime }\mid \ldots \mid \beta _{m}A^{\prime }}$

そして、新しい非終端記号(「末尾」または「残り」と呼ばれることが多い) 用の別のセット: ${\displaystyle A'}$

${\displaystyle A^{\prime }\rightarrow \alpha _{1}A^{\prime }\mid \ldots \mid \alpha _{n}A^{\prime }\mid \epsilon }$

直接の左再帰がなくなるまでこのプロセスを繰り返します。

例として、ルールセットを考えてみましょう

${\displaystyle {\mathit {Expression}}\rightarrow {\mathit {Expression}}+{\mathit {Expression}}\mid {\mathit {Integer}}\mid {\mathit {String}}}$

これを左再帰を避けるために書き直すと、

${\displaystyle {\mathit {Expression}}\rightarrow {\mathit {Integer}}\,{\mathit {Expression}}'\mid {\mathit {String}}\,{\mathit {Expression}}'}$

${\displaystyle {\mathit {Expression}}'\rightarrow {}+{\mathit {Expression}}\,{\mathit {Expression}}'\mid \epsilon }$

上記のプロセスを拡張して、最初にサイクル内の最も番号の大きい非終端記号で間接左再帰を直接左再帰に変換することにより、すべての左再帰を排除することができます。

入力 文法: 非終端記号とその生成規則の集合${\displaystyle A_{1},\ldots ,A_{n}}$

出力 同じ言語を生成するが左再帰を使わない修正文法

1. 各非終端記号について:${\displaystyle A_{i}}$
   1. 反復によって文法が変更されなくなるまで繰り返します。
      1. 各規則（終端記号と非終端記号のシーケンス）について:${\displaystyle A_{i}\rightarrow \alpha _{i}}$${\displaystyle \alpha _{i}}$
         1. が非終端記号で始まり、次のようになる場合:${\displaystyle \alpha _{i}}$${\displaystyle A_{j}}$${\displaystyle j<i}$
            1. 先導なしでも構いません。${\displaystyle \beta _{i}}$${\displaystyle \alpha _{i}}$${\displaystyle A_{j}}$
            2. ルールを削除します。${\displaystyle A_{i}\rightarrow \alpha _{i}}$
            3. 各ルールについて:${\displaystyle A_{j}\rightarrow \alpha _{j}}$
               1. ルールを追加します。${\displaystyle A_{i}\rightarrow \alpha _{j}\beta _{i}}$
   2. 上記のように直接左再帰を削除します。${\displaystyle A_{i}}$

ステップ 1.1.1 は、何らかの規則 の右側にある最初の非終端記号を拡張することに相当しますが、 の場合のみです。 が左再帰を生成する生成規則のサイクル内の 1 つのステップである場合、これによりそのサイクルは 1 ステップ短縮されますが、多くの場合、規則の数が増えるという代償を伴います。 ${\displaystyle A_{j}}$${\displaystyle A_{i}\to A_{j}\beta }$${\displaystyle j<i}$${\displaystyle A_{i}\to A_{j}\beta }$

このアルゴリズムは、非終端記号の位相的順序付けを確立するものと見なすことができます。つまり、の場合のみルールが存在します。このアルゴリズムは非終端記号の順序付けに非常に敏感であることに注意してください。最適化では、この順序付けを適切に選択することに重点が置かれることがよくあります。^{[説明が必要]}${\displaystyle A_{i}\to A_{j}\beta }$${\displaystyle j>i}$

上記の変換は文法によって生成された言語を保持しますが、文字列の認識を証明する解析ツリーを変更する可能性があります。適切なブックキーピングを使用すると、ツリーの書き換えによって元の状態に戻すことができますが、この手順を省略すると、違いによって解析の意味が変わる可能性があります。

結合性は特に脆弱です。新しい文法では、左結合演算子は通常、右結合のような配置で表示されます。たとえば、次の文法から始めます。

${\displaystyle {\mathit {Expression}}\rightarrow {\mathit {Expression}}\,-\,{\mathit {Term}}\mid {\mathit {Term}}}$

${\displaystyle {\mathit {Term}}\rightarrow {\mathit {Term}}\,*\,{\mathit {Factor}}\mid {\mathit {Factor}}}$

${\displaystyle {\mathit {Factor}}\rightarrow ({\mathit {Expression}})\mid {\mathit {Integer}}}$

左再帰を除去するための標準的な変換により、次の結果が得られます。

${\displaystyle {\mathit {Expression}}\rightarrow {\mathit {Term}}\ {\mathit {Expression}}'}$

${\displaystyle {\mathit {Expression}}'\rightarrow {}-{\mathit {Term}}\ {\mathit {Expression}}'\mid \epsilon }$

${\displaystyle {\mathit {Term}}\rightarrow {\mathit {Factor}}\ {\mathit {Term}}'}$

${\displaystyle {\mathit {Term}}'\rightarrow {}*{\mathit {Factor}}\ {\mathit {Term}}'\mid \epsilon }$

${\displaystyle {\mathit {Factor}}\rightarrow ({\mathit {Expression}})\mid {\mathit {Integer}}}$

LALR パーサー (左再帰文法を処理できる) の最初の文法を使用して文字列 "1 - 2 - 3" を解析すると、次の解析ツリーが生成されます。

この解析ツリーは左側の用語をグループ化し、正しい意味論(1 - 2) - 3 を与えます。

2番目の文法で解析すると、

これは、適切に解釈すると1 + (-2 + (-3))を意味し、これも正しいですが、入力に忠実ではなく、一部の演算子では実装がはるかに難しくなります。右再帰文法が1 - (2 - 3)に対してそれらを配置するのと同じように、右側の項がツリーのより深いところに表示されることに注意してください。

左再帰を含む形式文法は、弱等価な右再帰形式に変換されない限り、LL(k) パーサーやその他の単純な再帰下降パーサーでは解析できません。対照的に、左再帰は右再帰よりもスタック使用量が少ないため、LALR パーサーでは好まれます。ただし、より洗練されたトップダウン パーサーでは、削減を使用して一般的な文脈自由文法を実装できます。2006 年に、Frost と Hafiz は、直接的な左再帰生成規則を使用して曖昧な文法に対応するアルゴリズムを説明しました。^[3]このアルゴリズムは、2007年にFrost 、Hafiz、Callaghanによって、間接的および直接的な左再帰を多項式時間で処理し、非常に曖昧な文法の潜在的に指数関数的な数の構文解析木をコンパクトな多項式サイズの表現を生成する完全な構文解析アルゴリズムに拡張されました。 ^{[4]その後、著者らは、} Haskellプログラミング言語で記述されたパーサーコンビネータのセットとしてアルゴリズムを実装しました。^[5]

• 末尾再帰

• LALR(1)文法の実践的考察