Синтаксически управляемая генерация тестов для процессоров регулярных языков
Ключевые слова:
задача Китайского почтальона, ориентированный граф, регулярное выражение, рёберный граф, синтаксическая диаграмма Н. Вирта, тест минимальной длины
Аннотация
Описывается метод генерации тестов минимальной длины для синтаксически управляемых конечных процессоров, реализующих регулярные языки. Критерий выбора тестовых вариантов выражает заданную степень покрытия дуг графа, представляющего регулярное выражение, по которому строится процессор. Поскольку дуги графа помечены семантическими метками, то критерий выражает соответствующую степень взаимодействия между семантиками, и тест гарантирует выполнение этого критерия. Метод основан на алгоритме решения задачи Китайского почтальона на ориентированном графе, выводимом из регулярного выражения, определяющем конечно-автоматный язык, реализуемом процессором.
Литература
[1] N. Wirth, “The Programming Language Pascal,” Acta Informatica, vol. 1, 1971, pp. 35–63; doi:10.1007/BF00264291
[2] B. Martynenko, “Towards the 80th Anniversary of N. Wirth: Wirth’s Syntactic Charts in the SYNTAXTechnology,” in 3rd International Conference on Computer Technology in Russia and in the Former Soviet (SoRuCom 2014), Kazan, Russia, 13-17 Oct. 2014, pp. 199–206; doi: 10.1109/SoRuCom.2014.52
[3] B. K. Martynenko, Sintaksicheski upravlyaemaya obrabotka dannykh [Syntactically managed data processing]. 2nd ed., Saint-Petersburg, Russia: SPbSU, 2004 (in Russian).
[4] J. R. Evanas and E. Minieka, Optimization Algorithms for Networks and Graphs, 2nd ed., New York, NY, USA: Marcel Dekker, 1992.
[5] J. E. Hopcroft and J. D. Ullman, Formal languages and their relation to automata, Reading, MA: Addison Wesley, 1969.
[6] A. P. Ershova, S. S. Lavrova, and M.R. Shura-Bura eds., Algoritmicheskii yazyk Algol-60. Peresmotrennoe soobshchenie. [Revised Report on the Algorithmic Language Algol 60], Moscow, USSR: Mir, 1965 (in Russian).
[7] F. Harary, R. Z. Norman, and D. Cartwright, Structural Models: An Introduction to the Theory of Directed Graphs, Wiley, 1966.
[2] B. Martynenko, “Towards the 80th Anniversary of N. Wirth: Wirth’s Syntactic Charts in the SYNTAXTechnology,” in 3rd International Conference on Computer Technology in Russia and in the Former Soviet (SoRuCom 2014), Kazan, Russia, 13-17 Oct. 2014, pp. 199–206; doi: 10.1109/SoRuCom.2014.52
[3] B. K. Martynenko, Sintaksicheski upravlyaemaya obrabotka dannykh [Syntactically managed data processing]. 2nd ed., Saint-Petersburg, Russia: SPbSU, 2004 (in Russian).
[4] J. R. Evanas and E. Minieka, Optimization Algorithms for Networks and Graphs, 2nd ed., New York, NY, USA: Marcel Dekker, 1992.
[5] J. E. Hopcroft and J. D. Ullman, Formal languages and their relation to automata, Reading, MA: Addison Wesley, 1969.
[6] A. P. Ershova, S. S. Lavrova, and M.R. Shura-Bura eds., Algoritmicheskii yazyk Algol-60. Peresmotrennoe soobshchenie. [Revised Report on the Algorithmic Language Algol 60], Moscow, USSR: Mir, 1965 (in Russian).
[7] F. Harary, R. Z. Norman, and D. Cartwright, Structural Models: An Introduction to the Theory of Directed Graphs, Wiley, 1966.
Опубликован
2017-06-04
Как цитировать
Мартыненко, Б. К. (2017). Синтаксически управляемая генерация тестов для процессоров регулярных языков. Компьютерные инструменты в образовании, (5), 17-45. извлечено от http://cte.eltech.ru/ojs/index.php/kio/article/view/1411
Выпуск
Раздел
Информатика
Материал публикуется под лицензией:
