Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 29 стр.

UptoLike

ВУЗ: 

ВСГУТУ | Улан-Удэ

Составители: 

Рубрика: 

ли грамматики однозначными. Если какая-либо из них неоднозначна, привести пример
цепочки, для которой существует два различных дерева вывода.
Решение: Грамматика G
1
является неоднозначной, так как она имеет правила с правой
частью, содержащей два вхождения нетерминала S и знак арифметической операции.
Построим два дерева вывода для простейшей цепочки а + а + а:
Грамматика G
2
является однозначной, так как не содержит правил с двойным
вхождением нетерминального символа. Так, для цепочки а + а + а она имеет только одно
дерево вывода.
В некоторых случаях неоднозначность в грамматиках может устраняться путем
эквивалентных преобразований. Однако в общем случае проблема устранения
неоднозначности неразрешима. На практике от неоднозначности избавляются путем
задания словесных ограничений, называемых контекстными условиями языка, которые
включаются в его семантику.
Различают две стратегии грамматического разбора: восходящую и нисходящую, которые
соответствуют способу построения синтаксических деревьев. При нисходящей стратегии
разбора дерево строится от корня аксиомы вниз, к терминальным вершинам. Главной
задачей при нисходящем разборе является выбор того правила, которое следует применить
на рассматриваемом шаге. При восходящем разборе дерево строится от терминальных
вершин к корню дерева (аксиоме).
Преобразование цепочки, обратное порождению, называется редукцией.
4.4.1. Представление грамматики в виде графа
Дерево грамматического разбора не следует путать с представлением грамматики в виде
графа. Граф грамматики в качестве вершин содержит сентенциальные формы (любые
цепочки, выводимые из аксиомы).
Рассмотрим представление грамматики G в виде графа: G = (V
T
, V
N
, Р, S), в которой V
T
=
{a, b, с}, V
N
= {S}, P={S → aSa | bSb | c}.
4.5. Преобразования КС-грамматик
Часто требуется изменить грамматику таким образом, чтобы она удовлетворяла
определенным требованиям, не изменяя при этом порождаемый грамматикой язык. Для
этого используются эквивалентные преобразования КС-грамматик, некоторые из которых
рассмотрены ниже. 
ли грамматики однозначными. Если какая-либо из них неоднозначна, привести пример
цепочки, для которой существует два различных дерева вывода.
    Решение: Грамматика G1 является неоднозначной, так как она имеет правила с правой
частью, содержащей два вхождения нетерминала S и знак арифметической операции.
Построим два дерева вывода для простейшей цепочки а + а + а:




    Грамматика G2 является однозначной, так как не содержит правил с двойным
вхождением нетерминального символа. Так, для цепочки а + а + а она имеет только одно
дерево вывода.
    В некоторых случаях неоднозначность в грамматиках может устраняться путем
эквивалентных преобразований. Однако в общем случае проблема устранения
неоднозначности неразрешима. На практике от неоднозначности избавляются путем
задания словесных ограничений, называемых контекстными условиями языка, которые
включаются в его семантику.
    Различают две стратегии грамматического разбора: восходящую и нисходящую, которые
соответствуют способу построения синтаксических деревьев. При нисходящей стратегии
разбора дерево строится от корня аксиомы вниз, к терминальным вершинам. Главной
задачей при нисходящем разборе является выбор того правила, которое следует применить
на рассматриваемом шаге. При восходящем разборе дерево строится от терминальных
вершин к корню дерева (аксиоме).
    Преобразование цепочки, обратное порождению, называется редукцией.

      4.4.1. Представление грамматики в виде графа
     Дерево грамматического разбора не следует путать с представлением грамматики в виде
графа. Граф грамматики в качестве вершин содержит сентенциальные формы (любые
цепочки, выводимые из аксиомы).
     Рассмотрим представление грамматики G в виде графа: G = (VT, VN, Р, S), в которой VT =
{a, b, с}, VN = {S}, P={S → aSa | bSb | c}.




      4.5. Преобразования КС-грамматик

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

Страницы