Формальные языки и порождающие грамматики

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

Например, алфавит A = {a, b, c, +,!} содержит 5 букв, а алфавит B = {00, 01, 10, 11} содержит 4 буквы, каждая из которых состоит из двух символов.

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

Например, слово в алфавите A a=ab++c имеет длину l(a) = 5, а слово в алфавите B b=00110010 имеет длину l (b) = 4.

Если задан алфавит A, то обозначим A^* множество всевозможных цепочек, которые могут быть построены из букв алфавита A. При этом предполагается, что пустая цепочка, которую обозначим знаком $, также входит в множество A ^*.

Оп ределение. Формальной порождающей грамматикой Г называется следующая совокупность четырех объектов: Г = { V_т, V_A, <I>О V_A, R },

где V_т - терминальный алфавит (словарь); буквы этого алфавита называются терминальными символами; из них строятся цепочки порождаемые грамматикой;

V_A - нетерминальный, вспомогательный алфавит (словарь); буквы этого алфавита используются при построении цепочек; они могут входить в промежуточные цепочки, но не должны входить в результат порождения;

<I> - начальный символ грамматики <I> О V_A.

R - множество правил вывода или порождающих правил вида a ® b, где a и b - цепочки, построенные из букв алфавита V_тИ V_A, который называют полным алфавитом (словарем) грамматики Г

Язы́к — знаковая система, соотносящая понятийное содержание и типовое звучание (написание).

Синтаксис (построение, порядок, составление ) - система правил, определяющих допустимые конструкции языка программирования из букв алфавита.

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

Формальный язык - это множество конечных слов над конечным алфавитом. К формальным языкам относиться, например, компьютерный язык.

Для формальных языков характерна принадлежность к ограниченной предметной области (математика, химия, музыка и пр.). Назначение формального языка – адекватное описание системы понятий и отношений, свойственных для данной предметной области. Язык может развиваться, изменяться, дополнятся вместе с развитием свой предметной области.

Есте́ственный язы́к — в лингвистике и философии языка язык, используемый для общения людей и не созданный искусственно.

Компьютерный язык - этот термин соответствует понятию языка программирования, однако это соответствие не является вполне однозначным. Так, например, языки разметки (такие как HTML) не являются языками программирования, однако определённо относятся к компьютерным языкам.

Языки программирования - это формальные искусственные языки. Как и естественные языки, они имеют алфавит, словарный запас, грамматику и синтаксис, а также семантику.

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

Языки программирования, ориентированные на команды процессора и учитывающие его особенности ,называют языками низкого уровня.«Низкий уровень» не означает неразвитый, имеется в виду, что операторы этого языка близки к машинному коду и ориентированы на конкретные команды процессора. Языком самого низкого уровня является ассемблер. Программа, написанная на нем, представляет последовательность команд машинных кодов, но записанных с помощью символьных мнемоник.

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

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

Дата добавления: 2014-01-20