Разработка компиляторов

       

Построение выводов


Приведем алгоритм построения разметки C для грамматики в нормальной форме.

Данный алгоритм обходит дерево снизу-вверх. При этом он пытается применить все возможные правила к текущей вершине root. Если какое-либо правило R=N:p применимо, то в разметку для пары С[root][N] добавляется правило R .

Для того, чтобы проверить применимость правила для текущей вершины, проверяется соответствие этой вершины образцу в правой части правила (этим занимается функция Match ).

Кроме того, после вывода нового нетерминала в разметке C строится ее замыкание относительно цепных правил (это делает функция BuildClosure).

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



Содержание раздела