Регуляризация контекстно-свободных грамматик на основе эквивалентных преобразований синтаксических граф-схем тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Федорченко, Людмила Николаевна
- Специальность ВАК РФ05.13.11
- Количество страниц 160
Оглавление диссертации кандидат технических наук Федорченко, Людмила Николаевна
Основные обозначения и сокращения.
Введение.
Положения, выносимые на защиту.
Глава 1. ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ ГРАММАТИК В СОВРЕМЕННЫХ СИСТЕМАХ ПОСТРОЕНИЯ ТРАНСЛЯТОРОВ
1.1. Обзор основных методов синтаксического анализа.
1.2. Способы задания синтаксических структур.
1.3. Эквивалентные преобразования грамматик в инструментальных средствах Уасс/Вгёоп.
1.4. Эквивалентность как отношение подобия на синтаксических структурах.
Выводы по главе 1.
Глава 2. ОПРЕДЕЛЕНИЕ И РАСПОЗНАВАНИЕ КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ
С ПОМОЩЬЮ СИНТАКСИЧЕСКИХ ГРАФ-СХЕМ.
2.1. Основные понятия.
2.2. Контекстно-свободные грамматики в регулярной форме.
2.3. Выводимость в КСР-грамматике.
2.4. Синтаксическая граф-схема.
2.5. Рекуррентный алгоритм построения синтаксической граф-схемы.
2.6. Достижимые вершины в синтаксической граф-схеме.
2.7. Синтез распознающих автоматов для КСР -грамматик.
2.8. Свойства синтаксической граф-схемы.
2.9. Леммы о существовании состояний распознавателя в синтаксической граф-схеме.
2.10. Основная теорема о языке.
Выводы по главе 2.
Глава 3. РЕГУЛЯРИЗАЦИЯ КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК
3.1. Синтаксическая модель языка.
3.2. Этап предварительной подготовки грамматики.
3.3.Этапы обработки исходного текста грамматики.
3.4. Рекурсивные нетерминалы.
3.4.1. Левая и правая рекурсии.
3.4.2. Свойство 'самовложенности.
3.5. Подстановка нетерминала.
3.6. Исключение рекурсивных нетерминалов.
3.7. Число состояний распознавателя, синтезируемого по КСР-грамматике.
3.8. Минимизация регулярных выражений и состояний распознавателя.
Выводы по главе 3.
Глава 4. ИНСТРУМЕНТАЛЬНАЯ СИСТЕМА ЭКВИВАЛЕНТНЫХ
ПРЕОБРАЗОВАНИЙ БулвТ
4.1. Описание, спецификации и дизайн системы.
4.2. Экранное размещение синтаксической граф-схемы.
4.3. Интерфейс пользователя.
4.4. Генерация тестов в системе ЭупОТ.
4.6.Пример преобразования рекурсивного нетерминала.
Выводы по главе 4.
Рекомендованный список диссертаций по специальности «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», 05.13.11 шифр ВАК
Синтаксически управляемая обработка данных1997 год, доктор физико-математических наук Мартыненко, Борис Константинович
Метод моделирования процедур в лингвистическом процессоре автоматизированных диалоговых систем управления2003 год, кандидат технических наук Плоткин, Борис Владимирович
Синтез распознавателей языков компьютерного моделирования объектов с конечным числом состояний1999 год, кандидат технических наук Муромцев, Виктор Владимирович
Разработка и исследование инструментальных средств многоязыковой трансляции2005 год, кандидат технических наук Фадеев, Роман Викторович
Особенности синтаксического анализа открытых интерфейсных контекстно-свободных языков2005 год, кандидат физико-математических наук Лапшин, Владимир Анатольевич
Введение диссертации (часть автореферата) на тему «Регуляризация контекстно-свободных грамматик на основе эквивалентных преобразований синтаксических граф-схем»
При построении синтаксического анализатора как составной части транслятора необходимо проводить эквивалентные преобразования грамматики реализуемого языка. Сейчас языковые технологии активно включаются в различные сферы нашей жизни, что привело к развитию современных транслирующих систем, ориентированных на разнообразный ассортимент вычислительных устройств во многих предметных областях. При этом наиболее остро проявилась проблема быстрой настройки (преобразования) синтаксического определения языка на ту форму, которая допускает автоматическую или ручную реализацию, а также проблема учёта ограничений выбранного метода синтаксического анализа. Первая проблема обусловлена разнообразием спецификаций реализуемых языков, диапазон которых простирается от обычной формы Бэкуса-Наура (БНФ) и языка разметки HTML, до двухуровневых и других видов грамматик. Вторая - ведёт либо к языковой неоднозначности, либо к недетерминированности распознающего автомата. Решение этих проблем связано с корректным отображением транслируемого языка во внутреннее машинное представление. Для этого следует эффективно использовать информацию о языке, определяя его синтаксис и статическую семантику в виде специальной КС-грамматикой (трансляционной), которая помимо основной своей функции порождения цепочек языка позволяет задавать трансляции, необходимые разработчикам.
Существующие подходы к реализации языков и обширный набор средств автоматического построения трансляторов как правило используют встроенные в инструментальные системы разработки эквивалентные преобразования, часть из которых выполняются в ходе построения анализатора, а часть вручную, что существенно замедляет процесс разработки и приводит к большому числу итераций. Стало очевидным, что необходимо выполнять предварительную обработку (препроцессинг) по приведению синтаксических определений языка к нужной форме с помощью автономного инструментария, позволяющего заранее сформировать синтаксис языка и оптимизировать анализатор, применением процедуры регуляризации исходной трансляционной грамматики с помощью эквивалентных преобразований. Такой инструмент должен иметь удобный интерфейс и должен обладать достаточным набором функций по выполнению преобразований.
Исследование этих преобразований и их применения в технологиях разработки трансляторов является актуальной темой исследования, поскольку ведёт к разрешению проблем языковой неоднозначности и недетерминированности при автоматическом построении анализатора.
Цель работы -и* задачи? исследования. Основной целью диссертационной работы является разработка методики и алгоритмов эквивалентных преобразований трансляционной грамматики при'обработке языка в системах построения трансляторов, позволяющих повысить эффективность их разработки.
Для достижения поставленной цели в диссертационной работе поставлены следующие задачи:
1. Анализ существующих подходов и методов синтаксического разбора при построениианализатора языка с целью определения текущей картины в области применения эквивалентных преобразований и определения/ возможностей для её улучшения.
2. Построение модели определения и распознавания языка на основе синтаксической граф-схемы с целью проверки свойств и ограничений* на входную трансляционную грамматику для автоматического синтеза распознавателя языка.
3. Разработка алгоритмафегуляризации грамматики^языка на основе эквивалентных преобразований синтаксической граф-схемы, позволяющего оптимизировать построенный анализатор.
4. Построение экспериментальной инструментальной программной1 системы, реализующей разработанные алгоритмы, для практической проверки на» практике предложенных новых методов на известных эталонных примерах.
В соответствии с целью и перечисленными^выше задачами'объектом исследования являются КСР-грамматики, а предметом исследования - эквивалентные преобразования КСР-грамматик, их свойства и ограничения при построении эффективных распознавателей языков.
Методы исследования. Для решения поставленных задач в работе используются методы теории формальных языков и автоматов, теории графов и методы объектно-ориентированного программирования.
Научной новизной обладают следующие результаты выполненных исследований:
1. Впервые сформулирована и доказана теорема об адекватности распознающего автомата, построенного на основе синтаксической графсхемы и подкласса КСР-грамматик. (Совпадение, порождаемых и распознаваемых'языков).
2. Разработан и исследован алгоритм регуляризации трансляционной грамматики на основе синтаксической граф-схемы-с целью получения минимального по числу состояний синтаксического анализатора.
3. Разработана инструментальная система? SynGT (Syntax Graph Transformation), позволяющая выполнять основные алгоритмы эквивалентных преобразований и алгоритм регуляризации'КСР^-грамматики.
Обоснованность и достоверность научных положений, основных» выводов w рекомендаций^ содержащихся в диссертации обеспечиваются* анализом состояния'исследований в области технологий»построения трансляторов (рассмотрены практически все технологии? начиная с 60-х^ годов прошлого века), корректным'применением!методов-исследований? корректностью формулировок и строгим построением^доказательств утверждений «и следствий; а также подтверждаются реализацией предложенных алгоритмов в инструментальной* системе SynGT и результатами ее экспериментального применения на^фрагментах реальных языков>программирования.
Практическая* ценность результатов, работы. Разработанные модели и алгоритмы направлены на^ разрешение проблемы эквивалентных преобразований ^регуляризации трансляционных грамматик и\представлены в виде экспериментальной программной системы, позволяющей; по сравнению с известными-подходами, повысить скорость подготовки специ фикации реализуемого языка в 3-4 раза, а также точнее определить разработчику языкового процессора необходимые затраты экономических, временных и кадровых ресурсов. Разработанная автором инструментальная система SynGT используется в организациях НИЦ БТС МО РФ (с 2005 г.) и в Санкт-Петербургском государственном университете аэрокосмического приборостроения (с 2009 г.) - в диссертации приложены 2 акта о внедрении.
Разработанный алгоритм регуляризации /ССР-грамматики^ позволяет проверить, является ли порождаемый ею язык регулярным? и,тем самыми оптимизировать синтезируемый>языковой процессор.
Разработанный способ спецификации5 языка с использованием синтаксической граф-схемы может быть применён-для тестирования; корректной работы анализатора. Алгоритмы для генерации- множества* тестовых предложений языка могут быть использованы при проведении-тестирования и в других подобных действующих системах построения трансляторов.
Реализация результатов работы. Исследования, отраженные в диссертации, применялись при построении компилятора для языка ANSI Си в совместном с INRIA (Франция) и институтом A.M. Ляпунова (МГУ) проекте «ОСС- Открытый компилятор языка Си», (проект № 14) и в проекте «Компилятор языка Си для цифровых процессоров» в 1995-98гг.
Результаты диссертационного исследования была использованы в рамках исследований, выполнявшихся во время стажировки в Будапештском институте Вычислительной техники Венгерской Академии Наук и при выполнении НИР по созданию транслятора языка Алгол-68, выполнявшейся в Ленинградском государственном университете.
Апробация результатов работы. Результаты диссертационного исследования докладывались на международном семинаре "Computer Networks" в Венгерской Академии наук, международных конференциях в Польше (2001, 2002, 2003), в Калининградском государственном университете (2008), серии международных конференций "Региональная информатика" в 1998, 2000, 2002, 2004, 2006, 2008 годах, серии Санкт-Петербургских межрегиональных конференциях "Информационная безопасность регионов^ России (ИБРР - 2005, 2007)".
Публикации. Основные результаты и выводы диссертационной работы опубликованы в 20 научных публикациях, две публикации - из списка ВАК.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, трёх приложений, списка использованной литературы и двух актов внедрения результатов диссертации. Объем диссертационной работы составляет 160 страниц машинописного текста, содержит 66 рисунков, 6 таблиц и приложения. Список литературы включает 81 наименование.
Похожие диссертационные работы по специальности «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», 05.13.11 шифр ВАК
Модели и реализация транслирующих компонентов системы функционального программирования2009 год, кандидат физико-математических наук Стасенко, Александр Павлович
Средства разработки и анализа алгоритмов решения задач структурного синтеза на графах2006 год, кандидат технических наук Бакулина, Мария Алексеевна
Исследование и разработка методов и средств реализации диаграммных графических языков САПР2007 год, кандидат технических наук Шаров, Олег Геннадьевич
Исследование и разработка эффективных методов реализации языков программирования1984 год, кандидат технических наук Лийб, Дональд Бернхардович
Синтаксические методы описания и обработки информации, представленной функциональными зависимостями и сигналами сложной формы1999 год, кандидат технических наук Мосунов, Сергей Евгеньевич
Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Федорченко, Людмила Николаевна
Основные результаты, полученные в- диссертационном исследовании состоят в следующем:
- Разработаны и реализованы алгоритмы эквивалентных преобразований грамматик с целью построения компактных и эффективных анализаторов языков, с улучшенными на 10-15-20%, по сравнению с известными системами из семейства компиляторов GNU характеристиками по эффективности и объему памяти. На этих алгоритмах построена* схема регуляризации трансляционной грамматики языка. Эквивалентные преобразования и метод регуляризации на их основе являются единственным средством расширить область применимости метода синтаксического анализа языка, который фиксирован в системе построения-трансляторов.
- Предложен метод построения простых и естественных распознавателей языков для достаточно большого класса грамматик. После того, как процедура эквивалентных преобразований закончится, в качестве результата синтаксического анализа рассматривается «описание» его всех возможных маршрутов в синтаксической граф-схеме в виде последовательности меток, специфицирующих эти маршруты (пути) При такой постановке синтаксический анализ рассматривается как перевод (трансляция) предложения языка в строку тт, представляющую собой вызовы семантических процедур для генерации машинного кода.
- Разработана специальная инструментальная система эквивалентных преобразований КСР-грамматик SynGT, обеспечивающая автоматизированную настройку синтаксиса реализуемого языка в рамках простого метода синтаксического разбора. Система является автономной и может быть использована и в других технологиях разработки. В настоящий момент система БупСТ позволяет применять эквивалентные преобразования к правилам любой приведённой КС-грамматики в регулярной.форме. Класс трансляционных грамматик, удовлетворяющих методу синтаксического анализа, изложенному в главе 2, порождает детерминированные языки, определение которых дано Д.Кнутом.
- В работе выбор метода синтаксического анализа был продиктован, следующими соображениями:
- эффективностью разбора текста.(линейное время);
- достаточно широким классом- допустимых, грамматик с исчерпывающим определением его грамматических свойств (порождающие детерминированные языки).
- простым*набором базисных эквивалентных преобразований.
- Эффективность метода построения анализатора' достигается в реI зультате предварительного этапа-обработки; входной КСР-грамматики, в результате чего синтезируются таблицы состояний магазинного автомата. Если синтез таблиц заканчивается успешно (все состояния распознавателя существуют и конечны), то программа разбора, использующая построенные таблицы состояний, проводит разбор цепочки длины п за время Сп.
- Методы, изложенные в диссертационной работе, были использованы при проведении ряда научно-исследовательских работ. В дальнейшем разработанные методы и программное средство БупОТ будут применены в перспективных приложениях по обработке языков для различных предметных областей.
- Разработанная методика и алгоритмы эквивалентных преобразований трансляционной грамматики могут быть эффективно использованы в проектах различной направленности, связанных с реализацией языка для различных предметных областей, в том?числе на всех уровнях в системах обеспечения информационной безопасности, например, при обработке и анализе правил политик безопасности, определении поведенческих сценариев, проверке их на непротиворечивость, разработке тестов и тестовых процедур, поиске областей уязвимости кода приложений, решении задач обработки больших по объёму спецификаций требований программного проекта, документы для которых могут содержать сотни и тысячи пунктов требований, в задаче преобразования внутренних форматов данных, например, КОР-формата, описывающего ЮЕРО-диаграмму, к формату данных, описывающему иМ1-диаграмму, и многие другие.
- Алгоритм регуляризации грамматики может применяться для создания миниатюрных языковых процессоров во встраиваемое ПО.
- Достигнутый уровень автоматизации при использовании системы эквивалентных преобразований совместно с выбранной технологией автоматизации проектирования трансляторов составляет от 50% до 100% в зависимости от специфики проекта. Снижение трудозатрат - примерно в 3—4 раза.
Заключение
Список литературы диссертационного исследования кандидат технических наук Федорченко, Людмила Николаевна, 2009 год
1. Ахо А. В., Сети Р., Ульман Д. Д. Компиляторы: принципы, технологии и инструменты. М.: Вильяме, 2001.
2. Ахо А. В., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1. Синтаксический анализ, 612 с. Т.2. Компиляция, 487 е., М.:Мир,1978.
3. Баранов С.Н. Реализация системы символьных вычислений МИНИСАК на языке Форт. / Л.: Наука, Математич. методы постр. и анализа алг., 1990. С.3—15.
4. Баранов С.Н. Система символьных вычислений МИНИСАК// Программирование, 3, 1993. С.62-73.
5. Глушков В.М. Синтез цифровых автоматов. Физматгиз. 1962.
6. Иванищев В.В., Марлей В.Е. Введение в теорию алгоритмических сетей. СПб: Изд. СПбГТУб 2000,179 с.
7. Издательство журнала «Открытые системы» Электронный ресурс. URL:http://www.osp.ru/os/2009/03/8158133/
8. Клини С. Представление событий в нервных сетях. / В кн.: Автоматы. М.:ИЛ,1956,с.15-67.
9. Кнут Д.О. О переводе (трансляции) языков слева направо// Сб. «Языки и автоматы»- М.:Мир. 1975. С.9-42.
10. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. М.:Мир. 1979.
11. Марлей В.Е. Алгебра алгоритмических сетей. //Теоретические основы и прикладные задачи интеллектуальных информационных технологий. СПб.: Изд. «Анатолия», 1998.С.200-207.'.'.;-■■■ .••.-. 138 •■■
12. Марлей В.Е., Морозов В.П. Интерпретация алгоритмических сетей как языковых конструкций. //Проблемы автоматизации в научных и производственных процессах М::Наука, 1985.-С.37-46.
13. Мартыненко: Б.К. Синтаксически управляемая обработка;данных. СПб, СПбГУ, 1997. 362 с.15: Опалева Э;А., Самойленко В.П., Семенова О.Н. Формальные методы описания перевода: Учеб. пособие. СПб.: СПбГЭТУ., 2000.
14. Пересмотренное сообщение об Алголе 68. / Под ред. А. ван Вейнгаар-ден. Пер. с англ. М.: Мир, 1979. 533 с.
15. Федорченко Л.Н, Извлечение крайней рекурсии из КСР-грамматики в системе SynGT, Труды СПИИРАН, вып.1,т. 1. — СПб: СПИИРАН, 2002, с.350-359 ; .
16. Федорченко:Л;Н., Заболотский В.П. Лингвистический инструментарийш задачах обеспечения информационной безопасности. СПб.: Изд-во Политехи^ ун-та, журнал «Проблемы информационной безопасности. Компьютерные системы» № 4, 2008 г., С. 60-68
17. Федорченко Л.Н., О регуляризации контекстно-свободных грамматик. Изв. вузов. Приборостроение, 2006. Т.49, №11, с.50-54.
18. Федорченко Л.Н. Об одном алгоритме синтаксического анализа языков, порождаемых R-грамматиками. / В сб. «Алгоритмы и системы автоматизации научных исследований и проектирования». М.: Наука, 1980.
19. Федорченко Л.Н. «О числе состояний распознавателя, синтезированного по контекстно-свободной грамматике в регулярной форме». В сб. «Информационно-вычислительные проблемы автоматизации, научных исследований». М.: Наукам983.
20. Aho A.V. and Johnson S.C. LR parsing / Computing. Surveys 6:2,1974 P.99-124
21. Aho, A.V. and Ullman, J.D. A technique for speeding up LR(k) parsers / SIAM J. Computing 2:2, 1973, pp 106-127.
22. Anderson Т., Eve J. and Horning J. J. Efficient LR(1) parsers/ Acta Informática 2:1, 1973, pp' 12-39.
23. B.W.Kernigan, D.M.Ritchie. The С Programming Language. Second Edition. Prentice Hall, 1988.
24. Baranov S.N. and Lavarenne C. Open С Compiler in Forth. // EuroForth'95 Conf.Proc. 27-29 Oct. 1995 Schl.Dagstuhl, Germany.
25. Bochman G.V. and Ward P. Compiler writing system for attribute grammars / Computer J. 21:2, 1978, pp 144-148.
26. Charles Donnelly and Richard Stallman, Bison, The YACC-compatible Parser Generator Электронный' ресурс.: http://dinosaur.compilertools.net/#bison
27. Cremers А В , and Ginsburg S., Context-free grammar forms /J Comput SystScI 11 (1975), 86-117.
28. De Remer F. and Penello T. Efficient computation of LALR(1) look-ahead sets / TOPLAS 4:4, 1982. P. 615-649.
29. De Remer F. Simple LR(k) grammars / Comm ACM 14:7, 1971, pp 453460.
30. Dick Grune and Ceriel Jacobs Parsing Techniques. A Practical Guide , Ellis Horwood, Chichester, England (1990), p.322.
31. Dick Grune Two Level grammars are more expressive than Type 0 grammars or are they?, Dept. of Mathematics and Computer Science Vrije Uni-versiteit, De Boelelaan 1081, HV Amsterdam. Электронный ресурс.: dick@cs.vu.nl
32. Early J. Ambiguity and precedence in syntax description / Acta Informática 4:2, 1975, pp 183-192.
33. Floyd R.W. Syntactic analysis and operator precedence / JACM, 10, (July 1963), 316p.
34. Foster, J.M. A syntax improving program / Computer J.11:1, 1968. P. 3134.
35. Ginsburg S. A survey of grammar forms / Acta Cybernetica, 3(4):269-280, 1977.
36. Ginsburg S., Harrison Michael A.: Bracketed context free languages. (2005)
37. Graham S. L. On Bounded Right Context Languages and Grammars / SIAM J. Comput. 3(1974), 224-254.
38. Graham S.L. Extended precedence, bounded right context languages, and deterministic languages (extended abstract)// Proc. Symp. on Switching and Automata Theory, Oct. 1970, pp. 175-180.
39. Gray J. N. and Harrison M. A., On the covering and. reduction problems for context free grammars. Journal of the. ACM 19, 675-698. 1972.
40. Harrison M. A., and Havel I. M. Strict Deterministic Grammars,, Journal of Computer and Systems Science, Vol. 7 pp. 237-277, 1973.
41. Hotz G. Normal-form transformations of context-free grammars / Acta Cybernetica, 4(1):65-84, 1978.
42. HTML Материал из электронной энциклопедии Википедия Электронный ресурс. URL:http://ru.Wikipedia.org/wiki/HTML
43. Hunt III Н. В. and Rosenkrantz D. J., Complexity of grammatical similarity relations // In: Procs of a Conf. on Theoretical Computer Science Waterloo 1977, 139-145.
44. Johnson S.C. YACC Yet Another Compiler-Compiler. // Сотр. Sci. Tech. Rep.39. Bell Telephone Laboratories. 1975. New Jersey: Murray Hill. Электронный ресурс. URL: http://www.usc.edu/~ram1335/yacc.doc
45. Kenichi Taniguchi, Tadao Kasami: A Result on the Equivalence Problem for Deterministic Pushdown Automata/J. Comput. Syst. Sci. 13(1): 38-50 (1976)
46. KnuthDonald E. Backus Normal Form vs. Backus Naur Form // Communications of the ACM 7 (12),1964: p. 735-736.
47. Korenjak A. J. and Hopcroft J. E. Simple deterministic languages // IEEE Conf. Record.of 7th Annual Symposium on Switching and Automata Theory, 1966, pp.36^16.
48. Koster C.H.A. et all. CDL3 manual- Электронный ресурс. URL: http:www.es. ru.nl/~kees/vbcourse/ivbstuff/ cdl3.pdf.
49. Koster C.H.A. Two-level Grammars// Budapest. Seminar on Automata and Mathematical Linguistics, Mathematisch Instituut, May 1970.
50. Krai J. and Demner J.: Semi-top-down syntactic analysis//Report UVT 6/73/M Institute of Computation Technique. August 1973.
51. Kral J., Demner J.: Almost Top-Down Analysis for generalized LR(k) Grammars. Methods of Algorithmic Language Implementation 1975: 149-172
52. Lewis P., Rozenkrantz D., Stearns R. Attributed Translations/ J. Computer and System Sciences 9(3) (1974) 279-307.
53. Lewis P.M. Compiler Design Theory. Addison-Wesley. 1996.
54. M.Sintzoff, "Existence of a van Wijngaarden syntax, for every recursively enumerable set", Annales de la Societe Scientifique de Bruxelles 81(11), pp.115-118 (1967).
55. Mc Naughton, R. The development of formal language theory since 1956 / Internat. J. Found. Comput. Sci. (1990), p. 355-368.
56. McNaughton R. The theory of automata. A survey in "Advances in Computers,". F. L. Alt, Ed., vol. II, pp. 379-421,. Academic Press, N.Y.
57. Nijholt A. and Soisalon-Soininen E. Ch(k) grammars: A characterization of LL(k) languages. ln:Mathematical Foundations of Computer Science, 8th Conf., J. Becvar (ed.), Springer-Verlag, Berlin, Lect. Notes in Comput. Sci. 74, 1979. P. 390-397.
58. Open С Compiler. SYNTAX ANALYZER. GRAMMAR REQUIREMENTS SPECIFICATIONS. File GRSRS.txt Совместный СПИИРАН и INRIA проект- 1995.
59. Paull M. and Unger S. Structural equivalence of context-free grammars / Jornal of Computer and System Sciences 2 (1968), 427-463.
60. Paull M.C., and 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.
61. Prather R.E. Regular Expressions for Program Computations, American Mathematical Monthly, 104, No. 2, 1997.
62. Raiha K.-J., Saarinen M., Sarjakoski M., Sippu S., Soisalon-Soininen E. and Tienari M. // Revised report on the compiler writing system HLP78, Report A-1983-1, Dept. of Computer Science, University of Helsinki, 1983.
63. Reynolds J.C., and Haskell R. Grammatical coverings. Unpub. memorandum, Syracuse University, 1970. From ACM Transactions on Programming Languages and Systems (TOPLAS). V. 9 , Issue 4 (Oct 1987), pp.543-566 1987 ISSN:0164-0925.
64. Rozenkrantz D.J., Stearns R.E. Compiler Construction. An Advanced Course: Springer-Verlag, 2001.
65. Salomaa K. and Yu S. Decidability of structural equivalence of E0L grammars / Theoretical Computer Science 82 1991.
66. Soisalon-Soininen E. and Ukkonen E. A method for transforming grammars into LL(k) form / Acta Informatica 12, 1979. P. 339-369.
67. Stearns R.E. Deterministic top-down parsing // Proc. 5th Annual Princeton Conf. on Information Sciences and Systems, 1971. P. 182-188.
68. Linger S.H. A global parser for context-free phrase structure grammars, CACM, 11 (April 1968), 240-246; 11 (June 1968), 427c.
69. Vern Paxson Flex- a fast scanner generator, Электронный ресурс. URL:http://dinosaur.compilertools.net/.
70. Wirth N., Weber H.: Euler: A Generalization of Algol and Its Formal Definition / Comm. ACM 9(1): 11-23, and 9(2): 89-99, 1966.
71. Wirth Niklaus: What can we do about the unnecessary diversity of notation for syntactic definitions? CACM, Vol. 20, Issue 11, November 1977. P. 822823.
72. Wood D. The theory of left factored languages/ Computer J. 12:4, 1969, pp.349-356.1. ТЕРМИНЫ
73. Программное обеспечение (ПО) Software. в области вычислительной техники и программирования - это совокупность всей информации, данных и программ, которые обрабатываются компьютерными системами.
74. Языковым процессором language processor. называют ПО, которое транслирует язык программирования в машинный код.
75. Транслятор, использующий в качестве входного языка, язык, близкий к машинному (автокод или ассемблер), традиционно называют ассемблером.
76. Компиляция compilation. трансляция программы на язык, близкий к машинному. Трансляция программы, составленной на исходном языке, в объектный модуль (осуществляется компилятором)
77. Компилятор compiler. -1). Машинная программа, используемая для компиляции.2.. Программа (или техническое средство), выполняющая компиляцию.3.. Транслятор, выполняющий преобразование программы, составленной-на исходном языке, в объектный модуль.
78. Прямые методы трансляции это эвристические методы, в которых для каждой-конструкции языка разрабатывался свой алгоритм перевода в машинный эквивалент. Их недостатки - они медленные и не носили структурный характер.
79. Основой любого языка является алфавит это набор допустимых элементарных знаков (букв, цифр и служебных знаков). Знаки объединяются в слова (цепочки) - элементарные конструкции языка-; рассматриваемые как неделимые символы языка, имеющие смысл
80. Лексика я зыка это словарный состав языка вместе с описанием способов их представления.
81. Регуляризация КС-грамматики это процесс эквивалентного преобразования произвольной КС грамматики G в КС грамматику G1 в регулярной форме (КСР-грамматику), причем такой, что из нее исключаются все самовставленные нетерминальные символы.
82. Часть таких преобразований реализована в системе SynGT (Syntax Graph Transformations)^ ,22, 23.
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.