4

楽しみのためにこれを実行する：http ：//www.diku.dk/hjemmesider/ansatte/torbenm/Basics/

null許容型の計算例で、最初に固定小数点計算を使用します。（セクション3.8を参照）

私はSchemeで物事を行っており、再帰に大きく依存しています。

null許容型または最初に再帰を介して実装しようとすると、次のようなプロダクションで無限に再帰することは明らかです。

N -> N a b

ここで、Nは非終端記号であり、a、bは終端記号です。

これは、プロダクションルールの左側に表示される非終端記号のセットを維持し、一度説明した後でそれらを無視することによって、再帰的に解決できますか？

これはnull許容型で機能するようです。最初はどうですか？

編集：これは私が遊んで学んだことです。下部にあるソースコードのリンク。

非終端記号は、null許容でない限り、firstの計算で無視することはできません。

検討：

N -> N a
N -> X
N ->

ここでは、がnull可能NでN aあるため、無視できます。のメンバーであるとN置き換えN -> N aてN -> a推測することができます。afirst(N)

ここでは無視できませんN：

N -> N a
N -> M
M -> b

Ninを無視した場合、それはfalseであるN -> N aと推測されます。代わりに、Nはnull許容ではないことがわかります。したがって、最初に計算するときに、RHSの最初のシンボルとして見つかった生成を省略できます。afirst(N)N

これにより、次のようになります。

N -> M
M -> b

これはb、にあることを示していfirst(N)ます。

ソースコード： http： //gist.github.com/287069

それで...これは大丈夫ですか？

4

1 に答える 1

1

私は読み続けることをお勧めします:)

3.13 Rewriting a grammar for LL(1) parsing特に3.13.1 Eliminating left-recursion。

間接的な左再帰にも遭遇する可能性があることに注意してください。

A -> Bac
B -> A
B -> _also something else_

ただし、ここでの解決策は、最初の例のように直接左再帰を排除することと非常に似ています。

もう少しわかりやすい方法で説明しているこのペーパーを確認することをお勧めします。より少ない理論:)

于 2011-03-08T16:00:46.827 に答える