製作語法LL（1）

Question

我有以下語法：

小號→一個S B S | b S a S | ε

因爲我試圖爲它編寫一個小編譯器，所以我想使它成爲LL（1）。我看到這裏似乎有一個第一/二次衝突，我知道我必須使用替代來解決它，但我不確定如何去做。這裏是我提出的語法，但我不確定它是否正確：

S-> aSbT | epsilon

T> bFaF | epsilon

F-> epsilon

有人可以幫忙嗎？

Answer 1

在他original paper on LR parsing，克努特給出了這種語言，這是他臆想「是這個語言最短的可能明確的語法：」下面的語法

小號→及小量; | aAbS | bBaS

A →＆epsilon; | aAbA

B →＆epsilon; | bBaB

直觀上，它試圖將任何As和Bs字符串分解爲完全平衡的塊。一些塊以a開始並以b結束，而其他塊以b開始並以a結束。

我們可以計算FIRST和FOLLOW集如下：

FIRST（S）= {＆小量，A，B}

FIRST（A）= {＆小量;,一}

FIRST（b）= {＆小量，b}

FOLLOW（S）= {$}

FOLLOW（A）= {b}

FOLLOW（B）= {A}

在此基礎上，我們得到以下LL（1）解析表：

| a | b | $ 
--+-------+-------+------- 
S | aAbS | bBaS | e 
A | aAbA | e | 
B | e | bBaB | 

所以這個語法不僅LR（1） ，但它也是LL（1）。

希望這會有所幫助！