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

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

=== Скачать файл ===

Синтаксис и семантика языка. Итак, каждый язык — это множество цепочек символов над некоторым алфавитом. Но кроме алфавита язык предусматривает также правила построения допустимых цепочек, поскольку обычно далеко не все цепочки над заданным алфавитом принадлежат языку. Символы могут объединяться в слова или лексемы — элементарные конструкции языка, на их основе строятся предложения — более сложные конструкции. И те и другие в общем виде являются цепочками символов, но предусматривают некоторые правила построения. Таким образом, необходимо указать эти правила, или, строго говоря, задать язык. В общем случае язык можно определить тремя способами:. Перечислением всех допустимых цепочек языка;. Указанием способа порождения цепочек языка заданием грамматики языка ;. Определением метода распознавания цепочек языка. Первый из методов является чисто формальным и на практике не применяется, так как большинство языков содержат бесконечное число допустимых цепочек и перечислить их просто невозможно. Трудно себе представить, чтобы появилась возможность перечислить, например, множество всех правильных текстов на русском языке или всех правильных программ на языке Pascal. Иногда для чисто формальных языков можно перечислить множество входящих в них цепочек, прибегнув к математическим определениям множеств. Однако этот подход уже стоит ближе ко второму способу. Видно, что пустая цепочка символов в этот язык не входит. Второй способ предусматривает некоторое описание правил, с помощью которых строятся цепочки языка. Тогда любая цепочка, построенная с помощью этих правил из символов алфавита языка, будет принадлежать заданному языку. Например, с правилами построения цепочек символов русского языка вы долго и упорно знакомились в средней школе. Третий способ предусматривает построение некоторого логического устройства распознавателя — автомата, который на входе получает цепочку символов, а на выходе выдает ответ: Например, читая сейчас этот текст, вы в некотором роде выступаете в роли распознавателя надеюсь, что ответ на вопрос о принадлежности текста русскому языку будет положительным. Говоря о любом языке, можно выделить его синтаксис и семантику. Кроме того, трансляторы имеют дело также с лексическими конструкциями лексемами , которые задаются лексикой языка. Ниже даны определения всех этих понятий. Синтаксис языка — это набор правил, определяющий допустимые конструкции языка. Чаще всего синтаксис языка можно задать в виде строгого набора правил, но полностью это утверждение справедливо только для чисто формальных языков. Правда, не каждый задумается при этом, что он оперирует синтаксисом алгебры. Семантика языка — это раздел языка, определяющий значение предложений языка. Семантика для большинства языков определяется неформальными методами отношения между знаками и тем, что они обозначают, изучаются семиотикой. Чисто формальные языки лишены какого-либо смысла. Однако изложить любому ученику синтаксис алгебры гораздо проще, чем ее семантику, хотя в случае алгебры семантику как раз можно определить формально. Лексика — это совокупность слов словарный запас языка. Слово или лексическая единица лексема языка — это конструкция, которая состоит из элементов алфавита языка и не содержит в себе других конструкций. Иначе говоря, лексическая единица может содержать только элементарные символы и не может содержать других лексических единиц. Лексическими единицами лексемами русского языка являются слова русского языка, а знаки препинания и пробелы представляют собой разделители, не образующие лексем. Лексическими единицами алгебры являются числа, знаки математических операций, обозначения функций и неизвестных величин. В языках программирования лексическими единицами являются ключевые слова, идентификаторы, константы, метки, знаки операций; в них также существуют и разделители запятые, скобки, точки с запятой и т. Языки программирования занимают некоторое промежуточное положение между формальными и естественными языками. С формальными языками их объединяют строгие синтаксические правила, на основе которых строятся предложения языка. От языков естественного общения в языки программирования перешли лексические единицы, представляющие основные ключевые слова чаще всего это слова английского языка, но существуют языки программирования, чьи ключевые слова заимствованы из русского и других языков. Кроме того, из алгебры языки программирования переняли основные обозначения математических операций, что также делает их более понятными человеку. Для задания языка программирования необходимо решить три вопроса:. Только первые два вопроса полностью или частично удается решить с помощью теории формальных языков. Для решения остальных вопросов приходится прибегать к другим, неформальным методам. Первый вопрос решается легко. Определяя алфавит языка, мы автоматически определяем множество допустимых символов. Для языков программирования алфавит — это чаще всего тот набор символов, которые можно ввести с клавиатуры. Основу его составляет младшая половина таблицы международной кодировки символов таблицы ASCII , к которой добавляются символы национальных алфавитов. Второй вопрос решается в теории формальных языков только частично. Для всех языков программирования существуют правила, определяющие синтаксис языка, но как уже было сказано, их недостаточно для того, чтобы строго определить все допустимые предложения языков программирования. Дополнительные ограничения накладываются семантикой языка. Эти ограничения оговариваются в неформальном виде для каждого отдельного языка программирования. К таким ограничениям можно отнести необходимость предварительного описания переменных и функций, необходимость соответствия типов переменных и констант в выражениях, формальных и фактических параметров в вызовах функций и др. Отсюда следует, что практически все языки программирования, строго говоря, не являются формальными языками. И именно поэтому во всех трансляторах кроме синтаксического разбора и анализа предложений языка дополнительно предусмотрен семантический анализ. Третий вопрос в принципе не относится к теории формальных языков, поскольку, как уже было сказано, такие языки лишены какого-либо смысла. Для ответа на него нужно использовать другие подходы. В следующей главе, посвященной основным принципам построения трансляторов и компиляторов, будут более подробно указаны отличия языков программирования от формальных языков, которые нужно принимать во внимание при создании трансляторов и компиляторов для языков программирования. Грамматика — это описание способа построения предложений некоторого языка. Иными словами, грамматика — это математическая система, определяющая язык. Фактически, определив грамматику языка, мы указываем правила порождения цепочек символов, принадлежащих этому языку. Таким образом, грамматика — это генератор цепочек языка. Она относится ко второму способу определения языков — порождению цепочек символов. Грамматику языка можно описать различными способами. Например, грамматика русского языка описывается довольно сложным набором правил, которые изучают в начальной школе. Для некоторых языков в том числе для синтаксических конструкций языков программирования можно использовать формальное описание грамматики, построенное на основе системы правил или продукций. Правило или продукция — это упорядоченная пара цепочек символов a,b. Далее, говоря о грамматиках языков программирования, будем иметь в виду только правила построения синтаксических конструкций языка. Однако следует помнить, что грамматика любого языка программирования в общем случае не ограничивается только этими правилами. Язык, заданный грамматикой G, обозначается как L G. Формально грамматика G определяется как четверка G VT,VN,P,S , где:. VT — множество терминальных символов или алфавит терминальных символов;. VN — множество нетерминальных символов или алфавит нетерминальных символов;. S — целевой начальный символ грамматики SОVN. Алфавиты терминальных и нетерминальных символов грамматики не пересекаются: Это значит, что каждый символ в грамматике может быть либо терминальным, либо нетерминальным, но не может быть терминальным и нетерминальным одновременно. Целевой символ грамматики — это всегда нетерминальный символ. Далее будут даны строгие формальные описания того, как связаны различные элементы грамматики и порождаемый ею язык. А пока предварительно опишем смысл множеств VN и VT. Множество терминальных символов VT содержит символы, которые входят в алфавит языка, порождаемого грамматикой. Как правило, символы из множества VT встречаются только в цепочках правых частей правил. Множество нетерминальных символов VN содержит символы, которые определяют слова, понятия, конструкции языка. Каждый символ этого множества может встречаться в цепочках как левой, так и правой частей правил грамматики, но он обязан хотя бы один раз быть в левой части хотя бы одного правила. Правила грамматики обычно строятся так, чтобы в левой части каждого правила был хотя бы один нетерминальный символ. Во множестве правил грамматики может быть несколько правил, имеющих одинаковые левые части, вида: Тогда эти правила объединяют вместе и записывают в виде: Одной строке в такой записи соответствует сразу n правил. Такую форму записи правил грамматики называют формой Бэкуса—Наура. Форма Бэкуса—Наура предусматривает, как правило, также, что нетерминальные символы берутся в угловые скобки: Ниже приведен пример грамматики, которая определяет язык целых десятичных чисел со знаком:. Рассмотрим составляющие элементы грамматики G:. Следует отметить, что символ — это бессмысленное сочетание букв русского языка, но это обычный нетерминальный символ грамматики, такой же, как и два других. Названия нетерминальных символов не обязаны быть осмысленными, это сделано просто для удобства понимания правил грамматики человеком. В принципе, в любой грамматике можно полностью изменить имена всех нетерминальных символов, не меняя при этом языка, заданного грамматикой, — точно так же, например, в программе на языке Pascal можно изменить имена идентификаторов, и при этом не изменится смысл программы. Для терминальных символов это неверно. Набор терминальных символов всегда строго соответствует алфавиту языка, определяемого грамматикой. Вот, например, та же самая грамматика для языка целых десятичных чисел со знаком, в которой нетерминальные символы обозначены большими латинскими буквами далее это будет часто применяться в примерах:. Здесь изменилось только множество нетерминальных символов. Принцип рекурсии в правилах грамматики. Особенность рассмотренных выше формальных грамматик в том, что они позволяют определить бесконечное множество цепочек языка с помощью конечного набора правил конечно, множество цепочек языка тоже может быть конечным, но даже для простых реальных языков это условие обычно не выполняется. Приведенная выше в примере грамматика для целых десятичных чисел со знаком определяет бесконечное множество целых чисел с помощью 15 правил. В такой форме записи грамматики возможность пользоваться конечным набором правил достигается за счет рекурсивных правил. Рекурсия в правилах грамматики выражается в том, что один из нетерминальных символов определяется сам через себя. Рекурсия может быть непосредственной явной — тогда символ определяется сам через себя в одном правиле, либо косвенной неявной — тогда то же самое происходит через цепочку правил. В рассмотренной выше грамматике G непосредственная рекурсия присутствует в правиле: Чтобы рекурсия не была бесконечной, для участвующего в ней нетерминального символа грамматики должны существовать также и другие правила, которые определяют его, минуя его самого, и позволяют избежать бесконечного рекурсивного определения в противном случае этот символ в грамматике был бы просто не нужен. В теории формальных языков более ничего сказать о рекурсии нельзя. Но чтобы полнее понять смысл рекурсии, можно прибегнуть к семантике языка — в рассмотренном выше примере это язык целых десятичных чисел со знаком. Если попытаться дать определение тому, что же является числом, то начать можно с того, что любая цифра сама по себе есть число. Далее можно заметить, что любые две цифры — это тоже число, затем — три цифры и т. Если строить определение числа таким методом, то оно никогда не будет закончено в математике разрядность числа ничем не ограничена. Однако можно заметить, что каждый раз, порождая новое число, мы просто дописываем цифру справа поскольку привыкли писать слева направо к уже написанному ряду цифр. А этот ряд цифр, начиная от одной цифры, тоже в свою очередь является числом. Они элементарны и не требуют пояснений. Так или иначе, явно или неявно рекурсия всегда присутствует в грамматиках любых реальных языков программирования. Именно она позволяет строить бесконечное множество цепочек языка, и говорить об их порождении невозможно без понимания принципа рекурсии. Как правило, в грамматике реального языка программирования содержится не одно, а целое множество правил, построенных с помощью рекурсии. Рабочая программа по английскому языку для студентов подготовки бакалавров направления Для входа в систему необходимо ввести имя пользователя логин и пароль, Далее нажать Воспитательной работы на учебный год г. Сохрани ссылку в одной из сетей: Информация о документе Дата добавления: Доступные форматы для скачивания: Синтаксис и семантика языка Итак, каждый язык — это множество цепочек символов над некоторым алфавитом. В общем случае язык можно определить тремя способами: Перечислением всех допустимых цепочек языка; 2. Указанием способа порождения цепочек языка заданием грамматики языка ; 3. Особенности языков программирования Языки программирования занимают некоторое промежуточное положение между формальными и естественными языками. Для задания языка программирования необходимо решить три вопроса: Грамматики и распознаватели Формальное определение грамматики. Форма Бэкуса—Наура Грамматика — это описание способа построения предложений некоторого языка. ВНИМАНИЕ Далее, говоря о грамматиках языков программирования, будем иметь в виду только правила построения синтаксических конструкций языка. Формально грамматика G определяется как четверка G VT,VN,P,S , где: Ниже приведен пример грамматики, которая определяет язык целых десятичных чисел со знаком: Вот, например, та же самая грамматика для языка целых десятичных чисел со знаком, в которой нетерминальные символы обозначены большими латинскими буквами далее это будет часто применяться в примерах: Лекция 10 Грамматики и распознаватели Принцип рекурсии в правилах грамматики Особенность рассмотренных выше формальных грамматик в том, что они позволяют определить бесконечное множество цепочек языка с помощью конечного набора правил конечно, множество цепочек языка тоже может быть конечным, но даже для простых реальных языков это условие обычно не выполняется. Внемашинное информационное обеспечение Основные понятия Слайд 4 Информационная база Данные, отражающие состояние определенной предметной области и используемые информационной системой Вербальная модель архитектуры предприятия и информационной системы. Логико- лингвистические и семиотические Понятие системы в настоящее

Кузнечный пресс своими руками видео

Анкерный болт описание

Детские перевозки автобусом правила

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

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

=== Скачать файл ===

Лекция 2. Формальные языки и способы их задания

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

I.Формальные языки и грамматики

Report Page