Вопросы сложности анализа конъюнктивных грамматик тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

1 Введение

2 Определения и простейшие свойства

2.1 Грамматика.

2.2 Формулы.

2.3 Вывод.

2.4 Длина вывода

2.5 Дерево вывода.

2.6 Линейные конъюнктивные грамматики.

2.7 Однозначные и неоднозначные грамматики.

3 Выразительные возможности конъюнктивных грамматик

3.1 Грамматики для классических не-контекстно-свободных языков.

3.2 Грамматики для некоторых других абстрактных языков

3.3 Построение грамматик для языков всех вычислений данного вычислительного устройства.

3.4 Грамматики для простейших языков программирования

4 Нормальные формы

4.1 6-конъюнкты.

4.2 Единичные конъюнкты.

4.3 Бинарная нормальная форма

4.4 Линейная нормальная форма.

5 Распознавание и синтаксический анализ

5.1 Алгоритм для грамматик в бинарной нормальной форме

5.2 Алгоритм для грамматик в линейной нормальной форме

5.3 Алгоритм для грамматик общего вида.

5.4 Алгоритм для линейных грамматик общего вида.

Оглавление

5.5 Алгоритм нисходящего разбора.

5.6 Метод рекурсивного спуска.

5.7 Алгоритм восходящего разбора

5.8 Сравнение алгоритмов синтаксического анализа.

6 Задача принадлежности

6.1 Полиномиальное решение задачи принадлежности.

6.2 Р-полнота задачи принадлежности.

6.3 Р-полнога задачи принадлежности для линейных конъюнктивных грамматик.

7 Задача генерации строк

7.1 Постановка задачи как задачи распознавания свойств

7.2 Сложность для конъюнктивных и линейных конъюнктивных грамматик.

7.3 Сложность задачи для распространённых вычислительных устройств.

7.4 Анализ результатов.

8 Вопросы описательной сложности

8.1 Терминология

8.2 Описание контекстно-свободных языков конъюнктивными грамматиками.

8.3 Нерекурсивная оценка роста описательной сложности

9 Дополнительные вопросы

9.1 Неразрешимые задачи.

9.2 Сложность распознавания конъюнктивных языков по памяти

9.3 Связь с другими семействами языков.

9.4 Рост длин строк из конъюнктивных языков.

9.5 Конъюнктивные грамматики и системы языковых уравнений

А.2 Написание грамматики.226

А.З Использование сгенерированных анализаторов.227

А.4 Алгоритмы синтаксического анализа.229

А.4.1 Табличный алгоритм для произвольных грамматик 229 А.4.2 Нисходящий конъюнктивный алгоритм SLL(A) . . . 230

в заключение дадим краткий обзор всех существующих результатов по конъюнктивным грамматикам, а также рассмотрим некоторые представляющие интерес открытые проблемы.i . Введён класс конъюнктивных грамматик, обобщающих контекстно-свободные грамматики путём введения явной операции конъюнкции, имеющей семантику теоретико-множественного пересечения, в формализм правил [34, 35, 36].i i . Установлена возможность описания конъюнктивными грамматиками некоторых важных абстрактных языков — {а"Ь'^с" I п ^ 0}, [wcw 1 W 6 {a,b}*} и др. [34, 35, 36 .Ш. Ряд существенных понятий теории контекстно-свободных языков распространён на случай конъюнктивных грамматик: вывод, дерево вывода, однозначность и др. [34, 36].iv. Рассмотрено понятие длины вывода как меры вычислительной сложности конъюнктивных грамматик [34, 36].V . Введён класс линейных конъюнктивных грамматик, обобщающий понятие линейной контекстно-свободной грамматики и сохраняющий некоторые важные свойства последних [36].vi . Показано, что из любой конъюнктивной грамматики можно удалить так называемые е-конъюнкты и единичные конъюнкты, обобщающие понятия контекстно-свободного е-правила и цепного (chain) правила [34, 35, 36].Глава, 10. Заключение 221 У11. Введена бинарная нормальная форма для конъюнктивных грамматик, обобщающая бинарную нормальную форму (нормальную форму Хомского) для контекстно-свободных грамматик; дан алгоритм приведения произвольной конъюнктивной грамматики к бинарной нормальной форме УШ. Введена линейная нормальная форма для линейных конъюнктивных грамматик, обобщающая линейную нормальную форму для линейных контекстно-свободных грамматик; дан алгоритм приведения произвольной линейной конъюнктивной грамматики к бинарной нормальной форме [36].1х. Алгоритм распознавания и синтаксического анализа Соске Kasami-Younger обобщён на случай конъюнктивных грамматик в бинарной нормальной форме. Сложность полученного алгоритма —

0(п^) по времени и О(п^) по памяти — такая же, как и в контекстно свободном случае. Результат представлен в [34, 36].X. Известный алгоритм распознавания и синтаксического анализа для контекстно-свободных грамматик в линейной нормальной форме обобщён на случай конъюнктивных грамматик в линейной нормальной форме. Сложность полученного алгоритма — (9(?г^) по времени и 0{п) по памяти — такая же, как и в контекстно свободном случае. Результат представлен в [36].х1. Алгоритм распознавания и синтаксического анализа С г а Ь а т -

Нагг180п-Ки720 для произвольных контекстно-свободных грамматик обобщён на случай произвольных конъюнктивных грамматик. Сложность полученного алгоритма — 0{п^) по времени и О(п^) по памяти — такая же, как и в контекстно свободном случае. Показано, что простая модификация этого алгоритма позволяет ему работать на линейных конъюнктивных грамматиках за время 0{п^), используя 0{п) памяти. Результат представлен в [39].хи. Алгоритм распознавания и синтаксического анализа ЪЬ{к) для контекстно-свободных грамматик обобщён на случай конъюнктивных грамматик путём введения древесно структурированной магазинной памяти в синтаксический анализатор; этот алгоритм имеет сложность, пропорциональную длине вывода распознаваемой строки [37 .Глава 10. Заключение 222 xi i i . Метод рекурсивного спуска (вариант ЬЬ{к), удобный для ручной

реализации) обобщён на случай конъюнктивных грамматик [37].xiv. Алгоритм распознавания и синтаксического анализа Generalized L R (обобщённый LR) для произвольных контекстно-свободных грамматик обобщён на случай произвольных конъюнктивных грамматик. Сложность полученного алгоритма колеблется от линейной до кубической. Результат представлен в [40].XV. Показана, что общая задача принадлежности для конъюнктивных грамматик разрешима за полиномиальное время — О(п^), где п — суммарная длина записи грамматики и входной строки [39].xvi. Показана Р-полнота задачи принадлежности для конъюнктивных грамматик [38, 39].xvii . Показана Р-полнота задачи принадлежности для линейных конъюнктивных грамматик [39 .xviii . Показана NP-полнота задачи определения существования строки, лексикографически предшествующей данной строке и принадлежащей данному конъюнктивному языку. Результат впервые представляется в данной работе.xix. Показывается алгоритмическая неразрешимость следующих задач распознавания свойств конъюнктивных грамматик; пустота, универсальность, конечность, эквивалентность, включение, контекстно-свободность, регулярность, однозначность. Часть из этих результатов формулируется в [34, 35, 36]; в полном объёме они представляются впервые.XX. Показано, что замыкание семейства контекстно-свободных языков относительно пересечения — собственное подмножество семейства конъюнктивных языков [36 .xxi. Показано, что замыкание семейства детерминированных контекстно-свободных языков относительно всех теоретико множественных операций — собственное подмножество семейства конъюнктивных языков [40].xxii . Показывается, что любой конъюнктивный язык является контекстно-зависимым. Результат представляется впервые.Глава 10. Заключение 223 конъюнктивных языков является собственным подмножеством семейства контекстно-зависимых языков [36].xxiv. Показывается, что рост описательной сложности при переходе от описания контекстно-свободных языков конъюнктивными грамматиками к описанию контекстно-свободными является неограниченным относительно числа нетерминальных символов и относительно числа правил [36].XXV. Показывается, что рост описательной сложности при переходе от описания контекстно-свободных языков конъюнктивными грамматиками к описанию контекстно-свободными является рекурсивно неограниченным относительно общей длины записи грамматики. [36].xxvi. Даётся характеризация конъюнктивных грамматик системами языковых уравнений, разрешёнными относительно неизвестных и использующих операции конкатенации, объединения и пересечения xxvii. Написан генератор синтаксических анализаторов Whale Calf [52], реализующий все описанные в данной работе алгоритмы распознавания и синтаксического анализа.

1. A. V . Aho, R. Sethi, J . D. Ullman. Compilers: principles, techniques and tools, Addison-Wesley, Reading, Mass., 1986.

2. A . V . Aho and J . D. Ullman, The Theory of Parsing, Translation andCompiling, Vol. I: Parsing, Prentice-Hall, 1972.

3. J. Autebert, J . Berstel and L . Boasson, "Context-Free Languages andPushdown Automata", Handbook of Formal Languages, Vol. 1, pp. 111174, Springer-Verlag, Berlin, 1997.

4. Y . Bar-Hillel, M . Perles, E. Shamir, "On formal properties of simple phrase-structure grammars", Zeitschrift für Phonetik, Sprachwis senschaft, und Kommunikationsforschung, 14 (1961), 143-177.

5. A . K . Chandra, D. C. Kozen, L. J . Stockmeyer, "Alternation", Journalof the ACM, 28 (1981) 114-133.

6. N . P. Chapman, LR Parsing, Cambridge University Press, 1987.

7. J. Dassow, Gh. Päun, Regulated Rewriting in Formal Language Theory,Akademie-Verlag, Berlin, and Springer-Verlag, Berlin, 1989.

8. J. Dassow, G. Päun, A . Salomaa, "Grammars with Controlled Derivations", in Handhook of Formal Languages, Vol. 2, pp. 101-154, SpringerVerlag, Berlin, 1997.

9. F . DeRemer, "Simple LR(A;) grammars". Communications of the ACM,14:7 (1971), 94-102.

10. J . Earley, "An efficient context-free parsing algorithm". Communicationsof the ACM, 13:2 (1970), 94-102.

11. R. W. Floyd, "On the non-existence of a phrase-structure grammar forAlgol 60", Communications of the ACM, 5 (1962), 483-484. Литература 237

12. S. Ginsburg, S. A . Greibach and M . A . Harrison, "One-way stack automata", Journal of the ACM, 14:2 (1967) 389-418.

13. L. M . Goldschlager, "The monotone and planar cirquit value problemsare log space complete for P", SIGACT News, 9:2 (1977), 25-29.

14. I. Gorun, "A hierarchy of context-sensitive languages". Lecture Notes inComputer Science, 45 (1976), 299-303.

15. S. L . Graham, M . A . Harrison, "Parsing of general context-free languages", Advances in Computers, 14 (1976) 77-185.

16. S. L . Graham, M . A . Harrison, W. L. Ruzzo, "An improved context-freerecognizer", ACM Transactions of Programming Languages and Systems, 2:3 (1980) 415-462.

17. M . A . Harrison, Introduction to formal language theory, Addison-Wesley,Reading, Mass., 1978.

18. J. Hartmanis, "On the succinctness of different representations of languages", SI AM Journal on Computing, 9 (1980), 114-120.

19. J. Hartmanis, "On Godel speed-up and succinctness of language representations", Theoretical Computer Science, 26 (1983), 335-342.

20. T. Jiang, B. Ravikumar, "A note on the space complexity of some decision problems for finite automata". Information Processing Letters 40 (1991) 25-31.

21. N . Jones, "Space-bounded reducibility among combinatorial problems",Journal of Computer and System Sciences, 11 (1975) 68-85.

22. T. Kasami, "An efficient recognition and syntax-analysis algorithm forcontext-free languages". Science Report AFCRL-67-758, A i r Force Cambridge Research Laboratory, Bedford, Mass., 1965.

23. D. E . Knuth, "On the translation of languages from left to right". Information and Control, 11 (1967), 269-289. Литература 238

24. D. Е. Knuth, "Top-down syntax analysis", Acta Informática, 1 (1971),79-110.

25. W. Kuich, "Semirings and Formal Power Series: Their Relevance to Formal Language and Automata", Handbook of Formal Languages, Vol. 1, 609-677, Springer-Verlag, Berlin, 1997.

26. R. Ladner, R. J. Lipton, L . J. Stoclcmeyer, "Alternating pushdown andstack automata", SI AM J. Comput, 13 (1984) 135-155.

27. M . Latta, R. Wall, "Intersective context-free languages", Lenguajes Naturales у Lenguajes Formales IX, Barcelona, 1993, 15-43.

28. P. M . Lewis, R. E. Stearns, "Syntax-directed transduction", Journal ofthe ACM, 15:3 (1968), 465-488.

29. P. М. Lewis, R. E. Stearns, J . Hartmanis, "Memory bounds for recognition of context-free and context-sensitive languages", IEEE Conference Record on Switching Circuit Theory and Logical Design, Ann Arbor, Michigan, 1965, 191-202.

30. L. Y . Liu and P. Weiner, "An infinite hierarchy of intersections ofcontext-free languages". Mathematical Systems Theory, 7 (1973) 187192.

31. E. Moriya, "A grammatical characterization of alternating pushdownautomata". Theoretical Computer Science, 67 (1989) 75-85.

32. A . Охотин, "0 расширении формализма контекстно-свободныхграмматик операцией пересечения", Труды IV Международной конференции "Дискретные модели в теории управляюищх систем", (2000) 106-109.

33. А. Okhotin, "Conjunctive grammars", in Pre-proceedings of DGAGRS2000, Dept. of Computer Science, University of Western Ontario, London, Ontario, Canada. Report No. 555 (2000).

34. A. Okhotin, "Conjunctive Grammars", final revision of [35], Journal ofAutomata, Languages and Combinatorics, 6:4 (2001), 519-535.

35. A . Okhotin, "Top-Down Parsing of Conjunctive Languages", Grammars,5:1 (2002), 21-40. Литература 239

36. А. Охотин, "О Р-полноте задачи принадлежности дляконъюнктивных грамматик", Дискретная математика и математическая кибернетика: труды международной школысеминара, Ратмино, 31 мая-З июня 2001 г., стр. 24.

37. А. Okhotin, "А recognition and parsing algorithm for arbitrary conjunctive grammars", Theoretical Computer Science, в печати.

38. A . Okhotin, " L R parsing for conjunctive grammars". Grammars, 5:2(2002), в печати.

39. A . Охотин, "Конъюнктивные грамматики и системы языковыхуравнений". Программирование, 28:5 (2002), в печати.

40. А. Okhotin, "О сложности задачи генерации строк", сдано вредакцию журнала "Дискретная математика".

41. Н. G. Rice, "On completely recursively enumerable classes and their keyarrays", Journal of Symbolic Logic, 21 (1956) 304-341.

42. G. Rozenberg, A . Salomaa, Cornerstones of Undecidability, PrenticeHall, 1994.

43. W. Rytter, "On the recognition of context-free languages", 5th Symposium on Fundamentals of Computation Theory, Lecture Notes in Computer Science, 208 (1985), 315-322.

44. K . Sikkel, A . Nijholt, "Parsing of context-free languages", Vol. 2, pp.61-100, Springer-Verlag, Berlin, 1997.

45. V . Strassen, "Gaussian elimination is not optimal", Numerische Mathematik, 13 (1969), 354-456.

46. I. H. Sudborough, " A note on tape-bounded complexity classes and linear context-free languages". Journal of the Association for Computing Machinery, 22:4 (1975), 499-500.

47. M . Tomita, Efficient Parsing for Natural Language, КЪшет AcademicPubhshers, 1986.

48. L. G. Valiant, "General context-free recognition in less than cubic time".Journal of Computer and Systems Sciences, 10 (1975), 308-315.

49. H. VoUmer, Introduction to Circuit Complexity, Springer-Verlag, Berhn,Heidelberg, 1999. Литература 240

50. Whale Calf, a parser generator for conjunctive grammars,http://www.cs.queensu.ca/home/okhotin/whalecalf/.

51. D. Wotschke, "The Boolean Closures of Deterministic and Nondeterministic Context-Free Languages", Lecture Notes in Computer Science, 1 (1973), 113-121.

52. D. Wotschke, "Nondeterminism and Boolean Operations in PDAs", Journal of Computer and Systems Sciences, 16:3 (1978), 456-461.

53. D. H . Younger, "Recognition and parsing of context-free languages intime n^", Information and Control, 10 (1967), 189-208.

54. S. Y u , "Regular Languages", in Handbook of Formal Languages, Vol. 1,41-110, Springer-Verlag, Berlin, 1997.