Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Автоматные языки и грамматики. Задача трансляции автоматных языков.

Читайте также:
  1. DBASe-подобные реляционные языки
  2. IV. Работа над задачами.
  3. IV. Работа над задачами.
  4. IV. Работа над задачами.
  5. IV. Работа над задачами.
  6. IV. Работа над задачами.
  7. V. Работа над задачами.
  8. V. Работа над задачами.
  9. V. Работа над задачами.
  10. V. Работа над задачами.

Грамматики типа 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; просмотров: 35; Нарушение авторских прав


<== предыдущая лекция | следующая лекция ==>
Формы Бэкуса-Науэра и синтаксические графы. | Минимизация конечных автоматов
lektsii.com - Лекции.Ком - 2014-2019 год. (0.036 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты