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

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

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

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

Для формирования модели грамматики обозначим элементарные лексические единицы языка строчными буквами латинского алфавита. Знаки этого множества называют терминальными (от лат. terminus - предел,конец). Множество терминальных символов обозначим знаком V_T. Это множество называют также словарем или лексикой языка. Множество V_T - счетно, но не конечно, т.к. всегда можно добавить новую лексему для какой-либо синтаксической переменной.

Элементарными лексическими единицами большинства языков программирования являются:

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

< служебные слова>::= AND ½ ARRAY ½ BEGIN ½ CASE ½ CONS ½ DIV ½ DOWNTO ½ DO ½ ELSЕ ½ END ½ FILE ½ FOR ½ FUNCTION ½ GOTO ½ IF ½ IN ½ LABEL ½ MOD ½ NIL ½ NOT ½ OF ½ OR ½ PACKED ½ PROCEDURE ½ PROGRAM ½ RECORD ½ REPEAT ½ SET½ THEN ½ TO ½ TYPE ½ UNTIL ½ VAR ½ WHILE ½ WITH;

< специальные символы>::= + ½ - ½ * ½ / ½ = ½ < ½ > ½ <= ½ >= ½ [ ½ ] ½ (½) ½ _ ½:= ½ " ½ ' ½. ½, ½: ½; ½ ¹ ½# ½$;

десятичные числа без знака.

В выражениях и предложениях формального языка, cодержащих лексемы и синтаксические переменные, лексемы всегда заключены в кавычки. Например, "BEGIN", "NOT", AND" и др.

Для обозначения синтаксических переменных введем прописные буквы латинского алфавита. Знаки этого множества называют нетерминальными. Обозначим множество нетерминальных символов знаком V_N.

Множество V_N - счетно и конечно.

Элементарными синтаксическими переменными для языка программирования являются:

< блок >:: = <блок-операторов>½<блок-процедуры>½<блок-функции>½...;

< заголовок >::= <заголовок-программы>½<заголовок-процедуры>½

<заголовок-функции>½...;

< идентификатор >::= <идентификатор-программы>½<идентификатор-

переменной>½...;

< оператор >::= <оператор-присваивания>½<оператор-ЕСЛИ>...;

< операция >::= <операция-сложения>½<операция-умножения>

½<операция-отношения>½...;

и другие синтаксические переменные.

В языке Паскаль всего около 240 синтаксических переменных.

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

Объединение символов двух множеств V_T и V_N представляет множество символов формального языка, т.е.

V = V_TÈV_N. (2)

Цепочки символов формального языка могут содержать различное количество терминальных и/или нетерминальных символов. Поэтому множество правильных цепочек может быть записано так:

V^* . (3)

Если каждый элемент множества V* обозначить строчной буквой греческого алфавита, то множество V* можно описать перечислением его элементов:

V* = { a; b; g;... } (4)

Например,

a:= "PROGRAM"<идентификатор-программы>";"<блок>".";

b:= "CONST" <определение-константы> "; ";

g:= "(" <идентификатор> { ", " <идентификатор> } ") ";

где знак ":=" означает: "...присвоить значение...". Цепочка a ÎV* содержит пять символов множества V, цепочка b ÎV* - три символа и цепочка g Î V* - не менее трех символов, т.к. в языках программирования знак "{.. }" означает многократное повторение выражения, заключенного в фигурные скобки, включая нуль раз.

Конструкция программы на любом языке программирования состоит, как правило, из двух частей: заголовка - <заголовок-программы> и тела программы - <блок>. В заголовке программы, начинающемся служебным словом "PROGRAM", ей присваивается имя (идентификатор), вслед за которым в круглых скобках задается перечень идентификаторов тех файлов, через которые программа взаимодействует с внешним миром. В теле программы должны следовать в определенном порядке разделы меток, констант, типов, переменных, процедур, функций и операторов. Так как разделы, предшествующие разделу операторов, носят описательный характер, то каждый из них может быть пустой цепочкой, а раздел операторов является основным и должен присутствовать в любой программе. Поэтому в последующих объяснениях <блок> содержит только описание операторов, т.е. исполняет функции <блока-операторов>.

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

Продукцию или правило подстановки записывают так:

a::=b, (5)

где a - левая часть правила,

b - правая часть правила.

Если правил несколько,то их необходимо индексировать:

p _i: a _i::= b _i, где i = 1;2;3;... (6)

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

a Î V* \ e, где e - пустая цепочка. (7)

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

b Î V * или b ÎV*\ V_N. (8)

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

<программа>::= <заголовок-программы> "; "<блок>". ";

<заголовок-программы>::= "PROGRAM"<идентификатор-программы>;

<блок>::= <раздел-операторов> |...;

<раздел-операторов>::= "BEGIN" <оператор> " END";

<оператор>::= <оператор-присваивания> |...;

<оператор-присваивания>::= <переменная> ":= " <выражение>;

<выражение>::= <терм> <операция-сложения> <терм>;

<терм>::= <множитель> <операция-умножения> <множитель>;

<множитель>::= <переменная>;

<переменная>::= <идентификатор-переменной>;

<операция-сложения>::= " + " | " - " | "OR";

<операция-умножения>::= " x " | " / " | "DIV" | "MOD" |"AND".

Синтаксической переменной <идентификатор-программы> присвоим какое-либо значение (например, "ALGEBRA"), т.е.

<идентификатор-программы>::= "ALGEBRA".

Cинтаксической переменной <идентификатор-переменной> также присвоим какое-либо значение, начинающееся с буквы (например," i "), т.е.

<идентификатор-переменной>::= " i ".

Последовательность использования правил подстановки в процессе формирования цепочки терминальных и/или нетерминальных символов называют выводом. Поэтому эти же правила часто называют правилами вывода. Для указания процесса вывода используют знак "=>".

Выводы бывают левосторонние и правосторонние. При левостороннем выводе продукцию применяют к самому левому нетерминальному символу цепочки, а при правостороннем - к самому правому.

Пример 4. а) Для начального символа <программа> (пример 3) исполнить левосторонний вывод:

<программа> => <заголовок-программы> ";" <блок> "." => "PROGRAM" <идентификатор-программы> ";" <блок> "." => "PROGRAM" "ALGEBRA" ";" <блок> "." => "PROGRAM" "ALGEBRA" ";" <раздел-операторов> "." => "PROGRAM" "ALGEBRA" ";" "BEGIN" <оператор> "END" "." => "PROGRAM" "ALGEBRA" ";" "BEGIN" <оператор-присваивания> "END" "." =>."PROGRAM" "ALGEBRA" ";" "BEGIN" <переменная> ":= " <выражение> "END" "." => "PROGRAM" "ALGEBRA" ";" "BEGIN" <идентификатор-переменной> ":=" <выражение> "END" "." => "PROGRAM" "ALGEBRA" ";" "BEGIN" " i " ":=" <выражение> "END" "." =>..

b) Для начального символа <программа> (пример 3) исполнить правосторонний вывод:

<программа> => <заголовок-программы> ";" <блок> "." => <заголовок-программы> ";" <раздел-операторов> "." => <заголовок-программы> ";" "BEGIN" <оператор> "END" "." => <заголовок-программы> ";" "BEGIN" <оператор-присваивания> "END" "." => <заголовок-программы> ";" "BEGIN" <переменная> ":=" <выражение> "END" "." =>...

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

Пример 5. Для cинтаксической переменной <выражение> (пример 3) выполнить левосторонний вывод:

<выражение> => <терм><операция-сложения><терм>=> <множитель> <операция-умножения><множитель><операция-сложения><терм> => <переменная><операция-умножения><множитель><операция-сложения> <терм>=> <идентификатор-переменной><операция-умножения> <множитель> <операция-сложения><терм> => "i" <операция-умножения> <множитель><операция-сложения><терм> => "i" "x" <множитель><операция-сложения><терм> => "i" "x" <переменная><операция-сложения><терм> => "i" "x" <идентификатор-переменной><операция-сложения><терм> => "i" "x" "i" <операция-сложения><терм> => "i" "x" "i" "+" <терм> => "i" "x" "i" "+" <множитель><операция-умножения><множитель> => "i" "x" "i" "+" <переменная> <операция-умножения><множитель> => "i" "x" "i" "+" <идентификатор-переменной><операция-умножения> <множитель> => "i" "x" "i" "+" "i" <операция-умножения> <множитель> => "i" "x" "i" "+" "i" "x" <множитель> "i" "x" "i" "+" "i" "x" <переменная> => "i" "x" "i" "+" "i" "x"<идентификатор-переменной> => "i" "x" "i" "+" "i" "x" "I".

Имя начальной синтаксической переменной языка, для которой дано множество правил вывода называют начальным символом и обозначают буквой J. Роль начального символа может исполнять любая синтаксическая переменная. Для текста программы начальной синтаксической переменной является <программа>. Для части текста программы - выражения - начальной синтаксической переменной является <выражение>.

Итак, модель формальной грамматики может быть описана совокупностью четырех основных компонент:

G = á V _T; V _N;J; P ñ, (9)

где V_T = { a;b;c;... } - терминальные символы;

V_N = { A;B;C;...} - нетерминальные символы;

JÎ Vn - начальный символ;

P = { p_i |i = 1; 2; 3;... } - синтаксические правила.

Множество правильных цепочек терминальных символов представляет выражения и предложения формального языка данной формальной грамматики L(G):

L (G) = { a, b, g,...½ a, b, g Î V *\ VN }. (10)

Текст программы, ограниченный разделителем ".", называют предложением, а часть текста, ограниченную разделителем ";", - выражением.

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

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

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