Главная страница Случайная лекция
Мы поможем в написании ваших работ!
Порталы:
БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика
Мы поможем в написании ваших работ!
Тема 9. Классификация грамматик
План лекции:
1. Классификация грамматик
2. Грамматический разбор
1. Классификация грамматик
Правила порождающих грамматик позволяют осуществлять преобразования строк.
Ограничения же на виды правил позволяют выделить классы грамматик. Рассмотрим классификацию, которую предложил Н. Хомский.
Грамматики типа 0 - это грамматики, на правила вывода которых нет ограничений.
Грамматики типа 1, или контекcтные грамматики -это грамматики, все правила которых имеют следующий вид: хАу → хϕу, где A Î VN, x, y, ϕÎ(VN ÈVT)+.
Грамматики типа 2 - это бесконтекстные, или контекстно-свободные грамматики (КС-грамматики). Правила вывода для этих грамматик имеют следующий вид: А → ϕ, где А Î VN, ϕ Î (VN ∪ VT)*.
Грамматики типа 3 - это автоматные грамматики, которые делятся на два типа:
а) леволинейные (леворекурсивные), правила вывода для которых имеют следующий вид: А → Аа | a, где А Î VN;
б) праволинейные (праворекурсивные), правила вывода для которых имеют следующий вид: А → Aа | a.
Язык L называется языком типа i, если существует грамматика типа i, порождающая язык L.
4.3.1. Методика решения задач
Пример 1. Дана порождающая грамматика G = (VT, VN, Р, S), в которой VT = {a, d, е}, VN= {В, С, S}, Р = {S → аВ, В → Cd | dC, С → е}. Выписать терминальные цепочки, порожденные данной грамматикой, и определить длину их вывода.
Решение. Получим следующие терминальные цепочки:
S → аВ → aCd → aed,
S → аВ → adC → ade,
длина вывода которых равна 3.
Пример 2. Дана грамматика G = (VT, VN, Р, C), в которой VT = {a, b, c, d, е}, VN = {A, В,
С, D, E}, Р = {A → ed, В → Ab, С → Bc, С → dD, D → Ae, E → bc}. Определить, принадлежит ли языку L(G) цепочка eadabcb.
Решение. Выведем возможные терминальные цепочки из аксиомы с помощью заданных
правил вывода:
С → Bc → Abc → edbc,
С → dD → dAe → dede.
Так как первые же терминальные символы полученных цепочек не совпадают с заданной, можно сделать вывод о том, что цепочка eadabcb не принадлежит языку L(G).
Пример 3. Построить КС-грамматику (грамматику типа 2), порождающую цепочки из 0 и 1 с одинаковым числом тех и других символов.
Решение. Определим множества, задающие грамматику: VT = {0, 1}; VN = {S}; Р ={S → 0S1, S → 1S0, S → ε, S → S01, S → S10}.
Пример 4. Описать язык, порождаемый следующими правилами: S → bSS | а.
Решение. Построим несколько терминальных цепочек, применяя заданные правила вывода:
S → a;
S → bSS → baa;
S → bSS → bbSSS → bbaaa;
S → bSS → bbSSbSS → bbaabaa;
S → bSS → bbSSbSS → bbbSSbSSbbSSbSS → ...
Из полученных цепочек видно, что:
а) цепочки всегда начинаются с терминала b, кроме аксиомы, и заканчиваются терминалом а;
б) количество терминалов а в любой цепочке всегда на 1 больше, чем b.
Исходя из этих выводов, определим язык, порождаемый заданными правилами, следующим образом:
L(G) = {α | α Î {a, b}*}, |a| = |b| + 1, причем цепочки начинаются с терминала b и
заканчиваются терминалом а.
2. Грамматический разбор
В КС-грамматике может быть несколько выводов, эквивалентных в том смысле, что в них применяются одни и те же правила к одинаковым в промежуточном выводе цепочкам, но в различном порядке. Например, для грамматики G с правилами вывода S → ScS|b|a возможны следующие эквивалентные выводы терминальной цепочки acb: S → ScS → Scb → acb и S → ScS → acS → acb.
Деревом вывода цепочки х в КС-грамматике G = (VT, VN, Р, S) называется упорядоченное дерево, каждая вершина которого помечена символом из множества V È VN È {ε} так, что каждому правилу А → b1b2b3 ... bk, использующемуся при выводе цепочки х, в дереве вывода соответствует поддерево с корнем А и прямыми потомками b1, b2, b3, ..., bk, которое приведено на рисунке:
A
b1 b2 … bk
В силу того, что цепочка х Î L(G) выводится из аксиомы S, корнем вывода всегда
является аксиома. Внутренние узлы вывода соответствуют нетерминальным символам.
Концевые вершины дерева вывода - листья - это вершины, не имеющие потомков. Такие вершины соответствуют либо терминалам, либо пустым символам (ε) при условии, что среди правил грамматики имеются правила с пустой правой частью. При чтении слева направо концевые вершины дерева вывода образуют цепочку х.
Дерево вывода часто называют деревом грамматического разбора, или
синтаксическим деревом, а процесс построения дерева вывода - грамматическим разбором (синтаксическим анализом). Одной цепочке языка может соответствовать больше одного дерева, так как эта цепочка может иметь разные выводы, порождающие разные деревья.
КС-грамматика G == (VT, VN, Р, S) называется неоднозначной (неопределенной), если
существует цепочка х Î L(G), имеющая два или более дерева вывода.
Рассмотрим пример.
Пусть даны две КС-грамматики:
G1 = (VT, VN, Р1, S), VN = {S},
P1={S → S+S | S | S⋅S | (S) | a};
G2= (VT, VN, Р2, S), VN = {S, A, B},
P2 = {S → S + A | A | A, A → A⋅B | A / B | B, B → a| (S)}, содержащие в множестве
терминальных символов знаки операций, круглые скобки и символ а. Определить, являютсяли грамматики однозначными. Если какая-либо из них неоднозначна, привести пример цепочки, для которой существует два различных дерева вывода.
Решение: Грамматика G1 является неоднозначной, так как она имеет правила с правой
частью, содержащей два вхождения нетерминала S и знак арифметической операции.
Построим два дерева вывода для простейшей цепочки а + а + а:
Грамматика G2 является однозначной, так как не содержит правил с двойным вхождением нетерминального символа. Так, для цепочки а + а + а она имеет только одно дерево вывода.
В некоторых случаях неоднозначность в грамматиках может устраняться путем эквивалентных преобразований. Однако в общем случае проблема устранения неоднозначности неразрешима. На практике от неоднозначности избавляются путем задания словесных ограничений, называемых контекстными условиями языка, которые включаются в его семантику.
Различают две стратегии грамматического разбора: восходящую и нисходящую, которые соответствуют способу построения синтаксических деревьев. При нисходящей стратегии разбора дерево строится от корня аксиомы вниз, к терминальным вершинам. Главной задачей при нисходящем разборе является выбор того правила, которое следует применить на рассматриваемом шаге. При восходящем разборе дерево строится от терминальных вершин к корню дерева (аксиоме).
Преобразование цепочки, обратное порождению, называется редукцией.
| <== предыдущая страница | | | следующая страница ==> |
| Общие сведения. В последние три десятилетия появилось большое количество работ по общей теории языков и грамматик | | | Тема 10. Преобразования КС-грамматик |
Дата добавления: 2015-07-26; просмотров: 182; Нарушение авторских прав
Мы поможем в написании ваших работ!