Гомоморфизм эквивалентных преобразований грамматик, применяемый при генерации анализаторов языка

При построении транслятора, как правило, необходимо проводить эквивалентные преобразования грамматики реализуемого языка, преобразующие синтаксическую спецификацию языка в тот вид, который допускает автоматическую или ручную реализацию исходного языка, и решающие проблемы учёта ограничений выбранного метода синтаксического анализа. Эти проблемы возникают как из-за разнообразия способов определения реализуемых языков, так и из-за языковой неоднозначности или недетерминированности распознающего автомата. Каждое преобразование, выполняемое на трансляционных КС-грамматиках, может задаваться как отношение подобия (гоморфизма), определяемое на классах грамматик. Такие отношения имеют непосредственную связь с сохранением семантического значения грамматических конструкций при эквивалентных преобразованиях синтаксиса, так как конечной целью трансляции является получение последовательности действий, предписываемых вычислительной среде. В статье представлен краткий обзор различных типов отношений подобия на грамматиках, применяемых при построении трансляторов c 1970-х гг. Представлена схема построения анализаторов LL-языков с использованием синтаксических граф-схем (СГС). Даны формальное понятие маршрута (пути) в СГС и пример автоматического преобразования КСР-грамматики формального языка CIAO, выполненный в системе эквивалентных преобразований SynGT (Syntax Graph Transformations).