А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 50
Текст из файла (страница 50)
252 Глава 4. Синтаксический анализ 4.1 Введение В этом разделе будет рассмотрено место синтаксического анализатора в типичном компиляторе. После этого мы обратимся к обычной грамматике для арифметических выражений, которой вполне достаточно для иллюстрации сути синтаксического анализа, поскольку методы синтаксического анализа выражений переносятся на большинство программных конструкций. Заканчивается этот раздел рассмотрением обработки ошибок, поскольку синтаксический анализатор должен с честью выходить из ситуаций. когда его входные данные не могут быть сгенерированы соответствующей грамматикой. 4.1.1 Роль синтаксического анализатора В нашей модели компилятора синтаксический анализатор получает строку токенов от лексического анализатора, как показано на рис.
4.1, и проверяет, может ли эта строка имен токенов порождаться грамматикой исходного языка. Мы также ожидаем от синтаксического анализатора сообщений обо всех выявленных ошибках, причем достаточно внятных и полных, а кроме того, умения обрабатывать обычные, часто встречающиеся ошибки и продолжать работу с оставшейся частью программы. Концептуально в случае корректной программы синтаксический анализатор строит дерево разбора и передает его следующей части компилятора для дальнейшей обработки. В действительности явное построение дерева разбора не требуется, поскольку проверки и действия трансляции, как мы уже видели, могут выполняться в процессе синтаксического анализа.
Таким образом, синтаксический анализатор и прочие части начальной стадии компилятора могу~ быть реализованы в виде единого модуля. Исх аннов ение прог Рнс. 4.1. Место синтаксического анализатора в модели компилятора Имеется три основных типа синтаксических анализаторов грамматик: универсальные, восходящие и нисходящие. Универсальные методы разбора, такие как алгоритмы Кока — Янгера — Касами (Соске — Уоцпйег — Казани) и Эрли (Еаг!еу), могут работать с любой грамматикой (см.
список литературы к главе 4). Однако эти 253 44. Введение обобшенные методы слишком неэффективны для использования в промышленных компиляторах. Методы, обычно применяемые в компиляторах, можно классифицировать как нисходящие (сверху вниз — гор-довп) или восходящие (снизу вверх — Ьойошир). Как явствует из названий, нисходящие синтаксические анализаторы строят дерево разбора сверху (от корня) вниз (к листьям), тогда как восходящие начинают с листьев и идут к корню. В обоих случаях входной поток синтаксического анализатора сканируется посимвольно слева направо. Наиболее эффективные нисходяшие и восходящие методы работают только с подклассами грамматик, однако некоторые из этих классов, такие как ЬЬ- и ЬК- грамматики, достаточно выразительны для описания большинства синтаксических конструкций языков программирования.
Реализованные вручную синтаксические анализаторы чаще работают с ЬЬ-грамматиками; например, предикгивный подход, описанный в разделе 2.4.2, работает с ЬЬ-грамматиками. Синтаксические анализаторы для большего класса ЬК-грамматик обычно создаются с помощью автоматизированных инструментов. В этой главе мы полагаем, что выход синтаксического анализатора является некоторым представлением дерева разбора потока токенов от лексического анализатора. На практике имеется множество задач, которые могут сопровождать процесс разбора, такие как сбор информации о различных токенах в таблицу символов, выполнение проверки типов и других видов семантического анализа, а также генерация промежуточного кода. Все эти задачи представлены одним блоком "Остальная часть начальной стадии" на рис.
4.Ь Детальнее они будут рассмотрены в последуюших главах. 4.1.2 Образцы грамматик Ниже представлены некоторые из грамматик, рассматриваемых в этой главе, что должно упростить дальнейшие ссылки на них. Конструкции, начинающиеся с ключевых слов наподобие Ьеа(в и !вг, проанализировать относительно просто, поскольку ключевое слово определяет выбор продукции грамматики, которая должна быть применена ко входному потоку. Поэтому мы сконцентрируемся на выражениях, работать с которыми сложнее из-за ассоциативности и приоритета операторов. Ассоциативность и приоритет операторов присутствуют в следующей грамматике, аналогичной грамматикам из главы 2, использовавшимся для описания выражений, слагаемых и сомножителей.
Е представляет выражение, состояшее из слагаемых, разделенных знаками +, Т представляет слагаемые, которые со- Глава 4. Синтаксический анализ стоят из сомножителей, разделенных знаками *, а Е представляет сомножители, которые могут быть либо выражениями в скобках, либо идентификаторами: Š— Е+Т(Т Т вЂ” Т*Е)à Š— (Е) (Ы (4. 1) Грамматика выражений (4.1) принадлежит классу ЕК-грамматик, которые подходят для восходящего синтаксического анализа. Эта грамматика может быть адаптирована для работы с дополнительными операторами и дополнительными уровнями приоритетов.
Однако она не может быть использована для нисходящего синтаксического анализа в силу ее леворекурсивности. Для нисходящего синтаксического анализа можно использовать следующий вариант грамматики (4.1), в котором устранена левая рекурсия: Š— Т Е' Е' — +Т Е' ) е Т вЂ” Е Т' (4.2) Т вЂ” ~ вг Т (е Š— (Е)~Ы Приведенная далее грамматика рассматривает * и + как идентичные, так что она пригодится для иллюстрации методов обработки неоднозначностей в процессе синтаксического анализа: Š— Е+ Е ( Е*Е ! (Е) ( Ы (4.3) Здесь Е представляет выражения всех типов.
Грамматика (4.3) допускает более чем одно дерево разбора для выражений наподобие а + 6 * с. 4.1.3 Обработка синтаксических ошибок В оставшейся части этого раздела мы рассмотрим природу синтаксических ошибок и общие стратегии восстановления после ошибок. Две из стратегий, называющиеся "в режиме паники" и "на уровне фразы", будут рассмотрены более детально в связи с конкретными методами синтаксического анализа. Если компилятор будет иметь дело исключительно с корректными программами, его разработка и реализация существенно упрощаются.
Однако от компилятора ожидается, что он будет помогать программисту обнаруживать и устранять ошибки, которые неизбежно содержатся в программах несмотря на огромные усилия даже самых квалифицированных программистов. Примечательно, что хотя ошибки — явление чрезвычайно распространенное, лишь в нескольких языках 255 4.1. Введение вопрос обработки ошибок рассматривался еще на фазе проектирования языка. Наша цивилизация была бы совсем другой, если бы в естественных языках были такие же требования к синтаксической точности, как и в языках программирования.
Большинство спецификаций языков программирования, тем не менее, не определяет реакции компилятора на ошибки — этот вопрос отдается на откуп разработчикам компилятора. Однако планирование системы обработки ошибок с самого начала работы над компилятором может как упростить его структуру, так и улучшить его реакцию на ошибки. Ошибки в программе могут быть на самых разных уровнях. ° Лексические ошибки включают неверно записанные идентификаторы, ключевые слова или операторы, например использование идентификатора е11рвеЯ1ге вместо е111рвеЯ1ге или отсутствие кавычек вокруг текста, являющегося строкой.
° Синтаксические ошибки включают неверно поставленные точки с запятой или лишние нли недостающие фигурные скобки ( или ). В качестве еще одного примера в С или )аяа синтаксической ошибкой является конструкция саве без охватывающего вн1ТсЬ (однако эта ситуация часто пропускается синтаксическим анализатором и перехватывается позже, на уровне генерации кода). ° Семантические ошибки включают несоответствие типов операторов и их операндов. В качестве примера можно привести оператор теТигп со значением в методе )ача, возвращающем тип чойс1.
° Логические ошибки могут быть любыми — от неверных решений программиста до использования в программе на языке С оператора присваивания = вместо оператора сравнения ==. Программа, содержащая оператор =, может быть корректной, но делать совсем не то, чего хотел от нее программист. Точность современных методов разбора позволяет очень эффективно выявлять синтаксические ошибки в программе. Некоторые методы синтаксического анализа, такие как ЕЕ и ЕК, обнаруживают ошибки на самых ранних стадиях, т.е. когда разбор потока токенов от лексического анализатора в соответствии с грамматикой языка становится невозможен. Говоря более точно, они обладают свойством коррекглного префикса (ч)аЫе-ргебх ргореггу), т.е, они обнаруживают ошибку, как только встречают префикс, который не может быть префиксом ни одной корректной строки данного языка.
Еще одна причина, по которой делается упор на восстановление после ошибки в процессе синтаксического анализа, — многие ошибки, чем бы они ни были вызваны, оказываются синтаксическими и выявляются при дальнейшей невозможности синтаксического анализа. Эффективно обнаруживаются и некоторые 256 Глава 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
