Информатика и выч. техника \ Теория языков программирования и методы трансляции

Контекстно-свободные языки. Свойства и распознаватели КС-языков. Преобразование КС-грамматик. КС-грамматики в нормальной форме, страница 15

Процедура Proc_A(str,k);

 Выбор str[k] из:

 a: Rule(3);

    вернуть k+1;

 b: Rule(4);

    вернуть Proc_A(str,k+1);

 c: Rule(5);

    вернуть Proc_C(str,k+1);

 иначе вернуть 0;

Процедура Proc_B(str,k);

 Выбор str[k] из:

 a: Rule(7);

    вернуть Proc_B(str,k+1);

 b: Rule(6);

    вернуть k+1;

 c: Rule(8);

    вернуть Proc_C(str,k+1);

 иначе вернуть 0;

Процедура Proc_C(str,k);

  Rule(9);

  i:=Proc_A(str,k);

  если i=0 вернуть 0;

  если str[i]≠’a’ вернуть 0;

  i:=Proc_B(str,i+1);

  если i=0 вернуть 0;

  если str[i]≠’b’ вернуть 0;

  вернуть i+1;

Пусть цепочка a = ‘acbaabb’.

Разбор начинается с вызова Proc_S(a,1). Дальнейшие вызовы и вывод номеров использованных правил будут происходить в следующем порядке:

Proc_S(a,1) (символ ‘a’, вывод 1) Þ Proc_A(a,2) (‘c’, вывод 5) Þ Proc_C(a,3) (вывод 9) Þ Proc_A(a,3) (‘b’, вывод 4) Þ Proc_A(a,4) (‘a’, вывод 3, в Proc_C верн. i=5) Þ Proc_B(a,6) (‘b’, вывод 6, в Proc_C верн. i=7) Þ вернули 8=n+1 Þ stop(+). Правила вывода 1, 5, 9, 4, 3, 6.

S Þ(1) aA Þ(5) acC Þ(9) acAaBb Þ(4) acbAaBb Þ(3) acbaaBb Þ(6) acbaabb.

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

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

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

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

3.5.1.2  Разбор для LL(k)-грамматик

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

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

Существуют LL(1), LL(2), LL(3), … грамматики. Все они в совокупности образуют класс LL-грамматик. В этом обозначении (LL) первая L означает, что входная цепочка считывается в направлении слева направо, а вторая L – что выполняется левосторонний разбор. Число k показывает, сколько символов справа от считывающей головки нужно рассмотреть для однозначного выбора альтернативы.

Алгоритм разбора входных цепочек для LL(k)-грамматик называется k-предсказывающим алгоритмом. 

Свойства LL(k)-грамматик.

§  Всякая LL(k)-грамматика для любого k>0 является однозначной.

§  Существует алгоритм проверки, является ли произвольная КС-грамматика LL(k)-грамматикой для строго определённого числа k.

§  Всякая грамматика, допускающая разбор по методу рекурсивного спуска, является LL(1)-грамматикой. Обратное не справедливо.

Проблемы LL(k)-грамматик:

§  Не существует алгоритма, позволяющего проверить, является ли произвольная КС-грамматика LL(k)-грамматикой для любого числа k.

§  Не существует алгоритма преобразования произвольной КС-грамматики к виду LL(k)-грамматики для некоторого k (либо доказывающего, что такое преобразование невозможно).

Для LL(k)-грамматик для любого k>1 не обязательно все k символов должны находиться в одной цепочке в правой части правила вывода. Если это так, то такая грамматика называется сильно LL(k)-грамматикой. Но обычно эти символы находятся в правых частях разных правил.

Особенности правил грамматики класса LL(1):

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

2)  В отличие от метода рекурсивного спуска допускаются правила вида A®Ba и пустые правила.

3)  Правила грамматики не должны содержать левой рекурсии.

LL-грамматики позволяют построить распознаватели с линейной трудоемкостью.

Для построения распознавателей LL(k)-грамматик используются два специальных множества, определяемых следующим образом:

§  FIRST(k,a) – множество терминальных цепочек, выводимых из aÎ(VTÈVN)* и укороченных до k символов. Формально FIRST(k,a) ={wÎVT*½½w½£ k и aÞ*w или aÞ*wx, xÎ(VTÈVN)*}, aÎ(VTÈVN)*, k>0.

§  FOLLOW(k,A) – множество укороченных до k символов терминальных цепочек, которые могут непосредственно следовать за AÎVN в цепочках вывода. Формально: для AÎVN и k > 0 FOLLOW(k,A) ={wÎVT*½SÞ*aAg и wÎFIRST(k,g), aÎVT*}.

Очевидно, что, если имеется цепочка терминальных символов aÎVT*, то FIRST(k,a) – это первые k символов этой цепочки.

Доказано, что грамматика G(VT,VN,P,S) является LL(k)-грамматикой тогда и только тогда, когда выполняется условие: "(A®b)ÎR и "(A®g)ÎR, b¹g  FIRST(k,bw)ÇFIRST(k,gw)=Æ для всех цепочек w таких, что SÞ*aAw.

Скачать файл