Левый вывод, правый вывод. Однозначные и неоднозначные грамматики




Последняя лекция по дисциплине ТАиФЯ

Детерминированные и недетерминированные МП-автоматы. Детерминированные языки

МП-автоматы могут быть детерминированными и недетерминированными. В детерминированном МП-автомате не допустимы переходы, предлагающие различные действия в одних и тех же ситуациях. В недетерминированном – допустимы. МП-автомат по умолчанию (по определению) считается недетерминированным.

Приведу (без доказательства) некоторые факты, установленные в науке об автоматах и формальных языках.

Неприятный факт:

В отличие от обычных конечных автоматов детерминированные и недетерминированные МП-автоматы имеют разную выразительную мощь и, вообще говоря, для недетерминированного МП-автомата нельзя построить эквивалентный ему детерминированный МП-автомат.

С помощью недетерминированного МП-автомата можно определить и распознать любой КС-язык. Для любого КС-языка может быть определен недетерминированный МП-автомат. Однако недетерминированные МП-автоматы существуют в основном в теории, их трудно и практически невозможно эмулировать (реализовать) на обычном компьютере.

С помощью детерминированных МП-автоматов можно описать и распознать лишь некоторое подмножество КС-языков. Языки этого подмножества называются детерминированными КС-языками. Таким образом, детерминированный КС-язык – это язык, распознаваемый детерминированным МП-автоматом.

Ценно то, что детерминированные МП-автоматы могут быть реализованы на компьютере.

Польза от детерминированных языков: именно детерминированные языки используются при описании синтаксиса языков программирования. Поэтому для языков программирования может быть построен синтаксический анализатор (компилятор) на базе детерминированного МП-автомата.

 

Ещё о задаче синтаксического анализа

Основное (хотя и не единственное) применение КС-языков – описание синтаксиса языков программирования. Используя грамматику для описания языка программирования, мы должны выполнить не только процедуру, определяющую синтаксическую корректность программы, но и сделать нечто большее. А именно: мы должны иметь возможность определить тип той или иной синтаксической конструкции, обнаруженной в программе (т.е. распознать, идентифицировать её), и предпринять в каждом случае какие-либо соответствующие действия. Таким образом, для КС-языков помимо задачи распознавания основной становится задача синтаксического анализа, решением которой является построенное дерево грамматического разбора (синтаксическое дерево).

Левый вывод, правый вывод. Однозначные и неоднозначные грамматики

Для любой сентенциальной формы, т.е. цепочки, выводимой из начального символа грамматики, может быть построено дерево вывода (синтаксическое дерево, дерево грамматического разбора). В дереве вывода отражено, какие правила были применены во время вывода и к каким нетерминалам они применялись. Однако дерево вывода не несёт никакой информации о порядке применения правил. Поскольку порядок подстановок (применения правил) в дереве скрыт, может быть много выводов, соответствующих одному и тому же дереву вывода.

Вывод называется левым выводом, когда на каждом шаге в сентенциальной форме заменяется самый левый нетерминальный символ правой частью соответствующего правила (т.е. правила, содержащего данный нетерминал в левой части). Для каждого дерева существует единственный левый вывод.

Вывод называется правым выводом, если всегда заменяется самый правый нетерминал. Для каждого дерева существует также единственный правый вывод.

Многие методы обработки языков рассчитаны исключительно на левые или правые выводы, т.к. они обеспечивают систематизацию процесса обработки.

Цепочке языка может соответствовать более, чем одно дерево вывода, т.к. она может иметь разные выводы, порождающие разные деревья. Когда одна цепочка может иметь несколько деревьев вывода, говорят, что соответствующая грамматика неоднозначна.

Из сказанного можно подытожить следующее:

1. Каждой цепочке, выводимой в данной КС-грамматике, соответствует одно или несколько деревьев вывода.

2. Каждому дереву соответствует один или более выводов.

3. Каждому дереву соответствует единственный левый и единственный правый вывод.

4. Если каждой цепочке, выводимой в данной КС-грамматике, соответствует единственное дерево вывода, то эта грамматика называется однозначной; в противном случае её называют неоднозначной.

Выяснение того, однозначна ли заданная грамматика, является в общем случае алгоритмически неразрешимой проблемой, т.е. не существует универсального алгоритма, способного для любой заданной КС-грамматики определить, однозначна ли она.

Известно, что методы построения синтаксических анализаторов путем конвертирования (преобразования) формальной грамматики в соответствующий автомат не приводят к желаемому результату для неоднозначных грамматик. Несмотря на этот удручающий факт, на практике дела обстоят не совсем уж плохо. Во многих случаях можно наложить на грамматики некоторые ограничения и тем самым упростить задачу – сделать её решаемой.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2019-01-11 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: