Теория формальных языков и грамматик

Группа 6301 СГАУ, Новиков Артур Романович

Преподаватель: Чигарина Елена Ивановна (428)

Преподаватель по практике: Литвинов Владимир Геннадьевич

План:

Лабораторная работа: синтаксический анализатор разбора машинной грамматики.

Контрольная работа: 5-6 учебная неделя.

Идея:

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

Литература:

Чигарина Е.В, Шамашов Н.А: теория конечных автоматов и формальных языков, 2007

Чигарина Е.В, Шамашов Н.А: основы теории формальных грамматик, 2001

Штернберг Л.Ф: теория формальных грамматик, 1979

Тема 0: Понятие тфг, математическая лингвистика грамматики.

Лингвистика – наука о языке.

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

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

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

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

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

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

Свойства языков: однозначность, разрешимость:

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

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

Если фраза имеет более одного дерева синтаксического разбора, то она неоднозначна.

Тема 1: Языки грамматики. Определения и обозначения.

1. Понятие грамматики языка с точки зрения теории формальных грамматик. Обозначение.

2. Классификация грамматик по Хомскому. Теорема о разрешимости контекстных языков.

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

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

5. Синтаксический анализ автоматных грамматик.

С точки зрения формальных грамматик, язык – это множество цепочек, построенных на символах алфавита.

Алфавит – непустое конечное множество символов, использующихся в цепочках языка.

Для обозначения символов цепочек используются латинские буквы: «a, b, c, d…», цифры: «1, 2, 3», знаки «;, :…».

A, B, C: «понятия», которые дальше расшифровываются.

Символ алфавита – конечная и неделимая единица.

Терминальное состояние – представление фразы в виде неделимых элементов.

{a, b, c},

F1 (альфа) = aaac

F2 (бета) = caab

F1*F2 \= F2*F1

Грамматика языка – это четвёрка объектов: <S, V_t, V_n, R>, где

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

Vt – множество терминальных символов грамматики.

Vn – множество нетерминальных символов грамматики.

R – множество правил грамматики.

Для обозначения правил существует несколько форм записи. Изначально использовалась форма Бэкуса-Наура.

Метаязык – язык для описания других языков.

[…] – необязательный факультативный элемент.

| - «или».

<предложение> ::= <подлежащее><группа сказуемого>

<подлежащее> ::= мать|отец

<группа сказуемого> ::= <сказуемое><дополнение>

<сказуемое> ::= любит|обожает

<дополнение> ::= сына|дочь

<предложение>  <подлежащее><группа сказуемого>  мать<группа сказуемого>  мать<сказуемое><дополнение>  мать любит дочь.

Всего 8 цепочек (вариантов).

Вместо «::=» можно ставить двойную стрелку. Слева направо – порождающая грамматика. Справа налево – воссоздающая.

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

S  SS|0|1

S  0S|1S|0|1 – один и тот же язык, вместо S либо 0, либо 1.

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

S  aS (правая), S  Sa (левая).

Классификация по Хомскому:

Грамматика является регулярной [тип 1], если правила вывода грамматики имеют следующий вид: A  aB|a: в левой части - нетерминал, в правой – терминал.

Грамматика является контекстно-свободной [тип 2] – бесконтекстная графика, если A  a.

Контекстная грамматика (К-грамматика), если она соответствует типу 1, или она контекстно-зависимая.

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

Тип 0 – любой язык, можно использовать при ответах.

Пример: S  aA|…|zA

A  aA|…|zA|oA|…|9A|a|…|z|o|…|9 – грамматика автоматная. Это идентификатор.

Теорема о разрешимости языков: любой контекстный язык является разрешимым.

Для любого контекстного языка L существует порождающая его грамматика в удлиняющей форме.

При любом выводе цепочки на каждом шаге вывода цепочки длина цепочки увеличивается хотя бы на один символ.

Если цепочка принадлежит языку L, то существует вывод этой цепочки, в котором количество шагов вывода конечно, и значит, за конечное время можно определить, принадлежит ли цепочка языку, то есть язык разрешим.

1.3. Техника построения контекстно-свободных формальных грамматик.

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

Для получения произвольного числа символов в цепочке используется одно из следующих правил:

<один или много A>  A | A <один или много A> // правая рекурсия

<один или много A>  A | <один или много A> A // левая рекурсия

<действительное число>  [<знак>][<целая часть>][<точка>][<дробная часть>][Е[<знак>]<порядок>].

<знак>  +|-

<целая часть>  <цифра>|<цифра><целая часть>

<дробная часть>  <целая часть>

<порядок>  <целая часть>

<цифра>  0|1|…|9

Техника построения автоматных грамматик определяется видом правых частей правил вывода в автоматных грамматиках.

На каждом шаге вывода выписываются терминальные символы, которые могут встретиться на этом шаге.

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

<число>  +<число без знака>|-<число без знака>|0<число без знака>|…|9<число без знака>|.|.<дробная часть числа>

<число без знака>  0<число без знака>|…|9<число без знака>|.<дробная часть числа>|.

<дробная часть>  0<дробная часть>|…|9<дробная часть>|E<порядок>

<порядок>  +<пбз>|-<пбз>|0<пбз>|…|9<пбз>|0|…|9

1.4. Представление автомата грамматик в виде графа.

S  S+S|S*S|V|C

V  a|…|z

C  0|…|9

Пример: b+a*3. Решение:

1. S  S+S  V+S  V+S*S  V+V*S  V+V*C  b+a*3

2. S  S*S  S+S*S  V+S*S  V+V*S  V+V*C  b+a*3

Цепочка, выводимая в грамматике, неоднозначна, если для её вывода существует более одного дерева вывода.

Грамматика называется неоднозначной, если она порождает неоднозначные цепочки.

F – конечное состояние.

F’ – предконечное состояние.

S  aA|…|zA

A  aA|…|zA|0A|…|9A|0|…|9|a|…|z

S

A

F

a…z

a…z

a…z 0…9

0…z

0…9

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

Автограмматика находится в детерминированной форме, если для любого терминала A (A /= F) существует не более одного нетерминала B с правилом вида A  aB.

Автограмматика находится во вполне детерминированной форме, если для любого терминала A (A /= F) существует единственный нетерминал B для терминала A, для которого имеется правило: A  aB.

F – символ, завершающий цепочку.

5. Синтаксический анализ автоматных грамматик.

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

Цепочка  Анализатор  Вывод информации.

Этапы построения анализатора:

1. По описанию языка. Если грамматика находится в недетерминированной форме, её нужно привести.

2. В соответствии с графом состояний пишется программа синтаксического анализатора.

3. В анализатор добавляется семантика.

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