Грамматика - предшествование
Cтраница 2
Большинство современных языков программирования относятся к этому классу, поэтому такой метод контроля для них является полным. Однако если в САП будет применен какой-либо новый язык программирования или введено расширение старого языка, выводящее его из класса языков, порождаемых грамматикой предшествования, то такой метод контроля также окажется неполным. Так, контекстно-свободные языки, задаваемые правилами Бэкуса, для своего полного синтаксического контроля требуют более широкого метода, основанного на применении принципов, совпадающих с принципами работы машин Тьюринга с магазинной памятью. Этот принцип учитывает метаре-зультат, для которого производится анализ очередного символа. [16]
Этот метод применим ко всем контекстно-свободным языкам [3], так как любую КС грамматику с помощью эквивалентного преобразования можно сделать грамматикой предшествования. Эффективность названного метода повышается, если матрицу отношений предшествования заменить функциями предшествования, также введенными Флойдом. Однако не всякая грамматика предшествования обладает функциями предшествования. В данной работе показывается, что каждую грамматику, не обладающую функциями предшествования, можно преобразовать в эквивалентную грамматику, обладающую такими функциями. [17]
 |
Схема транслятора, основанного на методе предшествования. [18] |
Для этого нужно прежде всего - стандартизировать лексику входных языков, т.е. правила записи служебных слов, идентификаторов и констант, а также алфавит. Алгоритм распознавателя универсален з классе грамматик предшествования. Алгоритм генератора предельно прост - - генератор вызывает требуемую семантическую подпрограмму и передает ей аргументы, определяемые элементом разбора. [19]
В принципе описываемый транслятор пригоден для перевода с нескольких входных языков, грамматики которых - грамматики предшествования, на несколько выходных языков. Транслятор, переводящий с М входных языков на N выходных, должен иметь М экземпляров таблиц порождающих правил и матриц предшествования и М X N наборов семантических подпрограмм. Однако за универсальность транслятора в классе грамматик предшествования приходится платить сравнительно невысокой эффективностью алгоритмов трансляции. [20]
Страницы: 1 2