Как преобразовать эту грамматику в LL (1)?

Question

S → Y | 1X

X → 1X | 0

Y → Y 0 | 1X1 | 2X2

Я не понимаю, как делать факторинг или замену, когда есть более одного символа. Благодарю вас.

Answer 1

X → 1 X | 0 

относится к 0-или-более 1 с последующим 0, так что это эквивалентно

X → 1* 0 

Тот же самый подход может быть использован, чтобы удалить левую рекурсию. Вы можете переписать

S → Y | 1 X 
X → 1 X | 0 
Y → Y 0 | 1 X 1 | 2 X 2 

в

S → Y | 1 X 
X → 1* 0 
Y → (1 X 1 | 2 X 2)* 0 

В EBNF:

S → Y | 1 X 
X → 1* 0 
Y → A* 0 
A → 1 X 1 | 2 X 2 

В BNF:

S → Y | 1 X 
X → 1* 0 
Y → A* 0 
A → 1 X 1 | 2 X 2 

1* → 1 1* | Ɛ 
A* → A A* | Ɛ 

Если все, что вы хотели сделать, чтобы устранен левую рекурсию , все готово.

---

Если вы хотите устранить общие префиксы тоже, вы не сделали, потому что оба суб-правила S может начинаться с 1 X. Чтобы исправить это, инлайн и распространять, чтобы получить следующее:

S → 0 
    | 1 X 1 Y 
    | 2 X 2 Y 
    | 1 X 
X → 1* 0 
Y → A* 0 
A → 1 X 1 | 2 X 2 

Теперь мы, наконец, в состоянии вынесем общий 1 X.

S → 0 
    | 1 X (1 Y)? 
    | 2 X 2 Y 
X → 1* 0 
Y → A* 0 
A → 1 X 1 | 2 X 2 

В EBNF:

S → 0 | 1 X B? | 2 X 2 Y 
X → 1* 0 
Y → A* 0 
A → 1 X 1 | 2 X 2 
B → 1 Y 

В BNF:

S → 0 | 1 X B? | 2 X 2 Y 
X → 1* 0 
Y → A* 0 
A → 1 X 1 | 2 X 2 
B → 1 Y 

B? → B | Ɛ 
1* → 1 1* | Ɛ 
A* → A A* | Ɛ