Разработка компиляторов
О преобразовании грамматик
Как мы уже видели в предыдущем примере, иногда может возникнуть потребность в преобразовании КС-грамматик.
К сожалению, не существует общего алгоритмического метода приведения КС-грамматик к произвольному виду, как не существует и алгоритма, определяющего равенство языков, задаваемых двумя КС-грамматиками. Однако известен целый ряд преобразований, таких как устранение бесполезных символов и устранение цепных правил, которые позволяют привести грамматику к более удобной форме.
Кроме того, известно, что любая КС-грамматика может быть приведена к нормальному виду Хомского , в котором все правила имеют один из следующих видов:
- , где А , B и C - нетерминалы
- , где a - терминал
- , при условии, что символ принадлежит языку, а нетерминал S не встречается в правых частях правил
Другим широко распространенным стандартным видом КС-грамматик является нормальная форма Грейбах , в которой все правые части правил начинаются с терминалов.
Перейдем к рассмотрению класса распознавателей, соответствующих классу языков, задаваемых КС-грамматиками - к магазинным автоматам.
