Определение языка. Синтаксис и семантика.

Язык-это любое подмножество множества строк над используемым алфавитом. У каждого языка есть свой синтаксис и семантика. Например, из всех возможных строк над алфавитом, состоящим из цифр, точки и знака минус, можно выбрать лишь те, которые являются корректной записью некоторого вещественного числа: L={0, -1.5, 1002.12123, 78, …}.

В основном языки обозначают заглавными буквами. В отличие от множества строк, язык может представлять собой конечное множество. Например, L-это язык над алфавитом {a,b}, в который входят лишь строки короче трех символов входят лишь строки короче трех символов, то его элементами окажутся всего 7 строк:

Алфавит-это любое конечное множество некоторых символов. Например, множество {1,2} это алфавит, состоящий из 1 и 2, множество {A, B, C, …, Z} представляет собой алфавит заглавных латинских букв. Как правило алфавит обозначается какой-нибудь заглавной греческой буквой.

Синтаксис языка-набор правил, описывающий комбинацию символ алфавита, считающиеся правильно структурированной программой или её фрагментом. Синтаксис очень простого языка можно описать на естественном языке: например, “все строки, состоящие только из 1 и 0” тогда 1111 и 1000110 принадлежат языку, а 1020 нет. Для описания синтаксиса более сложных языков применяется формальный метод определения синтаксиса, называется Бэкуса-Наура формой (БНФ), синтаксические единицы <предложение>, <подлежащее><сказуемое> называются нетерминальными символами, слова “кошки”, “собаки”, “спят”, “едят” терминальными символами, а правила-порождающими правилами.

Семантика задаёт значение всем предложениям языка. Например, <предложение>::=<подлежащее><сказуемое> <подлежащее>::=люди/собаки <сказуемое>::=говорят/спят.

Более сложный синтаксис языка лучше определять с помощью грамматики. Грамматика-это раздел, изучающий строй языка, в который входит набор правил для получения предложений языка. Например, 1.S->0S1 2.S->e возьмем синтаксис “все строки, сост. из 1 и 0”. S-->0S1-->00S11-->000S111-->000111 строка не содержащая S является предложением языка. Грамматика это четверка (N,T,P,S), где N-нетерминал, T-терминал, P-набор правил, S-начальный нетерминал.

Порождающие грамматики Хомского. Примеры порождающих грамматик.

Порождающей грамматикой Хомского называется четверка G=(N,T,P,S), где N-конечный алфавит нетерминальных символов, T-конечный алфавит терминальных символов, P-конечное множество правил порождения, S-начальный нетерминал грамматики G.

Пример очень простого языка: L={a} язык состоит из единственного символа. S->a это правило порождения языка L, или 1.S->A 2.A->a.

Пример языка простых арифметических выражений: L={a+a, a+a+a, a+a+a+a,....} 1. S->aA 2. A->+aA 3. A->+a это правило порождения любого языка из L. Породим a+a+a: S-->aA-->a+aA-->a+a+a.

Пример КС-языка 1.S->aBb 2.B->aCb/e 3.C->aBb/aSb/e, породим aabb: S-->aBb-->aaCbb-->aabb.

Пример КЗ-языка: Правила порождения любого предложения языка L: S->aS|a, породим aaa: S-->aS-->aaS-->aaa.