НАУЧНЫЙ ВЕСТНИК


НОВОСИБИРСКОГО ГОСУДАРСТВЕННОГО ТЕХНИЧЕСКОГО УНИВЕРСИТЕТА

ISSN (печатн.): 1814-1196          ISSN (онлайн): 2658-3275
English | Русский

Последний выпуск
№2(75) Апрель - Июнь 2019

Обработка ошибок в синтаксическом анализаторе компилятора языка El

Выпуск № 2 (75) Апрель - Июнь 2019
Авторы:

Малявко Александр Антонович
DOI: http://dx.doi.org/10.17212/1814-1196-2019-2-37-48
Аннотация

Рассматривается задача обработки синтаксических ошибок в компиляторе функционально-императивного языка программирования El, выполняемой с целью организации продолжения синтаксического разбора после останова для нахождения максимально возможного количества действительно допущенных ошибок. Предлагается комбинация нескольких известных способов нейтрализации синтаксических ошибок, ориентированная на особенности используемого в трансляторе алгоритма детерминированного синтаксического разбора. Парсер компилятора реализован в виде стекового автомата, управляемого входным токеном и символом, снимаемым с верхушки стека. Предлагаемый метод нейтрализации ошибок основан на полном переборе всех возможных вариантов модификации одного ошибочного токена: поочередная вставка, замена и удаление для выбора такого варианта перезапуска автомата, при котором следующая синтаксическая ошибка обнаруживается на максимальном расстоянии от нейтрализуемой. Если никакая модификация одиночного ошибочного токена не приводит к успешной нейтрализации, то в предлагаемом методе после каждого удаления расширяется множество допустимых токенов, вычисляемое как объединение множеств выбора нескольких символов, находящихся на верхушке стека автомата. Этот переход от обработки одиночной ошибки к обработке множественной позволяет уменьшить количество входныхтокенов, считываемых парсером без анализа, по сравнению с известным режимом паники. Описываемый алгоритм нейтрализации сочетается в El-компиляторе с «правилами для типичных ошибок», включаемыми в грамматику для таких возможных ситуаций, когда для успешной нейтрализации ошибки требуется вставить не один, а два или три токена. Подобные ошибки возможны в программах на языке El, их эффективная нейтрализация другими способами представляется весьма затруднительной.


Ключевые слова: формальная грамматика, порождающее правило, автомат, множество выбора, нисходящий разбор, одиночная ошибка, нейтрализация ошибок, компилятор

Список литературы

1. Maliavko A. Novel functional-imperative programming language El: a brief introduction // Proceedings of the 2018 International Multi-Conference on Industrial Engineering and Modern Technologies (FarEastCon). – Vladivostok, October 2018. – P. 1–7.



2. Crespi-Reghizzi S. Formal languages and compilation. – London: Springer, 2009. – 364 p.



3. Compilers: principles, techniques, and tools / A. Aho, M. Lam, R. Sethi, J. Ullman. – Reading: Addison-Wesley, 2006. – 795 p.



4. Maliavko A., Zhurkin P., Nagornov N. The functionally-imperative programming language El and its translator // 14th International Scientific-Technical Conference on Actual problems of Electronic Instrument Engineering (APEIE-2018). – Novosibirsk, 2018. – Vol. 1, pt. 4. – P. 469–476.



5. Watson D. A practical approach to compiler construction. – Springer, 2017. – 254 p.



6. Carroll J., Long D. Theory of finite automata with an introduction to formal languages. – New Jersey: Prentice Hall, 1989. – 447 p.



7. Малявко А.А. Использование веб-приложений и веб-технологий при разработке учебного программного обеспечения для изучения методов трансляции // Современное образование: технические университеты в модернизации экономики России: материалы Международной научно-методической конференции, 27–28 января 2011 года. – Томск: Изд-во ТУСУР, 2011. – С. 45–47.



8. Meduna A. Formal languages and computation: models and their applications. – Boca Raton: CRC Press, 2014. – 315 p.



9. Rosenkrantz D., Stearns R. Properties of deterministic top down grammars // Information and Control. – 1970. – Vol. 17 (3). – P. 226–256.



10. Waite W., ‎Goos G. Compiler construction. – Heidelberg: Springer, 2012.



11. Dos Reis A. Compiler construction using Java, JavaCC, and Yacc. – Hoboken: Wiley & Sons, 2012. – 664 p.



12. Малявко А.А. Формальные языки и компиляторы: учебное пособие для вузов. – М.: Юрайт, 2017. – 429 с.



13. Kumar R. Theory of automata, languages and computation. – Tata: McGraw-Hill, 2010.



14. Medeiros S. Mascarenhas F. Syntax error recovery in parsing expression grammars // Applied computing 2018: the 33rd Annual ACM Symposium on Applied Computing. – New York, 2018.



15. Cooper K., Torczon L. Engineering a compiler. – San Francisco: Morgan Kaufmann, 2003.



16. Wilhelm R., Seidl H., Hack S. Compiler design: syntactic and semantic analysis. – New York: Springer, 2013. – 216 p.



17. Parr T., Harwell S., Fisher K. Adaptive LL(*) parsing: the power of dynamic analysis // Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications. – New York: ACM, 2014. – P. 579–598.



18. Chandak M., Khurana K. Compiler design. – Hyderabad, India: Universitet press, 2018. – 480 p.



19. Grune R., Jacobs C. Parsing techniques: a practical guide. – New York: Springer, 2007. – 585 p.



20. Plaisted D. Source-to-source translation and software engineering // JSEA Special Issue on Software Dependability. – 2013. – Vol. 6, N 4A.



21. Afroozeh A., Izmaylova A. Faster, practical GLL parsing // Compiler Construction: 24th International Conference. – Heidelberg: Springer, 2015. – P. 89–108.



22. Safonov V. Trustworthy compilers. – Hoboken: Wiley & Sons, 2010. – 317 p.

Для цитирования:

Малявко А.А. Обработка ошибок в синтаксическом анализаторе компилятора языка El / А.А. Малявко // Научный вестник НГТУ. – 2019. – № 2 (75). – С. 37–48. – DOI: 10.17212/1814-1196-2019-2-37-48.

For citation:

Maliavko A.A. Obrabotka oshibok v sintaksicheskom analizatore kompilyatora yazyka El [Errors handling in the parser for the El-language compiler].Nauchnyi vestnik Novosibirskogo gosudarstvennogo tekhnicheskogo universitetaScience bulletin of the Novosibirsk state technical university, 2019, no. 2 (75), pp. 37–48. DOI: 10.17212/1814-1196-2019-2-37-48.

Просмотров: 18