Вестник БГУ. Математика, информатика
Библиографическое описание:
ГОМОМОРФИЗМ ЭКВИВАЛЕНТНЫХ ПРЕОБРАЗОВАНИЙ ГРАММАТИК, ПРИМЕНЯЕМЫЙ ПРИ ГЕНЕРАЦИИ АНАЛИЗАТОРОВ ЯЗЫКА // Вестник БГУ. Математика, информатика. - 2019. №2. . - С. 44-60.
Заглавие:
ГОМОМОРФИЗМ ЭКВИВАЛЕНТНЫХ ПРЕОБРАЗОВАНИЙ ГРАММАТИК, ПРИМЕНЯЕМЫЙ ПРИ ГЕНЕРАЦИИ АНАЛИЗАТОРОВ ЯЗЫКА
Финансирование:
Коды:
Аннотация:
При построении транслятора, как правило, необходимо проводить эквива- лентные преобразования грамматики реализуемого языка, преобразующие синтаксическую спецификацию языка в тот вид, который допускает автома- тическую или ручную реализацию исходного языка, и решающие проблемы учёта ограничений выбранного метода синтаксического анализа. Эти пробле- мы возникают как из-за разнообразия способов определения реализуемых языков, так и из-за языковой неоднозначности или недетерминированности распознающего автомата. Каждое преобразование, выполняемое на трансля- ционных КС-грамматиках, может задаваться как отношение подобия (гомор- физма), определяемое на классах грамматик. Такие отношения имеют непо- средственную связь с сохранением семантического значения грамматических конструкций при эквивалентных преобразованиях синтаксиса, так как конеч- ной целью трансляции является получение последовательности действий, предписываемых вычислительной среде.
В статье представлен краткий обзор различных типов отношений подобия на грамматиках, применяемых при построении трансляторов c 1970-х гг.
Представлена схема построения анализаторов LL-языков с использованием синтаксических граф-схем (СГС). Даны формальное понятие маршрута (пути) в СГС и пример автоматического преобразования КСР-грамматики формаль- ного языка CIAO, выполненный в системе эквивалентных преобразований SynGT (Syntax Graph Transformations).
В статье представлен краткий обзор различных типов отношений подобия на грамматиках, применяемых при построении трансляторов c 1970-х гг.
Представлена схема построения анализаторов LL-языков с использованием синтаксических граф-схем (СГС). Даны формальное понятие маршрута (пути) в СГС и пример автоматического преобразования КСР-грамматики формаль- ного языка CIAO, выполненный в системе эквивалентных преобразований SynGT (Syntax Graph Transformations).
Ключевые слова:
эквивалентные преобразования грамматик; отношение по- добия; гомоморфизм покрытия; КСР-грамматики; синтаксическая граф-схема; регуляризация грамматик.
Список литературы:
Fedorchenko L. Regularization of Context-Free Grammars. Saarbrucken: LAP LAMBERT Academic Publishing, 2011. 180 p.
Fedorchenko L., Baranov S. Equivalent Transformations and Regularization in Context-Free Grammars // Cybernetics and Information Technologies (CIT). Sofia, 2015. Vol. 14, No. 4. P. 11–28.
Ахо А. В., Сети Р., Ульман Д. Д. Компиляторы: принципы, технологии и инструменты. М.: Вильямс, 2001. 768 с.
Федорченко Л. Н. Регуляризация контекстно-свободных грамматик на ос- нове эквивалентных преобразований синтаксических граф-схем // Труды СПИИРАН. 2010. Вып. 4(15). С. 213–230.
Early J. Ambiguity and precedence in syntax description // Acta Informatica. 1975. Vol. 4, Iss. 2. P. 183–192.
Федорченко Л. Н. Эквивалентность как отношение подобия в трансляции языков // Вестник Бурятского государственного университета. 2014. № 9–3. С. 49–53.
Mc Naughton R. The development of formal language theory since 1956 // In- ternat. J. Found. Comput. Sci. 1990. Vol. 1, No. 4. P. 355–368.
Paull M. C., Unger S. H. Structural equivalence of context-free grammars // Journal of Computer and System Sciences. 1968. Vol. 2, Iss. 4. P. 427–463.
Paull M. C., Unger S. H. Structural Equivalence of LL-k Grammars // IEEE Conference Record of Ninth Annual Symposium on Switching and Automata Theory. 1968. P. 160–175.
ВЕСТНИК БГУ. МАТЕМАТИКА, ИНФОРМАТИКА 2019/2
image
Prather R. E. Regular Expressions for Program Computations // American Mathematical Monthly. 1997. Vol. 104, No. 2. P. 120–130.
Kenichi T., Tadao K. A Result on the Equivalence Problem for Deterministic Pushdown Automata // J. Comput. Syst. Sci. 1976. Vol. 13, Iss. 1. P. 38–50.
Ginsburg S. A survey of grammar forms // Acta Cybernetica. 1977. Vol. 3, No. 4. P. 269–280.
Ginsburg S., Harrison M. A. Bracketed context free languages // J. Comput. Syst. Sci. 1967. Vol. 1, Iss. 1. P. 1–23.
Korenjak A. J., Hopcroft J. E. Simple deterministic languages // IEEE Conf. Record of 7th Annual Symposium on Switching and Automata Theory. 1966. P. 36–46.
Salomaa K., Yu S. Decidability of structural equivalence of E0L grammars // Theoretical Computer Science. 1991. Vol. 82, Iss. 1. P. 131–139.
Cremers A. B., Ginsburg S. Context-free grammar forms // J. Comput. Syst. Sci. 1975. Vol. 11, Iss. 1. P. 86–117.
Hotz G. Normal-form transformations of context-free grammars // Acta Cyber- netica. 1978. Vol. 4, No. 1. P. 65–84.
Hunt III H. B., Rosenkrantz D. J. Complexity of grammatical similarity rela- tions // Procs of a Conf. on Theoretical Computer Science. Waterloo, Canada, 1977. P. 139–145.
Федорченко Л. Н., Мартыненко Б. К. Эквивалентные преобразования КСР- грамматик в регулярной форме в практике построения языковых процессоров. Ч. 1. Определение и распознавание КСР-языков посредством синтаксических граф-схем. Л., 1983. 46 с.
Gray J. N., Harrison M. A. On the covering and. reduction problems for context free grammars // Journal of the Association for Computing Machinery. 1972. Vol. 19, Issue 4. P. 675–698.
Martynenko B. K. Regular Languages and CF Grammars // Computer Tools in Education. 2012. No. 1. P. 14–20.
Федорченко Л. Н. Алгоритмы построения состояний анализатора для КСР- языка // Вестник Бурятского государственного университета. Математика, ин- форматика. 2016. № 4. С. 23–33.
Федорченко Л. Н., Афанасьева И. В. Метод описания систем со сложным поведением на принципах обобщённых автоматов // Вестник Бурятского госу- дарственного университета. Математика, информатика. 2018. № 4. С. 22–36. DOI: 10.18101/2304-5728-2018-4-22-36.
Fedorchenko L., Baranov S. Equivalent Transformations and Regularization in Context-Free Grammars // Cybernetics and Information Technologies (CIT). Sofia, 2015. Vol. 14, No. 4. P. 11–28.
Ахо А. В., Сети Р., Ульман Д. Д. Компиляторы: принципы, технологии и инструменты. М.: Вильямс, 2001. 768 с.
Федорченко Л. Н. Регуляризация контекстно-свободных грамматик на ос- нове эквивалентных преобразований синтаксических граф-схем // Труды СПИИРАН. 2010. Вып. 4(15). С. 213–230.
Early J. Ambiguity and precedence in syntax description // Acta Informatica. 1975. Vol. 4, Iss. 2. P. 183–192.
Федорченко Л. Н. Эквивалентность как отношение подобия в трансляции языков // Вестник Бурятского государственного университета. 2014. № 9–3. С. 49–53.
Mc Naughton R. The development of formal language theory since 1956 // In- ternat. J. Found. Comput. Sci. 1990. Vol. 1, No. 4. P. 355–368.
Paull M. C., Unger S. H. Structural equivalence of context-free grammars // Journal of Computer and System Sciences. 1968. Vol. 2, Iss. 4. P. 427–463.
Paull M. C., Unger S. H. Structural Equivalence of LL-k Grammars // IEEE Conference Record of Ninth Annual Symposium on Switching and Automata Theory. 1968. P. 160–175.
ВЕСТНИК БГУ. МАТЕМАТИКА, ИНФОРМАТИКА 2019/2
image
Prather R. E. Regular Expressions for Program Computations // American Mathematical Monthly. 1997. Vol. 104, No. 2. P. 120–130.
Kenichi T., Tadao K. A Result on the Equivalence Problem for Deterministic Pushdown Automata // J. Comput. Syst. Sci. 1976. Vol. 13, Iss. 1. P. 38–50.
Ginsburg S. A survey of grammar forms // Acta Cybernetica. 1977. Vol. 3, No. 4. P. 269–280.
Ginsburg S., Harrison M. A. Bracketed context free languages // J. Comput. Syst. Sci. 1967. Vol. 1, Iss. 1. P. 1–23.
Korenjak A. J., Hopcroft J. E. Simple deterministic languages // IEEE Conf. Record of 7th Annual Symposium on Switching and Automata Theory. 1966. P. 36–46.
Salomaa K., Yu S. Decidability of structural equivalence of E0L grammars // Theoretical Computer Science. 1991. Vol. 82, Iss. 1. P. 131–139.
Cremers A. B., Ginsburg S. Context-free grammar forms // J. Comput. Syst. Sci. 1975. Vol. 11, Iss. 1. P. 86–117.
Hotz G. Normal-form transformations of context-free grammars // Acta Cyber- netica. 1978. Vol. 4, No. 1. P. 65–84.
Hunt III H. B., Rosenkrantz D. J. Complexity of grammatical similarity rela- tions // Procs of a Conf. on Theoretical Computer Science. Waterloo, Canada, 1977. P. 139–145.
Федорченко Л. Н., Мартыненко Б. К. Эквивалентные преобразования КСР- грамматик в регулярной форме в практике построения языковых процессоров. Ч. 1. Определение и распознавание КСР-языков посредством синтаксических граф-схем. Л., 1983. 46 с.
Gray J. N., Harrison M. A. On the covering and. reduction problems for context free grammars // Journal of the Association for Computing Machinery. 1972. Vol. 19, Issue 4. P. 675–698.
Martynenko B. K. Regular Languages and CF Grammars // Computer Tools in Education. 2012. No. 1. P. 14–20.
Федорченко Л. Н. Алгоритмы построения состояний анализатора для КСР- языка // Вестник Бурятского государственного университета. Математика, ин- форматика. 2016. № 4. С. 23–33.
Федорченко Л. Н., Афанасьева И. В. Метод описания систем со сложным поведением на принципах обобщённых автоматов // Вестник Бурятского госу- дарственного университета. Математика, информатика. 2018. № 4. С. 22–36. DOI: 10.18101/2304-5728-2018-4-22-36.
Статья.pdf