Разработка компиляторов
Нормализация грамматик
Покажем, что для деревянной грамматики, у которой в правой части правил находятся образцы произвольного вида, существует эквивалентная грамматика в нормальной форме.
Пусть G=(A,N,S,R) - грамматика произвольного вида. Построим по ней грамматику G'=(A,N',S,R') в нормальной форме, действуя следующим образом:
- первоначально множества нетерминалов и правил для новой грамматики совпадают с таковыми для старой;
- выберем среди правил новой грамматики правило R=N:p, у которого образец p в правой части не находится в нормальной форме, и удалим его. Если такого правила нет, то грамматика уже находится в нормальной форме;
- добавим в грамматику столько новых нетерминалов, сколько сыновей у root(p) , которые не являются тривиальными образцами (т.е. листьями, помеченными нетерминалами);
- добавим в множество правил дополнительные правила, которые содержат в левой части новые нетерминалы, а в правой - те поддеревья p , которые не являются тривиальными образцами;
- добавим в множество правил правило N=p', где p' - образец, полученный из p заменой тех его поддеревьев, которые не являются тривиальными образцами, на листья, помеченные соответствующими новыми нетерминалами;
- перейдем к шагу 2.
