spoPresentation2

Задача разбора

Задача разбора в общем виде состоит в построении распознавателя для некоторого языка на основе уже имеющейся грамматики

Заданная грамматика и распознаватель должны быть эквивалентны, т.е. определять один и тот же язык

В общем виде эта задача решается не для всех языков. Для синтаксических конструкций ЯП задача разбора решаема

61

Задача разбора

Язык L(G) называется распознаваемым, если существует алгоритм, который за конечное число шагов позволяет определить, принадлежит ли произвольная цепочка D над основным словарем

грамматики языку L(G)

Если при этом число шагов алгоритма зависит от длины цепочки и может быть оценено до начала его выполнения, язык L(G) называется легко распознаваемым

62

Классификация грамматик

Ноам Хомски предложил классифицировать грамматики по структуре их правил

Если все без исключения правила грамматики удовлетворяют некоторой заданной структуре, то грамматика принадлежит заданному типу

63

Классификация грамматик

Тип 0. Грамматики с фразовой структурой

На структуру правил не накладывается никаких ограничений

Для грамматики вида G(T,N,P,S), V=N T правила имеют вид: DoE, D V+, E V*

Это самый общий тип грамматик. Все формальные грамматики принадлежат этому классу. Грамматики, которые относятся к типу 0, и не могут быть отнесены к другим типам, имеют самую сложную структуру

64

Классификация грамматик

Тип 1. Контекстно-зависимые (КЗ)

D1АD2oD1ED2 ; D1, D2 V*, А N, E V+

Один и тот же нетерминальный символ может быть заменен на ту или иную цепочку символов в зависимости от контекста, в котором он встречается

Неукорачивающие: DoE, D, E V+, |E|t|D|

Доказано, что КЗ и неукорачивающие грамматики эквивалентны

65

Классификация грамматик

Для любого языка, заданного КЗ грамматикой, можно построить неукорачивающую грамматику, задающую эквивалентный язык, и наоборот

При построении компиляторов КЗ не применяются, поскольку синтаксические конструкции ЯП имеют более простую структуру и могут быть построены с помощью грамматик других типов

66

Классификация грамматик

Тип 2. Контекстно-свободные (КС)

АoE, А N, E V+

КС грамматики имеют в правой части как минимум один символ. Они являются неукорачивающими

Образуются из условий КЗ-грамматик, у которых D1 = D2 = O V*

67

Классификация грамматик

Почти эквивалентный им класс – укорачивающие КС грамматики

АoE, А N, EV*

Синтаксис большинства ЯП основан на КС грамматиках

Их используют для построения синтаксического анализатора компиляторов

68

Классификация грамматик

Тип 3. Регулярные грамматики

Леволинейные грамматики

АoВJ, АoJ, А,В N, J Т*

При выводе нетерминальный символ если и остается, то слева

Праволинейные грамматики

АoJВ, АoJ, А,В N, J Т*

Леволинейные и праволинейные грамматики эквивалентны

69

Классификация грамматик

Для любого языка, заданного леволинейной грамматикой, может быть построена праволинейная, определяющая эквивалентный язык, и наоборот

Чаще используются леволинейные грамматики, поскольку их построение отвечает порядку построения предложений ЯП

Используются при описании лексем ЯП

На их основе строятся лексические анализаторы

70