Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 41 стр.

     - если не установлено ни одно отношение предшествования между те-
кущим символом входной цепочки и самым верхним символом в стеке, то ал-
горитм прерывается сообщением об ошибке;
     - если в стеке остаются символы ⊥нS, а во входном буфере только сим-
вол ⊥к, то входная строка прочитана полностью, и алгоритм разбора завершен
успешно.
     Пример 7.1. Дана грамматика G({a, (, )}, {S, R}, P, S), с правилами P:
1) S→(R | a; 2) R→Sa). Построить распознаватель для строки (((aa)a)a)⊥к.
      Этап 1. Построим множества крайних левых и крайних правых символов
L(A) и R(A) относительно всех нетерминальных символов грамматики (таблица
7.1).
        Таблица 7.1 – Построение множеств L(A) и R(A) для грамматики G
  Шаг                     Li(A)                             Ri(A)
                      L0(S)={(, a}                     R0(S)={R, a}
    0
                      L0(R)={S}                        R0(R)={)}
                      L1(S)={(, a}                     R1(S)={R, a, )}
    1
                      L1(R)={S, (, a}                  R1(R)={)}
                      L2(S)={(, a}                     R2(S)={R, a, )}
    2
                      L2(R)={S, (, a}                  R2(R)={)}
                      L(S)={(, a}                      R(S)={R, a, )}
Результат
                      L(R)={S, (, a}                   R(R)={)}
      Этап 2. На основе построенных множеств и правил вывода грамматики
составим матрицу предшествования символов (таблица 7.2).
      Поясним заполнение матрицы предшествования. В правиле грамматики
S→(R символ ( стоит слева от нетерминального символа R. Во множестве L(R)
входят символы S, (, a. Ставим знак <⋅ в клетках матрицы, соответствующих
этим символам, в строке для символа (.
      В правиле грамматики R→Sa) символ a стоит справа от нетерминального
символа S. Во множество R(S) входят символы R, a, ). Ставим знак ⋅> в клетках
матрицы, соответствующих этим символам, в столбце для символа a.
      В строке символа ⊥н ставим знак <⋅ в клетках символов, входящих во
множество L(S), т.е. символов (, a. В столбце символа ⊥к ставим знак ⋅> в клет-
ках, входящих во множество R(S), т.е. символов R, a, ).
      В клетках, соответствующих строке символа S и столбцу символа a, ста-
вим знак =⋅, т.к. существует правило R→Sa), в котором эти символы стоят ря-
дом. По тем же соображениям ставим знак =⋅ в клетках строки а и столбца ), а
также строки ( и столбца R.




                                                                              41