конспекты занятий по курсу

«Теория и реализация языков программирования»

 

Занятие 8

 

 

 

(<<<) предыдущий

наверх

следующий (>>>)

 

 

II. Некоторые вопросы применения теории при проектировании компиляторов

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

 

Оглавление

8.1. Цели разбора программы

8.2. Разбор сверху вниз

8.3. Множества FIRST и FOLLOW

Пример 8.1. Построение предсказывающего анализатора

* * *

 

8. Разбор программы и предсказывающие анализаторы

8.1. Цели разбора программы

Вы уже знаете, что когда мы посылаем свою программу на трансляцию, она сначала проходит лексический (пословесный) разбор (он же исследование, проверка, просмотр, сканирование, анализ или, по-английски, lexical analysis, lexical scan), где единая входная цепочка (программа) разбивается на далее неделимые (без потери смысла) слова (лексемы (греч.), токены (англ.) и пр. – в разных источниках по-разному) – константы, переменные, ключевые слова, разделители и т.д. Вид и правильность записи каждого слова можно распознать, проверить независимо от других, например, нет ли недопустимых знаков при задании числового значения или не превышена ли допустимая длина для имени переменной… При лексическом разборе происходит замена каждой лексемы на её тип (например, числовая константа) и ссылку на её значение (123 или какое-то иное) в создаваемых при разборе соответствующих таблицах.

После успешного прохождения лексического разбора встаёт следующий вопрос – правильно ли из отдельных слов языка построены его предложения и вся программа в целом? На него призван дать ответ синтаксический разбор программы, т.е. исследование правильности записи её предложений. Однако разных видов предложений в языке программирования множество. Как быстро понять, какую именно конструкцию программы мы разбираем, к примеру, описание процедуры, её переменных, тот или иной вид цикла и т.д.?

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

Например, обозначим S – правильно написанная программа.

Def – описатель переменной

Type – описатель типа переменной

Name – имя переменной

For  – один из допустимых операторов цикла и т.д.

Тогда некоторое подмножество правильно написанных на языке С программ может задаваться следующей грамматикой:

S main: ( ) {Def; For;}

Def  Def; Def   |   Type Name

Type  Integer | Float | …

Name  …

For  …

Для определения того, в какой последовательности порождается с помощью соответствующей КСГ правильно написанная программа, и служат предсказывающие анализаторы. Существуют как разборщики (анализаторы), предсказывающие последовательность применения правил грамматики, начиная с её аксиомы (разбор сверху вниз), так и анализаторы, которые определяют эту последовательность в обратном порядке (разбор снизу вверх). У каждого из этих видов есть свои особенности, достоинства и недостатки, определяющие предпочтительные области их применения. С ними мы кратко познакомимся позже.

 

 

 

8.2. Разбор сверху вниз

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

Затем необходимо определить правило, которое должно быть применено к X1, и т.д., до тех пор, пока в процессе такого построения сентенциальной формы (т.е. выводимого слова языка), соответствующей левому выводу, не будет применено правило Y a ... (Y w | w T*,  т.е. сведётся к цепочке из терминалов).

Этот процесс затем применяется для следующего самого левого нетерминального символа сентенциальной формы.

Общая схема такого анализатора представлена ниже

 

 


Таблично-управляемый предсказывающий анализатор имеет входной буфер, таблицу анализа и выход. Входной буфер содержит распознаваемую строку, за которой следует $ – правый концевой маркер, признак конца строки. Магазин содержит последовательность символов грамматики с $ на дне. Вначале магазин содержит начальный символ грамматики на верхушке и $ на дне. Таблица анализа – это двумерный массив M[A,a], где A – нетерминал, и a – терминал или символ $.

Анализатор управляется программой, которая работает следующим образом. Она рассматривает X – символ на верхушке магазина и a – текущий входной символ. Эти два символа определяют действие анализатора. Имеются три возможности.

1. Если X = a = $, анализатор останавливается и сообщает об успешном окончании разбора.

2. Если X = a ≠ $, анализатор удаляет X из магазина и продвигает указатель входа на следующий входной символ.

3. Если X – нетерминал, программа заглядывает в таблицу M[X,a]. По этому входу хранится либо правило для X, либо ошибка. Если, например, M[X,a] = {XUVW}, анализатор заменяет X на верхушке магазина на WVU {на верхушке U}. Будем считать, что анализатор в качестве выхода просто печатает использованные правила вывода. Если M[X,a] = error, анализатор обращается к подпрограмме анализа ошибок.

 

Вначале магазин анализатора содержит S$, (S – аксиома грамматики), во входном буфере w$ (w – входная цепочка).

 

 

 

8.3.  Множества FIRST и FOLLOW

При построении предсказывающего анализатора полезными оказываются две функции, FIRST и FOLLOW, позволяющие построить таблицу предсказывающего разбора для G, если, конечно, это возможно.

Если u – любая строка символов грамматики, положим FIRST(u) – множество терминалов, с которых начинаются строки, выводимые из u. Если , то  также принадлежит FIRST(u).

 

Для построения FIRST(X) для каждого знака грамматики X применим следующий алгоритм.

Алгоритм 8.1. Построение множеств FIRST для символов грамматики.

Шаг 1. Если X – терминал, то FIRST(X) – это {X}; если X – нетерминал, полагаем FIRST(X) = {}.

Шаг 2. Если имеется правило вывода  то добавить  к FIRST(X).

Шаг 3. Пока ни к какому множеству FIRST(X) нельзя уже будет добавить новые элементы или e:

если X – нетерминал и имеется правило вывода XY1Y2...Yk,

то включить  a в  FIRST(X), если для некоторого i  a FIRST(Yi) и

 принадлежит всем FIRST(Y1),..., FIRST(Yi-1), т.е. .

Если  принадлежит FIRST(Yj) для всех  j = 1,2,..., k, то добавить   к  FIRST(X). Например, всё, что принадлежит  FIRST(Y1)  принадлежит также и FIRST(X). Если из  Y1 не выводится  , то ничего больше не добавляем к  FIRST(X),  но если   то добавляем FIRST(Y2), и т.д.

Теперь FIRST для любой строки  X1X2...Xn можно вычислить следующим образом.

Шаг 1. Полагаем FIRST(X1X2...Xn) = {}.

Шаг 2. Добавим к FIRST(X1X2...Xn) все не   символы из FIRST(X1). Добавим также не  символы из FIRST(X2), если FIRST(X1), не  символы из FIRST(X3), если  принадлежит как FIRST(X1), так и FIRST(X2), и т.д. Наконец, добавим  к FIRST(X1X2...Xn), если  FIRST(Xi) для всех i.

 

Определим FOLLOW(A) для нетерминала A как множество терминалов a, которые могут появиться непосредственно справа от A в некоторой выводимой цепочке, т.е.  множество знаков aÎT таких, что существует вывод вида S Þ* uAav  для некоторых u и v.

Отметим, что между A и a  в ходе вывода могут появиться нетерминалы, из которых выводится e. Если A может быть самым правым знаком некоторой выводимой цепочки, то $ принадлежит FOLLOW(A).

 

Для вычисления FOLLOW(A) для нетерминала A применим алгоритм 8.2.

Алгоритм 8.2. Построение FOLLOW(X) для всех X – нетерминалов грамматики.

Шаг 1. Положить FOLLOW(X) = {}.

Шаг 2. Поместить $ в FOLLOW(S), где S – начальный символ и $ – правый концевой маркер.

Шаг 3. Если есть правило вывода A  uBv, то всё из FIRST(v), за исключением , добавить к FOLLOW(B).

Шаг 4. Пока ничего нельзя будет добавить ни к какому множеству FOLLOW(X): если есть правило вывода A  uB или A  uBv, где FIRST(v) содержит  (т.е. v ), то всё из FOLLOW(A) добавить к FOLLOW(B).

 

 

 

Пример 8.1. Построение предсказывающего анализатора

Построим предсказатель разбора для следующей КСГ:

S  ABC

A  BB |

B  CC | a

С  AA | b

Вычисляем значение функции FIRST

Начальное (и итоговое) значение функции для всех основных знаков грамматики (a и b) – они же.

FIRST (a) = a; FIRST (b) = b.

Для вспомогательных знаков – пустое множество:

Начинаем вычислять FIRST (S):

FIRST (S) += FIRST (A).           

FIRST (A) у нас пока не определено, начинаем вычислять его.

FIRST (A) += FIRST (B) | ,             т.е.  {}  FIRST (S)                       

FIRST (B) += FIRST (C) | a,              т.е.  {, a}  FIRST (S) 

FIRST (C) += FIRST (A) | b               т.е.  {, a, b}  FIRST (S)  

Поскольку  {}  FIRST (A), то вычисляя FIRST (S) на основе правила S  ABC мы должны дальше исследовать также FIRST (B), а если {}  FIRST (B), то и FIRST (С). Но в данном случае эти возможности уже рассмотрены и мы имеем окончательный ответ для S:

FIRST (S) = {, a, b}

Проведя подобные исследования для A, B и C, получим

FIRST (A) = FIRST (B) = FIRST (C) = {, a, b}

 

Вычисляем значение функции FOLLOW.

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

Начальное значение FOLLOW (S) = $ (поскольку в конец любой выводимой цепочки, как вы помните, перед началом разбора добавляется знак $ для однозначного определения её завершения. А аксиома S – это прообраз любой выводимой цепочки языка).

Для всех остальных вспомогательных знаков КСГ начальное значение функции равно :

FOLLOW (A) = FOLLOW (B) = FOLLOW (C) =

Вычисляем дальше.

Поскольку аксиома в данной грамматике у нас нигде в правой части правил не встречается, то к начальному значению FOLLOW (S) = $ мы уже ничего прибавить не сможем.

Вычислим FOLLOW (A):

В правой части знак A встречается в следующих правилах грамматики:

S  ABC

С  AA

Из первого правила (S  ABC) находим, что

FOLLOW (A) += FIRST (BC) \ {} = {a, b}

Поскольку {e}  FIRST (B) и {}  FIRST (С) (т.е. цепочка BC справа от А в правой части правила может сводиться к пустой), то также

FOLLOW (A) += FOLLOW (S), т.е. {a, b}  {$} = {a, b, $}

Из второго правила (С  AA) из первого вхождения А в правой части

FOLLOW (A) += FIRST (A) \ {}, т.е. ничего нового не добавляется.

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

FOLLOW (A) += FOLLOW (C)

FOLLOW (C) нам пока не известно, продолжаем вычисления.

Вычислим FOLLOW (B):

В правой части знак B встречается в следующих правилах грамматики:

S  ABC

A  BB

Из первого правила (S  ABC) находим, что

FOLLOW (B) += FIRST (C) \ {} = {a, b}

Поскольку {}  FIRST (C), то также

FOLLOW (B) += FOLLOW (S), т.е. {a, b}  {$} = {a, b, $}

Из второго правила (A  BB) из первого вхождения B в правой части

FOLLOW (B) += FIRST (B) \ {}, т.е. ничего нового не добавляется.

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

FOLLOW (B) += FOLLOW (A)

Также ничего нового нет.

Подобным образом вычисляем и значение FOLLOW (C) = {a, b, $}.

Построение таблицы предсказателя вывода производится по следующим правилам [1]:

Алгоритм 8.3. Построение таблиц предсказывающего анализатора.

Для каждого правила вывода A   грамматики выполнить шаги 1 и 2

Шаг 1. Для каждого терминала a из FIRST() добавить A  к  M[A, a].

Шаг 2. Если  FIRST(), добавить A  к  M[A, b] для каждого терминала b из FOLLOW(A). Если   FIRST() и $  FOLLOW(A), добавить A  к M[A, $].

Шаг 3. Положить все неопределённые входы равными «ошибка».

Применим указанный алгоритм к нашей грамматике:

 

 

 

 

a

b

$

 

 

 

 

S

S  ABC

S  ABC

S  ABC

 

 

 

 

A

A  BB

A  BB

A  BB

A  

 

 

 

 

B

B  a

B  CC

B  CC

 

 

 

 

C

C  AA

C  b

C  AA

 

 

 

 

$

 

 

допуск

 

 

 

 

Таблица получилась неоднозначной. Вообще говоря, можно работать и с неоднозначными таблицами, но тогда приходиться применять разбор с возвратами, разбирая какое же правило на самом деле должно было быть применено (нечто подобное мы имеем и при программировании по неопределённым автоматам).

Приведём пример разбора цепочки ab с помощью полученной таблицы:

 

 

 

Магазин

Вход

Правило
(выход разбора)

 

 

 

 

S$

ab$

 

 

 

 

 

ABC$

ab$

S  ABC

 

 

 

 

BBBC$

ab$

A  BB

 

 

 

 

aBBC$

ab$

B  a

 

 

 

 

BBC$

b$

 

 

 

 

 

CCBC$

b$

B  CC

 

 

 

 

bCBC$

b$

C  b

 

 

 

 

CBC$

$

C  AA

 

 

 

 

AABC$

$

A

 

 

 

 

ABC$

$

A

 

 

 

 

BC$

$

B  CC

 

 

 

 

CCC$

$

C  AA

 

 

 

 

AACC$

$

A

 

 

 

 

ACC$

$

A

 

 

 

 

CC$

$

C  AA

 

 

 

 

AAC$

$

A

 

 

 

 

AC$

$

A

 

 

 

 

C$

$

C  AA

 

 

 

 

AA$

$

A

 

 

 

 

A$

$

A

 

 

 

 

$

$

 

 

 

 

 

В данном случае мы угадали, какое правило свёртки надо было применять каждый раз для ячейки M[A, $] и возвратов не потребовалось, однако для более сложных цепочек очень может быть, что пришлось бы проверять и все указанные возможности.

Исследования показали, что в классе КС-языков существуют такие их подмножества, для которых получаемые таблицы разбора являются однозначными. Причём эти подмножества позволяют представить огромное большинство широко используемых ныне языков программиро­вания, исключая разве что очень своеобразные языки, к примеру, LISP (который учитывает контекстные зависимости и потому вообще не определяется никакой КС-грамматикой).

КС-языки, позволяющие получить однозначную предсказывающую таблицу при разборе сверху вниз получили название LL-языков, а при разборе снизу вверх – LR-языков. Установлено, что LR-языки полностью включают в себя множество LL-языков, а также такие, которые не входят во множество LL-языков. Но предсказывающие анализаторы для LR-анализа несколько сложнее, а сам разбор более трудоёмок, поэтому оба подхода имеют широкие применения в подходящих для каждого из них областях.

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

Эти вопросы мы рассмотрим подробнее на следующем занятии.

 

 

 

Совет. Познакомьтесь с более полными описаниями соответствующих алгоритмов и функций в пособии [1] и введёнными при этом понятиями и обозначениями.

 

== Ссылки ==

[1] Серебряков В.А. [и др.]. Теория и реализация языков программирования. М.: МЗ-Пресс, 2006 (2-е изд). – 294 c. (681.3/ Т33).

 

 

 

 

(<<<) предыдущий

наверх

следующий (>>>)