Стр. 8 - Информационные структуры и их преобразование

6 Содержание
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
Любой язык (русский, английский, французский и т.д.) включает в себя
алфавит и систему правил построения предложений, а вообще язык можно
определить как систему дискретных звуков, необходимых для описания
внешнего мира . Предложения языка записываются в виде
последовательности символов из некоторого алфавита. Такие символы будем
называть терминальными символами или терминалами, а
последовательности терминалов – терминальными цепочками. Но для
того, чтобы компьютер правильно сделал разбор предложения, оказалось
недостаточно этих двух понятий – терминал и система правил. Поэтому
были введены еще два понятия: начальный символ и нетерминальный
символ или нетерминал.
Если терминальные символы – символы, из которых нет
дальнейшего вывода, то нетерминальные символы – символы, из которых
возможен дальнейший вывод цепочки.
Начальный символ – общая запись всех возможных конструкций
языка, построенных из элементов данного алфавита по определенным
правилам, образующим систему правил; т.е. начальным символом может
быть предложение, слово, число и т.д.
Для чего нужен начальный символ? С него начинается построение
синтаксического дерева, т.е. в вышерассмотренном примере <предложение>
и будет являться начальным символом. Существует два варианта разбора
синтаксических деревьев: сверху вниз и снизу вверх. При разборе сверху
вниз мы получим множество конструкций, каждую из которых нужно будет
сравнить с введенной, и если ни одна из полученных конструкций не
совпадет с введенной, то можно утверждать, что введена неправильная
конструкция. Это очень долгий и трудоемкий вариант. При разборе снизу
вверх мы введенную конструкцию преобразуем согласно правилам, т.е.
отыскиваем правые части правил и заменяем их левыми частями, в
результате чего мы должны получить начальный символ, если по окончании
разбора начальный символ не получен, то можно сделать вывод, что введена
неправильная конструкция.
Учитывая вышеизложенное, вычислительную среду формально можно
представить в виде следующих правил:
<ВС>:=<АС><ПС>, <ПС>:=<ОС><ПИ>, где
ВС - вычислительная среда, АС - аппаратные средства;
ПС - программные средства; ОС - операционная система;
ПИ - программный интерфейс;
«: =» - «это есть» по определению.