Научный журнал
ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ.
СЕВЕРО-КАВКАЗСКИЙ РЕГИОН.

ТЕХНИЧЕСКИЕ НАУКИ


ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ СЕВЕРО-КАВКАЗСКИЙ РЕГИОН. 2017; 3: 43-48

 

http://dx.doi.org/10.17213/0321-2653-2017-3-43-48

 

АЛГОРИТМ СИНТАКСИЧЕСКОГО АНАЛИЗА КОНТЕКСТНО-СВОБОДНОЙ АППРОКСИМАЦИИ ДИНАМИЧЕСКИ ФОРМИРУЕМОГО КОДА

С.В. Григорьев, Д.А. Ковалев

Григорьев Семён Вячеславович – канд. физ.-мат. наук, ст. преподаватель, Санкт-Петербургский государственный университет, г. Санкт-Петербург, Россия. E-mail: semen.grigorev@jetbrains.com

Ковалев Дмитрий Александрович – студент, Санкт-Петербургский государственный университет, г. Санкт-Петербург, Россия. E-mail: dmitry.kovalev-m@ya.ru

 

 

Аннотация

Многие программы в процессе работы формируют из строк исходный код на некотором языке программирования и передают его для исполнения в соответствующее окружение (пример – dynamic SQL). Для статической проверки корректности динамически формируемого выражения используются различные методы, одним из которых является синтаксический анализ регулярной аппроксимации множества значений такого выражения. Аппроксимация может содержать строки, не принадлежащие исходному множеству значений, в том числе синтаксически некорректные. Анализатор в данном случае сообщит об ошибках, которые на самом деле отсутствуют в выражении, генерируемом программой. В данной статье описан алгоритм синтаксического анализа более точной, чем регулярная, контекстно-свободной аппроксимации динамически формируемого выражения.

 

Ключевые слова: синтаксический анализ; динамически формируемый код; контекстно-свободные грамматики; GLL; GFG; dynamic SQL; DSQL.

 

Полный текст: [in elibrary.ru]

 

Ссылки на литературу

  1. Рагозина А.К. Ослабленный синтаксический анализ динамически формируемых выражений на основе алгоритма GLL: магистерская дис. / СПбГУ. СПб., 2016.
  2. Scott E., Johnstone A. Gll parsing. Electronic Notes in Theoretical Computer Science, 253(7), 2009.
  3. Rekers J.G. Parser generation for interactive environments. PhD thesis, Citeseer, 1992.
  4. Pingali K., Bilardi G. A Graphical Model for Context-Free Grammar Parsing. Springer Berlin Heidelberg, Berlin, Heidelberg, 2015 p. 3–27.
  5. Christensen A.S., Møller A., Schwartzbach M.I. Precise analysis of string expressions. Proc. 10th International Static Analysis Symposium (SAS), Springer-Verlag: Berlin, June 2003 p. 1–18.
  6. Minamide Y. Static approximation of dynamically generated web pages. In: Proceedings of the 14th International Conference on World Wide Web, WWW ’05, ACM, 2005. p. 432–441.
  7. Asveld P.R.J., Nijholt A. The inclusion problem for some subclasses of context-free languages. Theor. Comput. Sci., 230(1-2):247–256, 1999.
  8. Annamaa A., Breslav A., Kabanov J., Vene V. An interactive tool for analyzing embedded sql queries. Programming Languages and Systems, Springer: Berlin, 2010. p. 131–138.
  9. Verbitskaia E., Grigorev S., Avdyukhin D. Relaxed Parsing of Regular Approximations of String-Embedded Languages, Springer International Publishing, Cham, 2016. p. 291–302.
  10. Doh K.-G., Kim H., Schmidt D.A. Abstract LR-Parsing, Springer Berlin Heidelberg, Berlin, Heidelberg, 2011. p. 90– 109.
  11. Tomita M. An efficient context-free parsing algorithm for natural languages. In: Proceedings of the 9th International Joint Conference on Artificial Intelligence. Vol. 2, IJCAI’85, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc. p. 756–764. 1985.
  12. Nevill-Manning C.G., Witten I.H. Identifying hierarchical structure in sequences: A linear-time algorithm. J. Artif. Int. Res., Sept. 1997. 7(1):67–82.