Главная > Разное > Автоматический синтаксический анализ
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6.2. ДРУГИЕ ПРЕОБРАЗОВАНИЯ

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

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

эквивалентна грамматике

а грамматика

эквивалентна грамматике

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

то мы можем ввести новый класс и записать

Если же для некоего класса имеются два правила подстановки, в которых нет явного совпадения, но которые могут начинаться с одного и того же слова, например

то мы можем сначала записать

а затем

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

мы получаем из нее

и возникает трудность в связи с правилом

так как за классом Z может следовать В.

Второе затруднение возникает из-за того, что процесс преобразования может оказаться бесконечным циклом. Рассмотрим грамматику

Сначала мы получаем из нее

а затем

Теперь мы находимся в таком же положении относительно классов Z, X и Y, в каком были первоначально относительно А, X и Y, и поэтому процесс никогда не закончится. В данном случае мы могли бы заметить аналогию и записать

Другой пример неудачного преобразования возникает при исходной грамматике

Для получения грамматик с операторным предшествованием или грамматик с предшествованием используются сравнительно простые преобразования. Обычно они сводятся к исключению нерекурсивных классов или к введению новых классов, как показано в гл. 5.

<< Предыдущий параграф Следующий параграф >>
Оглавление