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

хорошо, допустим, у меня следующая грамматика

<Exp> ->  <Term>
<EXp>  -> <Term> {<AddOp> <Exp>}  
<Term> -> <Factor> {<MultOp> <Term>}
<Factor> -> <id> |  <no> | ( <Exp> )

Вещь внутри {} необязательна. так что технически я могу просто иметь exp-> term или term-> Factor. Теперь возможен следующий вывод для, скажем, числа 10. exp-> term-> factor-> no-> 10 .. могу я просто добавить нет к exp?

<Exp> ->  <Term>|<no>

или это сделает грамматику неоднозначной или возникнут другие проблемы? Спасибо.

Ps Addop и MultOp стоят просто + и *


context-free-grammar
person vaish    schedule 01.05.2017    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Ваша исходная грамматика уже неоднозначна: <Exp> получает <Term> двумя разными способами: через производство 1 и через производство 2. Производство 1 ничего не добавляет к грамматике, поэтому вы можете просто удалить его, и вы получите однозначную грамматику для на том же языке.

Но затем, если вы добавите продакшн <Exp> -> <no>, вы снова получите неоднозначную грамматику, потому что <Exp> будет производным <no> двумя разными способами. Первый способ вы уже показали, а второй - банальное применение новой продукции.

person Michael Dyck    schedule 02.05.2017