Упражнения по формальным грамматикам. Примеры построения грамматик

1. Самостоятельные части речи:

существительные (см. морфологические нормы сущ.);
глаголы:
- причастия;
- деепричастия;
прилагательные;
числительные;
местоимения;
наречия;

2. Служебные части речи:

предлоги;
союзы;
частицы;

3. Междометия.

Ни в одну из классификаций (по морфологической системе) русского языка не попадают:

слова да и нет, в случае, если они выступают в роли самостоятельного предложения.
вводные слова: итак, кстати, итого, в качестве отдельного предложения, а так же ряд других слов.

Морфологический разбор существительного

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

План морфологического разбора существительного

"Малыш пьет молоко."

Малыш (отвечает на вопрос кто?) – имя существительное;

начальная форма – малыш;
постоянные морфологические признаки: одушевленное, нарицательное, конкретное, мужского рода, I -го склонения;
непостоянные морфологические признаки: именительный падеж, единственное число;
при синтаксическом разборе предложения выполняет роль подлежащего.

Морфологический разбор слова «молоко» (отвечает на вопрос кого? Что?).

начальная форма – молоко;
постоянная морфологическая характеристика слова: среднего рода, неодушевленное, вещественное, нарицательное, II -е склонение;
изменяемые признаки морфологические: винительный падеж, единственное число;
в предложении прямое дополнение.

Приводим ещё один образец, как сделать морфологический разбор существительного, на основе литературного источника:

"Две дамы подбежали к Лужину и помогли ему встать. Он ладонью стал сбивать пыль с пальто. (пример из: «Защита Лужина», Владимир Набоков)."

Дамы (кто?) - имя существительное;

начальная форма - дама;
постоянные морфологические признаки: нарицательное, одушевленное, конкретное, женского рода, I склонения;
непостоянная морфологическая характеристика существительного: единственное число, родительный падеж;
синтаксическая роль: часть подлежащего.

Лужину (кому?) - имя существительное;

начальная форма - Лужин;
верная морфологическая характеристика слова: имя собственное, одушевленное, конкретное, мужского рода, смешанного склонения;
непостоянные морфологические признаки существительного: единственное число, дательного падежа;

Ладонью (чем?) - имя существительное;

начальная форма - ладонь;
постоянные морфологические признаки: женского рода, неодушевлённое, нарицательное, конкретное, I склонения;
непостоянные морфо. признаки: единственного числа, творительного падежа;
синтаксическая роль в контексте: дополнение.

Пыль (что?) - имя существительное;

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

(с) Пальто (С чего?) - существительное;

начальная форма - пальто;
постоянная правильная морфологическая характеристика слова: неодушевленное, нарицательное, конкретное, среднего рода, несклоняемое;
морфологические признаки непостоянные: число по контексту невозможно определить, родительного падежа;
синтаксическая роль как члена предложения: дополнение.

Морфологический разбор прилагательного

Имя прилагательное - это знаменательная часть речи. Отвечает на вопросы Какой? Какое? Какая? Какие? и характеризует признаки или качества предмета. Таблица морфологических признаков имени прилагательного:

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

План морфологического разбора прилагательного

Пример предложения:

Полная луна взошла над городом.

Полная (какая?) – имя прилагательное;

начальная форма – полный;
постоянные морфологические признаки имени прилагательного: качественное, полная форма;
непостоянная морфологическая характеристика: в положительной (нулевой) степени сравнения, женский род (согласуется с существительным), именительный падеж;
по синтаксическому анализу - второстепенный член предложения, выполняет роль определения.

Вот еще целый литературный отрывок и морфологический разбор имени прилагательного, на примерах:

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

Прекрасна (какова?) - имя прилагательное;

начальная форма - прекрасен (в данном значении);
постоянные морфологические нормы: качественное, краткое;
непостоянные признаки: положительная степень сравнения, единственного числа, женского рода;

Стройная (какая?) - имя прилагательное;

начальная форма - стройный;
постоянные морфологические признаки: качественное, полное;
непостоянная морфологическая характеристика слова: полное, положительная степень сравнения, единственное число, женский род, именительный падеж;
синтаксическая роль в предложении: часть сказуемого.

Тоненькая (какая?) - имя прилагательное;

начальная форма - тоненький;
морфологические постоянные признаки: качественное, полное;
непостоянная морфологическая характеристика прилагательного: положительная степень сравнения, единственное число, женского рода, именительного падежа;
синтаксическая роль: часть сказуемого.

Голубые (какие?) - имя прилагательное;

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

Изумительных (каких?) - имя прилагательное;

начальная форма - изумительный;
постоянные признаки по морфологии: относительное, выразительное;
непостоянные морфологические признаки: множественное число, родительного падежа;
синтаксическая роль в предложении: часть обстоятельства.

Морфологические признаки глагола

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

Морфологические формы глаголов:

начальная форма глагола - инфинитив. Ее так же называют неопределенная или неизменяемая форма глагола. Непостоянные морфологические признаки отсутствуют;
спрягаемые (личные и безличные) формы;
неспрягаемые формы: причастные и деепричастные.

Морфологический разбор глагола

начальная форма - инфинитив;
постоянные морфологические признаки глагола:
- переходность:
- - переходный (употребляется с существительными винительного падежа без предлога);
  - непереходный (не употребляется с существительным в винительном падеже без предлога);
- возвратность:
- - возвратные (есть -ся, -сь);
  - невозвратные (нет -ся, -сь);
- - несовершенный (что делать?);
  - совершенный (что сделать?);
- спряжение:
- - I спряжение (дела-ешь, дела-ет, дела-ем, дела-ете, дела-ют/ут);
  - II спряжение (сто-ишь, сто-ит, сто-им, сто-ите, сто-ят/ат);
  - разноспрягаемые глаголы (хотеть, бежать);
непостоянные морфологические признаки глагола:
- наклонение:
- - изъявительное: что делал? что сделал? что делает? что сделает?;
  - условное: что делал бы? что сделал бы?;
  - повелительное: делай!;
- время (в изъявительном наклонении: прошедшее/настоящее/будущее);
- лицо (в настоящем/будущем времени, изъявительного и повелительного наклонения: 1 лицо: я/мы, 2 лицо: ты/вы, 3 лицо: он/они);
- род (в прошедшем времени, единственного числа, изъявительного и условного наклонения);
- число;
синтаксическая роль в предложении. Инфинитив может быть любым членом предложения:
- сказуемым: Быть сегодня празднику;
- подлежащим:Учиться всегда пригодится;
- дополнением: Все гости просили ее станцевать;
- определением: У него возникло непреодолимое желание поесть;
- обстоятельством: Я вышел пройтись.

Морфологический разбор глагола пример

Чтобы понять схему, проведем письменный разбор морфологии глагола на примере предложения:

Вороне как-то Бог послал кусочек сыру... (басня, И. Крылов)

Послал (что сделал?) - часть речи глагол;

начальная форма - послать;
постоянные морфологические признаки: совершенный вид, переходный, 1-е спряжение;
непостоянная морфологическая характеристика глагола: изъявительное наклонение, прошедшего времени, мужского рода, единственного числа;

Следующий онлайн образец морфологического разбора глагола в предложении:

Какая тишина, прислушайтесь.

Прислушайтесь (что сделайте?) - глагол;

начальная форма - прислушаться;
морфологические постоянные признаки: совершенный вид, непереходный, возвратный, 1-го спряжения;
непостоянная морфологическая характеристика слова: повелительное наклонение, множественное число, 2-е лицо;
синтаксическая роль в предложении: сказуемое.

План морфологического разбора глагола онлайн бесплатно, на основе примера из целого абзаца:

Его нужно предостеречь.

Не надо, пусть знает в другой раз, как нарушать правила.

Что за правила?

Подождите, потом скажу. Вошел! («Золотой телёнок», И. Ильф)

Предостеречь (что сделать?) - глагол;

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

Пусть знает (что делает?) - часть речи глагол;

начальная форма - знать;
непостоянная морфология глагола: повелительное наклонение, единственного числа, 3-е лицо;
синтаксическая роль в предложении: сказуемое.

Нарушать (что делать?) - слово глагол;

начальная форма - нарушать;
постоянные морфологические признаки: несовершенный вид, невозвратный, переходный, 1-го спряжения;
непостоянные признаки глагола: инфинитив (начальная форма);
синтаксическая роль в контексте: часть сказуемого.

Подождите (что сделайте?) - часть речи глагол;

начальная форма - подождать;
постоянные морфологические признаки: совершенный вид, невозвратный, переходный, 1-го спряжения;
непостоянная морфологическая характеристика глагола: повелительное наклонение, множественного числа, 2-го лица;
синтаксическая роль в предложении: сказуемое.

Вошел (что сделал?) - глагол;

начальная форма - войти;
постоянные морфологические признаки: совершенный вид, невозвратный, непереходный, 1-го спряжения;
непостоянная морфологическая характеристика глагола: прошедшее время, изъявительное наклонение, единственного числа, мужского рода;
синтаксическая роль в предложении: сказуемое.

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

Термины

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

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

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

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

Итак, грамматика определяется следующими характеристиками:

Вывод

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

Существование вывода для некоторого слова является критерием его принадлежности к языку, определяемому данной грамматикой.

Типы грамматик

Терминальный алфавит:

Σ {\displaystyle \Sigma } = {"0","1","2","3","4","5","6","7","8","9","+","-","*","/","(",")"}

Нетерминальный алфавит:

{ ФОРМУЛА, ЗНАК, ЧИСЛО, ЦИФРА }

1. ФОРМУЛА → {\displaystyle \to } ФОРМУЛА ЗНАК ФОРМУЛА (формула есть две формулы, соединенные знаком) 2. ФОРМУЛА → {\displaystyle \to } ЧИСЛО (формула есть число) 3. ФОРМУЛА → {\displaystyle \to } (ФОРМУЛА) (формула есть формула в скобках) 4. ЗНАК → {\displaystyle \to } + | - | * | / (знак есть плюс или минус, или умножить, или разделить) 5. ЧИСЛО → {\displaystyle \to } ЦИФРА (число есть цифра) 6. ЧИСЛО → {\displaystyle \to } ЧИСЛО ЦИФРА (число есть число и цифра) 7. ЦИФРА → {\displaystyle \to } 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (цифра есть 0 или 1, или... 9)

Начальный нетерминал:

ФОРМУЛА

Вывод :

Выведем формулу (12+5) с помощью перечисленных правил вывода. Для наглядности, стороны каждой замены показаны попарно, в каждой паре заменяемая часть подчеркнута.

ФОРМУЛА → 3 {\displaystyle {\stackrel {3}{\to }}} (ФОРМУЛА) (ФОРМУЛА ) → 1 {\displaystyle {\stackrel {1}{\to }}} (ФОРМУЛА ЗНАК ФОРМУЛА ) (ФОРМУЛА ЗНАК ФОРМУЛА) → 4 {\displaystyle {\stackrel {4}{\to }}} (ФОРМУЛА + ФОРМУЛА) (ФОРМУЛА + ФОРМУЛА ) (ФОРМУЛА + ЧИСЛО ) (ФОРМУЛА + ЧИСЛО ) (ФОРМУЛА + ЦИФРА ) (ФОРМУЛА + ЦИФРА ) (ФОРМУЛА + 5 ) (ФОРМУЛА + 5) → 2 {\displaystyle {\stackrel {2}{\to }}} (ЧИСЛО + 5) (ЧИСЛО + 5) → 6 {\displaystyle {\stackrel {6}{\to }}} (ЧИСЛО ЦИФРА + 5) (ЧИСЛО ЦИФРА + 5) → 5 {\displaystyle {\stackrel {5}{\to }}} (ЦИФРА ЦИФРА + 5) (ЦИФРА ЦИФРА + 5) → 7 {\displaystyle {\stackrel {7}{\to }}} (1 ЦИФРА + 5) (1 ЦИФРА + 5) → 7 {\displaystyle {\stackrel {7}{\to }}} (1 2 + 5)

ВВЕДЕНИЕ………… ………………………………….…………….4

Глава 1. ЯЗЫКИ И ГРАММАТИКИ. ОБОЗНАЧЕНИЯ, ОПРЕДЕЛЕНИЯ И КЛАССИФИКАЦИЯ ………………………………………………………………………………6

1.1. Понятие грамматики языка. Обозначения……………………………………………7

1.2. Классификация грамматик по Хомскому………………………..…………………13

1.3. Техника построения КС- и А- грамматик…………………………………………..16

1.4. Синтаксические деревья вывода в КС-грамматиках. Представление

А-грамматик в виде графа состояний. Неоднозначность грамматик……………..19

1.5. Синтаксический анализ А-языков…………………………………………………..23

Упражнения……………………………………………………………………………….29

Глава 2. РАСПОЗНАВАТЕЛИ И АВТОМАТЫ .……………………………….….…………32

Глава 3. АВТОМАТНЫЕ ГРАММАТИКИ И КОНЕЧНЫЕ АВТОМАТЫ …………….35

3.1. Автоматные грамматики и конечные автоматы…………………………………….35

3.2.Эквивалентность недетерминированных и детерминированных А-грамматик…… 36

Упражнения………………………………………………………………………………… 41

Глава 4. ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ КОНТЕКСТНО-СВОБОДНЫХ

И АВТОМАТНЫХ ГРАММАТИК ………………………………………………..….42

4.2. Исключение тупиковых правил из грамматик………………………………………46

4.3. Обобщенные КС-грамматики и приведение грамматик к удлиняющей форме…….48

4.4. Устранение левой рекурсии и левая факторизация………………………………..…52

Упражнения………………………………………………………………………………….53

Глава 5. СВОЙСТВА АВТОМАТНЫХ И КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ …55

5.1. Общий вид цепочек А-языков и КС-языков………………………………………..55

5.2. Операции над языками………………………………………………………………….59

5.2.1. Операции над КС-языками………………………………………………………59

5.2.2. Операции над А-языками………………………………………………………62

5.2.3. Операции над К-языками………………………………………………………66

5.3. Выводы для практики…………….………………………………………………….67

5.4. Неоднозначность КС-грамматик и языков…………………………………………71

Упражнения…………………………………………………………………………....…74

Глава 6. СИНТАКСИЧЕСКИЙ АНАЛИЗ КС-языков ……………………………...……...75

6.1. Методы анализа КС-языков. Грамматики предшествования………………….…75

6.2. Грамматики предшествования Вирта……………………………………………...77

Грамматики предшествования Флойда…….……………………………………...79

Функции предшествования…………………………………………………………81

Упражнения………………………………………………………………………………84

Глава 7. ВВЕДЕНИЕ В СЕМАНТИКУ ……………………………………………………….85

7.1. Польская инверсная запись….……………………………………………………...85

7.2. Интерпретация ПОЛИЗа……………………………….………………………..….87

7.3. Генерирование команд по ПОЛИЗу………………………………….…………....89

7.4. Алгоритм Замельсона и Бауэра перевода выражений в ПОЛИЗ………..……….91

7.5. Атрибутные грамматики……………………………………………………………97

Упражнения……………………………………………………………………………..100

Глава 8. ОСНОВНЫЕ ФАЗЫ КОМПИЛЯЦИИ ……………………………………...……100

ЗАКЛЮЧЕНИЕ

ПРИЛОЖЕНИЕ …………………………………………………………………………………105

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ ……………………………………………………….…….…115

Введение

Лингвистика - наука о языке. Математическая лингвистика - наука, занимающаяся формальными методами построения и изучения языков.

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

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

С проблемами объяснения языка машине сталкиваются многие разработчики программного обеспечения. Человеку свойственно изобретать новые языки. Здесь речь может идти не только о сложных компиляторах для новых алгоритмических языков программирования. Любая автоматизированная система должна понимать некоторый входной язык запросов. Новые информационные технологии предполагают привлечение конечного пользователя (ученого, конструктора, технолога, оператора) - специалиста в конкретной области, а не в области вычислительной техники и технологии программирования, к решению своих задач на ЭВМ. Для качественного решения этой проблемы между пользователем и ЭВМ должен существовать интеллектуальный интерфейс: пользователь должен ставить задачи и получать результаты их решения в терминах известной ему предметной области. То есть, необходима разработка широкого спектра предметно-ориентированных языков. Специалист в области программного обеспечения должен знать, как создаются языки и их программная поддержка.

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

Язык – это множество предложений (фраз), построенных по определенным правилам.

Грамматика - свод правил, определяющих принадлежность фразы языку.

Любой язык должен удовлетворять свойствам разрешимости и однозначности.

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

Основными разделами грамматики являются синтаксис и семантика.

Синтаксис - свод правил, определяющих правильность построения предложений языка.

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

Предложение может быть синтаксически верным и семантически неверным.

Синтаксис обычно упрощается тем, что не все фразы языка обязаны иметь смысл. Зачастую трудно понять смысл футуристов или речь некоторых политиков. В этой связи интересен пример академика Л.В.Щербы: «Глокая куздра штеко будланула бокра и кудрячит бокренка». Это фраза на русском языке, так как её можно разобрать по членам предложения, но смысл её неясен.

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

<предложение>

Природу неоднозначности фразы можно объяснить на примере все того же дерева разбора для фразы «Мать любит дочь».

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

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

Алгоритм был ранее определен как алфавитный оператор с конечной системой правил преобразования. Для записи входных, промежуточных и выходных слов используется некоторый алфавит. Каким-то образом должны быть описаны и правила преобразования. Очевидно, для этого требуется некоторый язык. Пригоден ли для описания алгоритма обычный разговорный язык?

Любой естественный язык возникал как средство общения людей. Именно по этой причине ему присущи такие особенности как:

· изменчивость, которая состоит в непостоянстве словарного состава языка;

· неоднозначность трактовки фраз различными людьми;

· избыточность, о чем шла речь в главе «Кодирование символьной информации».

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

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

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

Любая грамматика начинается с указания алфавита, т.е. набора символов, посредством которого строятся конструкции языка.

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

Помимо синтаксиса устанавливается система правил, позволяющих конструкциям языка придать смысл - эти правила образуют семантику языка.

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

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

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

Формальная грамматика задается упорядоченной четверкой {T , N, S, Р }, где Т и N - непересекающиеся конечные множества, образующие алфавит или словарь порождаемого формального языка; Т называется множеством (словарем) терминальных символов; N - множеством (словарем) нетерминальных (вспомогательных) символов. S - начальный (выделенный) вспомогательный символ из множества N. Р - набор правил вывода конструкций языка (подстановок) из выделенного вспомогательного символа, имеющие вид g → h, где g и h - цепочки, состоящие как из терминальных, так и нетерминальных символов.

Подстановки работают следующим образом: если в преобразуемой цепочке есть слово g , то оно заменяется словом h. Единственное ограничение на вид подстановок состоит в том, что слово g не может состоять только из терминальных символов. Это означает, что получение на некотором шаге цепочки, состоящей только из терминальных символов, свидетельствует о прекращении процесса порождения - эта цепочка является правильной, завершенной конструкцией порождаемого языка. Подстановки Р могут применяться к трансформируемой цепочке в произвольном порядке.

Грамматика формальная

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

Термины

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

Итак, грамматика определяется следующими характеристиками:

Вывод

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

Типы грамматик

Терминальный алфавит:

Σ ={"0","1","2","3","4","5","6","7","8","9","+","-","*","/","(",")"}.

Нетерминальный алфавит:

{ ФОРМУЛА, ЗНАК, ЧИСЛО, ЦИФРА }

1. ФОРМУЛА ФОРМУЛА ЗНАК ФОРМУЛА (формула есть две формулы, соединенные знаком) 2. ФОРМУЛА ЧИСЛО (формула есть число) 3. ФОРМУЛА (ФОРМУЛА) (формула есть формула в скобках) 4. ЗНАК + | - | * | / (знак есть плюс или минус или умножить или разделить) 5. ЧИСЛО ЦИФРА (число есть цифра) 6. ЧИСЛО ЧИСЛО ЦИФРА (число есть число и цифра) 7. ЦИФРА 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (цифра есть 0 или 1 или... 9)

Начальный нетерминал:

ФОРМУЛА

Вывод :

ФОРМУЛА (ФОРМУЛА) (ФОРМУЛА ) (ФОРМУЛА ЗНАК ФОРМУЛА ) (ФОРМУЛА ЗНАК ФОРМУЛА) (ФОРМУЛА + ФОРМУЛА) (ФОРМУЛА + ФОРМУЛА ) (ФОРМУЛА + ЧИСЛО ) (ФОРМУЛА + ЧИСЛО ) (ФОРМУЛА + ЦИФРА ) (ФОРМУЛА + ЦИФРА ) (ФОРМУЛА + 5 ) (ФОРМУЛА + 5) (ЧИСЛО + 5) (ЧИСЛО + 5) (ЧИСЛО ЦИФРА + 5) (ЧИСЛО ЦИФРА + 5) (ЦИФРА ЦИФРА + 5) (ЦИФРА ЦИФРА + 5) (1 ЦИФРА + 5) (1 ЦИФРА + 5) (1 2 + 5)

Аналитические грамматики

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

Источники

Гладкий А. В. Формальные грамматики и языки. - М.: Наука, 1973.
Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений . - Новосибирск: НГУ. - 1995. - 112 с.
Хомский Н., Миллер Дж. Введение в формальный анализ естественных языков // Кибернетический сборник / Под ред. А.А.Ляпунова и О.Б.Лупанова. - М.: Мир, 1965.

Wikimedia Foundation . 2010 .

Смотреть что такое "Грамматика формальная" в других словарях:

- (в лингвистике) логическая система, или исчисление, задающая некоторое множество («правильных») цепочек (= конечных последовательностей), построенных из символов заданного конечного набора, называемого «алфавитом» или «основным… … Большая советская энциклопедия

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

Грамматика формальная - В лингвистике: логическая система, или исчисление, задающая некоторое множество («правильных») цепочек (= конечных последовательностей), построенных из символов заданного конечного набора, называемого «алфавитом» или «основным (терминальным)… … Общее языкознание. Социолингвистика: Словарь-справочник

Грамматика (от греч. γράμμα «запись»), как наука, есть раздел языкознания, изучающий грамматический строй языка, закономерности построения правильных осмысленных речевых отрезков на этом языке (словоформ, синтагм, предложений, текстов). Эти … Википедия

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

ФОРМАЛЬНАЯ ГРАММАТИКА. Грамматика, последовательно проводящая принцип изучения только форм языка и исключающая из своего состава все явления, не обозначенные формами языка. Ф. Г. противополагается т. н. логической (название неточное) грамматике,… … Литературная энциклопедия

Генеративная лингвистика … Википедия

У этого термина существуют и другие значения, см. Грамматика (значения). Грамматика (др. греч. γραμματική от γράμμα «буква») как наука является разделом языкознания, который изучает грамматический строй языка, закономерности построения… … Википедия

См. грамматика формальная (в статье грамматика) … Словарь лингвистических терминов