Формальные языки, грамматики и основы построения трансляторов. Кревский И.Г - 18 стр.

                                                                              18
                                                 n   m
      Грамматикой, генерирующей язык L = { a b | n, m ≥ 0} является G0 = (
{ a, b}, {S, A, B}, P, S), где P = { S → AB, A → aA, A → ε, B → bB, B → ε }
      Начав с символа S и применяя последовательно по одному из правил
замены нетерминала в выводимой строке можно, например, генерировать
строку aaabb:
   S ⇒ AB ⇒ aAB ⇒ aaAB ⇒ aaaAB ⇒ aaaB ⇒ aaabB ⇒ aaabbB ⇒ aaabb
      Каждая строка, которую можно вывести из начального символа,
называется сентенциальной формой. Предложение – сентенциальная форма,
содержащая только терминалы. Терминалы будем обозначать строчными
(маленькими) буквами, а нетерминалы – прописными (большими).
      Как правило, предложения языка можно генерировать с помощью
более чем одной грамматики. Две грамматики, генерирующие один и тот же
язык, называют эквивалентными. С точки зрения разработчика транслятора
одна грамматика может быть гораздо удобней другой.


                           Контрольные вопросы
   1. Что определяет синтаксис языка?
   2. В чем отличие синтаксиса языка от семантики языка?
   3. Что такое грамматика и как она задается?
   4. Чем различаются терминальные и нетерминальные символы языка?
   5. Чем определяется возможность появления того или иного символа в
      предложении языка?
   6. Что такое «начальный символ» и чем он отличается от других
      символов языка?
   7. Задана грамматика с порождающими правилами:
S -> (S)                          S -> ε   ,
S -> SS                           где S - начальный символ, ε - пустая строка
      Принадлежат     ли    языку,   генерируемому       данной   грамматикой
следующие строки (аргументировать ответ, в случае принадлежности,
доказать с помощью вывода):