Приведенное определение СУ - схемы не накладывает никаких ограничений
на правила, кроме необходимости совпадения нетерминалов во входной и выходной
частях правила. Для построения детерминированных устройств, осуществляющих
перевод цепочек, используются СУ - схемы с дополнительными ограничениями
на вид правил, которые определяются так.
Определение. СУ-схема Т = {Va,Vтвх,Vтвых,Q,I} называется простой, если для каждого правила <A>╝a ,b из Q соответствующих друг другу вхождения нетерминалов встречаются в a и b в одном и том же порядке. |
Перевод называется простым СУ-переводом, если он определяется простой СУ-схемой. |
Вывод в этой СУ - схеме, выполняемый путем применения правил к самым
левым нетерминалам промежуточных цепочек, имеет вид:
(aET+*,a*(E+T))==> ==> (aTT+*,a*(T+T)) ==> (aFT+*,a*(F+T)) ==>
==> (aaT+*,a*(a+T)) ==> (aaF+*,a*(a+F)) ==> ==> (aaa+*,a*(a+a))
(a+F*F,aFF*+) ==>
(a+a*F,aaF*+) ==> (a+a*a,aaa*+)