Матрицы и функции предшествования.

Иногда вводят 2 числовые функции, обладающие свойствами: если Х⋖.Y, то Ф₁(Х)<Ф₂(Y) и т.д. для ≐, ⋗. Нужно использовать топологическую сортировку.

Кстати, используя сортировку нетерминалов, можно проще строить функции L и R.

l_t (A) = {tÎS_T | A ® tz или ($ C ÎS_N) A ® Ctz }

r_t (A) = {tÎS_T | A ® zt или ($ C ÎS_N) A ® ztC }

L_t (A) = l_t (A) È l_t (B) "(B Î L (A) Ç S_N)

R_t (A) = r_t (A) È r_t (B) "(B Î R (A) Ç S_N)

L_t (A) = {tÎS_T | A Þ⁺ tz или ($ C ÎS_N) A Þ⁺ Ctz }, R_t (A) = {tÎS_T | A Þ⁺ zt или ($ C ÎS_N) A Þ⁺ ztC }

4.7. Грамматики операторного предшествования (ГОП). (АУ-492)

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

Пример: G₀-операторная грамматика. Отношения предшествования задаются на S_T È {$}. Пусть a, b ÎS_T, gÎS_NÈ{ e }. Тогда a ≐ b Û (A ® aagbb) Î P,

a ⋖ b Û (A ® aaBb) Î P & (B Þ⁺ gbd Û b Î L_t (B)) $⋖ a Û S Þ⁺ gaa Û a Î L_t (S),

a ⋗ b Û (A ® aBbb) Î P & (B Þ⁺ dag Û a Î R_t (B)) a ⋗$ Û S Þ⁺ aag Û a Î R_t (S).

Операторная грамматика называется грамматикой операторного предшествования (ГОП), если между любыми двумя терминалами выполняется не более одного отношения операторного предшествования. Оказывается, что G ₀ является ГОП.

По G строится остовная грамматика G _S = ({ S }, S_T, P ¢, S):

A ®Y₁…Y _m Î P Þ S®X₁…X _m Î P ¢ & X_i = if Y_i ÎS_T then Y_i else S.

Т.е. все нетерминалы заменяются на корневой символ, а если при этом возникнет цепное правило (S®S) Î P¢, то его удаляют.

Легко видеть, что L (G) L (Gs).

Для G ₀ остовной будет грамматика G ₂: E ® E + E | E * E | (E) | a.

Она, очевидно, неоднозначна. Но матрица-то строилась по G ₀!!

Построение анализатора, используещего ОП.

Вход: ГОП. Выход: дерево свертки. Алгоритм см. ГПП.

Восстанавливаем по правому разбору:

4.8. Сравнительный анализ грамматик и языков. (АУ₁ 502, АУ₂ 193)

КС-грамматики É ГОП Примеры языков разных типов. (m, n ³ 1)

È

однозначные

È

LR É LL

È

LR(1)

È

ГПП

Примеры грамматик. G₁ÎLL(1): S ® AS | e, A ® aA | b. G₂ÎLR(1): S ® SaSb | e.

G₃ÎLL(2): S ® abA | e, A ® Saa | b. G₄ÎLL(2): S ® aAaa | bAba, A ® b | e.

G₅ÎLL(3): S ® aAaB | aAbB, A ® ab | a, B ® cB | a.???

G₆ÎLR(0): S ® B | C, B ® aB | b, C ® aC | c. G₇ÏLR(k): S ® Ab | Dc, A ® Aa | e, D ® Da | e.

G₈ÎLR(2)???: S ® aB, B ® abbb | abba. ~ G₉: S ® aabbC, C ® a | b.

4.9. Обработка синтаксических ошибок.

Обработка состоит в диагностике (определение типа и места) ошибки и нейтрализации.

Стратегии нейтрализации.

1. Режим переполоха (недопустимый символ игнорируется, изолируются все последующие символы до так называемого опорного; из стека удаляются символы, связанные с удаленным фрагментом).

2. Исключение символов (игнорирование символов до допустимого).

х:= s +y+ z)*(w + v) первую скобку удаляем и анализируем дальше.

Надо быть осторожным, особенно при удалении опорного символа.

3. Вставка символов (между недопустимыми символами вставляется символ, делающий их допустимыми). Вставка может привести к зацикливанию.

Не нашли, что искали? Воспользуйтесь поиском: