Карпов - Основы построения трансляторов (2005) (943926), страница 9
Текст из файла (страница 9)
К настоящему времени уже очевидна идея порождающих грамматик Хомского. Терминальные символы — это символы, из которых строятся цепочки языка, порождаемого грамматикой. Нетерминалы — это вспомогательные символы, обозначающие конструкции„категории, понятия языка. Эти символы необходимы, когда мы рассуждаем о языке, но в цепочках языка эти символы не встречаются. Например, нетерминал Г' в примере 2.16 обозначает конструкцию <группа сказуемого>, он нужен для задания языка, но этот символ не встречается ни в одной цепочке языка.
Из начального нетерминала, представляющего самую общую конструкцию грамматики, порождаются все цепочки языка. Ясен и метод, с помощью которого грамматика задает язык: для языка определяется несколько абстрактных конструкций (нетерминалов), и правила порождения определяют, как каждая конструкция или группа конструкций и символов языка может быть построена из других конструкций и символов языка. Вычисление смысла предложения языка можно выполнить с помощью приписывания слисювих хсуакигерисиго,. нетерминалам по дереву вывода этого предложения в задающей язык порождающей грамматике.
Языки и грамматики 53 «ИДЕНТИФИКАТОР>-+<БУКВА> ~ <ИДЕНТИФИКА ГОР><БУКВА> ~ <ИДЕНТИФИКАТОР> <ЦИФРА> Иногда именно нетерминалы записываются без скобок, а терминальные сим- волы выделяются апострофами, например: ехргекяоп-+ехрге~яоп 'Т ехргеьяоп " .ехргеьяоп Рассмотрим в качестве простого примера построение порождающей грамма- тики для простейшего языка программирования, который мы назовем Милан (от англ. — М1ш!апр~аре). Пусть программа на Милане записывается в сле- дующей форме: "есг1п = ~еаза и: = геаФ , и11е гВ~п с(о 1й' гг»и Е)1еп т: =- т-и е1яе и: = и-гп; ,'гл~е (гп) Ьед1п Ь еисми К!В;1, 1:= Е!кМ1е В с1о Ь ! 1~ В 1Ьеп 1, ! 1е В ег1еп г- е1ае Ь ! игл ~е (Е) Е0Е =! !<! т ! с ~ (е) б ! 1 б ! 1 ц!Сц >!<!> ! Е+Е ! Е-Е 1 Е*Е ! Е/Е ! геас$ :1остроенная грамматика языка Милан обладает рядом недостатков, которые удут выявляться и устраняться впоследствии.
В частности, эта грамматика ".вусмысленная, и приведенная программа нахождения наибольшего общего Эта программа вычисляет и выводит значение наибольшего общего делителя двух введенных натуральных чисел. Подобных программ в языке Милан чожно построить много (бесконечное количество), используя только опера- торы присваивания, условный и цикл. Построим грамматику зтого языка. Для обозримости обозначим имена конст- рукций, как и раньше, заглавными буквами: П вЂ” <ПРО! РАММА>, <СПИСОК ОПЕРАТОРОВ>, Я вЂ” <ОПЕРАТОР>,  — сУСЛОВИЕ>, Д— <ЗНАК ОТНОШЕНИЯ>, Š— сВЫРАЖЕНИЕ>, 1 — <ИДЕНТИФИКАТОР>, С' — <КОНСТАНТА>. Буквы и цифры не будем различать, их конечное чис- .1о.
Обозначим их терминалами 6 и ц. ! рамматика языка Милан может быть записана так: Языки и грамматики 11ростейший такой алгоритм, который может быть реализован на машине Тьюринга, состоит просто в недетерминированной проверке возможных подстановок правых частей продукций вместо подцепочек промежуточной цепочки вывода, совпадающих с левыми частями продукций. Доказано, что ничего лучшего для общей проблемы распознавания синтаксической структуры цепочки придумать нельзя. Однако для такого алгоритма мы не можем знать при произвольной входной ленте машины Тьюринга, остановится ли эта машина (либо в заключительном состоянии„либо из-за невозможности применения продукции), и не можем оценить время работы алгоритма.
Таким образом, оказывается, что в общем случае задача синтаксического анализа не может оыть эффективно решена в классе модели порождающей грамматики Хомского. На этом можно было бы завершить рассмотрение этого подхода к трансляции языков„считая его неудачным и неприменимым на практике, поскольку из этого факта, казалось бы, следует невозможность построения общей теории и необходимость разработки своего индивидуального алгоритма синтаксического анализа для каждого конкретного случая. Однако. как это часто бывает в науке, проблемы, которые трудно или даже невозможно решить в общей постановке, эффективно решаются для частных постановок, Более того, именно частные постановки этих проблем, как оказывается. покрывают подавляющее большинство возникающих на практике важных случаев.
Именно такая ситуация оказывается в теории формальных языков и грамматик. Важнейшую роль в методах трансляции играют частные случаи, подклассы общих грамматик Хомского, и, в частности, контекстно-свободные грамматики, правила которых значительно проще, чем правила грамматик Хомского общего вида. Очевидно, что именно форма правил грамматики (а не их число) имеет существенное значение для алгоритмов синтаксического анализа.
Хомский определил четыре типа (семейства) грамматик в зависимости от того, какой вид имеют левая и правая части правил вида о,— +Р. Хомский ввел четыре различных семейства языков, порождаемых. этими грамматиками, и для каждого семейства впоследствии были найдены классы абстрактных преобразователей (автоматов), которые могут осуществить соответствующее преобразование, а именно по заданным цепочке а и грамматике 6 из этого класса построить вывод этой цепочки в б. Чем больше ограничений налагается на вид правил в данном подклассе грамматик, тем более эффективным оказывается алгоритм синтаксического анализа для этого подкласса.
В табл. 2.1 представлены четыре типа грамматик Хомского и показан для каждого из этих четырех типов грамматик вид допускаемых правил, название этих классов и по- Глава 2 рождаемых ими языков, а также абстрактное устройство, способное реализо- вать общий алгоритм распознавания. Т а б л и ц а 2. 1 . Подклассы грамматик иерархии Хомского Вид правил Распознающие абстрактные устройства Название грамматик ~ Машины Тьюринга Неограниченные грамматики Свободные ~аггее) грамматики Линейно-ограниченные автоматы Контекстно-зависимые грамматики Неукорачивающие грамматики Грамматики непосредственных составляющих уАб — вафд НС-грамматики Контекстно-свободные грамматики ~ КС-грамматики ты с магазинной Автоматные грамматики А-грамматики Регулярные грамматики :1-~цД Л-+а ые автоматы Грамматики с конечным числом состояний 2.5.1.
Грамматики типа О Класс языков, порождаемых грамматиками типа О, совпадает с классом всех рекурсивно-перечислимых множеств слов, поэтому он может быть назван классом рекурсивно-перечислимых языков. Известно, что класс рекурсивно- перечислимых множеств слов распознается машинами Тьюринга. В грамматиках типа О на левую и правую части продукций не накладывается никаких ограничений.
Цепочки а и Р в правилах грамматики а — +Р могут быть любыми. Единственное ограничение — левая часть и не может быть пустой цепочкой. Иными словами, запрещается порождать пе ало из пичего в любом месте промежуточной цепочки вывода. Обычно а включает по крайней мере один нетерминал, од ко Хомский не исключает и возможность продукций, в которых терминальн цепочка заменяется на другую терминальную, как, например, аЬ-+Ба в грамматике 6~. Очевидно, что все рассмотренные нами грамматики принадлежат этому общему классу — типу О грамматик Хомского. Как уже говорилось, общего алгоритма распознавания для этого типа грамматик не существует.
Языки и грамматики 2.5.2. Грамматики типа 1 В грамматиках типа 1 (в соответствии с табл. 2.1 их еще называют контекстно-зависимыми грамматиками, грамматиками непосредственных составляющих или НС-грамматиками) продукции имеют вид уАб — +7ро. Здесь А — некоторый нетерминал, у и о — произвольные цепочки, фактически образующие контекст, в котором нетерминал А может быть заменен цепочкой 1э (с дополнительным ограничением, что р не мо>кет быть пустой цепочкой). Очевидно, что по сравнению с грамматиками типа 0 правила замены здесь более ограничены. Это значит, что не все грамматики типа О являются грамматиками типа 1 (хотя, конечно, бсе грамм~ц.ики типа 1 являются грамматиками типа О). Например„грамматики бд с правилом аЬ вЂ” +Ба и 6~, с правилом С — +ВС являются грамматиками типа О, но не грамматиками типа 1.
Рассмотрим, однако, грамматику С~„. порождающую язык Е~, = ~п о"с" ~ и > 0~: 5 — +аЯУС ~ аЬС С — +ВС ЬВ-+И> сС вЂ” +сс Кроме правила С — «ВС все остальные продукции б<, удовлетворяют ограничениям грамматик типа 1. Действительно, две последние продукции разрешают замену нетерминалов только в конкретном контексте„и эти ограничения вытекают из существа идеи порождения цепочек требуемой структуры, а первые две продукции разрешают заменять нетерминал 5 цепочками независимо от контекста (т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
