Синтаксические диаграммы

Это ориентированный граф с двумя фиксированными вершинами: входной, из которой дуги только выходят, и выходной, в которую дуги только входят.

Дуги этого графа могут быть помечены терминальными и нетерминальными символами. В расширенной диаграмме с терминальным Т и нетерминальным N алфавитами каждому нетерминалу А и его правилу вывода А ® a, где a - регулярное выражение в алфавите TUN, отвечает одна синтаксическая диаграмма. При обозначении дуг помеченными терминальными символами условились эти символы писать строчными буквами и заключать в окружность. Нетерминальные символы условились писать заглавными буквами и размещать в прямоугольнике. Регулярное выражение будет обозначаться греческими буквами внутри ромба.

На рисунке 2 показаны примеры изображения дуг, помеченных терминальным символом а, нетерминальным – А и регулярным выражением – a.

Рисунок 2

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

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