А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 17
Текст из файла (страница 17)
Синтаксический анализ— одна из наиболее фундаментальных задач юмпиляции; основные методы синтаксического анализа рассматриваются в главе 4. В этой главе для простоты мы начнем с исходных программ наподобие 9-5+2, в которых каждый символ является терминалом; в общем случае исходная программа содержит многосимвольные лексемы, группируемые лексическим анализатором в токены, первые юмпоненты которых представляют собой терминалы, обрабатываемые синтаксическим анализатором.
2.2.3 Деревья разбора Дерево разбора (рагзе нее) наглядно показывает, как стартовый символ грамматики порождает строку языка. Если нетерминал А имеет продукцию А — ХУЕ, то дерево разбора может иметь внутренний узел, помеченный как А, с тремя потомками, помеченными слева направо как Х, У и Л: Г~' х у х Формально для данной контекстно-свободной грамматики дерево разбора представляет собой дерево со следующими свойствами.
1. Корень дерева помечен стартовым символом. 2. Каждый лист помечен терминалом или е. Вз 2.2. Определение синтаксиса Терминология, связанная с деревьями Древовидные структуры данных встречаются в компиляции очень часто. ° Дерево состоит из одного или нескольких умов (поде). Узлы могут иметь метки (1аЬе1), которые в данной книге обычно являются символами грамматики.
При изображении деревьев мы зачастую представляем узлы только их метками. ° Ровно один узел является «арлен (гоог). Все узлы, за исключением корня, имеют единственный родительский узел (или просто родитель) (рагеп1); корень не имеет родительского узла. При изображении деревьев мы размещаем родительский узел для данного узла над ним и проводим ребро между ними.
Корень, таким образом, является самым верхним узлом. ° Если узел Ж родительский для узла М, то М является дочерним (сЬ11д) по отношению к зУ. Дочерние узлы одного узла называются родственньини или сестринскими (з)Ь11пд). Они упорядочены слева направо, и когда мы изображаем дерево, то упорядочиваем дочерние узлы данного узла соответствующим образом. ° Узел без дочерних узлов называется листом (1еа1). Другие узлы — у которых имеется один или несколько дочерних — представляют собой внутренние узлы (1шегюг попе).
° Потомком (дезсепдап1) узла зУ является сам Ж, дочерние по отношению к Ж узлы, узлы, дочерние по отношению к дочерним узлам )У, и так далее для любого количества уровней. Мы говорим, что узел зУ является предкам (апсеаюг) узла М, если М вЂ” потомок )У. 3. Каждый внутренний узел помечен нетерминалом. Если А является нетерминалом и помечает некоторый внутренний узел, а Хы Хз,..., Մ— метки его дочерних узлов слева направо, то должна существовать продукция А — Х1Хз Х„. Здесь каждое нз обозначений Хы Хз,..., Х„представляет собой либо терминальный, либо нетерминальный символ. В качестве частного случая продукции А — е соответствует узел А с единственным дочерним узлом е.
Пример 2.4. Вывод 9-5+2 в примере 2.2 проиллюстрирован деревом на рис. 2.5. Каждый узел дерева помечен символом грамматики. Внутренний узел и его до- 84 Глава 2. Простой синтаксически управляемый транслятор чериие узлы соответствуют продукции: внутренний узел соответствует заголовку продукции, а дочерние узлы — телу продукции. На рис. 2.5 корневой узел помечен как (нг — стартовый символ грамматики из примера 2.1. Дочерние узлы слева направо помечены как 1иб + и с(18(г. Заметьте, что 11зг — ~ Лзг + ййй является продукцией грамматики из примера 2.1.
Левый дочерний узел корня аналогичен корню, только его дочерний узел помечен как — вместо +. Все три узла, помеченные как Й818 имеют по одномУ дочеРнемУ УзлУ с метками-цифРами. о йкн ля ийв вив 5 Рис. 2.5. Дерево разбора строки 9-5+2 в соответствии с грамматикой в примере 2.1 Листья дерева разбора слева направо образуют крону (у1е14) дерева, которая представляет собой строку, выведенную (дептед), или порожденную (йепега~ед), из нетерминальиого символа в корне дерева разбора. На рис. 2.5 кроной является строка 9-5+2; для удобства все листья показаны на одном, нижнем, уровне. В дальнейшем выравнивать листья деревьев таким образом мы не будем.
Любое дерево естественным образом упорядочивает свои листья слева направо, основываясь на том принципе, что если Х и У вЂ” два дочерних узла одного родителя и узел Х находится слева от У, то все потомки Х будут находиться слева от любого потомка У. Другое определение языка, порожденного грамматикой, — это множество строк, которые могут быть сгенерированы некоторым деревом разбора. Процесс поиска дерева разбора для данной строки терминалов называется разборам (рагз1п8) или синтаксическим анализам этой строки. 2.2.4 Неоднозначности Следует быть предельно внимательным при рассмотрении структуры строки, соответствующей грамматике. Грамматика может иметь более одного дерева 85 2.2.
Определение синтаксиса разбора для данной строки терминалов. Такая грамматика называется пеодпозпичной (ат(лйцоцз). Чтобы показать неоднозначность грамматики, достаточно найти строку терминалов, которая дает более одного дерева разбора.
Поскольку такая строка обычно имеет не единственный смысл, следует разрабатывать однозначные (непротиворечивые) грамматики либо неоднозначные грамматики с дополнительными правилами для разрешения неоднозначностей. Пример 2.5. Предположим, мы используем только один нетерминал згг(пд и не различаем цифры и списки, как это делается в примере 2.1. Тогда грамматику можно записать следующим образом: з~г(пд — к(пп8 + зггт8 ( згг(п8 — зсггп8 ( О ! 1 ! 2 ! 3 ! 4 ! 5 ! б ! 7 ( 8 ) 9 Объединение записей для й88 и !и! в один нетерминальный символ згг(п8 имеет кажущийся смысл, поскольку отдельная цифра является частным случаем списка. Однако из рис. 2.6 видно, что, например, выражение 9-5+2 в такой грамматике имеет больше одного дерева разбора. Эти два дерева разбора соответствуют двум вариантам расстановки скобок в выражении: (9-5)+2 и 9-(5+2). Второе выражение дает в результате значение 2 вместо ожидаемого 6.
Грамматика в примере 2.1 не допускает такой интерпретации. и пппз пппх пппх — пппя пппх э пппх лппх — нпвя г 9 Пппя -'; люппа 9 5 Рис. 2.6. Два дерева разбора для выражения 9-5+2 2.2.5 Ассоциативность операторов По соглашению 9+5+2 эквивалентно (9+5)+2, а 9-5-2 эквивалентно (9-5) -2. Когда операнд типа 5 имеет операторы и слева, и справа, необходимы определенные соглашения, чтобы установить, какой именно оператор применяется к этому операнду. Мы говорим, что оператор + левоиссоциагппвеп, поскольку операнд со знаками "плюс" с обеих сторон используется левым оператором.
В большинстве языков программирования четыре арифметических оператора— сложение, вычитание, умножение и деление — левоассоциативны. 86 Глава 2. Простой синтаксически управляемый транслятор Некоторые распространенные операторы, например возведение в степень, правоассое(иативны. Другим примером правоассоциативного оператора может служить оператор присвоения (=) в С и его потомках; выражение а=Ье и рассматривается как а=(Ь=о).
Строки типа а=Ъ=с с правоассоциативным оператором генерируются следующей грамматикой: г18111 — г 1е11ег = г(8111 ~ 1енег 1енег — а ( Ь ! ( к Различия между деревьями разбора для левоассоциативных операторов наподобие — и правоассоциативных операторов наподобие = показаны на рнс.
2.7. Обратите внимание, что дерево разбора для 9-5-2 растет вниз влево, в то время как дерево разбора для а=Ь=с — вниз вправо. ли Яег — гля11 1аг — Е1Я11 2 еяя11 5 ! 9 Рнс. 2.7. Деревья разбора для лево- н нравоассоцнатнвных грамматик Рассмотрим выражение 9+5*2. Есть два способа его интерпретации: как ( 9+5) *2 и 9+ (5*2). Ассоциативные правила для + и * применяются при наличии одного и того же оператора, так что они не в состоянии разрешить эту неоднозначность. Поэтому, если имеется более одного типа операторов, необходимы правила, определяющие относительный приоритет операторов. Мы говорим, что оператор * имеет более высокий приоритет, чем +, если * получает свои операнды раньше +.
В обычной арифметике умножение и деление имеют более высокий приоритет, чем сложение и вычитание. Таким образом, 5 является множителем в умножении в случае как с 9+5*2, так и с 9*5+2, т.е. зти выражения эквивалентны 9+(5*2) и (9*5)+2 соответственно. Пример 2.6. Грамматика арифметических выражений может быть построена на основе таблицы, показывающей ассоциативность и приоритет операторов. Начнем с четырех основных арифметических операторов и таблицы приоритетов, 2.2.6 Приоритет операторов 1елег = пег а 1епег = пяаг ь 1еаег с 87 2.2. Определение синтаксиса представляющей операторы в порядке увеличения приоритетов (операторы, рас- положенные в одной строке, имеют одинаковые приоритеты): Левоассоциативные: + Левоассоциативные: * / Создадим два нетерминала — ехрг и 1егт — для этих уровней приоритета и дополнительный нетерминал/ас1ог для генерации базовых составляющих в выражениях, в данном случае — цифр и выражений в скобках: /ас!ог — !))й)1 ~ ( ехрг ) 1егт — 1егт * /ас(ог 1егт / /ас1ог /ас(ог Точно так же ехрг рассматривается как список элементов !егт, разделенных опе- раторами сложения или умножения: ехрг — ехрг + !егт ехрг — 1егт 1е!.т В результате грамматика приобретает следующий вид: ехрг+ 1егт ~ ехрг — 1егт ~ 1егт — 1егт +/ас1ог ~ 1егт //ас1ог ~ /ас1ог йд!1 ~ ( ехр! ) ехрг 1егт /ас1ог Эта грамматика рассматривает выражение как список элементов, разделенных знаками + и —.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
