Методические указания к лабораторным работам по курсу "Теория вычислительных процессов и структур". Домашова Д.В - 6 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

<оператор останова>::=[<метка>]=SТОР=[<строка>].
Первый из этих операторов выводит на печать строку (без кавычек),
явно заданную по имени, а второй печатает символ конца и строку, если она
есть.
Примечание
|В | ...| Z} эквивалентно А|В|... |Z;
[А |B | ... |Z] эквивалентно <пусто> A|B|…|Z .
Пример
(стр.1 = `АВСАВВАВС`;
стр.2 = `ВС`;
стр.3 = `АВА`;
стр.1*стp.4*стp.2*стp.5*|S(2);
1 = STOP = "F"
2 = PRINT = стр.4
= PRINT = стр.5;
стр.5 стр.З/F(1);
= STOP = `S`;)
1.2 Порождающие грамматики
Порождающая грамматика есть система
G={V
T
,V
N
,S,P},V
T
∩ V
N
=∅
где V
T
– словарь термин символов
;
V
N
– словарь нетермин символов V
T
∩
V
N
= ∅;
S – начальный символ , S∈V
N
;
P – набор правил вида α::=β, α,β-любые цепочки
Разбор по грамматике
Задача разбора – обратная задача прохождению , т.е. дана цепочка, нужно
найти ее вывод (рисунок 1.1):
1) нисходящий метод разбора
{S::=T|T+S,T::=a|b}
Дана : терминальная цепочка a+b+a
Найти ее вывод:
SÆ T+S Æ T+T+S Æ T+T+T Æ a+T+T Æ a+b+T Æ a+b+a
М.б. левосторонним и правосторонним
Недостаток : ненаглядность
2) восходящий метод разбора :
a+b+a Æ a+b+T Æ a+T+T Æ T+T+T Æ T+T+S Æ T+S Æ S
Недостаток : ненаглядность
3) разбор с помощью синтаксических деревьев
9
       <оператор останова>::=[<метка>]=SТОР=[<строка>].
       Первый из этих операторов выводит на печать строку (без кавычек),
явно заданную по имени, а второй печатает символ конца и строку, если она
есть.
      Примечание
       |В | ...| Z} эквивалентно А|В|... |Z;
      [А |B | ... |Z] эквивалентно <пусто> A|B|…|Z .
      Пример
      (стр.1 = `АВСАВВАВС`;
        стр.2 = `ВС`;
        стр.3 = `АВА`;
        стр.1*стp.4*стp.2*стp.5*|S(2);
      1 = STOP = "F"
      2 = PRINT = стр.4
      = PRINT = стр.5;
      стр.5 стр.З/F(1);
      = STOP = `S`;)

1.2 Порождающие грамматики

     Порождающая грамматика есть система

                              G={VT,VN,S,P},VT ∩ VN =∅
         где VT – словарь термин символов ;
             VN – словарь нетермин символов VT ∩ VN = ∅;
             S – начальный символ , S∈VN ;
             P – набор правил вида α::=β, α,β-любые цепочки
         Разбор по грамматике
Задача разбора – обратная задача прохождению , т.е. дана цепочка, нужно
найти ее вывод (рисунок 1.1):
     1) нисходящий метод разбора
         {S::=T|T+S,T::=a|b}
         Дана : терминальная цепочка a+b+a
         Найти ее вывод:
         SÆ T+S Æ T+T+S Æ T+T+T Æ a+T+T Æ a+b+T Æ a+b+a
         М.б. левосторонним и правосторонним
         Недостаток : ненаглядность
     2) восходящий метод разбора :
         a+b+a Æ a+b+T Æ a+T+T Æ T+T+T Æ T+T+S Æ T+S Æ S
         Недостаток : ненаглядность
     3) разбор с помощью синтаксических деревьев



                                                                        9

Страницы