Грамматика - предшествование
Cтраница 1
Грамматика предшествования [11.4] - это другая грамматика пространственного анализа; ее можно использовать для анализа двумерных математических выражений и анализа формата напечатанных страниц. [1]
Построить расширенную грамматику предшествования, которая служила бы также руководством по изучению языка, обычно не составляет труда. [2]
Заметим, что распознаватель для грамматики предшествования дает канонический разбор. [3]
Использование функций предшествования накладывает дополнительные ограничения на грамматику предшествования. [4]
 |
Дерево разбора. [5] |
Второе и третье требования, как и аналогичные требования к грамматике предшествования, обеспечивают беступиковость алгоритма разбора. Строго говоря, перечисленные требования не гарантируют однозначности алгоритма разбора. Это будет видно из дальнейшего. Однако характер возможных неоднозначностей таков, что они без особого труда устраняются семантическими подпрограммами. [6]
В принципе описываемый транслятор пригоден для перевода с нескольких входных языков, грамматики которых - грамматики предшествования, на несколько выходных языков. Транслятор, переводящий с М входных языков на N выходных, должен иметь М экземпляров таблиц порождающих правил и матриц предшествования и М X N наборов семантических подпрограмм. Однако за универсальность транслятора в классе грамматик предшествования приходится платить сравнительно невысокой эффективностью алгоритмов трансляции. [7]
Ясно, что построить грамматику, отвечающую требованиям функций ( предшествования, труднее, чем однозначную грамматику предшествования. [8]
Этот метод применим ко всем контекстно-свободным языкам [3], так как любую КС грамматику с помощью эквивалентного преобразования можно сделать грамматикой предшествования. Эффективность названного метода повышается, если матрицу отношений предшествования заменить функциями предшествования, также введенными Флойдом. Однако не всякая грамматика предшествования обладает функциями предшествования. В данной работе показывается, что каждую грамматику, не обладающую функциями предшествования, можно преобразовать в эквивалентную грамматику, обладающую такими функциями. [9]
Возможно это и удивительно, но такое простое правило применимо для довольно большого класса грамматик, включающего как простые, так и расширенные грамматики предшествования. [10]
Если устранить рекурсивность множеств L ( B) и L ( T) относительно В и Т соответственно, то рассматриваемая грамматика станет грамматикой предшествования. [11]
Следовательно, можно считать, что метод операторного предшествования есть обобщение метода стека с приоритетами для языков, порождаемых грамматиками с операторным предшествованием, а общий метод предшествования - обобщение этих двух методов для языков, порождаемых грамматиками предшествования. Надо, однако, отметить, что грамматики с операторным предшествованием в общем случае не являются подмножеством грамматик предшествования. [12]
 |
Граф вывода. [13] |
Алгоритм в каждом текущем предложении S, выделяет самую левую строку, заключенную между отношениями, и заменяет ее по соответствующему правилу грамматики. Если грамматика предшествования не имеет двух правил с одинаковыми строками г г, то данный алгоритм для каждого предложения SeLG всегда порождает одну и только одну последовательность правил сворачивания. [14]
Следовательно, можно считать, что метод операторного предшествования есть обобщение метода стека с приоритетами для языков, порождаемых грамматиками с операторным предшествованием, а общий метод предшествования - обобщение этих двух методов для языков, порождаемых грамматиками предшествования. Надо, однако, отметить, что грамматики с операторным предшествованием в общем случае не являются подмножеством грамматик предшествования. [15]
Страницы: 1 2