Математическая логика и теория алгоритмов. Стенюшкина В.А. - 102 стр.

                                     δ


                              δ     ц      δ

                                    к

                                    Рисунок 6.1

      В принципе, возможен обратный переход от конечного алфавита к регу-
лярной грамматике.

      6.7 Синтаксический анализ. Контекстно-свободные грамматики

       Основной задачей синтаксического анализа – выявление синтаксической
структуры исходной программы. Одним из способов решения той задачи являе-
тся моделирование построения дерева вывода в грамматике, описывающей
входной язык программирования. Такими грамматиками являются контекстно-
свободные грамматики.
       Различают левосторонние и правосторонние выводы.
       Вывод в КС – грамматике называется лево- | правосторонним, если пра-
вила вывода применяются к самому левому | правому вхождению нетерминаль-
ного символа каждой цепочки вывода.
       Пример – КС-грамматики G=< N, T, P, S >, N={E, R, F}, T={I, +, *, ), (},
S={E}, P={E       E+R, E   R, R    R*F, R       F F      (E), F  i} порождает
арифметические выражение, причём идентификатору соответствует термина-
льный символ i, а арифметическим операциям – символы + и * ; скобки (и)
имеют обычный смысл. В частности, для терминальной цепочки i+i*I левосто-
ронний вывод представляется цепочкой E        E+R         R+R      F+R      I+
           *           *
R     I+R F         I+F F   I+I*F       I + I * I, а правосторонний – цепочкой
E     E+R        E+R*F      E+R*I       E+F*I          E+I*I      R+I*I      F
+I*I       I + I * i.
       Наглядным представлением структуры программы является дерево син-
таксического разбора. Дерево разбора в КС – грамматике G=< N, T, P, S > есть
упорядоченное дерево, каждая вершина которого взвешена символом X∈T∪N.
При этом, если внутренняя вершина помечена символом А, а её прямые потом-
ки символами X1, … ,Xk, то A→ X1… Xk – правило грамматики G.