КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Автоматные языки и грамматики. Задача трансляции автоматных языков.
Грамматики типа 3 называют автоматными грамматиками (А - грамматиками). Правила вывода в таких грамматиках имеют вид:
<A> 
a или <A> a<B> или <A> <B>a,
где a 
Vт, <A>, <B> VА, причем грамматика может иметь только правила вида <A> a<B> - правосторонние правила, либо только вида <A> <B>a - левосторонние правила. Примерами автоматных грамматик могут служить правосторонняя грамматика Г1. 6 и левосторонняя грамматика Г1. 7.
Г1. 6
Vт = {a, b}, VА = {<I>, <A>},
R = { <I> a<I>,
<I> a<A>,
<A> b<A>,
<A> b<Z>,
<Z> $ }
Г1. 7
Vт = {a, b}, VА = {<I>, <A>},
R = { <I> <A>b,
<A> <A>b,
<A> <Z>a,
<Z> <Z>a,
<Z> $ }
Эти грамматики являются эквивалентными и порождают язык
L(Г7) = {a...ab...b | n,m > 0}
Между множествами языков различных типов существует отношение включения:
{ L типа 3 } 
{ L типа 2 } { L типа 1 } { L типа 0 }
Доказано, что существуют языки типа 0, не являющиеся языками типа 1, языки типа 2, не являющиеся языками типа 1, и языки типа 3, не являющиея языками типа 2.
Учитывая, что наибольшее практическое применение находят грамматики типа 2 и типа 3, дальнейшее изложение посвящается рассмотрению именно этих типов грамматик.
КС-грамматика определяет структуру цепочек и позволяет строить цепочки определенного языка. Магазинные автоматы, подобно рассмотренным ранее конечным автоматам, позволяют решать для контекстно-свободных языков задачу распознавания, которая заключается в том, что по заданной цепочке необходимо определить принадлежит ли она заданному языку.
В работах, связанных с формальными языками и грамматиками, используется модель магазинного автомата, состоящая из входной ленты, устройства управления и вспомогательной ленты, называемой магазином или стеком.
Автоматные языки и грамматики. Задача трансляции автоматных языков.
Исследователи, изучающие вопросы появления разума на нашей планете, полагают, что решающую роль в его развитии сыграло появление языка, который позволил не только выражать и сохранять знания, но и обмениваться ими.
С созданием компьютеров, возникла потребность в общении с подобными устройствами, поскольку оказалось необходимым передавать им приказы, задания и описания работы, которую они должны выполнять. Для этой цели начали разрабатывать специальные языки, которые стали называть искусственными в отличие от естественных языков общения людей. Искусственные языки должны быть, с одной стороны, удобными и понятными для человека, а с другой - должны восприниматься устройствами. Совмещение этих требований в одном языке оказалось трудной задачей, поэтому появились средства для преобразования текстов с языка, понятного человеку, на язык устройства. Такие средства назвали трансляторами
Транслятор может быть интерпретирующего или компилирующего типа. В первом случае его называют интерпретатором входного языка, а во втором -компилятором.
Интерпретатор последовательно читает предложения входного языка, анализирует их и сразу же выполняет, а компилятор не выполняет предложения языка, а строит программу, которая может в дальнейшем быть запущена для получения результата.
На вход компилятора подается текст, написанный на входном языке - языке, понятном человеку, а результатом работы компилятора является текст на языке, понятном устройству.
Для построения компилятора необходимо однозначное и точное задание входного и выходного языков. Такое задание предполагает определение правил построения допустимых конструкций (выражений) языка. Множество таких правил называют синтаксисом языка. Кроме того, задание должно включать описание назначения и смысла каждой конструкции языка. Такое описание называют семантикой языка.
Для построения точных и недвусмысленных описаний применяют метод абстракций, который предполагает выделение наиболее существенных свойств рассматриваемого объекта и опускание свойств, менее значимых для рассматриваемого случая. Например, при построении модели входных языков можно рассматривать входной текст как последовательность символов, построенную по определенным правилам, отвлекаясь от характера начертания символов и их расположения на листе. Математические модели, использующие представление текстов в виде цепочек символов, называют формальными языками и формальными грамматиками.
Формальные грамматики- Математические модели, использующие представление текстов в виде цепочек символов
КС-грамматика определяет структуру цепочек и позволяет строить цепочки определенного языка. Магазинные автоматы, подобно рассмотренным ранее конечным автоматам, позволяют решать для контекстно-свободных языков задачу распознавания, которая заключается в том, что по заданной цепочке необходимо определить принадлежит ли она заданному языку.
В работах, связанных с формальными языками и грамматиками, используется модель магазинного автомата, состоящая из входной ленты, устройства управления и вспомогательной ленты, называемой магазином или стеком.
Входная лента разделяется на клетки (позиции), в каждой из которых может быть записан символ входного алфавита. При этом предполагается, что в неиспользуемых клетках входной ленты расположены пустые символы ε.
Вспомогательная лента также разделена на клетки, в которых могут располагаться символы магазинного алфавита. Начало вспомогательной ленты называетсядном магазина. Связь устройства управления с лентами осуществляется двумя головками, которые могут перемещаться вдоль лент.
|
Рис. 1.
Головка входной ленты может перемещаться только в одну сторону - вправо или оставаться на месте. Она может выполнять только чтение. Головка вспомогательной ленты способна выполнять как чтение, так и запись, но эти операции связаны с перемещением головки определенным образом:
- при записи головка предварительно сдвигается на одну позицию вверх, а затем символ заносится на ленту,
- при чтении символ, находящийся под головкой считывается с ленты, а затем головка сдвигается на одну позицию вниз, т.о.головка всегда установлена против последнего записанного символа. Позицию, находящуюся в рассматриваемый момент времени под головкой, называют вершиной магазина.
Определение. Магазинный автомат М определяется следующей совокупностью семи объектов:
M = {P , S , sо , f , F , H , hо }, где
P - входной алфавит,
S - алфавит состояний,
sо - начальное состояние,
sо S ,
F - множество конечных состояний, F является подмножеством S,
H - алфавит магазинных символов, записываемых на вспомогательную ленту,
hо - маркер дна, он всегда записывается на дно магазина, hо H,
f - функция переходов
f : {P 
{ ε }} x S x H S x H*,
если М - автомат детерминированный, и
f:{P { ε }} x S x H M( S x H*) ,
если М - автомат недетерминированный.
Функция f отображает тройки ( pi, sj, hk) в пары ( sr, υ ), где υ H* и hk - символ в вершине магазина, для детерминированного автомата или в множество пар для недетерминированного автомата.
Эта функция описывает изменение состояния магазинного автомата, происходящее при чтении символа с входной ленты и премещении входной головки.
В дальнейшем при построении магазинных автоматов потребуются две разновидности функций переходов, изменяющих состояние автомата без перемещения входной головки:
1) функция переходов с пустым символом в качестве входного символа:
f0(s, ε, h) = (s', β),
которая, независимо от того какой символ находится под читаюшей гловкой входной ленты, предписывает прочитать символ h из вершины магазина, изменить состояние автомата на s' и записать цепочку β в магазин.
2) функция переходов с определенным входным символом:
f*(s, a, h) = (s', β),
которая предписывает изменение состояния и запись цепочки в магазин при условии, что символ a читается входной головкой, а в вершине магазина находится символ h.
Дата добавления: 2015-01-29; просмотров: 211; Мы поможем в написании вашей работы!; Нарушение авторских прав |