Advertisement
Guest User

Untitled

a guest
May 2nd, 2012
49
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.03 KB | None | 0 0
  1. Рассмотрим такой пример грамматики:
  2.  
  3. S -> A x
  4. A -> y
  5.  
  6. A -> B
  7.  
  8. B -> y z
  9. и попробуем разобрать ею строку ‘yzх’. Для разбора нетерминала S надо разобрать нетерминал А. По первому провилу для А распознается у, вместе с ним и А. Для продолжения распознования S надо распознать символ х в остатке ввода ‘zx’. Это невозможно, поэтому анализатор делает откат, и пытается распознать А по-другому. В этот раз строка yz распознается как нетерминал В, и затем А. Разобрав затем символ х мы сможем разобрать стартовыый нетерминал S.
  10. Алгоритм выше использует медленные откаты (slow-back). Существует более эффективный, но менее общий механизм откатов для анализаторов сверху вниз --- fast back. разница двух алгоритмов в том, что при fast-back после разбора первой подцели делается предположение, что распознование корректно ,и если в дальнейшем оставшиеся подуелит распознать не удастся, то распознование базовой цели сразу же закончится неуспехом, без попыток распозновать первую подцель иным способом. Грамматику многих языков программирования можно переписать так, чтобы она распозновалась с помощью fast-back алгоритма. Подробнее об этом можно прочитать у Флойда (1964).
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement