刪除左遞歸語法

Question

如何刪除以下語法中的左遞歸？

S -> 「url」 「(「 STRING 「)」 // basic services 
| S 「?」 S // sequential execution 
| S 「|」 S // concurrent execution 
| 「timeout」 「(「 REAL 「,」 S 「)」 // timeout combinator 
| 「repeat」 「(「 S 「)」 // repetition 
| 「stall」 // nontermination 
| 「fail」 // failure 

Answer 1

訣竅是創建一個正確的遞歸父生產。

T -> S 
T -> S "?" T // sequential execution 
T -> S "|" T // concurrent execution 

S -> 「url」 「(「 STRING 「)」 // basic services 
| 「timeout」 「(「 REAL 「,」 S 「)」 // timeout combinator 
| 「repeat」 「(「 S 「)」 // repetition 
| 「stall」 // nontermination 
| 「fail」 // failure 

這將識別同一組輸入，但要注意T現在是正確的聯想，而不是左聯想。