- •Формальные грамматики и языки.
- •Задача разбора
- •Классификация грамматик по Холмскому.
- •Диаграмма состояний
- •Отношения предшествования
- •Распознаватель
- •Матрица предшествования
- •Некоторые приемы приведения к грамматикам простого предшествования.
- •Представление автоматов.
- •Концевые маркеры и выходы из распознавания.
- •Эквивалентность состояний.
- •Проверка эквивалентности двух состояний.
- •Недостижимые состояния.
- •Алгоритм составления списка достижимых состояний.
- •Приведённые автоматы.
- •Получение минимального автомата.
- •Недетерминированные автоматы.
- •Эквивалентность недетерминированных и детерминированных конечных распознавателей (нкр и дкр).
- •Задание:
- •Транслятор.
- •Введение таблицы символов.
- •Включение неявной информации.
- •Обнаружение ошибок.
- •Макрообработка и операции, выполняемые во время компиляции.
- •Синтез объектной программы.
- •Оптимизация.
- •Генерация кода.
- •Редактирование связей и загрузки.
- •Задача идентификации. Реализация ка при работе трансляторов.
- •Хранение информации о лексемах.
- •Механизм запоминания.
- •Метод хеширования.
- •Нисходящий разбор с возвратами.
- •Начальная установка.
- •Новый человек.
- •Неудача
- •Класс грамматик, допускающих нисходящий распознаватель.
- •Статистические управляемые схемы перевода и атрибутные грамматики.
- •Контекстные условия
Задание:
Построить КА, который будет распознавать слова GO TO, причём между ними может быть произвольное (включая нулевое) число пробелов.
Транслятор.
Транслятор для входного языка, порождаемого грамматикой предшествования можно построить по классической схеме, в которой чётко выделяются 3 части: лексический анализатор, распознаватель (синтаксический анализатор) и генератор (семантический анализатор);
Цель лексического анализа состоит в переводе исходной программы на стандартный входной язык компилятора и преобразовании её к виду, удобному для дальнейшей обработки на этапах синтаксического и семантического анализа.
В процессе лексического анализа обычно собираются из отдельных знаков (букв и цифр) простые синтаксические конструкции – лексемы. Лексемы – минимальные единицы информации, наделённые смыслом (идентификаторы, цифры, служебные слова и т.д.). При дальнейшей обработке такие простые конструкции рассматриваются как неделимые, поэтому оставлять их распознавание и сборку до этапа синтаксического анализа невыгодно.
В общем случае, в процессе лексического анализа необходимо выполнить следующее:
Перекодировать исходную программу, рассматриваемую как входная строка, и привести её к стандартному входному языку.
Выделить и собрать из отдельных знаков основные символы языка – лексемы.
Распознаватель решает задачу разбора. Алгоритм для грамматик предшествования уже рассмотрен. В процессе синтаксического анализа распознаватель использует матрицу предшествования (или функции предшествования) и таблицу порождающих правил грамматики входного языка. Каждая запись этой таблицы содержит одно из порождающих правил и ( для некоторых правил) имя семантической подпрограммы, которую нужно выполнить, когда это правило применяется для редукции.
Результат работы распознавателя – разбор входной программы.
Генератор получает на вход разбор и, используя семантические подпрограммы, отвечающие применённым при разборе правилам, генерируют машинные команды или предложения другого входного языка.
Возможны 2 схемы работы транслятора.
Первая – использует блочный принцип, при котором части транслятора вызываются в последовательности: лексический анализатор, распознаватель, генератор. Каждая часть обрабатывает всю программу от начала до конца и только после этого работает следующая часть.
Во второй схеме используется принципы подпрограмм, когда все части транслятора работают совместно, каждый очередной входной символ лексического анализатора немедленно обрабатывается распознавателем, а каждый элемент разбора, если нужно, тут же вызывает требуемую семантическую подпрограмму генератора. Первую схему применяют, когда все части транслятора одновременно не умещаются в быстрой памяти машины, а вторую когда весь транслятор можно разместить в быстрой памяти.
На практике обе схемы часто комбинируют. Например, в начале работает только блок лексического анализа, а затем – блок, объединяющий распознаватель и генератор, построенный по схеме подпрограмм.
Описываемый
транслятор можно использовать для
перевода с
входного
языка, грамматика которого является
грамматикой предшествования. Для этого
нужно прежде всего стандартизировать
лексику входного языка, т.е. правила
записи служебных слов, идентификаторов,
констант и алфавита. Тогда алгоритм
лексического анализатора будет
определяться только особенностями
устройств, применяемых для подготовки
и ввода программ, и принятым стандартам
ввода программ, и принятым стандартам
входного языка распознавателя. Алгоритм
распознавателя универсален в классе
грамматик предшествования. Алгоритм
генератора предельно прост – генератор
вызывает требуемую семантическую
подпрограмму и передаёт ей аргумент,
определяемые элементом разбора.
Может быть предложена следующая структура данных грамматик простого предшествования для быстрой работы.
Таблица терминалов:
Число
терминалов
255
длинна терминала не >31, но неограниченна
Таблица нетерминалов:
Начальный нетерминальный символ найти и поставит первым. После этого создать таблицу правил и правых частей и расширив таблицу нетерминалов.
Таблица нетерминалов:
Адрес нетерминала |
Индекс в таблице правил |
Количество правил |
Таблица правил
Где число =(+) код терминала (индекс в таблице терминалов), =(-) код нетерминала (-индекс в таблице - нетерминалов). Таблица правил сортируется в порядке возрастания кодов нетерминалов.
А программа распознавателя с известным алгоритмом с помощью приведённых таблиц, матрицы предшествования и цифровой свёртки терминальной цепочки лексическим анализатором может построить дерево разбора, из которого выброшены терминальные элементы, а метки вершин «нетерминалы» заменены на соответствующие номера правил. Дерево разбора может быть представлено матрицей, каждая строка которой хранит следующую информацию:
Номер правила |
Левая часть |
количество |
отец |
Сын 1 |
Сын 2 |
… |
23.11.Синтаксис входного языка задается таблицей порождающих правил. Используя эту таблицу, матрица предшествования строится автоматически.
Семантика входного языка в терминах выходного языка отражена в семантических подпрограммах, которые составляются в ручную. В принципе, описываемый транслятор пригоден для перевода с нескольких входных языков, грамматики которых – грамматики простого предшествования, на несколько выходных языков. За универсальность транслятора в классе грамматик предшествования приходится платить невысокой эффективностью алгоритмов трансляции.
Рассмотрим применение метода предшествования для преобразования в польскую обратную запись предложения языка, порождаемые грамматикой G'1. Чтобы язык был более реалистичен, будем считать, что в качестве идентификаторов в языке может использоваться строчная латинская буква. Каждая такая буква воспринимается распознавателем, как идентификатор И.
Составим таблицу порождающих правил, дополнив её семантическими подпрограммами для перевода её в польскую обратную запись:
Номер правила |
Порождающее правило |
Семантическая подпрограмма для перевода. |
1 2 3 4
5 6 7
8
9 |
П → B B→B' B'→T B'→B'+T
T→T' T'→M T'→T'xM
M→И
M→ (B) |
«Записать символ '+' в выходную строку»
«Записать символ 'х' в выходную строку» «Записать идентификатор в выходную строку» |
Трансляции a + bxc в польскую обратную запись, используя распознаватель предшествования, таблицу порождающих правил и семантических подпрограмм и матрицу предшествования, получаем:
Запись в выходную строку |
Стек распознавателя |
Отношение предшествования |
Входная строка |
N правила |
Семантическая подпрограмма |
а
|
|
|
a+bxc |
- |
- |
|
|
+bxc |
8 |
u |
|
М |
|
+bxc |
6 |
- |
|
Т' |
|
+bxc |
5 |
- |
|
Т |
|
+bxc |
3 |
- |
|
В' |
|
+bxc |
- |
- |
|
В' |
|
bxc |
- |
- |
|
В' b |
|
xc |
8 |
u в выходную строку |
|
b |
B' +M B' +T' B' +T' X B' T' X C |
|
xc xc c
|
6 - - 8 |
- - - u в выходную строку |
c |
B'
+T'
X
|
|
|
7 |
x в выходную строку |
x |
B' + T' B' +' T
|
|
|
5 4 |
- x в выходную строку |
+ |
B'
|
|
|
2 1 |
- - |
|
M |
|
|
|
|
Если
последовательно выписать символы,
записываемые в ходе анализа в стек
распознавателя и при успешном разборе
дополнить полученную строку парой
П,
то получим (,-разделитель):
⊥,а,
М, T',T,B',+,b,M,T',x,c,M,T’,T,
,П
– которая представляет собой ОПЗ
разбора, полученную обходом дерева
разбора:
Cтроку можно записать короче, если заменить нетерминал номерами правил, применяемых для их получения: ,a,8,+,b,8,x,c,8,7,4.
Запись разбора в таком виде поступает на вход генератора кода. (см. схему)
Этап лексического анализа подготавливает исходную программу к синтаксическому анализу: убирает из текста программы комментарии, распознаёт и отделяет трансляционные директивы, выделяет и осуществляет свёртку лексем входного языка, что существенно влияет на выбор алгоритмов синтаксического анализа, который осуществляется не для входного языка L(G), а для преобразованного L(G’). Лексемы, наиболее часто выделяемые в языках программирования:
<идентификатор>, <служебные слова>, <целое число>, <вещественное число>, <одномерные разделители>, <двумерные разделители>, <комментарии>, <трансляционные дерективы> и т.п.
Если класс лексем L(Gk)(автоматный язык) бесконечен(например –идентификатор) или конечен, но достаточно велик, то выделяемые в программе лексемы tk L(Gk), заполняются в специальной таблице к, они являются элементами справочника транслятора и могут обслуживаться в зависимости от реализации специальными программами обслуживания таблиц, либо стандартными программами обслуживания справочника (метод хеширования).
Лексический анализатор – это следующие отображение:
lex:
→ (V'T)*
- преобразование, реализуемое сканером
для входного языка L(G).
На входе сканер lex
воспринимает цепочку х
VT*,
а на входе выдаёт цепочку лексем у
(V'T)*
Построение сканера осуществляется за несколько шагов:
Выделить во входном языке L(G) на основании описания его синтаксиса с помощью КС – грамматики G множество классов лексем Lk, 1≤k≤i, i
1.Видоизменить КС – грамматику G входного языка L(G), так чтобы она удовлетворяла следующим требованиям:
подмножество {U1,U2,…,Ui}
VN
(множество
нетерминалов) i
1,
такое что, каждому, нетерминалу Uk
можно поставить в соответствие
автоматную грамматику Gk=(
,
,
Pk,
Uk),
порождающую автоматный язык фраз
L(Gk)={tk|tk
,Uk=>*tk}.
Языки L(Gk) (k=1,…,i)попарно не пересекаются. Т.е. k,j [1,i],k
i,
L(Gk)
L(Gi)=
.
Каждая цепочка x
однозначно
представляется как конкатенация
подцепочек из языков L(Gk),
т.е. x=tk1,tk2,…,
tkn,
n1
tkj
L(Gkj)
1≤j≤n,
1≤kj≤i.
Определим новую КС – грамматику G'=(VT',
VN',
P',S'),
где VN'=VN
\{U1,…,Ui}.
VT'={V1,…,Vi},
P'=P\
Очевидно, что для каждого предложения
x
найдётся
!-ная цепочка y
такая, что S
*y
*x,
y=Uk1,Uk2,…,Ukn,
x=tk1,tk2,…tkn,
Ukj
*tkj,
1≤j≤n.
Для каждой автоматной грамматики Gk построить диаграмму состояний Dk – неформальную модель распознавателя языка
.Выполнить «склеивание» диаграмм состояний Dk.
Определить условия выхода из сканера при достижении конца произвольной лексемы из каждого класса лексем.
Разбить символы входного алфавита VT на непересекающиеся классы.
Выбрать формат и код образцов лексем (Vk, ltk); выбрать метод идентификации лексем в таблице TVk.
Запрограммировать семантические подпрограммы и распознаватель по «склеенной» диаграмме состояний.
Языки, порождаемые автоматными грамматиками, представлены в конечных автоматах, поэтому шагу 4 можно придать строгую интерпретацию:
А) Построить НДКА-ы по диаграммам состояний как по источникам;
Б) Построить НДКА, который допускает
объединение языков
),
представления построенными автоматами
из пункта А);
В) Построить детерминированный конечный автомат (ДКА) по недетерминированному автомату из пункта Б) ДКА является формалированным распознавателем лексем входной цепочки x VT*.30.11.2005
Реализация шага 1 – наиболее неформальный этап проектирования сканера. При выделении классов лексем следует руководствоваться содержательной интерпретацией понятия лексемы, как цепочки символов исходного алфавита, имеющей регулярную структуру.
Видоизменение исходной КС - грамматики G существенно не перестраивает G, т.к. в силу определения лексемы синтаксис языка задаётся относительно неделимых лексических единиц. Основные преобразование следующие: замена вхождения лексем класса Uk в правила исходной грамматики на Uk и добавление к G правил автоматной грамматики Gk, порождающей этот класс лексем. В общем случае проблема распознавание автоматных языков в классе КС – языков, определённых КС – грамматиками рекурсивно не разрешима.
«Склеенная»
диаграмма или КА определяет распознающую
часть сканера. Поставим в соответствие
каждому состоянию ДКА КА и каждому
входному символу α
,
семантическую процедуру р(х, α
)
– наличие которой - выполнять операции,
связанные с выделением лексем, их
идентификацией и кодированием образов
лексем.

а
в
выходную строку
B