c - 次の文法の左導出と右導出

Question

これはとても簡単なトピックです。私は自分自身に恥ずかしいです。しかし、学期が始まる前にいくつかの復習問題を行っていて、このトピックについて完全に空白にしていることに気付きました.

文法を仮定すると:

int = int digit | digit
digit = 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19

次の左導関数と右導関数を書きます。

15 14 13 12

次のようになるはずです。

int => int digit
=> int digit digit
=> int digit digit digit
=> digit digit digit digit

...しかし、私は何をすべきかわかりません (または、それが正しいとしても)。また、他の方向にそれを行う方法もわかりません!

したがって、誰かが私に a) 将来これを行う方法を説明し、b) プロセスを理解していることを確認できるように答えてくれたら素晴らしいと思います。すべての助けに本当に感謝しています！

Answer 1

この場合、左端と右端の派生は同じです。これは、あなたが示したとおりです。

左端の導出は、左端の非終端記号を最初に展開します。右端の導出は、右端の非終端記号を最初に展開します。

ウィキペディアには良い例があります。 文法について

S → S + S
S → 1
S → a

これは左端の派生です:

S → S + S
  → 1 + S
  → 1 + S + S
  → 1 + 1 + S
  → 1 + 1 + a

これは右端の派生です:

S → S + S
  → S + a
  → S + S + a
  → S + 1 + a
  → 1 + 1 + a