Предварительные обсуждения

Введение

С о д е р ж а н и е

ФОРМАЛЬНЫЕ ЯЗЫКИ И ГРАММАТИКИ

Схемы СУ-перевода

Выше был описан принцип СУ-перевода, позволяющий получить линейную последовательность команд результирующей программы или внутреннего пред-

Введение.................................................................................... 3

1. Предварительные обсуждения.................................................... 4

2. Формальные грамматики............................................................. 9

3. Классификация формальных грамматик..................................... 15

4. Система составляющих.............................................................. 23

5. Синтаксические диаграммы........................................................ 26

6. Синтаксическое дерево.............................................................. 30

7. Алгоритмы обхода вершин дерева разбора................................. 40

7.1. Алгоритм обхода "сверху-вниз"................................................ 40

7.2. Алгоритм обхода "снизу-вверх"................................................ 41

8. Двоичное дерево........................................................................ 43

9. Свойства двоичного дерева...................................................... 52

10.Грамматический разбор цепочек.............................................. 56

10.1 Разбор цепочки "сверху-вниз"................................................ 57

10.2 Разбор цепочки "снизу-вверх"................................................ 62

11. Операции над языками............................................................ 65

Заключение............................................................................ 67

Контрольные вопросы и задачи............................................... 68

Индивидуальные задания........................................................ 70

Указатель обозначений............................................................. 72

Предметный указатель............................................................. 73

Список литературы................................................................... 75

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

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

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

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

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

Набор знаков, обеспечивающих формирование различимых единиц языка, называют базовым набором, а упорядоченный набор знаков - алфавитом языка. Набор 26 букв латинского алфавита обеспечивает формирование различимых единиц большинства европейских языков, набор 33 букв кириллического алфавита - формирование различимых единиц большинства славянских языков, а набор десяти цифр - написание любого числа и т.п.

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

Для объяснения синтаксиса формального языка можно рассмотреть основные правила формирования синтаксических конструкций естественного языка. Множество слов естественного языка разбито на синтаксические группы: существительные, глаголы, прилагательные, предлоги и т.д. Представителем каждой группы является синтаксическая переменная, сохраняющая имя синтаксической группы. Для удобства изложения представим синтаксические переменные, заключенными в угловые скобки, а слова, - заключенными в кавычки. Например, <существительное>, <глагол>, <прилагательное> и "алгоритм", "подмножество", " функция" и т.д..

Упорядоченная последовательность слов, которая описывает какие-либо признаки предмета, процедуры, события и/или связи между ними, формирует новую синтаксическую конструкцию - выражение. В выражение включаются слова из различных синтаксических групп. Например, выражение "собственное подмножество" это есть <прилагательное> и <существительное>, "вычислить значение" это - <глагол> и <существительное>.

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

Основной или начальной синтаксической переменной естественного языка является <предложение>, а остальные синтаксические переменные принимают участие в формировании правильной цепочки слов, отвечающей правилам синтаксиса и семантики этого языка.

Для строгого и точного описания синтаксиса языка удобно использовать какой-либо метаязык. Наиболее распространенным среди них является язык формул Бэкуса-Наура (язык БНФ или Бэкуса нормальная форма). На языке БНФ синтаксис языка описывается в виде некоторых формул, весьма похожих на обычные математические формулы.

Введем условные обозначения:

::= - знак о том, что выражение, стоящее слева, может быть

замещено выражением, стоящим справа ("...состоит из...");

<.. > - синтаксическая переменная языка;

".. " - слово (лексема) языка;

<.. ><.. >.. - соединение синтаксических переменных союзом "и";

<.. > | <.. >|.. - разделение синтаксических переменных

разделителем "или";

".. " <.. >.. | <.. > ".. ".. - соединение синтаксических

переменных и лексем союзом "и" и разделение

выражений и/или предложений языка разделителем "или";

".. " ".. ".. - cоединение лексем союзом "и";

".. " | ".. "|.. - разделение лексем разделителем "или";

{.. } - многократное повторение выражения, заключенного в

фигурные скобки, включая нуль раз;

[... ] - одно- или нулькратное повторение выражения,

заключенного в прямоугольные скобки.

Тогда основная формула БНФ может быть представлена в виде

Х::= Y1 ½ Y2 ½ Y3 ½..., (1)

где Х - выражение, определяемое только синтаксической

переменной;

Y_i - выражение, определяемое набором синтаксических

переменных и/или лексем, где I = 1, 2, 3,....

При подстановке вместо Х выражений Yi осуществляется вывод синтаксически правильной конструкции выражения или предложения, описываемого синтаксической переменной X.

Введем знак "=>", показывающий использование одного из правил синтаксиса и выводимости синтаксически правильной цепочки.

Пусть дано некоторое множество правил и множество лексем естественного языка, описанные на языке БНФ:

<предложение>::= <подлежащее> <сказуемое> |..;

<подлежащее>::= <прилагательное> <существительное> |..;

<сказуемое>::= <глагол> <дополнение> |..;

<дополнение>::=<предлог> <существительное>|

<прилагательное> <cуществительное> |..;

<cуществительное>::= "алгоритм" | "сходимость" | "кошка" | "диван"|..;

<глагол>::= "иметь" | "лежать" |..;

<прилагательное>::= "рыжий" | "хороший" | "высокий" |..;

<предлог>::= " на " |..; и т.д..

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

Знак "I" в правой части правил показывает возможность выбора значения синтаксической переменной, указанной в левой части.

Например,

<дополнение>::= <прилагательное> <существительное>;

<дополнение>::= <предлог> <существительное>;

<глагол>::= "иметь";

<глагол>::= "лежать";

и т.д.

Используя только эти правила естественного языка, можно показать возможности вывода и/или распознавания синтаксически правильных цепочек лексем в предложениях.

Пример 1. Пусть дано предложение "хороший алгоритм имеет высокую сходимость".

Верна ли синтаксическая конструкция предложения?

<предложение> => <подлежащее><сказуемое> => <прилагательное> <существительное> <сказуемое> => "хороший" <существительное> <cказуемое> => "хороший" "алгоритм" <сказуемое> => "хороший" "алгоритм" <глагол> <дополнение> => "хороший" "алгоритм" "имеет" <дополнение> => "хороший" "алгоритм" "имеет" <прилагательное> <существительное> => "хороший" "алгоритм" "имеет" "высокую" <существительное> => "хороший" "алгоритм" "имеет" "высокую" "cходимость".

Так доказана верность синтаксической конструкции исходного предложения.

Пример 2. Пусть дано предложение "рыжая кошка лежит на диване".

Верна ли синтаксическая конструкция предложения?

<предложение> => <подлежащее> <сказуемое> => <подлежащее> <глагол> <дополнение> => <подлежащее> <глагол> <предлог> <существительное> => <подлежащее> <глагол> <предлог> "диван" => <подлежащее> <глагол> "на" "диване" => <подлежащее> "лежит" "на" "диване" => <прилагательное> <существительное> "лежит" "на" "диване" => <прилагательное> "кошка" "лежит" "на" "диване" => "рыжая" "кошка" "лежит" "на" "диване".

Так доказана верность синтаксической конструкции исходного предложения.

Следует обратить внимание, что в первом примере правила грамматики применялись к крайней левой синтаксической переменной предложения, а во втором - к крайней правой.

Кстати, опираясь на вышеприведенное множество правил и лексем, можно вывести синтаксически правильные, но бессмысленные предложения. Например, "рыжий" "алгоритм" "лежит" "сходимости" или "высокая" "кошка" "имеет" "хороший" "диван"

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

Основными семантическими единицами естественного языка являются "понятие","суждение" и "умозаключение".

Выражение естественного языка, в котором находят отражение какие-либо признаки предмета, процедуры, события или связей между ними, называют понятием. Каждое понятие подразумевает заданными некоторую синтаксическую конструкцию и некоторое множество атрибутов, включаемых в описание признаков предмета, процедуры, события или связей между ними. Множество атрибутов, включаемых в описание, определяет содержание понятия, а множество предметов, процедур или событий - его объем.

Например, в понятие "аудитория" включен единственный атрибут - помещение, в котором читаются лекции и проводятся семинарские занятия, но объем его неограниченно большой (даже в одном учебном заведении может быть очень много аудиторий). В понятие "аудитория № 332 главного учебного корпуса УГАТУ" включены четыре атрибута - помещение, в котором читаются лекции и проводятся практические занятия, имя помещения внутри здания, имя здания и его принадлежность учебному заведению, но объем этого понятия ограничен единственным помещением.

Выражение естественного языка, в котором утверждается (или отрицается) факт существования предмета, процедуры, события или связей между ними, называют суждением. Над этими суждениями может быть задана логическая функция, которая принимает значения "true" или "false".

Например, выражение " 14 декабря 2012г. в 9.45 в аудитории 332 состоится лекция на тему..." может быть истинным или ложным по факту свершения этого события. Следовательно, это выражение является суждением.

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

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

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

Формальные языки, подобно естественным языкам, строятся над алфавитами основных символов, формируя синтаксические конструкции в виде лексем, выражений и предложений. Множество синтаксических и семантических правил формального языка не допускает многозначной интерпретации, что свойственно естественным языкам, и дает точное объяснение смысла и значения каждой синтаксической конструкции. Особое место среди формальных языков занимают языки программирования, т.к. они обеспечивают взаимодействие человека и вычислительной машины при решении конкретной задачи.

Дата добавления: 2015-06-27