ПРАВОЛИНЕЙНЫЕ ГРАММАТИКИ Обобщение автоматных грамматик. Порождающие правила в виде: A ωB или A ω где A, В – не терминалы, ω – терминальная цепочка, допустимо: ω = λ. Пример праволинейной грамматики Грамматика: G 5 (L) = {, N, S, P} = {a, b}, N = {S, T, C}, S = {S}, P = {S aaT, T aT, T bbC, T C, C a}. Процесс порождения: S => aaT => aaC => aaa, S => aaT => aabbC => aabba, S => aaT => aaaT => aaaC => aaaa, S => aaT => aaaT => aaabbC => aabba,...

Преобразование праволинейной грамматики к автоматной грамматике 1. Пусть в грамматике имеется правило: A a 1 a 2...a n B, (*) где n > 1. Добавим в грамматику новые не терминалы: B 1, B 2,..., B n-1 И вместо правила (*) добавим правила: A a 1 B 1, B 1 a 2 B 2,..., B n-1 a n B 2. Пусть в грамматике имеется правило: A B, (**) а также правила: B β 1, B β 2,..., B β m, Вместо правила (**) добавим правила: A β 1, A β 2,..., A β m

3. Пусть в грамматике имеется правило: A λ, (***) а также правила: B 1 ω 1 A, B 2 ω 2 A,..., B k ω k A, Вместо правила (***) добавим правила: B 1 ω 1, B 2 ω 2,..., B k ω k, 4. Пусть в грамматике имеется правило: S λ, (****) где S – начальный нетерминал. Это порождающее правило оставляем без изменения. ____________________________________________________________________________________________________________ В результате таких преобразований язык не изменится. Если в языке не было правила вида (****) и оно не появилось после всех преобразований, то получившаяся грамматика будет автоматной. Следствие: множество праволинейных языков почти совпадает с множеством автоматных языков.

Регулярные множества Регулярные множества – это следующие множества цепочек символов из некоторого алфавита Σ: Пустое множество Ø. Множество из пустой цепочки {λ}. Множество из любого символа {a} алфавита Σ. Множество всех возможных цепочек вида αβ (конкатенация); α Є A, β Є B, где A, B – регулярные множества. Объединение множеств A U B, где A, B – регулярные множества. Объединение множеств всех возможных цепочек вида λ, α 1, α 1 α 2, α 1 α 2 α 3,... и т.д., где все α 1, α 2, α 3,... принадлежат регулярному множеству A (A* – транзитивное замыкание A ).

Регулярные выражения Регулярное выражение – это шаблон для задания регулярного множества цепочек символов из некоторого алфавита Σ. Кроме символов алфавита Σ в регулярное выражение могут входить вспомогательные метасимволы: Ø (пустое множество), λ (пустая строка), скобки { }, скобки { }*, вертикальная черта |. Пустое множество обозначается знаком Ø. Пустая цепочка обозначается знаком λ. Символ алфавита Σ обозначает себя сам. Если α и β – оба регулярные выражения, то запись вида αβ – регулярное выражение, обозначающее конкатенацию цепочек из α и β ; Если α и β – оба регулярные выражения, то запись вида α | β – регулярное выражение, обозначающее объединение множеств цепочек из α и β ; Если α – регулярное выражения, то запись вида {α} – то же самое регулярное выражение, рассматриваемое, как единое целое; Если α – регулярное выражения, то запись вида {α}* – регулярное выражение, обозначающее объединение множеств цепочек из: λ, α, αα, ααα,... и т.д., ({α}* – транзитивное замыкание α).

Примеры 1. Регулярное выражение: {λ|+|–}{0|1|2|3|4|5|6|7|8|9}{0|1|2|3|4|5|6|7|8|9}* задает запись целого числа без знака или со знаком «+» или «–». ____________________________________________________________________________________________________________________________________ Для краткости вместо явного перечисления цифр или букв через символ «|», будем использовать многоточие. ____________________________________________________________________________________________________________________________________ 2. Регулярное выражение: {0|1|... |9}{0|1|... |9}*.{0|1|... |9}{0|1|... |9}* задает запись беззнакового десятичного числа с дробной частью. ____________________________________________________________________________________________________________________________________ 3. Регулярное выражение: {A|B|...|Z}{0|1|... |9|A|B|...|Z}* задает запись идентификатора (имени) для большинства языков программирования.

Преобразование регулярного выражения к праволинейной грамматике 1. Пусть задано регулярное выражение α. Запишем прообраз порождающего правила в виде: S α, где S – начальный нетерминал. 2. Пусть прообраз порождающего правила имеет вид: A aβ, где A – некоторый нетерминал, a – терминал. Заменим это правило на следующие: A aB, B β, где B – новый нетерминал. 3. Пусть прообраз порождающего правила имеет вид: A {α 1 |α 2 }β, где A – некоторый нетерминал. Заменим это правило на следующие: A α 1 β, A α 2 β. 4. Пусть прообраз порождающего правила имеет вид: A {α}*β, где A – некоторый нетерминал. Заменим это правило на следующие: A β, A αA. Преобразования проводятся до тех пор, пока все полученные порождающие правила не станут праволинейными.