Формальные языки, грамматики и основы построения трансляторов. Кревский И.Г - 26 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

26
4. ПРОБЛЕМА РАЗ БОРА
Компилятор должен решить проблему проверки строк символов, чтобы
определить, принадлежат ли они данному языку, и если да, то распознать
структуру строк в терминах порождающих правил грамматики. Эта проблема
известна как проблема разбора. Исследуем грамматику с порождающими
правилами (E - начальный символ).
1. Е
→
Е + Т
2. Е
→
T
3. T
→
T * F
4. T
→
F
5. F
→
(Е)
6. F
→
x
7. F
→
y
Ясно, что строка (x + y) * x принадлежит данному языку. В частности,
это можно вывести следующим образом (для каждого шага вывода указан
номер применяемого правила):
2) E
⇒
T
3)
⇒
T * F
4)
⇒
F * F
5)
⇒
(E)* F
1)
⇒
(E + T) * F
2)
⇒
(T + T) * F
4)
⇒
(F + T) * F
6)
⇒
(x + T)*F
4)
⇒
(x + F) * F
7)
⇒
(x + y) * F
6)
⇒
(x + y) * x
Или же это можно вывести так:
2) E
⇒
T
3)
⇒
T * F
6)
⇒
T * x
4)
⇒
F * x
5)
⇒
(E) * x
1)
⇒
(E + T) * x
4)
⇒
(E + F) * x
7)
⇒
(E + y) * x
2)
⇒
(T + y) * x
4)
⇒
(F + y) * x
6)
⇒
(x + y) * x 
                                                                       26
                           4. ПРОБЛЕМА РАЗБОРА
     Компилятор должен решить проблему проверки строк символов, чтобы
определить, принадлежат ли они данному языку, и если да, то распознать
структуру строк в терминах порождающих правил грамматики. Эта проблема
известна как проблема разбора. Исследуем грамматику с порождающими
правилами (E - начальный символ).
     1. Е → Е + Т                           5. F → (Е)
     2. Е → T                               6. F → x
     3. T → T * F                           7. F → y
     4. T → F
     Ясно, что строка (x + y) * x принадлежит данному языку. В частности,
это можно вывести следующим образом (для каждого шага вывода указан
номер применяемого правила):
     2) E ⇒ T                               4)    ⇒ (F + T) * F
     3)    ⇒T*F                             6)    ⇒ (x + T)*F
     4)   ⇒F*F                             4)    ⇒ (x + F) * F
     5)    ⇒ (E)* F                         7)    ⇒ (x + y) * F
     1)    ⇒ (E + T) * F                    6)    ⇒ (x + y) * x
     2)    ⇒ (T + T) * F


     Или же это можно вывести так:
     2) E ⇒ T                               4)    ⇒ (E + F) * x
     3)    ⇒T*F                             7)    ⇒ (E + y) * x
     6)    ⇒T*x                             2)    ⇒ (T + y) * x
     4)    ⇒F*x                             4)    ⇒ (F + y) * x
     5)    ⇒ (E) * x                        6)    ⇒ (x + y) * x
     1)    ⇒ (E + T) * x

Страницы