Разработка компиляторов

       

Нормализация грамматик


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

Пусть G=(A,N,S,R) - грамматика произвольного вида. Построим по ней грамматику G'=(A,N',S,R') в нормальной форме, действуя следующим образом:

  1. первоначально множества нетерминалов и правил для новой грамматики совпадают с таковыми для старой;
  2. выберем среди правил новой грамматики правило R=N:p, у которого образец p в правой части не находится в нормальной форме, и удалим его. Если такого правила нет, то грамматика уже находится в нормальной форме;
  3. добавим в грамматику столько новых нетерминалов, сколько сыновей у root(p) , которые не являются тривиальными образцами (т.е. листьями, помеченными нетерминалами);
  4. добавим в множество правил дополнительные правила, которые содержат в левой части новые нетерминалы, а в правой - те поддеревья p , которые не являются тривиальными образцами;
  5. добавим в множество правил правило N=p', где p' - образец, полученный из p заменой тех его поддеревьев, которые не являются тривиальными образцами, на листья, помеченные соответствующими новыми нетерминалами;
  6. перейдем к шагу 2.



Содержание раздела