Сделать грамматику однозначной?

Question

У меня есть следующая проблема. Эта грамматика неоднозначна:

stmt -> if expr then stmt stmt '| a

stmt '-> else stmt | EPSILON

выраж -> б

Я попытался изменить его, и мой результат:

STMT -> если выражение затем STMT»» | a

stmt '' -> stmt | STMT»

STMT» -> B еще STMT

выраж -> б

Но это не создает тот же язык.

Может ли кто-нибудь помочь мне изменить двусмысленную грамматику, чтобы она была однозначной и принимала один и тот же язык?

Answer 1

Использование данной грамматики состоит из двух левых выводов для строки if b then if b then a else a следующим образом.

Вывод 1:

if expr then stmt stmt' 
if b then stmt stmt' 
if b then if expr then stmt stmt' stmt' 
if b then if b then stmt stmt' stmt' 
if b then if b then a stmt' stmt' 
if b then if b then a stmt' 
if b then if b then a else stmt 
if b then if b then a else a 

Вывод 2:

if expr then stmt stmt' 
if b then stmt stmt' 
if b then if expr then stmt stmt' stmt' 
if b then if b then stmt stmt' stmt' 
if b then if b then a stmt' stmt' 
if b then if b then a else stmt stmt' 
if b then if b then a else a stmt' 
if b then if b then a else a 

Деревья разбора остается одинаковой для большей части. Но после получения if b then if b then a stmt' stmt' порядок узлов изменяется, тем самым влияя на структуру дерева. Следовательно, данная грамматика неоднозначна.