Матрица - предшествование
Cтраница 2
Если конфликты предшествования становятся нормой, то для записи элемента матрицы предшествования уже недостаточно двух бит. Здесь нужно либо записывать каждый элемент матрицы предшествования тремя битами, либо использовать две матрицы с двухбитовыми элементами, одну для выделения правого конца основы, а другую - для левого. В обоих случаях нужно заготовить также две таблицы троек: таблицу правых троек для устранения неоднозначности на правом конце предполагаемой основы и таблицу левых троек для устранения неоднозначности на левом конце. [16]
Пусть получена мозаичная структура модулей, представленная на рис. 4.3.10 с матрицей предшествования МС. Итогом преобразования является матрица МС. На рис 4.3.11 представлен граф иерархической структуры модулей. В вершинах графа отмечены номера модулей, соответствующих графу мозаичной структуры и новому графу. [17]
Если изменяется входной язык, то нужно изменить таблицу порождающих правил, матрицу предшествования и семантические подпрограммы. [18]
В § 7 - 1 были рассмотрены алгоритмы анализа программ, основанные на использовании матрицы предшествования. [19]
Сейчас же будем считать, что отношения предшествования между символами языка каким-то образом определены и матрица предшествования построена. [20]
Если N - число нетерминальных символов грамматики, а Т - число терминальных символов, то объем матрицы предшествования для левого конца основы равен ( Л / - f - T) X ( N - ( - Т), а для правого - ( Л / Г) Х7 поскольку входная строка состоит только иа терминальных символов. [21]
При трансляции с каждого конкретного языка транслятор собирается из блока анализа входного текста, блока распределения памяти, блока оптимизации ( если он используется), словаря терминальных символов данного языка, таблицы грамматических правил с адресами обращений к генерирующим подпрограммам, матрицы предшествования для данного языка ( если ее использует блок анализа), блока или блоков генерирующих подпрограмм, набора семантических подпрограмм. [22]
Первое из приведенных требований позволяет ограничиться установлением отношений предшествования только для терминальных символов. Это значительно сокращает размер матрицы предшествования и повышает эффективность алгоритма разбора по сравнению с методом предшествования. [23]
 |
Схема транслятора, основанного на методе предшествования. [24] |
Синтаксис входного языка задается таблицей порождающих правил. Используя эту таблицу, матрицу предшествования можно построить автоматически по правилам, описанным в 5.3.4. Семантика входного языка в терминах выходного языка отражена в семантических подпрограммах, которые составляются вручную. [25]
Обычно матрицу предшествования хранят в упакованном виде: по 2 бита на элемент матрицы. Но и в упакованном виде матрица предшествования занимает достаточно много места. [26]
 |
Конфликты предшествования на концах предпо. [27] |
Если конфликты предшествования становятся нормой, то для записи элемента матрицы предшествования уже недостаточно двух бит. Здесь нужно либо записывать каждый элемент матрицы предшествования тремя битами, либо использовать две матрицы с двухбитовыми элементами, одну для выделения правого конца основы, а другую - для левого. В обоих случаях нужно заготовить также две таблицы троек: таблицу правых троек для устранения неоднозначности на правом конце предполагаемой основы и таблицу левых троек для устранения неоднозначности на левом конце. [28]
Распознаватель решает задачу разбора. В процессе синтаксического анализа распознаватель использует матрицу предшествования ( или функции предшествования) и таблицу порождающих правил грамматики входного языка. Каждая запись этой таблицы содержит одно из порождающих правил и ( для некоторых правил) имя семантической подпрограммы, которую нужно выполнить, когда это правило применяется для редукции. [29]
В принципе описываемый транслятор пригоден для перевода с нескольких входных языков, грамматики которых - грамматики предшествования, на несколько выходных языков. Транслятор, переводящий с М входных языков на N выходных, должен иметь М экземпляров таблиц порождающих правил и матриц предшествования и М X N наборов семантических подпрограмм. Однако за универсальность транслятора в классе грамматик предшествования приходится платить сравнительно невысокой эффективностью алгоритмов трансляции. [30]
Страницы: 1 2 3