Файл: Отчеты оформляются в виде файлов формата Microsoft Word (файлы других форматов не принимаются), размер шрифта 1214.docx

и выполняется условие 3:

Условие 3. В грамматике есть правило вида

Z : χ X , где χ – произвольная, возможно пустая цепочка, а  – цепочка, либо состоящая только из аннулируемых нетерминалов, либо просто пустая.

И, наконец, символ Y является последователем символа X, если Y есть последователь некоторого символа Z (неважно, непосредственный или нет)и выполняется условие 4:

Условие 4. В грамматике есть совокупность правил следующего вида:

Z	:	χ1Z11
Z 1	:	χ2Z22
...
Zn-1	:	χn Znn
Zn	:	χ0X0,

где χ₀, χ₁,..., χ_n – произвольные цепочки, а ₀, ₁,..., _n – цепочки, состоящие только из аннулируемых нетерминалов или просто пустые.

Условия 1 и 2 определяют отношение «символ Y есть непосредственный последователь символа X», а условия 3 и 4 – отношение «символ X есть последний (замыкающий) символ в цепочке, выводимой из символа Z». Искомое отношение «символ Y есть последователь символа X» является произведением этих двух отношений.

Хотя для решения задачи синтаксического анализа интерес представляют только множества последователей нетерминальных символов, для их вычисления приходится определять множества последователей всех (терминальных и нетерминальных) символов грамматики.

Множества предшественников и последователей символов грамматики будут самым существенным образом использоваться в процессе преобразования формальных грамматик в синтаксические акцепторы, т.е. при выполнении всех лабораторных работ 3-8 и курсовой работы.

4. 
   Порядок выполнения работы (рекомендуется использовать в качестве примера систему правил Samples/Sample3):
   

1. 
   Разработать описание синтаксиса языка, заданного на курсовую работу. Описание синтаксиса должно включать:
   

• 
  структуру файла программы (состав модулей/секций файла);
  
• 
  структуру и назначение каждой секции/модуля;
  
• 
  формат и точный способ выполнения всех операторов (присваивания, цикла, …) в виде последовательности операций, сложность которых не выше сложения/ умножения/сравнения/… двух значений, условного или безусловного перехода.
  

---

1. 
   Используя систему правил Samples/Sample3 как основу:
   

• 
  освоить и изучить ввод и редактирование синтаксических правил, содержащих слова-строки, группирование, операции выбора и квантификаторы;
  
• 
  проанализировать соответствие фактических правил видимым/редактируемым правилам в процессе редактирования системы правил; понять, как выявляется начальный нетерминал грамматики;
  
• 
  разобраться в причинах возникновения недоступных и бесплодных нетерминалов, отображаемых серым цветом и отсутствующих в системе фактических правил после завершения ввода правил, содержащих такие символы;
  
• 
  разобраться в том, каким образом пакет ВебТрансБилдер разделяет правила на лексические и синтаксические; описать принципы этого разделения.
  

1. 
   Изучить по [2-5] теоретические определения и алгоритмы вычисления отношений предшествования и последования для символов грамматики.
   
2. 
   Освоить просмотр свойств грамматик и их символов в пакете ВебТрансБилдер; необходимо достичь понимания того, почему те или иные символы грамматики имеют свой конкретный набор свойств (пункты меню «Показать/Правила грамматики», «Показать/Множества предшественников» и «Показать/Множества последователей»).
   
3. 
   Используя полученные навыки работы с грамматиками и программным обеспечением, начать поэтапную разработку грамматики языка для заданного варианта курсовой работы, реализовать правила, определяющие как минимум выражения со всеми знаками операций языка, заданного на курсовую работу, оператор присваивания и не менее одного управляющего оператора.
   
4. 
   Выполнить построение транслятора по разработанной грамматике и шаблону табличного восходящего анализатора для языка JavaScript. Проверить работоспособность построенного транслятора на фрагментах тестовых программ, написанных на заданном языке; добиться того, чтобы выражения и выполняемые операторы воспринимались транслятором как правильные.
   
5. 
   Подготовить, сдать и защитить отчет к лабораторной работе.
   

5. 
   Требования к содержанию отчета.
   

Отчет должен содержать:

• 
  цель работы;
  
• 
  описание синтаксиса языка как результат выполнения пункта 4.1 и как часть расчетно-пояснительной записки к курсовой работе;
  
• 
  результаты разработки (пункт 4.5) и тестирования (пункт 4.6) грамматики для языка, заданного на курсовую работу;
  
• 
  матричное представление отношений предшествования и последования для символов этой грамматики, сформированное пакетом ВебТрансБилдер; краткое описание этих отношений;
  
• 
  результаты своего анализа алгоритмов и способов преобразования видимой системы правил в фактическую, выявления или формирования начального нетерминала, разделения правил на лексические и синтаксические, выявления недостижимых и бесплодных нетерминалов; этот анализ должен быть проведен для результата выполнения пункта 4.5;
  
• 
  выводы и заключение.
  

---

6. 
   Контрольные вопросы.
   

1. 
   Что такое терминальные и нетерминальные символы формальных грамматик?
   
2. 
   Что такое рекурсия? Перечислите виды рекурсии.
   
3. 
   Что такое контекстно-свободные грамматики?
   
4. 
   Вычислите множество предшественников цепочки символов
   WR для грамматики G_a2.
   
5. 
   Является ли однозначной грамматика:
   

1. 
   S : S "|" S
   
2. 
   S : S S
   
3. 
   S : "(" S ")"
   
4. 
   S : ident
   

1. 
   Что такое аннулируемый нетерминал?
   
2. 
   Что такое стековая память? Какие операции обычно определяются над стековой памятью?
   
3. 
   Что такое множество последователей символа грамматики?
   
4. 
   Чем понятие вывода отличается от понятия непосредственного вывода?
   
5. 
   Что такое недетерминированность конечного автомата без памяти? Какие бывают виды недетерминированности?
   
6. 
   Устраните левую рекурсию в такой грамматике:
   

1. 
   S : "(" L ")"
   
2. 
   S : ident
   
3. 
   L : L "," S
   
4. 
   L : S
   

1. 
   Что такое дерево грамматического разбора?
   
2. 
   Какие нетерминальные символы называются бесплодными?
   
3. 
   Что такое рекурсивный цикл в грамматике?
   
4. 
   Какие грамматики называются эквивалентными?
   
5. 
   Могут ли быть эквивалентными два конечных автомата без памяти, имеющие разное количество финальных состояний?
   
6. 
   Вычислите множества последователей для грамматики из вопроса 6.5.
   
7. 
   Что такое контекстно-зависимая грамматика?
   
8. 
   Что такое отношение предшествования символов?
   
9. 
   Можно ли удалить из грамматики пряморекурсивный нетерминал?
   
10. 
    Постройте дерево разбора предложения (ident, (ident, ident)) в грамматике из вопроса 6.11.
    
11. 
    Что такое факторизация?
    
12. 
    Сформулируйте физический смысл перехода по пустой цепочке в финальное состояние конечного автомата без памяти.
    
13. 
    Можно ли и, если можно, то как преобразовать косвенную рекурсию в прямую?
    
14. 
    Определите алфавиты терминальных и нетерминальных символов для грамматики из вопроса 6.11.
    
15. 
    Какие конечные автоматы без памяти называются эквивалентными?
    
16. 
    Перечислите условия, которые определяют отношение последования символов грамматики.
    
17. 
    Вычислите вручную множества предшественников и последователей и все свойства символов для фрагмента грамматики, определяющий синтаксис условного оператора языка С:
    

1. 
   Operator : …
   
2. 
   Operator : "if" "(" LogicalExpression ")" Operator Rest
   
3. 
   Rest : "else" Operator
   
4. 
   Rest :
   

29. 
    Является ли грамматика вопроса 6.29 однозначной?
    
30. 
    Как соотносятся между собой языки и грамматики?
    
31. 
    Могут ли быть эквивалентными два конечных автомата без памяти, имеющие различное количество рабочих состояний?
    
32. 
    Как вычисляется множество предшественников цепочки символов?
    
33. 
    Почему из системы порождающих правил грамматики не может быть удален ее начальный нетерминал?
    
34. 
    Как связаны между собой понятия вывода и дерева грамматического разбора?
    

---

---

Лабораторная/практическая работа № 4

1. 
   Название работы: «Синтаксис языков программирования. Нисходящий синтаксический анализ.
   
2. 
   Цели работы: изучение основных идей и понятий нисходящих методов синтаксического анализа, выявление свойств формальных грамматик, необходимых для реализации нисходящего восстановления дерева грамматического разбора, приобретение навыков построения процедурной и различных автоматных реализаций нисходящего анализа, исследование поведения нисходящих синтаксических акцепторов.
   
3. 
   Основные теоретические сведения:
   

1. 
   Нисходящие методы синтаксического анализа
   

Нисходящими называются такие методы синтаксического анализа, при которых восстановление дерева грамматического разбора выполняется сверху от начального нетерминала контекстно-свободной грамматики вниз к анализируемому предложению (входной цепочке терминалов).

Каждый шаг процесса восстановления дерева состоит в применении одного непосредственного вывода, т. е. в замене единственного нетерминального символа правой частью какого-либо правила для этого нетерминала. Главное прагматическое требование к этому процессу – необходимость организации безоткатного однонаправленного движения вниз по дереву.

Отсюда следует, что выбор правила на каждом шаге должен осуществляться таким образом, чтобы гарантировать:

1. 
   Восстановление дерева для любого правильного предложения и
   
2. 
   Обнаружение невозможности восстановить дерево для любого неправильного предложения.
   

Оказывается, что дать такие гарантии можно отнюдь не для любой грамматики и, более того, не для любого языка.

Существуют языки, для которых никакая порождающая грамматика не позволяет организовать безвозвратное нисходящее восстановление дерева грамматического разбора (в чистом виде, т. е. без применения специальных мер, модифицирующих свойства грамматики). Существуют и такие языки, для которых одни порождающие грамматики пригодны для детерминированного нисходящего восстановления дерева, а другие нет. Языки программирования обычно относятся именно к этой группе.

В этом разделе вначале будет сформулирована основная идея группы нисходящих методов, затем определены критерии выбора правила для выполнения каждого очередного непосредственного вывода и на этой основе – условий, которым должна удовлетворять грамматика для организации восстановления дерева разбора сверху вниз. В общей форме будут определены

---