I.9.2. Запись правил грамматики в графическом виде

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

1)точка входа в диаграмме никак не обозначается, из нее начинается входная дуга;

2) нетерминальный символ обозначается прямоугольником, в котором вписано обозначение символа;

3)цепочка нетерминальных символов на диаграмме обозначается овалом, кругом, внутрь которого вписана цепочка;

4) узловая точка в диаграмме обозначается или закрашена кружком;

5)точка выхода никак на диаграмме не обозначается, в нее входит дуга графа.

Каждая дуга имеет одну точку входа и одну точку выхода, но сколько угодно вершин 3ех типов.

Пример графического представления цепочки целых десятичных цифр со знаком

 

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

 

I.10. Распознаватель

I.10.1. Схема распознавателя

Разборщик – это специальный автомат, который позволяет определить принадлежность цепочки символов некоторому языку. Задача его в том, чтобы на основании исходной цепочки символов определить принадлежит ли она заданному языку или нет.

Распознаватель – это один из способов определения языка.

 

 

В общем виде его можно изобразить в виде условной модели, которая отражает работу алгоритма распознавателя.

 

Лента (1) содержит входную цепочку символов. К ней примыкает считывающая головка для считывания символов этой цепочки. УУ – координирует работу распознавателя, оно имеет набор состояний и память для хранения своего состояния. Внешняя память хранит информацию в процессе работы распознавателя и, в отличии от УУ, имеет значительно огромный объем. Распознаватель работает символами своего алфавита, который конечен. Он содержит все допустимые символы входных цепочек, а так же дополнительный алфавит символов, которые могут обрабатываться УУ и храниться во внешней памяти. Распознаватель выполняет следующие операции:

1) чтение очередного символа из входной цепочки;

2) сдвиг входной цепочки на заданное количество символов;

3) доступ к внешней памяти для чтения или записи информации;

4) преобразование информации в памяти.

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

1) содержанием входной цепочки символов и в положении считывающей головки в ней;

2) состоянием УУ;

3) содержанием внешней памяти.

В начале конфигурации считывающая головка обозревает 1ый символ входной цепочки. УУ находится в начальном заданном состоянии, а внешняя память либо пуста, либо содержит информацию. Для распознавателя создается 1 или несколько конфигураций. Язык, определяемый распознавателем, - это множество всех цепочек, допускаемые распознавателем.

 

I.10.2. Задача разбора

Для каждого языка программирования важно уметь не только построить текст программы, но и определить принадлежность текста к данному языку. Эту задачу решают компиляторы в числе прочих задач. Компилятор должен построить эквивалентную ей результирующую программу. В отношении исходной программы компилятор выступает в роле распознавателя. Грамматики и распознаватель – два независимых метода, которые могут быть использованы для определения какого-либо языка. При создании компилятора для некоторого языка программирования возникает задача связи между собой этих методов создания языка. Разработчикам известны языки программирования и грамматика (и стандартный язык). Задача разработчика построить распознаватель для заданного языка, который будет основой в компиляторе. Таким образом, задача разбора заключается в следующем: на основе грамматики некоторого языка построить распознаватель для этого языка. Заданная грамматика и распознаватель должны быть эквивалентны, т.е. определять один и тот же язык. Задача разбора в общем виде может быть решена не для всех языков. Языки программирования не являются чисто формальными языками и несут в себе некоторый смысл – семантику, то задача разбора для создания реальных компиляторов понимается несколько шире, чем она формируется для чисто формальных языков, т.е.компилятор должен определить, принадлежность одной цепочки символов заданному языку, но и определить ее смысловую нагрузку. Необходимо выявить те правила грамматики, на основании которых цепочка была рассмотрена. Задача разбора расширяется тем, что распознаватель в составе компилятора должен установить не только факт ошибки в входной программе, но и по возможности определить тип ошибки, но и то место в входной цепочке символов, где она встречается.