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

       

О преобразовании грамматик


Как мы уже видели в предыдущем примере, иногда может возникнуть потребность в преобразовании КС-грамматик.

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

Кроме того, известно, что любая КС-грамматика может быть приведена к нормальному виду Хомского , в котором все правила имеют один из следующих видов:

  • , где А , B и C - нетерминалы
  • , где a - терминал
  • , при условии, что символ принадлежит языку, а нетерминал S не встречается в правых частях правил

Другим широко распространенным стандартным видом КС-грамматик является нормальная форма Грейбах , в которой все правые части правил начинаются с терминалов.

Перейдем к рассмотрению класса распознавателей, соответствующих классу языков, задаваемых КС-грамматиками - к магазинным автоматам.



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