Построение вывода по дереву.

 

Можно восстановить вывод по синтаксическому дереву при помощи обратного процесса. Из рис.1.4,с видно, что концевые узлы образуют цепочку 22. Самый правый концевой куст указывает непосредственный вывод:

2<цифра>=>22

Чтобы пройти по синтаксическому дереву до 2<цифра>, мы отсекаем куст тот дерева - удаляем его. Например, отсекание этого куста (на рис.1.4,в) дает нам дерево на рис.1.4,б. Этот процесс часто называют непосредственной редукцией.

Рассматривая рис.1.4,б, мы видим, что последним здесь должен быть вывод <цифра> <цифра> => 2<цифра>. Это нам дает

<цифра><цифра>=>2<цифра>=>22

Продолжаем процесс, всегда восстанавливая последний непосредственный вывод, на который указывает концевой куст синтаксического дерева, и затем отсекая этот куст.

Подводя итог, сформулируем следующие положения о синтаксических деревьях:

· для каждого синтаксического дерева существует, по крайней мере, один вывод;

· для каждого вывода есть соответствующее синтаксическое дерево (но несколько разных выводов могут иметь одно и то же дерево);

· куст дерева указывает на непосредственный вывод, в котором имя куста заменяется узлами куста. Следовательно, в грамматике существует правило, левой частью которого является имя куста, а правой частью - цепочка из узлов куста;

· концевые узлы дерева образуют выводимую сентенциальную форму;

· пусть U-корень поддерева для сентенциальной формы w=хuу, где u образует цепочку концевых узлов этого поддерева. Тогда u - фраза сентенциальной формы w для U. Она является простой фразой, если поддерево представлено единственным кустом.

Кроме вывода (1.3), есть другой вывод предложения 22 в G1.

(1.4) <число>=><чс>=><чс><цифра>

=><цифра><цифра>=><цифра>2=>22

у него то же самое синтаксическое дерево, что и у вывода 1.3. В действительности есть еще и третий вывод 22:

(1.5) <число>=><чс>=><чс><цифра>

=><чс>2=><цифра>2=>22

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

 

Неоднозначность.

 

Гораздо более важным является вопрос не единственности синтаксического дерева. Рассмотрим грамматику, содержащую среди прочих правила:

По этим правилам мы могли бы образовать предложение "time flies" двумя различными способами с различными синтаксическими деревьями (рис.1.5).

Рис.1.5. Синтаксические деревья для неоднозначного предложения.

В английском языке каждое из этих предложений имеет смысл

1) “Время летит ” time в данном случае существительное, а flies глагол в 3-ем лице.

2) “Хронометрировать мух” time в данном случае глагол, а flies существительное во множественном числе.

Дело в том, что без контекста мы не можем понять предложение, поскольку не можем его правильно разобрать; мы не можем однозначно разделить его на составные части. Поэтому, если компилятор должен уметь транслировать все правильные исходные программы, резонно потребовать, чтобы язык был однозначно определен. Теперь введем следующее

О п р е д е л е н и е 1.10. Предложение грамматики неоднозначно, если для его вывода существуют два синтаксических дерева. Грамматика неоднозначна, если она допускает неоднозначные предложения, в противном случае она однозначна.

Заметим, что мы называем неоднозначной грамматику, а не сам язык. Изменяя неоднозначную грамматику, но, конечно, не изменяя ее предложения, можно иногда получить однозначную грамматику для того же самого множества предложений. Однако есть языки, для которых не существует однозначной грамматики. Такие языки называются существенно неоднозначными.

Не надо забывать, что в данный момент речь идет лишь о синтаксисе. Согласно определению выше, предложение может быть однозначным, но мы можем все же не понять, что оно означает из-за неоднозначного смысла слов.

К сожалению, было доказано, что проблема распознавания неоднозначности алгоритмически неразрешима. Это означает, что не существует алгоритма (т.е. нельзя составить такой алгоритм), который воспримет любую НФБ-грамматику и заведомо определит за конечное число шагов, является она однозначной или нет. Можно, однако, разработать достаточно простые, но нетривиальные условия, такие, что если грамматика им удовлетворяет, то можно утверждать, что она однозначна. Эти условия являются достаточными, но не необходимыми.

 

Однозначная грамматика для арифметических выражений.

 

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

(1.6) <Е>::=<Е>+<Е>|<Е>*<Е>|(<Е>)| i.

Сентенциальная форма <Е>+<Е>*<Е> имеет два синтаксических дерева (рис.1.6) и две основы <Е> + <Е> и <Е> * <Е>. Если мы хотим разобрать эту сентенциальную форму, то с какой основы мы должны начать? Грамматика неоднозначна, и можно выбрать любую из основ. Таким образом, мы не можем сказать, что выполняется раньше: сложение или умножение.

Рис.1.6. Два синтаксических дерева для <Е>+<Е>*<Е>.

 

Рассмотрим теперь грамматику G3[<врж>]:

<врж>::=<терм>|<врж>+<терм>|<врж>-<терм>

<терм>::=<множ>|<терм>*<множ>|<терм>/<множ>

<множ>::=(<врж>)|i

Единственное дерево для выражения i+i*i показано ниже, и, таким образом, в соответствии с этой грамматикой предложение однозначно. В действительности все предложения G3 однозначны. Теперь определим, согласно G3, что в выражении i+i*i должно выполняться раньше: умножение или сложение. Операндами для +, согласно дереву, являются <врж>, из которого получается i, и <терм>, из которого в свою очередь получается i*i. Это означает, что умножение должно быть выполнено первым для того, чтобы образовать <терм> для сложения; следовательно, умножение предшествует сложению.

Рис.1.7.

 

Грамматику G3 следует предпочесть грамматике 1.6 по двум причинам: она однозначна и указывает, что умножение предшествует сложению.

ЗАДАЧА РАЗБОРА.

 

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

Все алгоритмы разбора, которые мы описываем, называются алгоритмами разбора слева направо ввиду того, что они обрабатывают сначала самые левые символы рассматриваемой цепочки и продвигаются по цепочке вправо только тогда, когда это необходимо. Мы могли бы подобным же образом определить разбор справа налево, но он менее естествен. Инструкции в программе выполняются слева направо, да и мы читаем тоже слева направо.

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

(1.7) N::=D | N D

D::=0|1|2|3|4|5|6|7|8|9

На первом шаге непосредственный вывод N=>N D будет строиться так, как это показано в первом дереве на рис.1.8. На каждом последующем шаге самый левый нетерминал V текущей сентенциальной формы хVу заменяется на правую часть u правила V::=u, в результате чего получается следующая сентенциальная форма.

Этот процесс для предложения 35 представлен на рис.1.8 в виде пяти деревьев. Фокус в том, конечно, что надо получить ту сентенциальную форму, которая совпадает с заданной цепочкой.

Метод восходящего разбора состоит в том, что, отправляясь от заданной цепочки, пытаются привести ее к начальному символу. На первом шаге при разборе предложения 35 терминал 3 приводится к D, в результате чего получается сентенциальная форма D5. Таким образом, мы построили непосредственный вывод D5=> 35, как это показано в самом правом частичном синтаксическом дереве на рис.1.9. На следующем шаге D приводится к N, что показано во втором дереве справа. Этот процесс продолжается до тех пор, пока не будет получено первое дерево рис.1.9. Мы расположили деревья на рисунке справа налево, потому что такое расположение лучше иллюстрирует построенный вывод, который теперь читаем, как обычно, слева направо. Заметим, что выводы, произведенные двумя различными распознавателями, различны, но имеют одно и то же синтаксическое дерево.

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

Рис.1.8. Нисходящий разбор и построение вывода.

 

Рис.1.9. Восходящий разбор и построение вывода.

 

О п р е д е л е н и е 1.11. Непосредственный вывод хUу => х u у называется каноническим и записывается хUу => х u у, если у содержит только терминалы. Вывод w=>+v называется каноническим и записывается w=>+v, если каждый непосредственный вывод в нем является каноническим.

Каждое предложение, но не каждая сентенциальная форма имеет канонический вывод. Рассмотрим в качестве примера сентенциальную форму 3D грамматики 1.7. Ее единственным выводом является

<число>=>ND=>DD=>3D

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

Мы, конечно, еще не касались главных проблем разбора.

1. Предположим, что при нисходящем разборе надо заменить самый левый нетерминал V, и пусть имеется n правил:

V::=x₁|х₂|...|х_n.

Как узнать, какой цепочкой х_i следует заменить V?

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

На эти вопросы не всегда легко ответить. Одним из решений является выбор некоторого из возможных вариантов наугад в предположении, что он верен. Если позднее обнаружится ошибка, то мы должны вернуться назад и попытаться применить другой вариант. Этот прием называется возвратом. Очевидно, что возвраты могут привести к чрезмерному расходу времени.

Другим решением является просмотр контекста вокруг обрабатываемой в данный момент подцепочки. Именно так мы поступаем, когда вычисляем выражение, подобное А+В*С. Мы задаем себе вопрос, "можно ли вначале вычислить А+В", и отвечаем на него отрицательно, замечая, что за А+В следует *.

Один из первых алгоритмов разбора, который действительно использовался в компиляторе, был описан Айронсом. Метод, положенный в основу этого алгоритма, являлся смесью нисходящего и восходящего методов, и мы не будем обсуждать его подробнее.