Зачет по курсу «Системы программирования»

Вариант 1. (2005)

• Основные задачи лексического анализатора. Привести два-три примера ситуаций, в которых лексический анализатор выдаст ошибку.
• Библиотека STL: Дать определение итератора. Чем различаются прямые и обратные итераторы? Привести пример использования обратного итератора.
• Общая схема работы компилятора.
• Дать определение недостижимого символа грамматики. Привести пример грамматики, содержащей недостижимый символ.
• Привести примеры использования статической, динамической и стековой памяти.
• Определить тип по Хомскому заданной грамматики G = (VT, VN, P, S). Определить порождаемый язык и тип языка по Хомскому.

  P: S → AB⊥
  AB → aABcB | X
  Xc → cX
  XB → bX
  X⊥ → cb⊥

• Написать грамматику для языка L₁. Вставить в нее действия по переводу цепочек языка L₁ в соответствующие цепочки языка L₂ (в ходе анализа цепочек языка L₁ методом рекурсивного спуска). В качестве действий допустимо только использование оператора cout << … .
  

  L1 = { aⁿαbⁿ, α∈(c, d)⁺, n ≥ 0 }
  L2 = { 0^m1^n + k, где m — количество символов c в цепочке α, k — количество символов d в цепочке α}

• Построить ДС, соответствующую заданной Р-грамматике G = (VT, VN, P, S).
  

  P: S → Sa | Aa | Sb | a | b
  A → Sa | Ab | a

  Если ДС задает НКА, то по алгоритму преобразования НКА в КА построить КА и написать соответствующую ему грамматику, иначе написать анализатор по заданной грамматике.
• Дана КС-грамматика G = (VT, VN, P, S). Определить, применим ли к ней метод рекурсивного спуска. Ответ обосновать.

  S → aSB | bAf | ε
  A →  bAc | cS 
  B →  cB | d

• Записать на ПОЛИЗе фрагмент программы на С:

  do { x = (a + b)/ x *((-a) /(b + x) - 3); S += x; } while (x > c);