※遞歸下降法：

簡而言之，就是比如文法是

S→T，T→FM,?F→+M，M→a

用偽代碼表示這個文法

則首先要寫 procedure?S?

BEGIN

T;

END

然后寫 procedure?T

BEGIN

F;

M;

END

Procedure?F

BEGIN

+M;

END

Procedure?M

BEGIN

匹配a

END

這樣的過程是遞歸下降的過程。遞歸下降方法僅表示一種思路，沒有特別的

※LL(1)預測分析法：

第一個L表示從左到右掃描輸入串

第二個L表示最左推導

1表示分析時每步只需向前查看一個符號

How to identify whether a grammar is LL(1), LR(0) or SLR(1)?

If you have no FIRST/FIRST conflicts and no FIRST/FOLLOW conflicts, your grammar is LL(1).

An example of a FIRST/FIRST conflict:

S?->?Xb?|?Yc X?->?a? Y?->?a

By seeing only the first input symbol a, you cannot know whether to apply the production S -> Xb or S -> Yc, because a is in the FIRST set of both X and Y.

An example of a FIRST/FOLLOW conflict:

S?->?AB? A?->?fe?|?epsilon? B?->?fg

By seeing only the first input symbol f, you cannot decide whether to apply the production A -> fe or A -> epsilon, because f is in both the FIRST set of A and the FOLLOW set of A (A can be parsed as epsilon and B as f).

Notice that if you have no epsilon-productions you cannot have a FIRST/FOLLOW conflict.

2.

X → Yz | a

Y → bZ | ε

Z → ε

To check if a grammar is LL(1), one option is to construct the LL(1) parsing table and check for any conflicts. These conflicts can be

• FIRST/FIRST conflicts, where two different productions would have to be predicted for a nonterminal/terminal pair.

• FIRST/FOLLOW conflicts, where two different productions are predicted, one representing that some production should be taken and expands out to a nonzero number of symbols, and one representing that a production should be used indicating that some nonterminal should be ultimately expanded out to the empty string.

• FOLLOW/FOLLOW conflicts, where two productions indicating that a nonterminal should ultimately be expanded to the empty string conflict with one another.

Let's try this on your grammar by building the FIRST and FOLLOW sets for each of the nonterminals. Here, we get that

FIRST(X)?=?{a,?b,?z} FIRST(Y)?=?{b,?epsilon} FIRST(Z)?=?{epsilon}

We also have that the FOLLOW sets are

FOLLOW(X)?=?{$} FOLLOW(Y)?=?{z} FOLLOW(Z)?=?{z}

From this, we can build the following LL(1) parsing table:

????a????b????z???$ X???a????Yz???Yz?? Y????????bZ???eps Z?????????????eps

Since we can build this parsing table with no conflicts, the grammar is LL(1).

To check if a grammar is LR(0) or SLR(1), we begin by building up all of the LR(0) configurating sets for the grammar. In this case, assuming that X is your start symbol, we get the following:

(1) X'?->?.X X?->?.Yz X?->?.a Y?->?. Y?->?.bZ(2) X'?->?X.(3) X?->?Y.z(4) X?->?Yz.(5) X?->?a.(6) Y?->?b.Z Z?->?.(7) Y?->?bZ.

From this, we can see that the grammar is not LR(0) because there are shift/reduce conflicts in states (1) and (6). Specifically, because we have the reduce items Z → . and Y → ., we can't tell whether to reduce the empty string to these symbols or to shift some other symbol. More generally, no grammar with ε-productions is LR(0).

However, this grammar might be SLR(1). To see this, we augment each reduction with the lookahead set for the particular nonterminals. This gives back this set of SLR(1) configurating sets:

(1) X'?->?.X X?->?.Yz?[$] X?->?.a??[$] Y?->?.???[z] Y?->?.bZ?[z](2) X'?->?X.(3) X?->?Y.z?[$](4) X?->?Yz.?[$](5) X?->?a.??[$](6) Y?->?b.Z?[z] Z?->?.???[z](7) Y?->?bZ.?[z]

Now, we don't have any more shift-reduce conflicts. The conflict in state (1) has been eliminated because we only reduce when the lookahead is z, which doesn't conflict with any of the other items. Similarly, the conflict in (6) is gone for the same reason.

轉載于:https://blog.51cto.com/11259454/1769146

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的Formal Languages and Compilers-LL(1),FIRST and FOLLOW的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。