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

1. ВВЕДЕНИЕ

Часто при вычислениях нам приходится иметь дело с объектами, обладающими структурой. Грамматическая структура английского предложения состоит из подлежащего, сказуемого, группы дополнения и прочих элементов. Структурными элементами программы для вычислительной машины являются подпрограмма, процедура, выражение. Блок-схеме соответствует структура из многоугольников и линий. Массив данных имеет структуру, которая определяется соответствующими индексами. Перечень таких примеров можно было бы продолжить. У нас может возникнуть желание описывать подобные структуры таким образом, чтобы суметь потом оперировать с соответствующими классами, как мы оперируем с классом грамматически правильных английских предложений, с классом синтаксически правильных алгольных программ или с классом правильно сформированных массивов или файлов определенного вида. Такие описания пригодятся для того, чтобы мы могли определять, принадлежит ли заданный объект определенному классу, или чтобы мы могли получать примеры элементов класса, или чтобы мы могли оперировать с целыми классами, например при поиске пересечения двух классов. Структура сама по себе тоже может интересовать нас. Например, грамматическая структура предложения помогает нам интерпретировать его смысл, раскрывая Связи между частями. Аналогично структура алгольной программы показывает нам нужные связи между соответствующими частями и тем самым помогает компилировать эту программу. Так, структура алгольного выражения

может быть изображена в виде

который показывает, какие части арифметического выражения связаны знаком плюс, а какие — знаком умножения.

Если бы соответствующая структура имела вид

то интерпретация выражения была бы совершенно другой.

Поэтому нам нужны формальные описания структур объектов. Поскольку раньше всего были изучены грамматические описания предложений, то обычно пользуются терминологией, заимствованной из лингвистики, хотя целью рассмотрений могут оказаться и нелингвистические применения грамматик. В этой книге мы будем иметь дело только с одномерными объектами, а именно с последовательностями (предложениями) из неделимых элементов (слов). Под структурой (грамматическим разбором) предложения будут пониматься порядок и структура его частей. Мы будем пользоваться так называемыми контекстно-свободными грамматиками. Они не являются единственным средством описания структур предложений, но обычно именно на них основывается применение грамматик для компиляции [1, 7, 10, 13, 15].

Грамматики могут применяться для двух различных целей. Во-первых, мы могли бы захотеть рассматривать грамматику как формальный набор правил для порождения всех корректных предложений какого-то языка. В таком случае дело сводится к составлению грамматик для порождения языков и к преобразованиям грамматик. Например, авторы сообщения об Алголе придумали такую грамматику, которая могла бы формально порождать правильные (грамматически) алгольные программы. Во-вторых, кто-то мог бы задать нам набор грамматических правил и некоторое предложение и попросить нас либо разобрать это предложение в соответствии с этими правилами, либо выяснить, существует ли хотя бы один способ такого разбора. Этот второй подход привел к постановке задач отыскания алгоритмов, которые будут производить грамматический разбор эффективно и заведомо гарантированы от зацикливания. Именно такие задачи мы будем рассматривать в данной книге. Подобные алгоритмы называются алгоритмами грамматического разбора или синтаксическими анализаторами.

Грамматики, используемые для описания языков программирования, гораздо более просты, чем те грамматики, которые нужны для естественных языков. Поэтому мы никоим образом не будем затрагивать последних, и всюду далее подразумевается, что рассматриваемые грамматики непригодны для естественных языков [8]. Языки программирования разрабатываются с таким расчетом, чтобы было легко читать и писать на них (а также компилировать с них), поэтому они обычно имеют простую структуру.

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

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

В скобочной записи оно приобретает вид

и задача грамматического разбора становится тривиальной, так как скобки описывают структуру. Однако такое систематическое внесение скобок в алгольное выражение или в английское предложение сделало бы текст неудобочитаемым, и поэтому обычно скобки отсутствуют, а ставятся они только тогда, когда без них нельзя обойтись. У нас может появиться желание различать разные способы образования групп символов. Если переписать предыдущее выражение, употребляя круглые скобки для групп, соответствующих знаку плюс, и квадратные скобки для групп, соответствующих знаку умножения, то оно будет выглядеть следующим образом:

Возможна и такая запись:

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

В гл. 2 приводятся некоторые элементарные определения и примеры грамматик. В гл. 3 рассматривается общая проблематика грамматического разбора. Глава 4 посвящена методам грамматического разбора, применимым к любым контекстно-свободным грамматикам. В гл. 5 рассматриваются некоторые ограниченные классы грамматик, для которых можно обеспечить высокую скорость синтаксического анализа. В гл. 6 речь идет о преобразованиях грамматик и, в частности, о получении эквивалентных грамматик, более удобных для синтаксического анализа, чем исходные грамматики. Из гл. 7, а также из первой части гл. 6 можно получить краткое представление о том, как разбор структуры программы может использоваться для компиляции.

Впервые синтаксический анализ применялся в компиляторах Брукера и Морриса [3, 4, 5] и Айронса [21, 22]. Более подробную библиографию содержит отличная обзорная статья Фельдмана и Гриса [10].

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

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