Синтаксис и семантика языка

Способы задания языков

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

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

Алфавит -это счетное множество допустимых символов языка. Это множество символовобозначают V. Согласно формальному определению, алфавит не обязательно должен быть конечным (перечислимым) множеством, но реально все существующие языки строятся на основе конечных алфавитов.

Цепочка символов a является цепочкой над алфавитом V: a(V),если в нее входят только символы, принадлежащие множеству символов V. Для любого алфавита V пустая цепочка l может как являться, так и не являться цепочкой l (V). Это условие оговаривается дополнительно.

Если V – некоторый алфавит, то:

● V⁺ –множество всех цепочек над алфавитом V без l;

● V* - множество всех цепочек над алфавитом V, включая l.

Справедливо равенство: V* = V⁺ È{λ}

Языком L над алфавитом V: L(V) называется некоторое счетное подмножество цепочек конечной длины из множества всех цепочек над алфавитом V. Из этого определения следует два вывода: во-первых, множество цепочек языка не обязано быть конечным; во-вторых, хотя каждая цепочка символов, входящая в язык, обязана иметь конечную длину, эта длина может быть сколь угодно большой и формально ничем не ограничена.

Все существующие языки попадают под это определение. Большинство реальных естественных и искусственных языков содержат бесконечное множество цепочек. Также в большинстве языков длина цепочки ничем не ограничена. Цепочку символов, принадлежащую заданному языку, называют предложением языка, а множество цепочек символов некоторого языка L(V)-множеством предложений этого языка.

Два языка L(V) и L'(V) совпадают (эквивалентны): L’(V)=L(V), если L’(V)⊆L(V) и L(V)⊆L’(V).

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

Два языка L(V) и L’(V) почти эквивалентны, если L’(V)È{l}= L(V)È{l}. Множества допустимых цепочек символов почти эквивалентных языков могут различаться только на пустую цепочку символов.

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

Язык задать можно тремя способами:

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

2. Указанием способа порождения цепочек языка (заданием грамматики языка)

3. Определением метода распознавания цепочек языка.

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

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

Третий способ предусматривает построение некоторого логического устройства (распознавателя) – автомата, который на входе получает цепочку символов, а на выходе выдает ответ: принадлежит или нет эта цепочка заданному языку [1].

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

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

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

Лексика – это совокупность слов (словарный запас) языка. Слово или лексическая единица языка – это конструкция, которая состоит из элементов алфавита языка и не содержит в себе других конструкций. Иначе говоря, лексическая единица может содержать только элементарные символы и не может содержать других лексических единиц.

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

Дата добавления: 2014-12-27