ЛИНГВИСТИЧЕСКИЕ СРЕДСТВА

ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Конспект лекций


ВВЕДЕНИЕ
В состав любой вычислительной системы может входить комплекс программ, которые называются трансляторами. Транслятор обеспечивает автоматический перевод программ с алгоритмического языка в машинные коды.

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

Более подробно остановимся на компиляторах. Компилятор – это не что иное, как программа, написанная на некотором языке, для которой входной информацией служит исходная программа, а результатом является эквивалентная ей объектная программа. Раньше компиляторы писались на автокоде. Часто это был единственно доступный язык. Однако сейчас существует тенденция писать компиляторы на языках высокого уровня, поскольку при этом уменьшается время, затрачиваемое на программирование и отладку, а также обеспечивается удобочитаемость компилятора, когда работа над ним завершена.

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

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

Взаимодействие между компонентами компилятора может осуществляться разнообразными способами.

В настоящей работе рассматриваются основные подходы к созданию транслирующих программ.

Приведенные подходы будут полезны для бакалавров 2-го курса специальности 230100 – "Информатика и вычислительная техника" при выполнении лабораторных и курсовой работы по дисциплине "Лингвистические средства вычислительных систем" и магистров 5-го года обучения специальности 230100 – "Информатика и вычислительная техника" при выполнении лабораторных работ по дисциплине «Теория языков программирования и методы трансляции».

---

Лекция 1. ТЕОРИЯ ФОРМАЛЬНЫХ ГРАММАТИК И

ЯЗЫКОВ
План:

1. 
   Грамматика
   
2. 
   Формальные определения грамматики и языка
   
3. 
   Классификация грамматик
   
4. 
   Синтаксические деревья
   

Ключевые слова: синтаксис языка, семантика языка, грамматика, формальный язык, синтаксический язык.
1. Грамматика
Грамматика языка является формальным описанием его синтаксиса или формы, в которой записаны отдельные предложения программы или вся программа. Грамматика не описывает семантику или значения различных предложений.

В качестве иллюстрации разницы между синтаксисом и семантикой рассмотрим два предложения:
i := j + k и i := x + y ,
где (x), (y) являются действительными переменными, а (i), (j), (k)
целыми.

Эти два предложения имеют одинаковый синтаксис. Оба являются операторами присваивания. Но с точки зрения семантики, эти предложения разные, так как компилируются в совершенно различные последовательности машинных команд.

В первом случае складываются целые переменные (j) и (k) и результат присваивается переменной (i).

Во втором случае необходимо сложить вещественные переменные (x) и (y), а результат преобразовать к целому виду и полученное значение присвоить переменной (i).

В качестве примера мы будем использовать программу на языке ПАСКАЛЬ, изображённую на рис. 1, однако обсуждаемые концепции и подходы приложимы и к другим языкам. Существует несколько различных форм записи грамматик, среди которых мы рассмотрим форму Бекуса-Наура (БНФ). БНФ не самое мощное из известных средств описания синтаксиса. Однако эта форма достаточно проста, широко используется и предоставляет достаточные для большинства приложений средства.

На рис. 2 изображена одна из возможных грамматик БНФ для очень узкого подмножества языка ПАСКАЛЬ. Полное описание грамматики БНФ для ПАСКАЛЯ содержится в [].

program primer; var sum, a, rez, i: integer; begin sum:=0; for i:=1 to 100 do begin read(a); sum:=sum+a end; rez:=sum div100–a*a; write(rez,sum) end.

Рис. 1
Грамматика БНФ состоит из множества правил вывода, каждое из которых определяет синтаксис некоторой конструкции языка. Рассмотрим, например, правило 8 на рис. 2:

<присваивание>  ид := <арифметическое выражение>

---

1. <программа>  <имя программы> var <раздел переменных> begin <раздел операторов> end. 2. <имя программы>  ид 3. <раздел переменных>  <список переменных>:<тип> 4. <список переменных>  ид /<список переменных>, ид 5. <тип>  integer 6. <раздел операторов> <оператор>/<раздел операторов>;<оператор> 7. <оператор>  <присваивание>/<ввод>/<вывод>/<цикл> 8. <присваивание>  ид := <арифметическое выражение> 9. <арифметическое выражение>  <слагаемое>/<арифметическое выражение> +/- <слагаемое> 10. <слагаемое>  <значение> / <слагаемое> */div <значение> 11. <значение>  ид/ конст/(<арифметическое выражение>) 12. <ввод>  read (<список переменных>) 13. <вывод>  write (<список переменных>) 14.<цикл>  for <выражение цикла> to <тело цикла> 15. <выражение цикла>  ид :=<арифметическое выражение> do <арифметическое выражение> 16. <тело цикла>  <оператор>/ begin <раздел операторов> end

Рис. 2

Это определение оператора присваивание языка ПАСКАЛЬ, обозначенное как <присваивание>. Символ «» можно читать как «является по определению». С левой стороны от этого символа находится определяемая конструкция языка (в нашем случае <присваивание>), а с правой – описание синтаксиса этой конструкции. Строки символов, заключенные в угловые скобки, называются нетерминальными символами. Они составляют синтаксические классы языка. Символы, не заключенные в угловые скобки, называются терминальными символами. Они составляют лексические классы или алфавит языка. В рассматриваемом примере нетерминальными символами являются <присваивание> и <арифметическое выражение>, а терминальными - ид и :=. Таким образом, это правило определяет, что конструкция <присваивание> состоит из идентификатора (терминал ид), символа алфавита :=, за которым следует конструкция <арифметическое выражение>. Пробелы для написания грамматики не существенны и вставляются только для наглядности.

Для распознавания нетерминального символа <присваивание> необходимо, чтобы существовало определение для нетерминального символа <арифметическое выражение>. Это определение дается правилом 9 на рис. 2:
<арифметическое выражение>  <слагаемое>/<арифметическое выражение> +/- <слагаемое>

---

Это правило предполагает две возможности, разделенные символом /. Первая состоит в том, что <арифметическое выражение> состоит из одной конструкции <слагаемое>. Другой вариант состоит в том, что <арифметическое выражение> состоит из конструкции <арифметическое выражение>, за которым следует знак + или -, за которым следует конструкция <слагаемое>. Это правило является рекурсивным, т.е. конструкция <арифметическое выражение> определяется рекурсивно в терминах себя самой. В соответствии с этим правилом, нетерминальным символом <арифметическое выражение> является любая последовательность из одного или более слагаемых, разделенных знаками + или -.
2. Формальные определения грамматики языка
Прежде, чем приступать к реализации транслирующих программ необходимо определить некоторые понятия.

Алфавит языка – непустое, конечное множество символов. Например, пусть алфавит языка включает три символа: {a, b, c}.

Предложение – непустое конечное множество символов алфавита. Например, из трех символов алфавита мы можем получить бесконечное количество предложений: aabb, abcc, bac, bca и т.д.

Грамматика устанавливает правила вывода синтаксически правильных предложений из всех возможных. Формально грамматика G определяется как четверка объектов: (N, T, P, S), где N– множество нетерминальных символов, образующее синтаксические классы языка, T – множество терминальных символов, образующее алфавит языка, P – множество правил переписывания (например, в форме Бэкуса-Наура), S – начальный нетерминальный символ грамматики, с которого начинается разбор любого предложения языка.

Языком L над грамматикой G называется множество предложений, состоящих из терминальных символов T, выводимых с помощью правил P начиная с начального нетерминального символа S.
3. Классификация грамматик
Одна из классификаций грамматик связана с видом правил переписывания P. По этой классификации грамматики разделяют на регулярные, контекстно-свободные, контекстно-зависимые и без ограничений.

Грамматика называется регулярной, если правила переписывания имеют вид:

---

AcB или Ac, где A, B – нетерминальные символы, c – терминальный символ грамматики.

Пример. G1=({S}, {0,1}, P={S0S/1S/0/1}, S}).

Грамматика называется контекстно-свободной, если правила переписывания имеют вид: Aw, где A– нетерминальный символ,
wЄ(N V T) – обединение нетерминальных и терминальных символов грамматики.

Пример. G2=({A,Z}, {a,*, +, (, )}, P={AZ/A+Z, Za/Z*a/(A)}, A}).

Грамматика называется контекстно-зависимой, если правила переписывания имеют вид: kw, где k, wЄ(N V T) – объединение нетерминальных и терминальных символов грамматики, причем |k|≤|w|.

Пример. G3=({S,B,C}, {a,b,c}, P={SaSBC/abC, CBBC, bBbb, bCbc, cCcc}, S}).

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

Грамматика большинства языков программирования записывается в терминах контекстно-свободных грамматик.

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

На рис. 3а изображено дерево грамматического разбора для предложения read(a) с помощью правил 12 и 4 грамматики, представленной на рис.2.

На рис. 3б приведено синтаксическое дерево разбора предложения rez:=sumdiv100–a*a. Это дерево выводится с помощью правил 8, 9, 10, 11 грамматики, представленной на рис. 2.

Рис. 3
Таким образом, рассматривая правила грамматики, начиная с начального, можно построить синтаксическое дерево для всей программы, представленной на рис.1.
Контрольные вопросы

1. 
   Что такое синтаксис языка?
   
2. 
   Что такое семантика языка?
   
3. 
   Что определяет грамматика языка?
   
4. 
   Что такое формальный язык?
   
5. 
   Для чего используются синтаксические деревья?
   
6. 
   Как называется транслятор, у которого функциональное
   назначение-перевод программы с языка низкого уровня в машинные коды?
   
7. 
   Какая грамматика имеет следующие 4 компонента:
   

---

Смотрите также файлы

• Финансовые инновации и рынок инновационных финансовых продуктов.docx

• Отчет о учебной практике по дисциплине Практические основы бухгалтерского учета активов организации в организации ооо Автоцентр Кемерово.docx

• Памятка для участников и организаторов.docx

• Соответственно, целью моего эссе будет выяснить, как совместить толерантность и свободу.docx

• Практическая работа к теме 1 Ценности и их роль для человека и общества Изучила контент (информацию).docx