Книга: Системное программное обеспечение. Лабораторный практикум

Заполнение матрицы предшествования

Для заполнения матрицы операторного предшествования необходимы множества крайних левых и крайних правых терминальных символов, представленные в табл. 3.7, и правила исходной грамматики G.

Заполнение таблицы рассмотрим на примере лексем or и (.

Символ or не стоит рядом с другими терминальными символами в правилах грамматики. Поэтому знак «=.» («составляет основу») для него не используется. Символ or стоит слева от нетерминального символа D в правиле Е ? Е or D. В множество L_t(D) входят символы and, а и (. Поэтому в строке матрицы, помеченной символом or, ставим знак «<.» («предшествует») в клетках на пересечении со столбцами, помеченными символами and, а и (.

Кроме того, символ or стоит справа от нетерминального символа Е в том же правиле Е ? Е or D. В множество R_t(E) входят символы or, xor, and, а и). Поэтому в столбце матрицы, помеченном символом or, ставим знак «.>» («следует») в клетках на пересечении со строками, помеченными символами or, xor, and, а и).

Больше ни в каких правилах символ or не встречается, поэтому заполнение матрицы для него закончено.

Символ (стоит рядом с терминальным символом) в правиле С ? (Е) (между ними должно быть не более одного нетерминального символа – в данном случае один символ Е). Поэтому в строке матрицы, помеченной символом (, ставим знак «=.» («составляет основу») на пересечении со столбцом, помеченным символом).

Символ (также стоит слева от нетерминального символа Е в том же правиле С ? (Е). В множество L_t(E) входят символы or, xor, and, а и (. Поэтому в строке матрицы, помеченной символом (, ставим знак «<.» («предшествует») в клетках на пересечении со столбцами, помеченными символами or, xor, and, а и (.

Больше ни в каких правилах символ (не встречается, поэтому заполнение матрицы для него закончено.

Повторяя описанные выше действия по заполнению матрицы для всех терминальных символов грамматики G, получим матрицу операторного предшествования. Останется только заполнить строку, соответствующую символу «начало строки», и столбец, соответствующий символу «конец строки».

Начальным символом грамматики G является символ S, поэтому для заполнения строки, помеченной ?н, возьмем множество L_t(S). В это множество входят символы if, а и;. Поэтому в строке матрицы, помеченной символом ?н, ставим знак «<.» («предшествует») в клетках на пересечении со столбцами, помеченными символами if, а и;.

Аналогично, для заполнения столбца, помеченного ?_к, возьмем множество R^(S). В это множество входит только один символ —;. Поэтому в столбце матрицы, помеченном символом ?_к, ставим знак «.>» («следует») в клетке на пересечении со строкой, помеченной символом;.

В итоге получим заполненную матрицу операторного предшествования, которая представлена в табл. 3.8.

Оглавление книги