Изготовление грамматики LL (1)

Question

У меня есть следующая грамматика:

S → a S b S | b S a S | ε

Поскольку я пытаюсь написать для него небольшой компилятор, я бы хотел сделать это LL (1). Я вижу, что здесь существует конфликт FIRST/FOLLOW, и я знаю, что мне нужно использовать подстановку для его решения, но я не совсем уверен, как это сделать. Вот моя предложенная грамматика, но я не уверен, что она правильная:

S-> aSbT | epsilon

T-> bFaF | эпсилон

F-> эпсилон

Может кто-то помочь?

Answer 1

В original paper on LR parsing, Кнут дает следующую грамматику для этого языка, он домыслы «является кратчайшей возможной однозначной грамматикой для этого языка:»

S → & эпсилон; | aAbS | bBaS

A → & epsilon; | aAbA

B → & epsilon; | bBaB

Интуитивно, это пытается разбить любую строку As и Bs на блоки, которые полностью балансируют. Некоторые блоки начинаются с a и заканчиваются на b, в то время как другие начинаются с b и заканчиваются на.

Мы можем вычислить первый и ПОСЛЕДУЮЩИЕ наборы следующим образом:

FIRST (S) = {& эпсилон ;, а, б}

ПЕРВЫЙ (А) = {& эпсилон ;, а}

ПЕРВЫЙ (В) = {& эпсилон ;, б}

ПОСЛЕДУЮЩИЕ (S) = {$}

ПОСЛЕДУЮЩИЕ (а) = {Ь}

FOLLOW (B) = {а}

Исходя из этого, мы получаем следующую LL (1) синтаксический анализ таблицы:

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

И так эта грамматика не только LR (1) , но это тоже LL (1).

Надеюсь, это поможет!