Лекция 10 Левокурсивные и правокурсивные грамматики Определение 10. 1




НазваниеЛекция 10 Левокурсивные и правокурсивные грамматики Определение 10. 1
Дата конвертации13.02.2013
Размер445 b.
ТипЛекция


Лекция 10

  • Левокурсивные и правокурсивные грамматики


Определение 10.1

  • Некоторый нетерминальный символ А контекстно-свободной грамматики G = (N, , P, S) называется рекурсивным, если существует вывод А + А для некоторых  и . Если при этом  = , то А называется леворекурсивным. Аналогично, если  = , то А называется праворекурсивным. Грамматика, имеющая хотя бы один леворекурсивный нетерминальный символ, называется леворекурсивной. Грамматика, в которой все нетерминальные символы, кроме, быть может, начального символа, рекурсивные, называется рекурсивной.



Заметим, что для рекурсивных грамматик в выводе А + А всегда либо   , либо   . Если  =  и  = , то грамматика G является циклической грамматикой.

  • Заметим, что для рекурсивных грамматик в выводе А + А всегда либо   , либо   . Если  =  и  = , то грамматика G является циклической грамматикой.

  • Пример 10.1. Примером праворекурсивной грамматики является грамматика со следующей схемой:

  • <число>  <цифра>

  • <число>  <цифра><число>

  • <цифра>  1

  • <цифра>  0

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



Пример 10.2. Тот же самый язык, что и в примере 10.1. порождает леворекурсивная грамматика со следующей схемой:

  • Пример 10.2. Тот же самый язык, что и в примере 10.1. порождает леворекурсивная грамматика со следующей схемой:

  • <число>  <цифра>

  • <число>  <число><цифра>

  • <цифра>  1

  • <цифра>  0



Пример 10.3. Примером леворекурсивной грамматики является грамматика со следующей схемой:

  • Пример 10.3. Примером леворекурсивной грамматики является грамматика со следующей схемой:

  • <идентификатор>  <буква>

  • <идентификатор>  <идентификатор><буква>

  • <идентификатор>  <идентификатор><цифра>

  • <буква>  А

  • <цифра>  1

  • <цифра>  0

  • Данная грамматика порождает множество идентификаторов, начинающихся с буквы А.



Пример 10.4. Тот же самый язык, что и в примере 10.3. порождает праворекурсивная грамматика со следующей схемой:

  • Пример 10.4. Тот же самый язык, что и в примере 10.3. порождает праворекурсивная грамматика со следующей схемой:

  • <идентификатор>  <буква>

  • <идентификатор>  <буква><символ идентификатора>

  • <символ идентификатора><буква>

  • <символ идентификатора>  <буква> <символ идентификатора>

  • <символ идентификатора><цифра>

  • <символ идентификатора>  <цифра> <символ идентификатора>

  • <буква>  А

  • <цифра>  1

  • <цифра>  0



Лемма 10.1

  • Пусть G = (N, , P, S) – КС-грамматика, в которой для некоторого нетерминального символа А все А-правила имеют вид

  • А  A1 | A2 | … | Am | 1 | 2 | … | n |

  • причем ни одна из цепочек i не начинается с А.

  • Пусть G'=(N{A'}, , P', S), где A' – новый нетерминал, а P' получается из P заменой этих А-правил следующими правилами

  • А  1 | 2 | … | n | 1A' | 2A' | … | nA' |

  • А'  1 | 2 | … | m | 1A' | 2A' | … | mA'

  • Тогда L(G') = L(G).



Доказательство. Цепочки, которые можно получить в грамматике G из нетерминала А применением А-правил лишь к самому левому нетерминалу, образуют регулярное множество

  • Доказательство. Цепочки, которые можно получить в грамматике G из нетерминала А применением А-правил лишь к самому левому нетерминалу, образуют регулярное множество

  • (1 + 2 + … + n )( 1 + 2 + … + m )*

  • Это в точности те цепочки, которые можно получить в грамматике G' из А с помощью правых выводов, применив один раз А-правило и несколько раз А'-правила (в результате вывод уже не будет левым). Все шаги вывода, на которых не используются А-правила, можно непосредственно сделать и в грамматике G', так как не А-правила в обеих грамматиках одни и те же. Отсюда можно заключить, что L(G)  L(G').



Обратное включение доказывается аналогично. В грамматике G' берется правый вывод и рассматриваются последовательности шагов, состоящие из одного применения А-правила и нескольких применений А'-правил. Таким образом, L(G') = L(G).

  • Обратное включение доказывается аналогично. В грамматике G' берется правый вывод и рассматриваются последовательности шагов, состоящие из одного применения А-правила и нескольких применений А'-правил. Таким образом, L(G') = L(G).

  • Грамматика примера 10.4. получена из грамматики примера 10.3. с использованием преобразования леммы 10.1.



Лемма 10.2

  • Пусть G = (N, , P, S) – КС-грамматика, в которой для некоторого нетерминального символа А все А-правила имеют вид

  • А  A1 | A2 | … | Am | 1 | 2 | … | m

  • причем ни одна из цепочек i не начинается с А.

  • Пусть G'=(N, , P', S), где P' получается из P заменой этих А-правил следующими правилами

  • А  1 | 2 | … | m | 1A | 2A | … | mA

  • Тогда L(G') = L(G).

  • Грамматика примера 10.1. получена из грамматики примера 10.2. с использованием преобразования леммы 10.2.



На рисунке 10.1. показано, как действуют преобразования на дерево вывода

  • A

  • A i1

  • ... i2

  • A

  • A ik



Пример 10.5. Пусть G0 – обычная грамматика с правилами

  • Пример 10.5. Пусть G0 – обычная грамматика с правилами

  • E  E+T

  • E  T

  • T  T*F

  • T  F

  • F  (E)

  • F  a

  • Эквивалентная ей грамматика G`



E  T

  • E  T

  • E  TE'

  • E'  +T

  • E'  +TE'

  • T  F

  • T  FT '

  • T '  *F

  • T '  *FT '

  • F  (E)

  • F  a

  • Рассмотрим теперь, как преобразовать приведенную леворекурсивную КС-грамматику к КС-грамматике, не имеющей левой рекурсии.



Алгоритм 10.2

  • Устранение левой рекурсии.

  • Вход: Приведенная КС-грамматика G=(N,,P,S)

  • Выход: Эквивалентная КС-грамматика G` без левой рекурсии.

  • Метод.

  • Пусть N = {A1,…, An}, т.е. все нетерминальные символы грамматики упорядочены некоторым произвольным образом. Преобразуем G так, чтобы в правиле Ai   цепочка  начиналась либо с терминала, либо с такого Aj, что ji.

  • 1) Положим i=1.



2) Пусть множество Ai – правил – это Ai  Ai | … | Aim | 1 | … | p , где ни одна из цепочек j не начинается с Ak, если k  i (если это не выполнено, можно ввести новый нетерминальный символ, заменить первый символ правила этим символом и добавить дополнительное правило в грамматику).

  • 2) Пусть множество Ai – правил – это Ai  Ai | … | Aim | 1 | … | p , где ни одна из цепочек j не начинается с Ak, если k  i (если это не выполнено, можно ввести новый нетерминальный символ, заменить первый символ правила этим символом и добавить дополнительное правило в грамматику).

  • Заменим Ai–правила правилами:

  • Ai  1 | … | p | 1Ai' | … | pAi'

  • Ai'  1 | … | m | 1Ai' | … | mAi'

  • где A'i — новый нетерминал. Правые части всех Ai-правил начинаются теперь с терминала или с Ak для некоторого k > i.

  • 3) Если i=n, полученную грамматику G' считать результатом и остановиться. В противном случае положить i=i+1 и j=1.



4) Заменить каждое правило вида Ai  Aj правилами Ai  1|…|m, полученными в результате замены Aj правыми частями всех Aj-правил вида

  • 4) Заменить каждое правило вида Ai  Aj правилами Ai  1|…|m, полученными в результате замены Aj правыми частями всех Aj-правил вида

  • Aj  1|…|m. Так как правая часть каждого Aj-правила начинается уже с терминала или с Ak для k > j, то и правая часть каждого Ai-правила будет теперь обладать этим свойством.

  • 5) Если j=i–1, перейти к шагу (2). В противном случае положить j=j+1 и перейти к шагу (4).



Теорема 10.1

  • Для каждого КС-языка существует порождающая его не леворекурсивная грамматика.

  • Доказательство есть следствие приведенных в данном разделе преобразований.

  • Пример 10.5. Пусть G есть КС-грамматика с правилами

  • ABCa

  • BCAAb

  • CABCCa



Положим A1=A, A2=B и A3=C

  • Положим A1=A, A2=B и A3=C

  • После каждого применения шага (2) или (4) алгоритма получаются следующие грамматики (указываем только новые правила).

  • Шаг (2) для i=1: G не меняется

  • Шаг (4) для i=2, j=1: BCABCbab

  • Шаг (2) для i=2: BCAabCABabB

  • BCb BCb

  • Шаг (4) для i=3, j=1: CBCBaBCCa

  • Шаг (4) для i=3, j=2: CCACBabCB CABCBab BCBaBCCa

  • Шаг (2) для i=3: CabCBab BCBaB a abCBCab BCB CaB CaC

  • CACB CABCB CCCACB ABCB C



Задание 13

  • Привести пример лево-рекурсивной грамматики (рекурсия не является непосредственной), устранить в грамматике левую рекурсию.



Похожие:

Лекция 10 Левокурсивные и правокурсивные грамматики Определение 10. 1 iconЛекция 5 Классификация грамматик по Хомскому Линейные грамматики Определение 1
Грамматика g = (N, , P, S) называется линейной, если все ее правила имеют вид  либо , где   N,  N,   *,   *
Лекция 10 Левокурсивные и правокурсивные грамматики Определение 10. 1 iconЛекция 9 Отношения, графы Определения Определение. Пусть а и b объекты. Определение. Пусть а и b объекты. Через ( а, b )
Определение. Отношение {(b, а) | (а, b)  R} называется обратным к отношению r и часто обозначается через r-1
Лекция 10 Левокурсивные и правокурсивные грамматики Определение 10. 1 iconЛекция 13 Неоднозначные грамматики. Способы устранения неоднозначности
Если грамматика используется для определения языка программирования, желательно, чтобы она была однозначной. В противном случае программист...
Лекция 10 Левокурсивные и правокурсивные грамматики Определение 10. 1 iconЛекция 1 Определение функции двух переменных

Лекция 10 Левокурсивные и правокурсивные грамматики Определение 10. 1 iconЛекция 4 Формальные грамматики
При этом "задание" может осуществляться по-разному, оно означает либо возможность для каждой цепочки данного языка подобрать такой...
Лекция 10 Левокурсивные и правокурсивные грамматики Определение 10. 1 iconЛекция 9 9 апреля 2002 г. Композиты Текстуры Композирование (Определение) Compositing

Лекция 10 Левокурсивные и правокурсивные грамматики Определение 10. 1 iconМорфология. Словообразование лекция 15 Определение морфологии
Пользовалась особым вниманием в трудах американских структуралистов (Л. Блумфилд, З. Хэррис)
Лекция 10 Левокурсивные и правокурсивные грамматики Определение 10. 1 iconЛекция 3 Непрерывность
Теперь переформулируем определение непрерывности в других терминах. Обозначим и назовем его приращением аргумента в точке
Лекция 10 Левокурсивные и правокурсивные грамматики Определение 10. 1 iconЛекция №14 Сетевые операционные системы. Виртуализация, кластеры, облачные сервисы
Это определение применимо к большинству современных операционных систем общего назначения
Лекция 10 Левокурсивные и правокурсивные грамматики Определение 10. 1 iconЛекция 5 План лекции
Определение Грубера (явная онтология есть явная спецификация концептуализации предметной области)
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница