Равны ли эти 2 грамматики?

Я надеюсь, что ваше задание будет отмечено кем-то, кто даст хороший отзыв. Хотелось бы верить, что кое-где еще работает высшее образование, но, очевидно, это иллюзия.

Тем не мение. Грамматика, с которой вы в конечном итоге столкнетесь, является правильным решением проблемы в том виде, в каком вы ее представляете, но решение основано на неправильном представлении и ошибке, которые по совпадению компенсируют друг друга и дают правильный результат.

Во-первых, неправильное представление: левая рекурсия — это не то же самое, что неоднозначность, и, следовательно, левая факторизация и устранение левой рекурсии не устраняют неоднозначность. В частности, ваше утверждение о том, что «это устраняет двусмысленность, но по-прежнему не является SLR (1)», ошибочно. Преобразование не устраняет двусмысленность; грамматика по-прежнему не является SLR(1), потому что она по-прежнему неоднозначна.

E                   E
T E'                T E'
A T' E'             A T' E'
B A' T' E'          B A' T' E'
x A' T' E'          x A' T' E'
x T' E'             x T' E'
x + A T' E'         x E'
x + B A' T' E'      x + A + A E'
x + x A' T' E'      x + B A' + A E'
x + x T' E'         x + x A' + A E'
x + x + A T' E'     x + x + A E'
x + x + B A' T' E'  x + x + B A' E'
x + x + x A' T' E'  x + x + x A' E'
x + x + x T' E'     x + x + x E'
x + x + x E'        x + x + x
x + x + x

Ошибка заключается в стирании T правил. Вы начинаете с

E -> T E' .
T -> A T' .
T' -> + A T' .
T' -> - A T' .
T' -> .

Отсюда можно легко стереть T, так как он используется только в одном месте:

E -> A T' E'.
T' -> + A T' .
T' -> - A T' .
T' -> .

Однако стереть T' не так просто, потому что он рекурсивный. И, в любом случае, в E' нет производства, использующего T', поэтому добавление новых производств в E' не является механическим устранением T'.

Однако произведения, которые вы решили добавить к E', на самом деле устраняют двусмысленность. Так молодец, в этом смысле. Но обратите внимание, что вы могли бы сделать это без устранения левой рекурсии:

E -> E + A + A .
E -> E + A - A .
E -> E - A + A .
E -> E - A - A .
E -> A + A .
E -> A - A .
E -> A .
A -> A * B .
A -> A / B .
A -> B .
B -> ( E ) .
B -> x .

Эта грамматика однозначна по той же причине, что и ваша: операторы + и - разлагаются на последовательность троичных операций, которым, возможно, предшествует одна бинарная операция (в случае последовательность аддитивных операторов содержит нечетное число операторов). Но это не SLR(1). В самом деле, это не LR(k) для любого k, потому что невозможно узнать, должна ли последовательность операций начинаться с тернарной или бинарной операции, пока мы не узнаем, четное или нечетное число операторов.

Но мы можем решить эту проблему (по сути, так же, как и ваша грамматика), сделав аддитивные операторы правоассоциативными:

E -> A + A + E .
E -> A + A - E .
E -> A - A + E .
E -> A - A - E .
# Rest of the grammar is the same

Эта грамматика, конечно, не LL(1); это не левый фактор. Но исходная задача не требовала грамматики LL(1), а приведенное выше — это SLR(1).

Однако это всего лишь одна из возможных интерпретаций исходной неоднозначной грамматики, и, вполне возможно, не самая естественная, поскольку правая ассоциативность обычно не является естественной интерпретацией. Если в задаче не указана желаемая ассоциативность, невозможно узнать, что требуется.