Разработка компиляторов
Построение выводов (продолжение)
Рассмотрим задачу сопоставления с образцом для вершины дерева (функция Match). Нас в данном случае интересуют образцы двух видов: лист, помеченный неким терминальным символом и дерево высоты один, корень которого помечен неким терминальным символом, а листья - нетерминалами. Кроме того, возможны образцы цепных правил, но они будут учтены при построении замыкания. Этим набором исчерпываются все образцы грамматики в нормальной форме.
Что касается образца первого вида, то данная вершина соответствует ему в том и только том случае, когда она является листом, помеченным тем же самым терминальным символом.
Для соответствия вершины образцу второго вида необходимо и достаточно, чтобы она была помечена нужным терминалом, а ее сыновья выводились в грамматике G из соответствующих нетерминалов образца. Поскольку построение разметки C происходит снизу-вверх, последнее условие может быть трактовано как непустота множества правил для данной вершины и данного нетерминала.
Наконец, функция BuildClosure, получая в качестве аргумента вновь выведенный нетерминал, строит замыкание разметки C относительно цепных правил, просто добавляя их в разметку для данной вершины и выведенного по цепному правилу нетерминала.
