parsing - LL(1) 解析 -- 再帰的な最初の選択肢を使用した First(A)

Question

次のようなプロダクションに FIRST() ルールを適用するにはどうすればよいですか。

A -> AAb | アブ | s

ここで、A は非終端記号で、b,s は終端記号です。

選択肢 1 と 2 の FIRST(A) は再び A になりますが、FIRST セットを取得するには端末が必要なので、これは FIRST の無限の適用に終わりますか?

Answer 1

To compute FIRST sets, you typically perform a fixed-point iteration. That is, you start off with a small set of values, then iteratively recompute FIRST sets until the sets converge.

In this case, you would start off by noting that the production A → s means that FIRST(A) must contain {s}. So initially you set FIRST(A) = {s}.

Now, you iterate across each production of A and update FIRST based on the knowledge of the FIRST sets you've computed so far. For example, the rule

A → AAb

Means that you should update FIRST(A) to include all elements of FIRST(AAb). This causes no change to FIRST(A). You then visit

A → Ab

You again update FIRST(A) to include FIRST(Ab), which is again a no-op. Finally, you visit

A → s

And since FIRST(A) already contains s, this causes no change.

Since nothing changed on this iteration, you would end up with FIRST(A) = {s}, which is indeed correct because any derivation starting at A ultimately will produce an s as its first character.

For more information, you might find these lecture slides useful (here's part two). They describe in detail how top-down parsing works and how to iteratively compute FIRST sets.

Hope this helps!

Answer 2

Answer 3

あなたの文法規則は、すでに認識しているように左再帰を持っており、LL パーサーは左再帰を使用して文法を解析できません。

したがって、最初に左再帰を取り除く必要があり、それからルールの最初のセットを計算できるはずです。