Lectures_1-7 (1040445), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

Существуют системы с двунаправленными в ыводами .Основные достоинства продукционных систем-это простота представления знаний иорганизация логического вывода .Основным недостатком продукционных а.1стем является резкое замедление проведе­ния лоrичеасого вывода nри росте числа правил в базе знаний . При этом именно в а.1стемах,работающих в режиме реального времени , ключевую роль играет асорость обработки инфор­мации. Поэтому разработка математических моделей nредставления знаний, ускоряющих ра­боту продукционных систем, является в ажной, актуальной и практически значимой задачей.К недостаткам можно также отнести: сложность оценки целостного образа знаний ,не­ясность вз аимных отношений правил .Традиционно база знаний созда~тся предметным экспертом, но такой подход не всегдаможет гарантировать качество управления. Эта nроблема может быть устранена на основеиспользования нейросетевых методов и технологий , неч~ткой логики , технологий мягких вы­числений, а также в ведением физических и информационных ограниче ний в формализован­ное описание модел и объектов управления.ДополнительноОсновные понятия процессов компиляцииГрамматикойгдеG называется совокупность G = (N,Т, Р,N - множество нетерминальных символов алфавита ,Т- множество терминальных символов алфавита,S),Р - множество правил продукции,S - начальный символ грамматмки.При этомNnТ=0, NU Т =алфавит, S Е N - начальный символ грамматмки принад­лежит множеству нетерминальных символов, и Р = {И ~ х} (И Е N, Х Е N U Т).Продукция - это упорядоченная пара (И, х) , записываемая как И ~ х , где И - символ , ах цепочка (конечная).ПустьG - грамматика .Цепочка и непосредственно порождает цепочкусредственно выводима изсать и = хИу,wU),т .

е . и=>w, если дляw(илиwнепо-некоторых цепочек Х и у можно запи-= xuy, и И ~ и- правило грамматики .Говорят, что v порождает w (запись v =>+w), если существует последовательность выво-довЗаписьv => + w означает, что либо V => w , либо v=w.Цепочка Х является сентенциальной формой в грамматикеS =>если существует вывод•х. т.е.

сентенциальная форма - это любой промежуточный или конечный результатвывода изS - начального символаграмматикиЕсли Х - сентенциальная форма в грамматикелов, то цепочка хG.GиХсостоит только из терминальных симво-- это предложение в грамматике G.Языком в грамматикеG называется множество возможных предложений вG: L(G) = {xjS =>ПустьG,G - грамматика, а w=•х,х Еr+}.xuy - сентенциальная форма .Тогда и называется фразой сентенциальной формыwдля нетерминального символа И, ее-ли S => *хИу и И => +и и простой фразой, если S => *xUy и И = и.Основой всякой сентенциальной формы называется самая левая простая фраза .Каждая грамматика описывает (задает) некоторый язык, и каждый язык описывается (задает­ся , порождается) некоторой грамматикой .Смнта кс м ческме деревья.

Задачм разбора м в ыводаЗадачи анализа текстов на тех или иных языках достаточно наглядно демонстрируютсяс помощью синтаксических дерев ьев .Правила построения синтаксического дерева для произвольного предложения в некото­рой грамматике следующие :1) В качестве корневого узла строится узелS (где S - нii'lальный символ грамматики);2) В имеющемся дереве выб1.1рается узел И , для которого в Р имеется продукцияИ -+ а 1 ...ak(если такого узла нет, то построение завершено);З) К дереву добавляются узлы а 1...

akи связи (И, а 1 )...(И,ak). и процесс повто­ряется , начиная с п.2 .Для правильно организованной грамматики процесс построения должен завершитьсяили иметь возможность завершиться в таком состоянии , когда все концевые узлы связаны стерминальными символами . При этом просмотр концевых узлов слева дает предложениеграмм атики , а концев ые узлы в любой момент построения дерева образуют сентенциальнуюфор му .Процесс порождения предложений грамматики, основанный на описанном выше алго­ритме построения дерева называется выводом.Как правило , интересует получение не любого, а некоторого , вполне определенного,предложения . Дело в том , что исходные программы , поступающие на вход транслирующей си­стемы, являются совокупностями симв ольных цепочек. Для успешного осуществления процес­са компиляции необходимо:ответить на вопрос "принадлежит ли текст программы входному языку?•, т.е.

являетсяли исходная програм м а совокупностью предложений входного языка ;определить синтаксическую структуру программы.Очевидно, что решение этих задач требует построения синтаксического дерева . Самфакт построения такого дерева будет свидетельствовать о том , что исходная программа явля­ется синтаксически правильной (с позиций грамматики входного языка) .Практически используют д ве стратегии вывода :левы й вывод-на каждом шаге вывода произв одится развертывание самого лев огоконцевого узла (допускающего это);правый вывод-осуществляется путем замены самого правого концевого узла , не со­ответствующего терминальному символу, правой частью одного из пра вил .Если на каждом шаге производится свертка строки к одному нетерминальному символу-этот процесс называется редукцией .В зависимости от порядка развертки (свертки) основ в сентенциальных формах разли­чают левосторонние и правосторонние выводы или редукции .Понятие автоматной грамматики.В общем случае правила продукции Р КС-граммматикиU-+а,гдеU ЕN,aЕ А* =G = (N, Т, Р, S)имеют вид(N UT)*.Мноrообразие возможных конфиrураций цепочки а определяет •мощность " каждого•определения", а следовательно и "порождающую" силу грамматики.

В ряде частных случаевудается наложить ряд ограничений на структуру правых частей продукций и за счет этого по­лучить некоторые качественные свойства выводов (редукций) , которые значительно упрощаютзадачу анализа входных текстов .Одним из частных классов КС-грамматик являются автоматные или реrулярные грамма­тики (А-грамматики) . Алларат автоматных грамматик наиболее широко используется nри про­ектировании лексических анализаторов (сканеров). Объектом анализа блока лексическогоанализа являются лексемы , в качестве которых для языка программирования обычно высту­пают идентификаторы переменных, числовые константы , ключе вые слова .Все лексемы строятся из литер (символов) . Множество используемых в языке литер мо­жет быть разбито на ряд классовнапример, классы букв , цифр, разделителей. После п:ро­-чтения очередного символа анализируемой программы сканер осуществляет определениекласса, к которому она принадлежит.

Дальнейший анализ предполагает определение допу­стимости вхождения литеры данного класса в обрабатываемую (анализируемую) лексему . Та­кой анализ существенно упрощается , если синтаксис ле ксем определяется реrулярными вы­ражениями , т. е . описывается автоматной грамматикой .Конечным автоматом (КА) является пятеркой вида :КА= (К, Т,где КТМM,S,Z)- алфавит состоЯiий КА,- входной алфавит,- отображение декартова произведения множествК и Т (множества К Х Т) на мно­жество К, представляемое графом переходов КА или таблицей состояний,S - начальное состояние КА (SЕ К),Z - непустое множество конечных состояний (Zс К) .Есnи КС-грамматика является А-грамматикой , то алфавит сосrояний Калфавит Т= N , входной= Т. Конечный автомат, реализующего разбор предложений этой грамматики пу­тем выполнения процесса редукции , можно посrроить следующим образом.Есnи во множесrве правил продукции есть хотя бы одно правило видаU -+-а (где атерминальный символ) , то ввести дополнительный нетерминальный символ (например , Q),все правила указанного вида преобразовать вU -+ Qа .Изобразить множество вершин графа состояний, обозначив каждую вершину одним нетерми­нальным символом.

ВершинаQ соответсrвует начальному сосrоянию автомата, авершинаS- заключительному (S - начальный символ грамматики) .Для каждого правила продукцийU-+Vaпровести дугу от вершиныVк вершинеUи поме­тить ее символом а.В зависимости от правил поведения конечные автоматы (КА) могут быть как детерминирован­ными , так и недетерминированными ..

Характеристики

Список файлов лекций