Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4)

Нажмите для полного просмотра!

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №2

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №3

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №4

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №5

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №6

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №7

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №8

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №9

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №10

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №11

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №12

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №13

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №14

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №15

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №16

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №17

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №18

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №19

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №20

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №21

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №22

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №23

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №24

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №25

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №26

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №27

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №28

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №29

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №30

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №31

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №32

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №33

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №34

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №35

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №36

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №37

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №38

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №39

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №40

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №41

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №42

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №43

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №44

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №45

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №46

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №47

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №48

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №49

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №50

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №51

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №52

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №53

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №54

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №55

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №56

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №57

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №58

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №59

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №60

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №61

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №62

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №63

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №64

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №65

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №66

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №67

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №68

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №69

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №70

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №71

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №72

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №73

Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4), слайд №74

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4). Доклад-сообщение содержит 74 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Глава 4 Синтаксический анализ 4.1 Распознаватели. Задача разбора 4.1.1 Общая схема распознавателя 4.1.2 Классификация распознавателей 4.1.3 Задача разбора 4.2 Распознаватели КС языков. Автомат с магазинной памятью (МП-автомат) 4.3 Синтаксический разбор 4.3.1 Методы разбора 4.3.2 Последовательность разбора 4.3.3 Использование просмотра вперед 4.3.4 Использование возврата 4.4 Нисходящие распознаватели с возвратами 4.5 Реализация нисходящего распознавателя с возвратами 4.6 Нисходящие распознаватели без возвратов. 4.6.1 Левосторонний разбор по методу рекурсивного спуска 4.6.2 Условия применимости РС-метода 4.6.3 Пример реализации РС-метода 4.8 Преобразование КС грамматик

Слайд 2

Описание слайда:

4.1 Распознаватели. Задача разбора Синтаксический анализ

Слайд 3

Описание слайда:

4.1.1 Общая схема распознавателя

Слайд 4

Описание слайда:

4.1.1 Общая схема распознавателя В процессе работы распознаватель может выполнять некоторые элементарные операции: Чтение очередного символа Сдвиг либо входной ленты либо считывающего устройства на заданное количество символов Преобразование информации в памяти Изменение состояния устройства управления УУ определяет какая операция будет выполняться на каждом шаге работы распознавателя.

Слайд 5

Описание слайда:

4.1.1 Общая схема распознавателя Конфигурация распознавателя определяется: состоянием устройства управления; содержимым цепочки символов и положением считывающей головки в ней; содержимым внешней памяти. Для распознавателя задана начальная конфигурация: устройство управления находится в заданном начальном состоянии, входная головка читает самый левый символ на входной ленте, память либо пуста либо имеет заранее установленное начальное содержимое.

Слайд 6

Описание слайда:

4.1.1 Общая схема распознавателя Заключительная конфигурация: устройство управления находится в одном из состояний, принадлежащем заранее выделенному множеству заключительных состояний, входная головка обозревает правый концевой маркер иногда требуется, чтобы заключительная конфигурация памяти удовлетворяла некоторым условиям. Распознаватель допускает входную цепочку α если, начиная с начальной конфигурации, в которой цепочка записана на входной ленте, распознаватель может проделать последовательность шагов, заканчивающихся заключительной конфигурацией.

Слайд 7

Описание слайда:

4.1.2 Классификация распознавателей по видам считывающих устройств односторонние двусторонние по видам УУ детерминированные недетерминированные по виду внешней памяти без внешней памяти с ограниченной внешней памятью с неограниченной внешней памятью Сложность распознавателя напрямую зависит от типа языка, входящие цепочки которого могут допускать распознаватели.

Слайд 8

Описание слайда:

4.1.2 Классификация распознавателей Распознавателем языка с фразовой структурой является недетерминированный двусторонний автомат с неограниченной памятью (машина Тьюринга). Распознавателем КЗ языка является недетерминированный двусторонний автомат с линейно-ограниченной памятью. Распознавателем КС языка является недетерминированный односторонний автомат с ограниченной магазинной памятью (МП-автомат). Среди всех КС языков выделяют класс КС детерминированных языков. Распознавателем регулярного языка является односторонний детерминированный конечный автомат без внешней памяти.

Слайд 9

Описание слайда:

4.1.3 Задача разбора На основе имеющейся грамматики некоторого формального языка построить распознаватель этого языка. Для КС, регулярных языков известно, что задача разбора разрешима.

Слайд 10

Описание слайда:

4.2 Распознаватели КС языков. Автомат с магазинной памятью (МП-автомат) МП –автомат можно представить следующим образом R (Q,V,Z, δ, q0, Z0,F). Q – множество состояний V – алфавит Z – множество магазинных символов V≤ Z δ - функция переходов, которая отображает Q × (V  {}) × Z в подмножество P(Q × Z*) q0 – начальное состояние Z0 – начальный магазинный символ F – непустое множество конечных состояний F≤ Q

Слайд 11

Описание слайда:

4.2 Распознаватели КС языков. Автомат с магазинной памятью (МП-автомат)

Слайд 12

Описание слайда:

4.2 Распознаватели КС языков. Автомат с магазинной памятью (МП-автомат) МП-автомат называется недерминированным, если возможен переход из одной конфигурации в более чем одну конфигурацию. МП-автомат принимает входную цепочку символов, если он переходит из начальной конфигурации (q0, Z0, α), q0  Q, Z0  Z, в одну из конечных конфигураций (f, z, ), f  F, z  Z, получив на вход эту цепочку символов.

Слайд 13

Описание слайда:

4.2 Распознаватели КС языков. Автомат с магазинной памятью (МП-автомат) На каждом шаге МП-автомат выполняет операции: ↑ - выталкивает из магазина верхний символ ↓А – поместить в магазин символ А. ↕XYZ – символ X замещается YZ Эквивалентно: ↑X↓Y↓Z [t] – УУ переходит в следующее состояние, t  Q → - входная головка смещается на один символ вправо.

Слайд 14

Описание слайда:

4.2 Распознаватели КС языков. Автомат с магазинной памятью (МП-автомат) Разработать автомат с магазинной памятью для разбора скобочных выражений. Множество входных символов: V= { ( , ) , } Множество магазинных символов: Z = { A, маркер дна ) Множество состояний: t Q = { S } q0 = S Z0 = S F = { S }

Слайд 15

Описание слайда:

4.2 Распознаватели КС языков. Автомат с магазинной памятью (МП-автомат)

Слайд 16

Описание слайда:

4.2 Распознаватели КС языков. Автомат с магазинной памятью (МП-автомат)

Слайд 17

$4.2 Распознаватели КС языков. Автомат с магазинной памятью (МП-автомат) Д\З. Разобрать работу МП-автомата α = ()()) β = (()) Результат работы...$

Описание слайда:

4.2 Распознаватели КС языков. Автомат с магазинной памятью (МП-автомат) Д\З. Разобрать работу МП-автомата α = ()()) β = (()) Результат работы представить в виде таблички.

Слайд 18

Описание слайда:

4.3 Синтаксический разбор Если попытаться формализовать задачу на уровне элементарного метаязыка, то она будет ставиться следующим образом: Дан язык L(G) с грамматикой G, в которой S - начальный нетерминал. Построить дерево разбора входной цепочки ω = a1a2a3...an.

Слайд 19

Описание слайда:

Классификация методов организации синтаксического разбора

Слайд 20

Описание слайда:

4.3.1 Методы разбора Нисходящий разбор заключается в построении дерева разбора, от корневой вершины. Разбор заключается в заполнении промежутка между начальным нетерминалом (начальный символ грамматики) и символами входной цепочки правилами, выводимыми из начального нетерминала. Подставляемое правило в общем случае выбирается произвольно.

Слайд 21

Описание слайда:

4.3.1 Методы разбора G = ({S}, {a, +, *}, P, S), S -> a S -> S + S S -> S * S S => S+S => a+S => a+S*S => a+a*S => a+a*S+S => a+a*a+S => a+a*a+a - левосторонний S => S+S => S+a => S*S+a => S*a+a => S+S*a+a => S+a*a+a => a+a*a+a -правосторонний S => S*S => S+S*S => S+S*S+S => a+ S*S+S => a+a*S+S => a+a*S+a => a+a*a+a - произвольный

Слайд 22

Описание слайда:

Нисходящий разбор слева-направо

Слайд 23

Описание слайда:

Нисходящий произвольный разбор

Слайд 24

Описание слайда:

4.3.1 Методы разбора При восходящем разборе дерево начинает строиться от терминальных листьев путем подстановки правил, применимых к входной цепочке, в общем случае, в произвольном порядке. Процесс построения дерева разбора завершается, когда все символы входной цепочки будут являться листьями дерева, корнем которого окажется начальный нетерминал.

Слайд 25

Описание слайда:

Восходящий разбор слева-направо

Слайд 26

Описание слайда:

Восходящий произвольный разбор

Слайд 27

Описание слайда:

4.3.1 Методы разбора Комбинированный разбор может быть реализован тогда, когда процесс распознавания разбивается на два этапа. На одном из них осуществляется нисходящий, а на другом - восходящий разбор. Комбинированным можно считать разбор в любом трансляторе, если фазу лексического анализа принять за первый этап, а синтаксического - за второй.

Слайд 28

Описание слайда:

Пример комбинированного разбора

Слайд 29

Описание слайда:

4.3.2 Последовательность разбора Повышение эффективности разбора осуществляется разработкой грамматик, специально поддерживающих согласованные между собой метод и последовательность. Грамматики предназначенные для нисходящего разбора обычно используются для левостороннего вывода, входная цепочка будет разбираться слева направо (когда порождение новой цепочки на каждом шаге осуществляется для самого левого нетерминала). Грамматики, ориентированные на восходящий разбор, обычно оптимизированы под правосторонний вывод, что позволяет, при синтаксическом разборе, осуществлять подстановки нетерминалов справа налево (когда порождение новой цепочки на каждом шаге осуществляется для самого правого нетерминала).

Слайд 30

Описание слайда:

4.3.3 Использование просмотра вперед В грамматиках могут встречаться альтернативные правила, начинающиеся с одинаковых цепочек символов. Возникающая неоднородность может быть решена путем предварительного просмотра правила на n символов вперед до той границы, начиная с которой данное правило можно будет отличить от других. В КС грамматиках число, определяющее количество символов, анализируемых перед выбором правила подстановки (1,2,...) используется для классификации: КС(1), КС(2). На ряду c просмотром вперед используется: преобразование грамматик к однозначным (детерминированным) и анализ с возвратами.

Слайд 31

Описание слайда:

4.3.4 Использование возврата Синтаксический разбор с возвратами выполняется аналогично тому, как осуществляется непрямой лексический анализ. Возвраты производятся для альтернативных правил, начинающихся с одинаковых подцепочек. Такой подход замедляет разбор.

Слайд 32

Описание слайда:

4.3.4 Использование возврата Рассмотрим КС-грамматику. L = {an bn | n>0} ab n=1 aabb n=2 aaabbb n=3 S -> ASB | ε A -> a B -> b Или S -> aSb | ab

Слайд 33

Описание слайда:

4.4 Нисходящие распознаватели с возвратами Синтаксический анализ

Слайд 34

Описание слайда:

Вообразим, что на любом этапе разбора, в каждом узле уже построенной части дерева находится по одному человеку. Люди, которые находятся в терминальных узлах, занимают места соответственно символам предложения. Вообразим, что на любом этапе разбора, в каждом узле уже построенной части дерева находится по одному человеку. Люди, которые находятся в терминальных узлах, занимают места соответственно символам предложения. Участок дерева разбора

Слайд 35

Описание слайда:

Некоему человеку надлежит провести разбор предложения ω. Некоему человеку надлежит провести разбор предложения ω. Ему необходимо отыскать вывод S =>+ ω, где S – начальный символ. Пусть для S существуют правила S ::= X1 X2 .. Xn | Y1 Y2 .. Ym | Z1 Z2 .. Zk Сначала человек пытается определить правило S ::= X1 X2 .. Xn. Если нельзя построить дерево, используя это правило, он делает попытку применить второе правило S ::= Y1 Y2 .. Ym. В случае неудачи он переходит к следующему правилу и т.д.

Слайд 36

Описание слайда:

Как ему определить, правильно он выбрал непосредственный вывод S ::= X1 X2 .. Xn? Как ему определить, правильно он выбрал непосредственный вывод S ::= X1 X2 .. Xn? Если вывод правилен, то для некоторых цепочек xi будет иметь место ω =x1 x2 .. xn, где Xi => + xi, для i=1,...,n. Прежде всего, человек, выполняющий разбор, возьмет себе приемного сына M1, который должен будет найти вывод X1=>*x1, такого, что ω = x1... Если сыну M1 удастся найти такой вывод, он (и любой из сыновей, внуков и т.д.) закрывает цепочку x1в предложении ω и сообщает своему отцу об успехе.

Слайд 37

Описание слайда:

Тогда его отец усыновит M2, чтобы тот нашел вывод X2=> *x2, где ω = x1x2... и ждет ответа от него и т.д. Тогда его отец усыновит M2, чтобы тот нашел вывод X2=> *x2, где ω = x1x2... и ждет ответа от него и т.д. Как только сообщил об успехе сын Mi-1,он усыновит еще и Mi, чтобы тот нашел вывод Xi => *xi. Сообщение об успехе, пришедшее от сына Mn, означает что разбор предложения закончен.

Слайд 38

Описание слайда:

Как же действует каждый из Mi? Как же действует каждый из Mi? Положим, целью Mi является терминал t, такой, что ω =x1 x2 .. xi-1 t.. ,где символы в x1,x2,...,xi-1 уже закрыты другими людьми. Mi проверяет, совпадает ли очередной незакрытый символ t с его целью Xi. Если это так, он закрывает этот символ и сообщает об успехе. Если нет, сообщает об неудаче. Если цель Mi – нетерминал Xi, то Mi поступает точно так же, как и его отец. Он начинает проверять правые части правил, относящихся к нетерминалу, и, если необходимо, тоже усыновляет или отрекается от сыновей. Если все его сыновья сообщают об успехе то Mi в свою очередь сообщает об успехе отцу.

Слайд 39

Описание слайда:

Если отец просит Mi найти другой вывод, а целью является терминальный символ, то Mi сообщает о неудаче, так как другого такого вывода не существует. В противном случае Mi просит своего младшего сына найти другой вывод и реагирует на его ответ также, как и раньше. Если все сыновья сообщат о неудаче, он сообщит о неудаче своему отцу. Если отец просит Mi найти другой вывод, а целью является терминальный символ, то Mi сообщает о неудаче, так как другого такого вывода не существует. В противном случае Mi просит своего младшего сына найти другой вывод и реагирует на его ответ также, как и раньше. Если все сыновья сообщат о неудаче, он сообщит о неудаче своему отцу. Каждый человек должен помнить о своей цели, о своем отце, сыновьях и свое место во входной цепочке и грамматике.

Слайд 40

Описание слайда:

4.5 Реализация нисходящего распознавателя с возвратами Синтаксический анализ

Слайд 41

Описание слайда:

Форма, которая будет использоваться для записи правил G = ({i, +, *, (, )}, {S, Е, Т, F}, Р, S) Р: 1) S ::= Е# 2) Е ::= Т + Е 3) Е ::= Т 4) Т ::= F * Т 5) Т ::= F 6) F ::= (Е) 7) F ::= i

Слайд 42

Описание слайда:

Принятые обозначения char input []; - строка содержит входную цепочку символов; char grammar []; - массив с грамматикой; int j; - индекс самого левого незакрытого терминала входной цепочки input[j]; int i; - индекс в массиве grammar определяющий цель с которой работает человек в данный момент; struct node { char goal; - цель int fat; - "имя" отца int son; - "имя" младшего из сыновей int bro; - "имя" его брата int i; - индекс в массиве grammar определяющий цель, с которой работает человек в данный момент } int v; - количество элементов в стеке; int с; - "имя" человека (индекс в стеке); #define MAX_LEVEL 50 node S[MAX_LEVEL]; - стек;

Слайд 43

Описание слайда:

Принятые обозначения Понятия относящиеся к человеку, работающему в данный момент (находится на уровне с) #define GOAL S[ с ] . goal #define FAT S[ с ] . fat #define SON S[ с ] . son #define BRO S[ с ] . bro #define I S[ с ] . i S(v) = (GOAL, FAT, SON, BRO, I) - в стек на уровень v заносится информация о текущей вершине разбора. Функции: int terminal (char g) - определяет, является ли g терминалом, если да, то возвращает 1 иначе 0. int index (char g) - возвращает индекс правой части для цели g в массиве grammar. int stop(int result) - прекращает разбор и возвращает результат разбора, т.е. является ли данная цепочка предложением или нет.

Слайд 44

Описание слайда:

Структура "семьи"

Слайд 45

Описание слайда:

Алгоритм в псевдокоде Начальная установка: S(l) = ('S', 0, 0, 0, 0); с = 1; v = 1; j = 1; goto новый человек ; новый человек: if (terminal(GOAL)) if (input[j] == GOAL) { j++; goto успех } else goto неудача I = index(GOAL); // индекс правой части для GOAL цикл: if (grammar[I] == ‘|’) if (FAT != 0) goto успех ; else stор('сообщение'); // предложение языка if (grammar[I] == '$') // конец правила if (FAT != 0) goto неудача else stop('сообщение); // не предложение языка

Слайд 46

Описание слайда:

Алгоритм в псевдокоде // очередная установка v++; S(v) = (grammar[I], 0, c, 0, SON); SON = v; с = v; goto новый человек успех: с = FAT; I++; goto цикл неудача: с = FAT; v--; son = S(son).bro; goto еще раз еще раз: if (SON == 0) {while (grammar [I++] != ‘|’); // переход к следующему правилу goto цикл // просьба к сыну повторить попытку выбора } I--; с = SON; if (!terminal(GOAL)) goto еще раз; // цель терминал, вывод построить нельзя j--; goto неудача ;

Слайд 47

Описание слайда:

Пример

Слайд 48

Описание слайда:

4.6 Нисходящие распознаватели без возвратов Алгоритм работы МП-автомата не требует возврата на предыдущий шаг и обладает линейными характеристиками от длины входной цепочки. В случае не успеха выполнения алгоритма входная цепочка однозначно не принимается и повторная итерация разбора не принимается. Выбор одного из возможных альтернатив является выбор ее на основе символа a є VT, обозреваемого считывающей головкой автомата на каждом шаге его работы.

Слайд 49

Описание слайда:

4.6.1 Левосторонний разбор по методу рекурсивного спуска Для каждого A є VN, строится своя процедура разбора, которая получает на вход цепочку символов α и положение считывающей головки. Если для A определено более одного правила, то процедура разбора ищет среди множества правил вида A -> aγ, a є VT, γ є (VT ᴜ VN)* правила, первый символ которого совпадал бы с текущим входным символом a = α[i]: Если такого правила нет, то алгоритм прекращается и цепочка не является цепочкой языка, Если правило найдено и единственное, то запоминается номер правила, считывающая головка перемещается вправо (i++), а для каждого нетерминала цепочки γ вызывается соответствующая процедура разбора.

Слайд 50

Описание слайда:

4.6.2 Условия применимости РС-метода либо A -> , где   (VT  VN)* и это единственное правило вывода для этого нетерминала; либо A > a11 | a22 | ... | ann, где ai  VT для всех i = 1,2,...,n; ai  aj для i  j; i  (VT  VN)*, т. е. если для нетерминала А правил вывода несколько, то они должны начинаться с терминалов, причем все эти терминалы должны быть различными. Этим условиям удовлетворяют незначительное количество КС-грамматик, это достаточные, но необязательные условия.

Слайд 51

Описание слайда:

4.6.3 Пример реализации РС-метода G ({a,b,c}, {A,B,C,S}, P, S) P: 1) S -> aA 2) S -> bB 3) A -> a 4) A -> bA 5) A -> cC 6) B -> b 7) B -> aB 8) B -> cC 9) C -> AaBb

Слайд 52

Описание слайда:

// 1) S -> aA // 1) S -> aA // 2) S -> bB int S () { int rc=0; if (c==’a’) { R.enque(1); gc(); rc=A(); } else if (c==’b’) { R.enque(2); gc(); rc=B(); } return (rc); }

Слайд 53

Описание слайда:

Слайд 54

Описание слайда:

4.8 Преобразование КС грамматик Для КС-грамматик невозможно проверить их однозначность и эквивалентность. Правила КС-грамматик преобразовывают к заранее заданному виду, чтобы получить эквивалентную грамматику. Все преобразования можно разбить на две группы: преобразования, связанные с исключением из грамматики тех правил и нетерминалов, без которых она может существовать (ведет к упрощению правил); преобразования, в результате которых изменяется вид и состав правил грамматики (не связано с упрощениями).

Слайд 55

Описание слайда:

4.8.1 Приведенные грамматики Приведенные КС-грамматики – это КС-грамматики, которые не содержат недостижимых и бесполезных символов, циклов, ε-правил. Для того, чтобы преобразовать произвольную КС-грамматику к приведенному виду необходимо: удалить все бесполезные символы; удалить все недостижимые символы; удалить ε-правила; удалить цепные правила или циклы.

Слайд 56

Описание слайда:

4.8.2 Удаление бесполезных символов Символ A  VN называется бесполезным в грамматике G = (VT, VN, P, S), когда из него нельзя вывести ни одной терминальной цепочки, т.е. если множество {   VT* | A   } пусто. Д/З Алгоритм удаления бесполезных символов (мет. Руденко)

Слайд 57

Описание слайда:

Алгоритм удаления бесполезных символов Вход: КС-грамматика G = (VT, VN, P, S). Выход: КС-грамматика G' = (VT, VN', P', S), не содержащая бесплодных символов, для которой L(G) = L(G’). Метод: Рекурсивно строим множества N0, N1, ... N0 = , i = 1. Ni = {A | (A -> )  P и   (Ni-1  VT)*}  Ni-1. Если Ni  Ni-1, то i = i + 1 и переходим к шагу 2, иначе VN' = Ni; P' состоит из правил множества P, содержащих только символы из VN'  VT;

Слайд 58

Описание слайда:

Алгоритм удаления бесполезных символов

Слайд 59

Описание слайда:

4.8.3 Удаление недостижимых символов Символ x  (VT  VN) называется недостижимым в грамматике G = (VT, VN, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики. x  α, где { α | S => α, α  (VT  VN) } ≠ 0 Пример. G ( {a, b}, {S, A, B}, P, S); P: S -> a | aA A -> b | bA B -> b Д/З Алгоритм удаления недостижимых символов (мет. Руденко)

Слайд 60

Описание слайда:

Алгоритм удаления недостижимых символов Вход: КС-грамматика G = (VT, VN, P, S) Выход: КС-грамматика G' = (VT', VN', P', S), не содержащая недостижимых символов, для которой L(G) = L(G'). Метод: V0 = {S}; i = 1. Vi = {x | x  (VT  VN), в P есть A->x и AVi-1, ,(VTVN)}  Vi-1. Если Vi  Vi-1, то i = i + 1 и переходим к шагу 2, иначе VN' = Vi  VN; VT' = Vi  VT; P' состоит из правил множества P, содержащих только символы из Vi.

Слайд 61

Описание слайда:

Пример G = ( {a,b,c,d}, {A, B, C, D, E, F, G, S}, P, S) P: S -> aAB | E A -> aA | bB B -> ACb | b C -> A | bA | cC | aE E -> cE | aE | Eb | ED | FG D -> a | c | Fb F -> BC | EC | AC | Fd G -> Ga | Gb

Слайд 62

Описание слайда:

Пример работы алгоритма N0 = , i=1 N1 = {B, D}, i=2, V0 ≠ V1 N2 = {B, D, A}, i=3, V1 ≠ V2 N3 = {B, D, A, S, C}, i=4, V2 ≠ V3 N4 = {B, D, A, S, C, F}, i=5, V3 ≠ V4 N5 = {B, D, A, S, C, F}, i=5, V4 = V5 VN' = V5 = { B, D, A, S, C, F }, VT' = VT P’: S -> aAB A -> aA | bB B -> ACb | b C -> A | bA | cC D -> a | c | Fb F -> BC | AC | Fd V0 = {S}, i=1 V1 = {S, a, A, B}, i=2, V0 ≠ V1 V2 = {S, a, A, B, b, C}, i=3, V1 ≠ V2 V3 = {S, a, A, B, b, C, c}, i=3, V2 ≠ V3 V4 = {S, a, A, b, B, C, c}, i=4, V3 = V4 VN'' = V5 = { B, A, S, C} VT'' = {a, b, c} P'': S -> aAB A -> aA | bB B -> ACb | b C -> A | bA | cC

Слайд 63

Описание слайда:

4.8.5 Устранение ε-правил Грамматика G называется грамматикой без ε-правил, если в ней не существует правил вида A -> ε, A ≠ S, и может присутствовать только одно правило S -> ε, в том случае, если пустая цепочка принадлежит языку ε  L (G), и при этом нетерминал S не встречается в правой части ни одного правила грамматики.

Слайд 64

Описание слайда:

4.8.5 Устранение ε-правил Алгоритм. 1. V0 = {A | (A -> ε)  P}; i = 1. 2. Vi = Vi-1 {A | (A -> α)  P, α  Vi-1}. 3. Если Vi ≠ Vi-1, то i=i+1, переход к шагу 2, иначе к шагу 4. 4. VN' = VN, VT’ = VT, в P' входят все правила из P кроме правила A -> ε. 5. Если (A -> α)  P и α  Vi*, то на основании цепочки α строим множество цепочек α' путем исключения из α всех возможных комбинаций символов из Vi. 6. Если S  Vi, тогда добавляем S' в множество VN' и в P’: S' -> ε | S, иначе S' = S.

Слайд 65

Описание слайда:

Пример G ( {a, b, c}, {A, B, C, S}, P, S) P: S -> AaB | aB | cC A -> AB | a | b | B B -> Ba | ε C -> AB | c 1. V0 ={ B }, i = 1 2. V1 = { B, A }, i=2, V0 ≠ V1 3. V2 = { B, A, C }, i=3, V1 ≠ V2 4. V3 = { B, A, C }, i=4, V2 ≠ V3 VN' = { A, B, C, S } VT' = {a, b, c} P': S -> AaB | Aa | aB | cC | a | c A -> AB | a | b | B B -> Ba | a C -> AB | A | B | c

Слайд 66

Описание слайда:

4.8.6 Устранение цепных правил Циклом или циклическим выводом грамматики G называется вывод A =>* A, A  VN. Циклы возможны в том случае, если в КС грамматике присутствует цепное правило A -> B, A, B  VN. Алгоритм. Для каждого нетерминального символа x строится специальное множество цепных символов Nx. Для каждого нетерминала из множества VN повторяются шаги 1-4, затем переходим к шагу 5. 1. N0x = {x}, i=1 2. Nix = Ni-1x { B | (A -> B)  P, A  Ni-1x }, i=1 3. Если Nix ≠ Ni-1x, то i=i+1, переход к шагу 3, иначе Nx = Nix – {x}, переход к шагу 1. 4. VN' = VN, VT' = VT, в P' входят все правила из P кроме правила A -> B. 5. Для всех правил (A -> α)  P, если A  NB, A ≠ B в P’ добавляем B -> α.

Слайд 67

Описание слайда:

Пример G ( {a, b, c}, {A, B, C, S}, P, S) P: S - > AaB | Aa | aB | cC | a | c A -> AB | a | b | B B -> Ba | a C -> AB | A | B | c

Слайд 68

Описание слайда:

Д/З ДЗ. Дана грамматика арифметических выражений, устранить цепные правила. G ( {a, b, +, *, (, )}, {F, T, E}, P, E) P: E -> E+T | T T -> T * F | F | (E) | a | b F -> (E) | a | b

Слайд 69

Описание слайда:

4.8.7 Устранение левой рекурсии Нетерминальный символ A грамматики G называется рекурсивным, если для него существует вывод A =>+ αAβ, α, β  (VT  VN)*: A - леворекурсивный, если α = ε, β ≠ ε A - праворекурсивный, если α ≠ ε, β = ε. КС грамматика может быть как лево- так праворекурсивной, а также может быть левоправорекурсивной относительно разных нетерминалов.

Слайд 70

Описание слайда:

4.8.7 Устранение левой рекурсии 1. N = { A1, A2 … An} i=1, n – количество нетерминалов 2. Рассмотрим все правила для Ai. Если эти правила не содержат левой рекурсии, то переносим их в P', символ Ai добавляем в множество VN'. Иначе если Ai -> Ai α1 | Ai α2 | … | Ai αm | β1 | β2 | … | βp , где ни одна цепочка βj не начинается с символа Ak 1 ≤ j ≤ p, k ≤ i. Вместо этого правила во множество P' дописывается правило вида Ai -> β1 | β2 | … | βp | β1Ai' | β2Ai' | … | βpAi' Ai' -> α1 | α2 | … | αm | α1Ai' | α2Ai' | … | αmAi' Если i=n, то грамматика G' построена, иначе i=i+1; j=1, переходим к шагу 4.

Слайд 71

Описание слайда:

4.8.7 Устранение левой рекурсии 3. Для устранения косвенной левой рекурсии. 4. Для символа Aj во множестве правил P' заменить все правила вида: Ai -> Aj α, где α  (VT  VN)* Ai -> β1 α | β2 α | … | βm α причем Aj -> β1 | β2 | … | βm все правила для Aj Т.к. правая часть нетерминала Aj не может начинаться с нетерминального символа Ai, то и правая часть правил для нетерминала Ai будет начинаться с этого символа. 5. Если j=i-1, то переход к шагу 2, иначе j=j+1, переход к шагу 4. 6. S' = An

Слайд 72

Описание слайда:

Пример G = ({a, b, +, *, (, )}, {F, T, E}, P, E) P: E -> E+T | T T -> T * F | F F -> (E) | a | b

Слайд 73

Описание слайда:

4.8.8 Устранение левой факторизации Если в грамматике существуют правила вида A -> aα1 | aα2 | … | aαn | β1 | … | βm, где a  VT, αi, βj  (VT  VN)* и входная строка начинается с непустой строки, выводимой из а, то неизвестно разворачивать по aα1 или aα2. Можно преобразовать правила вывода данного нетерминала объединив правила вывода с общими началами в одно правило: A -> aA' | 1 | ... | m A' -> 1 | 2 | ... | n

Слайд 74

Описание слайда:

Пример Рассмотрим грамматику условных операторов: S→if E then S| if E then S else S | a E→b После левой факторизации грамматика принимает вид S→ if E then S S' | a S' → else S | ε E→ b К сожалению, грамматика остается неоднозначной.