Стр. 23 - Информационные структуры и их преобразование

Содержание 21
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
пор, пока не окажется, что верхний символ стека находится в отношении
раньше(⋗) следующему сканируемому символу предложения. Это означает,
что верхний символ стека является концом основы. Затем, двигаясь в
обратном направлении, определяют верхнюю границу основы, далее её
находят в списке правил (основу), и она заменяется соответствующим
нетерминалом. Процесс продолжается до тех пор, пока в стеке не окажется
символ Z и следующим входным символом не станет #.
3.3. Операторное предшествование
Предшествование операторов
При использовании грамматик простого предшествования отношения
определялись между всеми символами как операндами, так и операторами.
Техника предшествования операторов формализует понятие
предшествования только между терминальными символами (операторами).
Грамматика G называется операторной грамматикой , если ни одно из
её правил не имеют вида
U: = …VW… , где V,W∈VN, то есть рядом не могут стоять два
нетерминала. Никакая сентенциальная форма не содержит двух соседних
нетерминальных символов:
1) R ≗ S, если U: = …RS…|…RVS…, где R,S∈VT, V∈VN.
2) R ∘>S, если U: = …WS… и W=>+…R|…RV
3) R <∘S, если U: = …RW… и W=>+S…|VS…
Построим отношение для грамматики: E: = E+T|T; T: = T*F|F; F: = (E)|i.
> > >
> > >
< = < < <
<> <> >
<> < <> +
+
  
  
   
    
    

i
)
(
*
i ) ( *