Не предусмотрен выход при выполнении условия R > R , так как

5 не предусмотрен выход при выполнении условия R > R , так как

j-1 j

такое условие не может иметь место; вообще в процессе работы ал-

горитма в стеке R не может появиться пара символов с отношением

>, так как это исключает сам алгоритм.

Блок 7 производит поиск правила y=Rj,...,Ri по таблице грам-

матических правил и запоминает номер правила n, если оно найдено.

Блок 8 записывает в счетчик q число символов строки

Xn (q:=│Xn│).

Блок 9 производит переход на генерирующую подпрограмму.

Блок 10 проверяет длину строки Xn.

Блок 11 "выталкивает" символы Rj,..., Ri из стека R и запи-

сывает в него первый символ строки Xn, обозначенный на блок-схе-

ме Xn(1).

Блок 12 записывает все символы строки Xn, кроме первого, пе-

ред первым непрочитанным символом входного текста. Это не вы-

зовет переполнения массива L, так как по условию │Xn│ <= │Yn│.

Следовательно, число символов строки x не может быть больше чис-

ла символов строки y.

Блок 13 проверяет, выполняется ли правило R1,...,Ri. Если

такое правило выполняется, то алгоритм анализа и свертывания

входного текста закончен. Если такое правило не выполняется, зна-

чит данный текст из-за допущенной ошибки не может быть свернут.

Описания языков программирования КС- и даже неукорачивающи-

ми грамматиками вынуждает переносить определение части формаль-

ных условий из синтаксиса в семантику. Например, в ФОРТРАНе при

анализе каждого идентификатора необходимо определить, является

ли его описание явным или неявным. Если описание явное, то опре-

деляется тип идентификатора.

Пример:

Имеется грамматика:

Vт = { А, B }, Vn = { S, D, H, B`, A` }

1: S -> A`SD

2: S -> A`B`A

3: AD -> HA

4: H -> D

5: B` -> B

6: BD -> BB`A

7: A` -> A

Эта грамматика порождает язык следующего вида:

(А**n)(B**n)(А**n) ; n - степень

L(S) =A`,A,H,D R(S)=A, D

L(B`)=B R(B`)=B

L(A`)=A,H,D R(A`)=A

L(H) =D R(H)=D, A

L(D) =" R(D)=A

L(B) =B R(B)=" (неопределено)

L(A) =H,D R(A)="

Матрица предшествования:

│

S │ = =

B`│ < < =

A`│ = = < < < <

H │ < < =

D │ > > > >

A │ > > > > > > >

B │ = > > > <

@ │ = < < < <

───┼────────────────────────

│ S B` A` H D A B @

Дерево вывода на основе матрицы и правил:

┌──────────────────────────┐

S+──┐ ┌─────────────А+ +D

│ │ │ \ /

│ S+─── +─────+B` H +────+3

│ │ │  │ │

│ │ +5 4+ │

│ │ │ │ │

│ │ +B D+ │

│ │ │ │ │

+А` +А` └──+──┘ │

│ │ ┌──/│\──┐ │

│ │ │ │ │ │

+1 +1 │ +B` │ │

│ │ │ │ │ │

│ │ │ +5 │ │

│ │ │ │ │ │

А А B В А А

Ф : BA ─> BDA B. .A

\./

./│\.

B D A

ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ ПОРОЖДАЮЩИХ ГРАММАТИК

В ГРАММАТИКИ ПРЕДШЕСТВОВАНИЯ

Грамматики называются эквивалентными, если порождающие их

языки совпадают.

Теорема 1. Пусть в порожденной грамматике имеется одно или

несколько вхождений строки y в правые части порождающих правил.

Преобразование грамматики путем введения нового нетерминала Ф,

нового правила вывода Ф::=y и замена всех или части вхождений

строк y на вхождения нового символа порождает новую грамматику,

эквивалентную исходной.

G - грамматика.

Строка АВ, которая входит хотя бы в одну часть грамматичес-

кого правила, называется парой. Если А С R(А), В С L(В), то пара

рекурсивно-неоднозначна.

Грамматика, не содержащая рекурсивно-неоднозначных пар сим-

волов, называется рекурсивно-приведенной. Любая приведенная грам-

матика - рекурсивно-приведенная.

АЛГОРИТМ ПРЕОБРАЗОВАНИЯ РЕКУРСИВНО-НЕОДНОЗНАЧНОЙ ГРАММАТИКИ

В ГРАММАТИКУ ПРЕДШЕСТВОВАНИЯ

1. Находим множество правых символов. Выбираем все рекурсив-

ные символы грамматики (А R(А)). Грамматические правила имеют

вид: Ф::=(psi). Выделяем все вхождения этих символов в строки

psi, при условии, что они являются левыми частями пар. Для каждо-

го выбранного символа, имеющего такое вхождение, введем новый не-

терминальный символ А, новое правило вывода и заменим все выде-

ленные вхождения А на вхождения А`.

2. Для каждого нового правила А`::= А ищем другое правило

вида Ф ::= А, и если R(А) не содержит последнего символа строки,

то заменяем правило Ф ::= А на Ф ::= А`.

3. Находим множество левых символов. Выбираем все леворекур-

сивные символы В L(B), при условии, что В - правый член некото-

рой пары. Выделим все вхождения этих символов в строку (psi), при

условии, что эти вхождения являются правыми членами пар. Для каж-

дого В, имеющего такое вхождение, вводим В`, В`::= В и заменим

все вхождения В на вхождения В`.

4. Для каждого нового правила В` ::= В ищем в G другие пра-

вила вида Ф ::= В, при условии, что правые части этих правил сов-

падают. Если L(B) не содержит первого символа строки Ф, то заме-

няем правило Ф ::= В на Ф ::= В`.

5. Находим множество левых и правых символов для полученной

грамматики, находим матрицу отношений предшествования, если мат-

рица однозначна выход.

6. Перебирая все вхождения пар во всех строках (psi), отли-

чаем вхождения таких пар АiDi, где неоднозначность типа >< или >=

имеется либо между Аi и В L(Di). Для каждого отличного вхождения

пары АiDi в строку (psi)m выделяем подстроку хАi, для нее вводим

нетерминал Nj и новое грамматическое правило вида Nj ::= xАi. В

правых строках грамматических правил выделенные вхождения цепоч-

ки xАi заменяем новым символом Nj. Если в одной строке в правой

части выделено несколько вхождений таких цепочек, то надо после-

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

в правых частях грамматического правила выделено несколько строк,

то замена выполняется сначала для самых длинных строк, потом для

самых коротких.

Похожие работы

Программное обеспечение удалённого доступа к технической документации

Скачать

84334

30

0

... работы. В ходе работы над дипломным проектом разработан транслятор. Проблема создания такого транслятора является очень актуальной, т.к. многим пользователям САПР необходимо доступ к технической документацию, которую удобнее хранить на удаленных серверах в формате HTML. Поэтому степень положительного эффекта от выполнения дипломного проекта научно-исследовательского характера 1=6.5. В ...

Андрей Петрович Ершов (1931-1988)

Скачать

50249

0

1

... направления, активно развиваемого сейчас в разных коллективах и странах. Отталкиваясь от трансформационной модели смешанных вычислений и от своих работ в области трансляции и оптимизации программ, Ершов определяет концепцию трансформационной машины. Трансформационная машина есть абстрактное вычислительное устройство, выполняющее программы в некотором "сверхязыке", действиями которого являются ...

Программа–конструктор для построения МП–транслятора по его параметрам с последующей проверкой задаваемых пользователем цепочек

Скачать

36295

1

7

... 166, 16 Mb RAM, Windows 95 Вывод   В ходе разработки курсового проекта я ближе ознакомился с теорией МП- трансляторов, научился писать программы - конструкторы для построения МП – транслятора по его параметрам с последующей проверкой задаваемых цепочек, закрепил знания по системному программированию. Разрабатывая программу, я научился применять знания дискретной математике, что облегчает ...

Технологии проектирования в инженерных средах

Скачать

141647

0

0

... позволяет связывать твёрдотельные модели, сборки или чертежи, созданные с помощью SolidWorks 97, с файлами других приложений, что значительно расширяет возможности автоматизации процесса проектирования. С помощью технологии OLE можно использовать информацию, полученную в других приложениях Windows, для управления моделями и чертежами SolidWorks. Например, размеры модели могут быть рассчитаны в ...