- •1.Системы программирования. Основные понятия и классификация.
- •2.Процесс компиляции. Основные понятия о процессе компиляции.(48)
- •3.Грамматики и классификация по Хомскому. Способы описания синтаксиса языков программирования.(стр43)
- •4.Лексический анализ. Основные понятия.(50)
- •5.Задачи синтаксического анализа. Основные понятия, канонические формы, используемые в синтаксическом анализе (Префиксная и постфиксная записи выражений.) (58)
- •6.Определение семантики языков на основе средств логического программирования. Определение базисных операторов на языке исчисления предикатов.
- •7.Теория взаимодействующих процессов. Основные принципы и определения.
- •8. Теория взаимодействующих процессов. Определения операций над следами.
- •9. Теория взаимодействующих процессов. Определение процесса.
- •10 Теория взаимодействующих процессов. Определение операций над процессами.
- •11. Параллельное программирование. Основные понятия на основе теории взаимодействующих процессов.
- •12. Основные принципы объектно-ориентированного программирования.
- •13. Порождения и их представления в виде синтаксических деревьев.
- •14. Способы представления процессов в теории взаимодействующих процессов (теоретико-множественное, процедурное, с помощью выражений над процессами).
- •15. Нисходящий синтаксический анализ.
- •16.Восходящий синтаксический анализ.
- •17.Этапы синтеза. Распределение памяти.
- •18. Принципы программирования на языке оссам.
15. Нисходящий синтаксический анализ.
Задача нисходящего анализа, как правило, сводится к нахождению левого порождения. Процесс нисходящего анализа начинается с символа предложения с последующей генерацией предложения языка. Рассмотрим в качестве примера язык вида {x m y n |m, n > 0}, определяемый следующими продукциями: S -> XY X -> xX X -> x Y - >yY Y -> y
После генерации знак предложения подчеркивается во входной строке.
Каждому этапу синтаксического анализа соответствуют три позиции таблицы: входная строка с подчеркнутыми символами, текущая продукция, а также текущее состояние сентенциальной формы. В конце синтаксического анализа все знаки входной строки подчеркнуты, а сентенциальная форма полностью совпадает с заданной строкой.
На каждом этапе первый неподчеркнутый символ определяется как входной символ и используется для разбора. Если в сентенциальной форме генерируется терминал, появляется еще один подчеркнутый символ. Принятие решений при нисходящем синтаксическом разборе обычно основывается на символе или последовательности символов предпросмотра. Под символом предпросмотра здесь имеется в виду либо текущий входной символ, либо символ, обозначающий признак конца строки. Существуют грамматики, поддерживающие методы нисходящего синтаксического анализа с одним символом предосмотра. Это -так - называемые LL(1) -грамматики. Термин LL(1) означает следующее :первая буква L определяет направление чтения слева
( Left ) направо,вторая буква L определяет использование левых ( Leftmost) порождений, цифра 1- один символ предосмотра. Соответственно LL(1) - язык определяется как язык, генерируемый посредством LL(1) -грамматики.
16.Восходящий синтаксический анализ.
Задача восходящего анализа, как правило, сводится к нахождению правого порождения. Рассмотрим в качестве примера рассмотренный в предыдущих разделах язык {x m y n |m, n > 0}, определяемый следующими продукциями: S -> XY X -> xX X -> x Y - >yY Y -> y
В отличие от нисходящего, при восходящем синтаксическом анализе этапы порождения определяются в противоположном порядке, то есть:xxxyy=> xxX yy=> xXyy=> Xyy=> XyY=> XY=> S. Применение продукции грамматики на каждом этапе предусматривает
замену правой части продукции ее левой частью, состоящей из одного символа.
При восходящем синтаксическом анализе правые части продукции
не распознаются до тех пор, пока не будут полностью считаны. В связи с этим требуется хранение частично распознанных правых частей продукций до замены их соответствующими левыми частями. Для этой цели используется стек. Таким образом, основные этапы процесса восходящего синтаксического анализа выражаются с помощью двух типов действий.
Занесение последнего считанного символа в стек - действие
переноса (SA-shift action) .
Замена строки наверху стека посредством применения продукции грамматики - действие свертки (RA - reduce action)
Вершина стека расположена справа, а в последнем столбце показан применяемый тип операций (SA | RA) . Действие переноса выполняет удаление символа и занесение его в стек. Действие свертки предусматривает изменения в вершине стека и в сентенциальной форме посредством применения продукции. В начальном состоянии синтаксического разбора стек пустой, а сентенциальная форма совпадает с анализируемым предложением (xxxyy) . В финальном состоянии сентенциальная форма совпадает с начальным символом грамматики (S), стек содержит также начальный символ грамматики, строка полностью прочитана.
