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

UptoLike

ВУЗ: 

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

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

Рубрика: 

2.3 Разбор по Р-грамматике
S::=C⊥
C::=Ab|Ba
A::=a|Ca Описывает язык
B::=b|Cb L={S
n
⊥|n≥1}=,{ab⊥,ba⊥,abab⊥,abba⊥,…}
Произведем разбор : цепочки abba⊥.
Выясним, принадлежит ли она языку. Для этого построим
синтаксическое дерево. Используем восходящий способ разбора (снизу-вверх)
Получим символ S Æ цепочка выводится Æ она принадлежит языку.
Пример – Рисунок 2.1
S
A
C
B
C
a
b
b
a
⊥
Рисунок 2.1 –Синтаксическое дерево цепочки abba
2.4 Диаграмма состояний
Наша задача : по грамматике построить анализатор. Для облегчения
этой задачи сначала построим диаграмму состояний, а по ней – анализатор.
Грам.Æ анализатор Грам.ÆДСÆанализатор
Обозначим: Н-начало, кружочки состояния
Изображения правил:
1) M::=t t
М
Н
2) N::=Mq
q
H
M
15
2.3 Разбор по Р-грамматике

     S::=C⊥
     C::=Ab|Ba
     A::=a|Ca                    Описывает язык
     B::=b|Cb                    L={Sn⊥|n≥1}=,{ab⊥,ba⊥,abab⊥,abba⊥,…}

     Произведем разбор : цепочки abba⊥.
     Выясним, принадлежит ли она языку. Для этого построим
синтаксическое дерево. Используем восходящий способ разбора (снизу-вверх)
     Получим символ S Æ цепочка выводится Æ она принадлежит языку.
     Пример – Рисунок 2.1
                     S


                 C


             B



         C


     A

     a       b       b   a   ⊥

     Рисунок 2.1 –Синтаксическое дерево цепочки abba


2.4 Диаграмма состояний

      Наша задача : по грамматике построить анализатор. Для облегчения
этой задачи сначала построим диаграмму состояний, а по ней – анализатор.
      Грам.Æ анализатор Грам.ÆДСÆанализатор
      Обозначим: Н-начало, кружочки состояния
      Изображения правил:
      1) M::=t            t
                         Н        М

                             q
     2) N::=Mq M                 H


                                                                        15

Страницы