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

                                                                       72
заменим ее нетерминалом А в соответствии с продукцией А → Abc. В
результате получим строку aAde. Заменяя d на В, левую часть продукции В
→ d, получаем аАВе, которая в соответствии с первой продукцией заменяется
стартовым символом S. Итак, последовательность из четырех сверток
позволяет привести строку abbcde к стартовому символу S. Эти сокращения
представляют собой обращенное (т.е. записанное в обратном порядке) правое
приведение S ⇒ aABe ⇒ aAde ⇒ aAbcde ⇒ abbcde .
              rm     rm     rm       rm




                                    Основы


      Неформально говоря, основа, или дескриптор (handle) строки – это
подстрока, которая совпадает с правой частью продукции и свертка которой
в левую часть продукции представляет собой один шаг обращенного правого
порождения. Во многих случаях крайняя слева подстрока β соответствующая
правой части некоторой продукции А → β не является основой, поскольку
свертка в соответствии с продукцией А → β приводит к строке, которая не
может быть свернута к стартовому символу. Если в предыдущем примере мы
заменим во второй строке aAbcde символ b нетерминалом А, то получим
строку aAAcde, которая не может быть свернута в S. По этой причине нам
следует дать более точное определение основы.
      Говоря формально, основа правосентенциальной формы γ является
продукцией А → β и позицией строки β в γ, такими, что β может быть
заменена нетерминалом А для получения предыдущей правосентенциальной
формы в правом порождении γ. Таким образом, если S ⇒αAw ⇒αβw , то А → β в
                                                   rm    rm


позиции после а представляет собой основу строки αβw. Строка w справа от
основы содержит только терминальные символы. Заметим, что грамматика
может быть неоднозначной, с несколькими правыми порождениями αβw.
Если грамматика однозначна, то каждая правосентенциальная форма
грамматики имеет ровно одну основу.