Специальная математика. Соловьев А.Е. - 83 стр.

 (E) * P{*}  (E + T{+}) * P{*}  (a{a} + b{b}) * c{c}{*}
Если выделить символы, заключенные в фигурные скобки, то получится исходное
выражение, оттранслированное в постфиксную запись.
   ab + c *
                              7.12. s и q - грамматики

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

Не s-грамматика :
S  aT - начинается с нетерминального. T  bT.
S  TbS
T  bT

Aналогичная s-грамматика (распознает тоже)
:
S  abR
S  bRbS
Ra
R  bR
  q-грамматика отличается от s-грамматики наличием аннулирующего правила (в правой
части есть пустой символ)   .
1. S  aAS
2. S  b
3. A  cAS
4. A  
   Из-за аннулирующих правил для q-грамматики вводится понятие следующего символа. N
(A) - множество терминальных следующих (Next) за А символов.
В данном случае за А могут следовать a или b - {a,b}.

S  aAS  aAaAS  aAaAb
E(1) = {a} - множество выбора для первого правила.
E(2) = {b}
E(3) = {c}
E(4) = N(A) = {a,b}

  Данная грамматика может быть распознана МП-автоматом, в который добавлена операция
замены . В этом случае автомат начинает работать с непустым стеком.


         S     A        
  a    1 AS 4          
              > <
  b    2  4          
               > <
  c         3  AS      
                
  ┤                    +

                                        — 83 —