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

                                                                                    74
                    E⇒E + E
                         rm

                    ⇒ E + E* E
                    rm

                    ⇒ E + E * id 3
                    rm

                    ⇒ E + id 2 * id 3
                    rm

                    ⇒ id1 + id 2 * id 3
                    rm


     Для удобства мы пометили подстрочными индексами id и подчеркнули
основу каждой правосентенциальной формы. Например, id1 представляет
собой основу право-сентенциальной формы id1+id2*id3, поскольку id
является правой частью продукции Е→ id, и замена id1 на E приведет к
предыдущей правосентенциальной форме E+id2*id3. Обратите внимание на
то, что строка справа от основы состоит только из терминальных символов.
     Поскольку грамматика (13.1) неоднозначна, имеется еще одно правое
порождение той же строки:
               E ⇒ E* E
                    rm

               ⇒ E * id 3
               rm

               ⇒ E + E * id 3
               rm

               ⇒ E + id 2 * id 3
               rm

               ⇒ id1 + id 2 * id 3
               rm


     Рассмотрим правосентенциальную форму E+E*id3. В этом порождении
E+E – основа E+E*id3, в то время как в ранее представленном порождении ее
основой является id3.
     Первое порождение дает оператору * больший приоритет, чем
оператору +, в то время как во втором порождении выше приоритет
оператора +.


                                           Обрезка основ


     Обращенное правое порождение может быть получено посредством
"обрезки основ". Мы начинаем процесс со строки терминалов w, которую
хотим   проанализировать.                 Если   w   –   предложение   рассматриваемой