Cтраница 3
Использование функций предшествования сокращает потребность в памяти с т2 до 2т величин. Правда, для хранения значений функций предшествования недостаточно двух бит, но доступ к значениям функций предшествования значительно проще, чем к элементам матрицы предшествования. Надо отметить, что использование функций предшествования приводит к исчезновению пустых позиций матрицы предшествования, позволяющих осуществлять контроль несовместности символов. [31]
Функции П6С не являются единственными функциями разбора, которые могут быть представлены в табличной форме; Несколько других функций рассматриваются в [11]: Используйте свое знание алгоритма ПСС ( или программу ANALYZER из гл. Замечание; Это ПСС степени ( 1 1 - 0 0):) Сравните требуемый для ПСС размер таблиц для функций Флойда I и ц, матрицы операторного предшествования Флойда, матрицы предшествования Вирта и Вебера, расширенных таблиц ппедшеетвования Маккимана и матриц перехода Замельзока п Баузра. [32]
Использование функций предшествования сокращает потребность в памяти с т2 до 2т величин. Правда, для хранения значений функций предшествования недостаточно двух бит, но доступ к значениям функций предшествования значительно проще, чем к элементам матрицы предшествования. Надо отметить, что использование функций предшествования приводит к исчезновению пустых позиций матрицы предшествования, позволяющих осуществлять контроль несовместности символов. [33]
Оператор wt доминирует над оператором иу если vv, содержится в области оператора и1 -, но не наоборот. Пространственный анализ проводится сначала путем группировки простых компонент изображения U в последовательности операторов, а затем путем построения структурного дерева Т изображения U. Чтобы построить структурное дерево Т для U, обозначим через F0 фрейм ( набор) изображения U. Построим две п х и матрицы предшествования Ml и М2 следующим образом: М1 ( г, j) есть, если и1 - доминирует над Wj, , если Wj доминирует над и1 -, и пробел - в других случаях; М2 ( /, j) есть, если и; предшествует Wj, , если и; предшествует и, , если оба оператора имеют одинаковое предшествование, и пробел-в других случаях. [34]
Для выделения основы ( или первичной фазы) левосторонний восходящий распознаватель обычно использует некоторый контекст. Если для однозначного определения основы на любом шаге синтаксического анализа достаточно рассмотреть не более т символов слева от основы и не более п символов справа, то говорят, что эта грамматика с ( т, п) ограниченным контекстом. Все рассмотренные выше распознаватели применимы только к грамматикам с ( 1 1) ограниченным контекстом. Например, в методе предшествования для этого нужно определить отношения предшествования между всеми возможными строками х и у, длина которых не превосходит тип соответственно. На практике этого не делают из-за чрезвычайно большого объема памяти, требующегося для хранения матрицы предшествования строк, а также резкого увеличения машинного времени. [35]