Учебное пособие: Разработка в структурно логической схемы микропроцессора

Под формальным определением языка программирования мы понимает полное описание синтаксиса и семантики. Желательно иметь такое описание.

Сведения о языке содержится в учебниках и руководствах. Часто эти описания не однозначные и не освещают всех тонкостей.

Формальное описание надо для разработчиков компилятора. Синтаксическое определение может задаваться формальными или не формальными способами.

Метаязык (металингвистические символы)

Формальное описания языка.

Метаязык

Использую синтаксические диаграммы

Скобочные конструкции

С помощью множеств

Метаязык

Описание любого формального языка описывается на МЕТО языке. Он может описывать синтез, либо семантику (смысл конструкций), либо все вместе. Для языков программирования наиболее распространенным МЕТО языком для описание синтеза служит нормальная форма БНФ. Перечислим основные понятия и конструкции этого языка:

Терминальный символ – символ, состоящей только из букв алфавита описываемого языка. Одна или несколько букв.

Не терминальный символ – сформулированная на русском или другом языке понятие описываемого языка программирования. Металингвистические переменные. Для того чтобы раскрыть понятие языка обозначаемыми не терминальными символами, используются правила подстановки. U и u – произвольные конечные последовательные цепочки терминальных символов. Знак:: = есть по определению или представляет собой. При описании языков программирования U - это один не терминальный символ. u – любая последовательность терминальных или не терминальных символов раскрывающая сущность не терминального символа с лева.

Символическое имя >:: =<буква> | <символическое имя> <бц>

<бц>:: =<буква> <цифра>

По одном из правил определяющие наиболее общих понятий языка строится первым и называется начальным символом языка.

Классификация языков по Хомскому

В основе этой классификации лежит форма левой и правой части правил подстановки. Языки делятся на 4 класса:

0

1

2

3

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

Класс 0. (Грамматика с фразовой структурой). Не накладывается ни каких ограничений на правила подстановки. Правило имеет вид приведенный выше, где U – произвольная не пустая последовательность терминальных и не терминальных символов. Класс 0 является наиболее мощным языки этого класса могут служить моделью естественных языков.

Класс 1 Контекстно-зависимая грамматика. U1 – нетерминальный символ. X Y u – произвольная цепочка терминальных и нетерминальных символов. Смысл этого правила состоит в том, что замена U на u осуществляется только в контексте X Y. Если длину обозначить, то видна что левая часть всегда меньше чем правая.

Класс 2 Контекстно-свободные грамматики. U ровно один не терминал. Грамматика класса 2 обычно используется для описания синтаксиса языков программирования.

Класс 3 Регулярной грамматикой. U – один не терминал. t – один терминал. n – один не терминал. Грамматика три может использоваться для описания символа простых языков. Используется для сборки лексем. Если б хотя бы одно правило подстановки относится к более высокому классу чем остальные, то и вся грамматика относится к этому классу. Для описания синтаксиса формального языка достаточно задать грамматику с помощью 4 объектов.

S→aS

S→a