Что называют грамматикой языка информатика

Что называют грамматикой языка информатика

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

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

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

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

Операторы выполняются в порядке их следования в тексте программы. Лишь с помощью операторов перехода этот естественный порядок может быть нарушен.

Важнейшие характеристики структурированной величины таковы: упорядоченность (да или нет), однородность (да или нет), способ доступа к элементам, фиксированность числа элементов (да или нет). Так, массив является упорядоченной однородной структурой с прямым доступом к элементам и фиксированным их количеством.

Всем программным объектам в языках даются индивидуальные имена. Имя программного объекта называют идентификатором (от слова «идентифицировать»). Чаще всего идентификатором является любая конечная последовательность букв к цифр, начинающаяся с буквы:

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

Многим слово «идентификатор» не нравится, и в настоящее время чаще употребляют слово «имя», поскольку

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

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

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

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

Заголовок необходим для ссылок на модуль.

Интерфейс содержит объявления, включая процедуры и функции.

Раздел «реализация» содержит тела процедур и функций, перечисленных в интерфейсной части.

Раздел «инициализация» содержит операторы, необходимые для инициализации модуля.

Каждый модуль компилируется отдельно, и каждый элемент модуля можно использовать в программе без дополнительного объявления.

Источник

Классификация формальных языков и грамматик по Хомскому

Формальная грамматика – это математическая система, определяющая язык посредством порождающих правил.
Определение 1.9. Формальной грамматикой называется четверка вида:

, (1.1)

Классификация грамматик в иерархии американского математика Хомского осуществляется по структуре правил вывода. В расширенной иерархии Хомского выделяется четыре типа грамматик.

Тип 0. Грамматика называется грамматикой типа 0 (грамматикой без ограничений или грамматикой с фразовой структурой), если на ее правила вывода не наложено никаких ограничений, кроме тех, которые указаны в определении грамматики.

Тип 1. Грамматика называется контекстно-зависимой грамматикой (КЗ-грамматикой), если каждое правило вывода из множества Р имеет вид a®b, где aÎ (VT È VN)+, b Î (VT È VN)* и |a| £ |b|. Расширение допускает не более одного e-правила, т.е. правила вида А®e, АÎVN.
Тип 2. Грамматика называется контекстно-свободной грамматикой (КС-грамматикой), если ее правила вывода имеют вид: , где и
Тип 3. Грамматика называется регулярной грамматикой (Р-грамматикой), выровненной вправо, если ее правила вывода имеют вид , где .
Грамматика называется регулярной грамматикой (Р-грамматикой), выровненной влево, если ее правила вывода имеют вид , где .

Расширение допускает единственное e-правило вида S®e, но в этом случае начальный символ грамматики S не должен встречаться в правых частях правил.

Определение 1.15. Язык L(G) называется языком типа k, если его можно описать грамматикой типа k, где k – максимально возможный номер типа грамматики.
Пример 1.7. Язык вида L=<0n1n | n>0> порождается КЗ-грамматикой (тип 1) G1 (пример 1.4) и КС-грамматикой (тип 2) G2= (<0, 1>, <S>, P2, S), где
множество правил вывода P2 содержит правила вида S® 0S1|01.
Так как не существует регулярной грамматики (тип 3), порождающей данный язык, то язык L является языком типа 2 или КС-языком.
Соотношение типов грамматик и языков представлено на рисунке 1.1.

Р – регулярная грамматика;КС – контекстно-свободная грамматика;

КЗ – контекстно-зависимая грамматика;
Тип 0 – грамматика типа 0.

Рисунок 1.1 – Соотношение типов формальных языков и грамматик

Пример 1.8. Примеры различных типов формальных языков и грамматик по классификации Хомского. Терминалы будем обозначать строчными символами, нетерминалы – прописными буквами, начальный символ грамматики – S.

а) Язык типа 0 L(G)= определяется грамматикой с правилами вывода:

б) Контекстно-зависимый язык L(G)=<anbncn | n³1> определяется грамматикой с правилами вывода:

в) Контекстно-свободный язык L(G)=<(aс)n(cb)n | n>0> определяется грамматикой с правилами вывода:

г) Регулярный язык L(G)=<w^ | wÎ<a, b>+, где нет двух рядом стоящих а> определяется грамматикой с правилами вывода:

Определение 1.16. Грамматики G1 и G2 называются эквивалентными, если они определяют один и тот же язык, т.е. .
Определение 1.17. Грамматики G1 и G2 называются почти эквивалентными, если заданные ими языки различаются не более чем на пустую цепочку символов, т.е. .
Пример 1.9. Для грамматики G1 эквивалентной будет грамматика G2 = (<0, 1>, <S>, P3, S), где P2: S® 0S1|01, т.к. L(G1)=L(G2)=<0n1n | n>0> (пример 1.7).

Почти эквивалентной для грамматики G1 будет грамматика G3 = (<0, 1>, <S>, P3, S), где множество правил вывода P3 содержит правила вида S® 0S1|e, т.к. L(G3)=<0n1n | n³0>.

Источник

Понятие о грамматике языка

Грамматика – это описание способа построения предложений некоторого языка. Иными словами, грамматика – это математическая система, определяющая язык.

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

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

Грамматика языка программирования содержит правила двух типов: первые (определяющие синтаксические конструкции языка) довольно легко поддаются формальному описанию; вторые (определяющие семантические ограничения языка) обычно излагаются в неформальной форме. Поэтому любое описание (или общепринятый стандарт) языка программирования обычно состоит из двух частей: вначале формально излагаются правила построения синтаксических конструкций, а потом на естественном языке дается описание семантических правил. Естественный язык понятен человеку, пользователю, который будет писать программы на языке программирования; для компилятора же семантические ограничения необходимо излагать в виде алгоритмов проверки правильности программы (речь, как уже было сказано выше, не идет о смысле программ, а только лишь о семантических ограничениях на исходный текст). Такой проверкой в компиляторе занимается семантический анализатор – специально для этого разработанная часть компилятора.

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

Язык, заданный грамматикой G, обозначается как L(G).

Две грамматики G и G’ называются эквивалентными, если они определяют один и тот же язык: L(G) = L(G’). Две грамматики G и G’ называются почти эквивалентными, если заданные ими языки различаются не более чем на пустую цепочку символов: L(G)<>=L(G’)<>.

1.2.2. Формальное определение грамматики. Форма
Бэкуса–Наура

Для полного формального определения грамматики кроме правил порождения цепочек языка необходимо задать также алфавит языка.

Формально грамматика G определяется как четверка G(VT,VN,P,S), где:

 VT – множество терминальных символов;

 VN – множество нетерминальных символов: VNVT = ;

 S – целевой (начальный) символ грамматики SVN.

Множество V = VNVT называют полным алфавитом грамматики G.

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

Эти два множества не пересекаются: каждый символ может быть либо терминальным, либо нетерминальным. Ни один символ в алфавите грамматики не может быть нетерминальным и терминальным одновременно. Целевой символ грамматики – это всегда нетерминальный символ.

Ниже приведен пример грамматики для целых десятичных чисел со знаком:

Рассмотрим составляющие элементы грамматики G:

 множество терминальных символов VT содержит двенадцать элементов: десять десятичных цифр и два знака;

 множество правил содержит 15 правил, которые записаны в три строки (то есть имеются только три различных правых части правил);

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

Для терминальных символов это неверно. Набор терминальных символов всегда строго соответствует алфавиту языка, определяемого грамматикой.

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

Здесь изменилось только множество нетерминальных символов. Теперь VN=. Язык, заданный грамматикой, не изменился – грамматики G и G’ эквивалентны.

Статьи к прочтению:

Английский язык: теоретическая грамматика. Лекция 2. Понятие системы в грамматике

Похожие статьи:

Формальные грамматики и языки. Элементы теории трансляции. (издание второе, переработанное и дополненное) 1999 УДК 519.682.1+681.142.2 Приводятся…

1.3.1. Классификация грамматик. Четыре типа грамматик по Хомскому Формальные грамматики классифицируются по структуре их правил. Если все без исключения…

Источник

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

Небольшое предисловие

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

Определение порождающей грамматики

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

Формализм порождающих грамматик Хомского был введен Ноамом Хомским в конце 50-х годов прошлого века. За короткое время этот формализм обрел необычайную популярность. Некоторое время порождающие грамматики рассматривались как панацея — универсальный подход для задания всевозможных языков, в том числе и естественных (т.е. языков, которые люди используют для повседневного общения между собой). Но время показало, что порождающие грамматики для описания естественных языков не очень удобны. Сейчас порождающие грамматики применяются, в основном, для описания синтаксиса формальных языков, подобных языкам программирования и другим компьютерным языкам.

Цепочки в правилах грамматики могут быть составлены из символов двух алфавитов: алфавита терминальных символов (терминалов) и алфавита нетерминальных символов (нетерминалов). Алфавит терминалов обозначают через T. Этот алфавит на самом деле совпадает с алфавитом того формального языка, который задает данная грамматика. Смысл термина «терминальный» состоит в том, что в правилах грамматики в левой части не может быть цепочек, которые составлены только из терминальных символов. Поэтому, если такая цепочка получилась в результате подстановки, то следующая процесс порождения цепочки остановится (terminate). Нетерминальные символы используются в промежуточных порождениях цепочек. Смысл нетерминала в задании алгоритма порождения цепочки может быть самый разный и обычно зависит от типа грамматики, в которой этот символ используется. Различные примеры использования нетерминальных символов будут рассмотрены ниже.

Но один нетерминальный символ всегда имеет один и тот же смысл — он обозначает все цепочки языка. Называется этот нетерминал «начальным нетерминальным символов порождающей грамматики» и обычно обозначается посредством латинского S (start или sentence). В каждой порождающей грамматике обязательно должно быть правило, к которого левая часть состоит из единственного начального нетерминала, иначе в данной грамматике нельзя будет породить даже одной цепочки.

Язык порождающей грамматики

Порождающая грамматика Хомского задает язык посредством конечного числа подстановок цепочек из начального нетерминала грамматики на основе правил порождения. Опишем это чуть более конкретно.

Для иллюстрации приведем два простых примера.

Пример очень простого языка

Язык простых арифметических выражений

Классы грамматик

Ноам Хомский ввел классы грамматик (и соответствующие классы языков) задавая ограничения на вид правил порождающей грамматики. Каждый класс грамматик имеет свою описательную мощность. Описательную мощность класса грамматик можно охарактеризовать, как возможность выражений в правилах грамматики определенных синтаксических отношений. Рассмотрим, как классы грамматик задают синтаксические отношения.

Грамматики типа 3

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

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

Контекстно-свободные грамматики

КС-грамматики задают два вида синтаксических отношений: отношение «быть рядом» и отношение «быть частью» или отношение иерархии. Отношение иерархии наиболее естественно для человеческого ума. Человеку свойственно типизировать вещи, т.е. рассматривать конкретные объекты своего мышления как части какого-то общего типа (класса). Каждая вещь, о которой думает человек, является экземпляром некоторого класса. Например, конкретный стул является экземпляром класса «стул» с соответствующими признаками. Человеческому уму также свойственно разделять типы на подтипы, двигаясь от более конкретных типов к более абстрактным. Скажем, стул есть подтип типа мебель, мебель есть подтип типа предмет, предмет есть подтип типа объект и т.п. Отношение «тип-подтип» и есть отношение иерархии.

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

Контекстно-зависимые грамматики и грамматики без ограничений

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

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

Зачем так необходимо выделять класс языков, задаваемых неукорачивающими грамматиками? Дело в том, что для таких языков можно задать распознающий автомат. Распознающая грамматика конструируется следующим образом: получая на вход цепочку, последовательно делаем порождения, упорядочивая их по длине порождаемой цепочки. Т.к. грамматика неукорачивающая, то таких порождений будет конечное множество и, если среди них не нашлось совпадения с данной на вход цепочкой, то напечатать «нет».

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

Приведем в качестве примера порождение цепочки aaaa : S => LS’R => LAS’BR => LAABBR => LABACBR => LBACACBR => LACACBR => LACABCR => LACBACCR => LABCACCR => LBACCACCR => LACCACCR => LCACACCR => LCCAACCR => LCCACACR => LCCACCAR => LCCACCR => LCCCACR => LCCCCAR => LCCCCR => aLCCCR => aaLCCR => aaaLCR => aaaaLR => aaaa

Заключение

Автор надеется, что последний пример ясно продемонстрировал читателю, что порождающая грамматика Хомского представляет собой своего рода программу, предназначенную для генерации цепочек формального языка, задаваемого этой грамматикой. Язык задания программы довольно специфический, соответственно и реализация «программ генерации» (грамматик) требует опыта и определенной привычки в их написании.

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

Источник