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

Формальные грамматики являются математическими моделями из грамматик , которые используются для создания и однозначно описать формальные языки . Они используются в теоретической информатике , особенно в теории вычислимости , и при создании компиляторов, с одной стороны, чтобы четко определить, является ли слово элементом языка, а с другой стороны, чтобы исследовать или доказать свойства этих формальных языков. Формальные грамматики классифицируются с использованием систем Semi-Thue, приведенных в иерархии Хомского .

описание

С формальной грамматикой, начиная с начального символа (также называемого начальной переменной ), производственные правила могут применяться из набора правил, которые генерируют новые символьные строки ( слова ) из начального символа , которые, в свою очередь, могут быть в дальнейшем заменены. Этот процесс также называют производным . ${\ displaystyle S}$${\ displaystyle P}$

Словарь грамматики, состоящий из непересекающихся объединения в алфавите из терминальных символов с набором нетерминальных символов , указывает , какие символы могут быть использованы для этого. Набор терминальных символов определяет, какие символы состоят из слов, которые не могут быть получены в дальнейшем. Взятые вместе, эти слова составляют формальный язык, описываемый грамматикой. С другой стороны, начальный символ должен быть нетерминальным символом. Дополнительные нетерминальные символы позволяют применять более дифференцированные правила. ${\ displaystyle V}$ ${\ displaystyle T}$ ${\ displaystyle N}$

По определению, продукционные правила - это упорядоченные пары , которые также записываются. Она применяется к строке путем замены одного вхождения строки в с . Слева от правила всегда должен быть хотя бы один нетерминальный символ. Многие правила с одинаковой левой частью, то есть также сокращенно обозначаются как . ${\ Displaystyle (\ альфа, \ бета)}$${\ displaystyle \ alpha \ rightarrow \ beta}$${\ displaystyle w}$${\ displaystyle \ alpha}$${\ displaystyle w}$${\ displaystyle \ beta}$${\ displaystyle \ alpha \ rightarrow \ beta _ {1}, \; \ ldots, \ alpha \ rightarrow \ beta _ {n}}$${\ displaystyle \ alpha \ rightarrow \ beta _ {1} \; | \; \ ldots \; | \; \ beta _ {n}}$

Например, можно использовать набор правил для каждой DERIVE или вывести строку . ${\ Displaystyle X \ rightarrow + \; | \; -}$${\ displaystyle 1X2}$${\ displaystyle 1 + 2}$${\ displaystyle 1-2}$

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

определение

Формальная грамматика представлена ​​4- мя кортежем , в котором:${\ Displaystyle G = (V, T, P, S)}$

• ${\ displaystyle V}$, конечный набор символов , который называется набором символов или словарем ,
• ${\ Displaystyle T \ подмножество V}$, подмножество , также называемое алфавитом , элементы которого называются терминальными символами,${\ displaystyle V}$
• ${\ displaystyle P \ subset \ left (V ^ {*} \ setminus T ^ {*} \ right) \ times V ^ {*}}$, конечный набор производственных правил , а также
• ${\ Displaystyle S \ in V \ setminus T}$, начальный символ .

Здесь корпус Kleenesche обозначает набор символов (или слов). ${\ displaystyle X ^ {*}}$${\ displaystyle X}$

Набор представляет собой набор нетерминальных символов (также называемых нетерминальными или метасимволами ), в частности, ему принадлежит начальный символ. Слово в левой части пар правил не должно состоять исключительно из терминальных символов, что также может быть выражено конкатенацией : ${\ Displaystyle N = V \ setminus T}$

${\ displaystyle \ left (V ^ {*} \ setminus T ^ {*} \ right) = V ^ {*} NV ^ {*}}$.

Это не имеет особого смысла, если у слова справа есть начальный символ. Некоторые авторы принимают это во внимание, соответствующим образом ограничивая связанный набор, т.е. ЧАС. путем замены. ${\ Displaystyle V ^ {*}}$${\ Displaystyle (В \ setminus \ {S \}) ^ {*}}$

Некоторые авторы также называют четверку грамматикой . Также существуют следующие разные обозначения:${\ displaystyle (N, T, P, S)}$${\ displaystyle G}$

• ${\ displaystyle \ Sigma}$для конечных символов здесь ,${\ displaystyle T}$
• ${\ displaystyle \ Sigma}$для всего словаря ( набора символов ) всех символов , здесь ,${\ displaystyle V}$
• ${\ displaystyle V}$для нетерминальных символов ( переменных ) здесь ,${\ displaystyle N}$
• ${\ displaystyle \ lambda}$для пустого слова здесь .${\ displaystyle \ epsilon}$

Язык, описываемый грамматикой

Правило данной грамматики гласит, что в слове с инфиксом R R можно заменить на Q, так что создается новое слово с инфиксом. Также говорится о том, что in переходит в грамматику или через правило , или что оно было получено из. Это можно отметить через (часто вместо ). Если нужно только выразить, что слово from может возникать в грамматике, не называя правила, вместо этого пишут ( если грамматика очевидна из контекста, тоже простая ). Соответственно, такой переход от в виде переходного отношения является естественным продолжением всех возможных контекстов, а именно: ${\ Displaystyle R \ rightarrow Q \ in P}$${\ displaystyle G}$${\ Displaystyle ш \ в V ^ {\ ast}}$${\ Displaystyle ш ^ {\ прайм}}$${\ displaystyle Q}$${\ displaystyle w}$${\ Displaystyle ш ^ {\ прайм}}$${\ displaystyle G}$${\ Displaystyle R \ rightarrow Q}$${\ Displaystyle ш ^ {\ прайм}}$${\ displaystyle w}$${\ displaystyle w \ rightsquigarrow _ {R \ rightarrow Q} w ^ {\ prime}}$${\ displaystyle \ Rightarrow}$${\ displaystyle \ rightsquigarrow}$${\ displaystyle G}$${\ Displaystyle ш ^ {\ прайм}}$${\ displaystyle w}$${\ displaystyle w \ rightsquigarrow _ {G} w ^ {\ prime}}$${\ displaystyle w \ rightsquigarrow w ^ {\ prime}}$${\ displaystyle w}$${\ Displaystyle ш ^ {\ прайм}}$${\ displaystyle P}$${\ Displaystyle V ^ {*}}$

${\ displaystyle \ rightsquigarrow \ ;: = \; \ {(и \ circ R \ circ v, u \ circ Q \ circ v) | (R, Q) \ in P, u, v \ in V ^ {*} \}}$,

где здесь обозначает в конкатенации слов. ${\ displaystyle \ circ}$

Если есть последовательность слов , в которых это верно , что для любого натурального числа с словом в проходах над ( ), то , что представлено на могут быть получены в шагах от . Такая последовательность слов называется производной или расчет по в длину . Кроме того, в средствах выводима , если существует, по крайней мере , один такой , что она может быть получена в стадии из . Если in может быть получено, это обозначается обозначением . Это дополнительно определено , что для каждого слова , что есть, так что соотношение рефлексивно-транзитивное огибающей отношения . ${\ displaystyle w_ {0}, w_ {1}, \ ldots, w_ {n} \ in V ^ {\ ast}}$${\ displaystyle i}$${\ Displaystyle 0 \ Leq я <п}$${\ displaystyle w_ {i}}$${\ displaystyle w_ {я + 1}}$${\ Displaystyle ш_ {я} \ rightsquigarrow _ {G} ш_ {я + 1}}$${\ displaystyle w_ {n}}$${\ displaystyle n}$${\ displaystyle w_ {0}}$${\ displaystyle w_ {0} \ rightsquigarrow _ {G} ^ {n} w_ {n}}$${\ displaystyle w_ {0}, w_ {1}, \ ldots, w_ {n}}$${\ displaystyle w_ {0}}$${\ displaystyle w_ {n}}$${\ displaystyle n}$${\ displaystyle w}$${\ Displaystyle ш ^ {\ прайм}}$${\ Displaystyle п \ в \ mathbb {N} _ {0}}$${\ Displaystyle ш ^ {\ прайм}}$${\ displaystyle n}$${\ displaystyle w}$${\ displaystyle w}$${\ Displaystyle ш ^ {\ прайм}}$${\ displaystyle w \ rightsquigarrow _ {G} ^ {\ ast} w ^ {\ prime}}$${\ Displaystyle ш \ в V ^ {\ ast}}$${\ displaystyle w \ rightsquigarrow _ {G} ^ {\ ast} w}$${\ displaystyle \ rightsquigarrow _ {G} ^ {\ ast}}$${\ displaystyle \ rightsquigarrow _ {G}}$

Теперь формальный язык, порожденный грамматикой, - это язык, который состоит из всех слов, которые, с одной стороны, состоят только из терминальных символов, а с другой стороны, могут быть получены из начального символа с конечным числом шагов: ${\ displaystyle G}$${\ Displaystyle L (G)}$

${\ displaystyle L \ left (G \ right): = \ left \ {w \ in T ^ {*} | S \ rightsquigarrow _ {G} ^ {*} w \ right \}}$

Не имеет значения, в каком порядке производственные правила применяются к производным словам и есть ли несколько вариантов получения слова из . Два грамматик и являются эквивалентными , если и только если языки генерируются путем и равны: ${\ displaystyle w}$${\ displaystyle S}$${\ displaystyle G_ {1}}$${\ displaystyle G_ {2}}$${\ displaystyle G_ {1}}$${\ displaystyle G_ {2}}$

${\ displaystyle G_ {1} \ mathrm {\ is \ {\ ddot {a}} эквивалентно \} G_ {2}: \ Longleftrightarrow L (G_ {1}) = L (G_ {2})}$

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

Примеры

${\ displaystyle G_ {1}}$быть грамматикой с терминальными символами , нетерминальными символами , начальным символом и с правилами ${\ Displaystyle \ {а, б \}}$${\ displaystyle \ {S, A, B \}}$${\ displaystyle S}$

${\ displaystyle {\ begin {matrix} S & \ to & ABS & \, (1) \\ S & \ to & \ varepsilon & \, (2) \\ BA & \ to & AB & \, (3) \\ BS & \ к & b & \, (4) \\ Bb & \ к & bb & \, (5) \\ Ab & \ к & ab & \, (6) \\ Aa & \ к & aa & \, (7) \ end {matrix}}}$

Вот пустое слово , которое слово длины 0. Эта грамматика определяет язык всех слов в форме с . Таким образом, из - за следующие выводы, слов , и элементы языка , описанных с помощью : ${\ Displaystyle \ varepsilon}$${\ displaystyle G_ {1}}$${\ Displaystyle а ^ {п} Ь ^ {п}}$${\ Displaystyle п \ в \ mathbb {N} _ {0}}$${\ Displaystyle \ varepsilon}$${\ displaystyle from}$${\ displaystyle aabb}$${\ displaystyle G_ {1}}$

• ${\ Displaystyle S \ rightsquigarrow \ varepsilon}$, используя правило (2),
• ${\ displaystyle S \ rightsquigarrow ABS \ rightsquigarrow Ab \ rightsquigarrow ab}$, посредством правил (1), (4) и (6),
• ${\ displaystyle S \ rightsquigarrow ABS \ rightsquigarrow ABABS \ rightsquigarrow ABAb \ rightsquigarrow AABb \ rightsquigarrow AAbb \ rightsquigarrow Aabb \ rightsquigarrow aabb}$, с помощью правил (1), (1), (4), (3), (5), (6) и (7).

Но есть и другие способы получить это слово от . ${\ displaystyle aabb}$${\ displaystyle S}$

Еще одна грамматика, описывающая тот же язык, - это контекстно-свободная грамматика со следующими правилами: ${\ displaystyle G_ {2}}$${\ displaystyle {\ begin {matrix} S & \ to & aSb \ | \ \ varepsilon \ end {matrix}}}$

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

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

Грамматики относятся к классам, которые характеризуются сходством. Самая известная классификация была описана Ноамом Хомским и Марселем Шютценбергером с использованием иерархии Хомского .

Иерархия Хомского

Иерархия Хомского делит на классы грамматик от типа 0 до 3 -го типа в зависимости от типа правил производства:

• Грамматики типа 0: грамматики со структурой фраз - это неограниченные формальные грамматики.
• Грамматики типа 1: контекстно-зависимые грамматики могут состоять только из правил, в которых ровно один нетерминальный символ заменяется строкой символов. Этот символ также может быть окружен другими символами в левой части правила, которые указывают контекст, в котором должна происходить замена.
• Грамматики типа 2: в контекстно-свободных грамматиках , с другой стороны, в левой части правил может быть только один нетерминальный символ. Затем символ можно заменить независимо от контекста.
• Грамматики типа 3: в случае обычных грамматик левые части правил также содержат ровно один нетерминальный символ. В лево-регулярных грамматиках правая часть правила может состоять не более чем из одного нетерминального символа, за которым следует не более одного конечного символа (например, ). С другой стороны, в довольно регулярных грамматиках правая часть максимума терминального символа может существовать, самая большая часть следует за нетерминальным (Пример:) .${\ displaystyle X \ to Ya}$${\ displaystyle X \ to aY}$

Связанные языковые классы уменьшаются в размерах. Существуют следующие отношения реального включения :

Для классов языка по типу с следующим: . ${\ displaystyle L_ {n}}$${\ displaystyle n}$${\ Displaystyle п \ в \ {0,1,2,3 \}}$${\ displaystyle L_ {3} \ subset L_ {2} \ subset L_ {1} \ subset L_ {0}}$

Другие языковые курсы

Помимо иерархии Хомского, были установлены другие классы грамматик:

• Монотонные грамматики описывают тот же языковой класс, что и контекстно-зависимые грамматики. Все более контекстно-зависимые грамматики , описывающие подкласс контекстно-зависимого языкового класса , несколько строже .
• Детерминированные контекстно-свободные грамматики описывают детерминированные контекстно-свободные языки . Они также описываются грамматиками LR (k) , которые важны для построения компиляторов. Другие известные грамматик в строительстве компилятор являются LL (K) грамматик и LF (к) грамматик .

Смотри тоже

• Грамматика графа
• Форма Бэкуса-Наура и расширенная форма Бэкуса-Наура
• Теория синтаксиса (формальных) грамматик в лингвистике
• Коммуникационная грамматическая система

литература

• Катрин Эрк, Лутц Приезе: теоретическая информатика. Всестороннее введение . 2-е расширенное издание. Springer-Verlag, Berlin et al.2002, ISBN 3-540-42624-8 , стр. 53-61 . 

веб ссылки

• Веб-сайт грамматики

Индивидуальные доказательства

1. ↑ Питер Бахманн: Основы теоретической информатики . Котбус 2001, стр. 47 ( PDF [доступ 12 февраля 2011 г.] конспект лекций). 
2. ↑ Хотя значение и / в данном случае ясно, необходимо уточнить, что имеется в виду (а также часто используемое ), проверяя контекст; где одночетверная грамматика, чтобы не уйти.${\ displaystyle T, N}$${\ displaystyle \ epsilon}$${\ displaystyle \ lambda}$${\ displaystyle V}$${\ displaystyle \ Sigma}$
3. ↑ ^б Klaus Reinhardt: Приоритет платежных машин и синхронизация языков полугусеничных ( сувенир в оригинале от 17 января 2018 года в Internet Archive ) Info: архив ссылка автоматически вставляется и не проверяются. Проверьте исходную и архивную ссылку в соответствии с инструкциями, а затем удалите это уведомление. , Факультет компьютерных наук Штутгартского университета; Докторская диссертация 1994 г. Здесь дословно указана грамматическая четверка , что означает в выбранном здесь обозначении . @ 1@ 2Шаблон: Webachiv / IABot / users.informatik.uni-halle.de${\ displaystyle (V, \ Sigma, P, S)}$${\ displaystyle (N, T, P, S)}$