文法をllに左分散する（1）

Question

文法をLL（1）に変換する必要がある宿題があります。私はすでに左の再帰を削除していますが、左因子を作るのに苦労しています。私が見つけたすべての例は簡単で、次のように見えます：

A -> aX | aY
なる：
A -> aZ
Z -> X | Y

という事は承知しています。しかし、私の文法はこのように見えます：

X -> aE | IXE | (X)E
E -> IE | BXE | ϵ
I -> ++ | --
B -> + | - | ϵ

これに簡単な例を適用する方法がわかりません。私は少なくとも数時間試してきましたが、私が試したことのすべてを追跡しました。一般的に、私の試みは次のように見えました：

X  -> X' | IXE
X' -> aE | (X)E
E  -> IE | BIX'E | BX'E | ϵ

そして、私は +または - で始まる1つの生産のみを持つeルールに変換しようとします。

X  -> X' | IXE
X' -> aE | (X)E
B' -> + | -
E  -> IE | B'IX'E | IX'E | B'X'E | X'E | ϵ

その後...

X  -> X' | IXE
X' -> aE | (X)E
B' -> + | -
E  -> +P | -M | ϵ
P  -> +E | IX'E | +X'E | X'E
M  -> -E | IX'E | -X'E | X'E

等々。しかし、私は常に多くの余分な非ターミナルと、実際にそれを左折したことなく、プロダクションの非常に長いプロダクション /チェーンで絶えず続きます。これにアプローチする方法がわかりません - 私は排除できないようです いくつかの 非末端A +から始まる複数のプロダクションがあります。

Answer 1

あなたの文法を見てみましょう：

$ qquad begin {align} x＆ to ae mid ixe mid（x）e e＆ to ie mid bxe mid varepsilon i＆ to text {++} mid mid mid mid text { - } b＆ to text {+} mid text { - } mid varepsilon end {align} $

$ x $には左翼は必要ありません。すべてのルールには、最初のセットがばらばらになります¹。これを明白にしたい場合は、$ i $をドロップしてインラインできます。

$ qquad begin {align} x＆ to ae mid text {++} xe mid text { - } xe mid（x）e e＆ to text {++} e mid text { - } e mid bxe mid varepsilon b＆ to text {+} mid text { - } mid varepsilon end {align} $ $

同様に、$ b $をインライン化できます。

$ qquad begin {align} x＆ to ae mid text {++} xe mid text { - } xe mid（x）e e＆ to text {++} e mid text { - } e mid text {+} xe mid text { - } xe mid xe mid varepsilon end {align} $

今、私たちは実際に$ e $で左翼を行わなければならないことがわかります。明らかな競合があり、$ xe $を介して追加の競合があります。したがって、$ xe $で1回$ x $をインラインにしましょう：

$ qquad begin {align} x＆ to ae mid text {++} xe mid text { - } xe mid（x）e e＆ to text {++} e mid text {} e mid text {+} xe mid text { - } xe mid aee mid text {++} xee mid text { - } xee mid（x（x ）ee mid varepsilon end {align} $

そして今、私たちはあなたの例と同じくらい簡単に左因子を左にすることができます：

$ qquad begin {align} x＆ to ae mid text {++} xe mid text { - } xe mid（x）e e＆ to text {+} p Mid text { - } m mid aee mid（x）ee mid varepsilon p＆ to text {+} e mid xe mid text {+} xee m＆ to text { - } e mid xe mid text { - } xee end {align} $

今ではどこにも到達していないことがわかります。$ text {+} $または$ text { - } $を代替案から除去することで、$ text {+の両方を備えた別の$ x $を掘り起こします。 } $ and $ text { - } $ inの最初のセット。

それでは、あなたの言語を見てみましょう。経由

$ qquad displaystyle x rightArrow ae rightArrow^* ai^n e rightArrow ai^nbxe $

と

$ qquad displaystyle x rightArrow ae rightArrow^* ai^n e rightArrow ai^nie $

あなたが持っている 任意に長い フォーム$+^+$のプレフィックス 異なる方法で終わります, 、セマンティックでは：ll（1）パーサーは、特定の（次の）$ text {+} $が属しているかどうかを決定できません。 ペア - これは、代替$ ie $ - または単独で来ることを選択することを意味します。これは、$ bxe $を選択することを意味します。

結果として、それはあなたのようには見えません 言語 で表現できます どれか LL（1）文法、だからあなたの文字を1つに変えようとすることは無駄です。

さらに悪いことです。 どれか 有限の外観。これは正式な証拠ではありませんが、あなたの言語がLLでさえないことを強く示唆しています。

あなたが何をしているのかを考えるなら、ポーランド語の表記と団結したオペレーターを混ぜると、解析が難しいはずであることはそれほど驚くことではありません。基本的に、左から数えなければなりません と $ text {+} $の長いチェーンで単一の$ b $-$ text {+} $を識別する権利から。チェーン内の複数の$ b $-$ text {+} $を考えると、言語さえ確信していません（2つあります 意味的には異なります しかし、構文的に等しい$ text {+} $）は、決定論的に（バックトラックなしで）解析できます。

---

1. これは、非ターミナル/ルールの代替案の派生物で最初に来ることができる端子のセットです。