Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 38
Текст из файла (страница 38)
что и квадратные, и фигурные скобки в описании с по>вошью формы РБНФ являются метасимволами. а не терминальными символами, используемыми в языке А<)а. условный оператор иначе — ы 'условный оператор> — т И <условие> сьал <операторы> т <иначе> ) )а1ае <операторы> епе и <иначе> — и е1аи <условие> слеп <операторы> Рис. 3.6. Снтттттиксттческий гриф и от<сания ои<рынтори л.х' языка,Ыа с утоттотпокт <)тор<ты )". НФ Использование графического представления для описания синтаксиса прелоставляет те жс выгоды. что и использование графическот о представления для описания чего-либо: оно ) величивает читабельность. позволяя нам наглядно представлять описываемый объеьг в двух измерениях.
3.3.4. Грамматики и устройства распознавания языков Ранее в этой главе мы говорили о с) шествовании тесной связи между устройствами пор<гкдения и расгюзнавания языка. Действительно. при наличии контекстно-свободной т рамматики существ) ет алгоритм созданил ) стройства распознавания языка. порождаемого этой грамматикой. Для этого построения оыло разработано большое количество систем программного обеспечения.
Подобные системы позволяют быстро созлавать синтаксический анализатор, являющийся частью компилятора нового языка. Одним из наиболее широко используемык генераторов синтаксических анализаторов является устройство уасс !) ет апог)тег сошр))егсогпрт)ег — сше один компилятор компиляторов) (Зоп)твои, )975).
Гдово 3. Описание синтаксиса и семантики Синтаксические анализаторы языков программирования, часто называемые программами синтаксического анализа, создают деревья синтаксического анализа для данной программы. В некоторых случаях дерево синтаксического анализа создается неявно, но во всех случаях информация, содержащаяся в дереве синтаксического анализа. возникает во время самого анализа. Программы синтаксического анализа делятся по принципу направления, в котором они создают деревья синтаксического анализа.
Существуют два обширных класса программ синтаксического анализа: нисходящие, в которых дерево порождается от корня вниз к листьям. и восходящие. в которых дерево создается от листьев вверх к корню, Пример нисходящего алгоритма синтаксического анализа кратко описан в разделе 3.4. 3.4. Рекурсивный нисходящий синтаксический анализ Как отмечалось в разделе 3.3.1.7, контекстно-свободная грамматика служит основой синтаксического анализатора. или программы синтаксического анализа. являюшегося частью компилятора.
Рассмотрим основанный на контекстно-своболной грамматике нисхоляший анализатор грамматики, который мы булем называть программой релурсивного нисходящего синтаксического анализа. Синтаксический анализ — это процесс отслеживания или созлания дерева синтаксического анализа для данной введенной строки.
Основной идеей рекурсивного нисходящего синтаксического анализа является существование подпрограммы для кажлого не- терминального символа грамматики. Обязанности подпрограммы, относящейся к конкретному нетерминальиому символу, следующие: при введении строки она создает эскизный вариант дерева синтаксического анализа, корнем которого является данный не- терминальный символ, а листья соответствуют введенной строке. В действительности. подпрограмма рекурсивного нисходящего синтаксического анализа — зто устройство синтаксического анализа языка (набора строк), который может порождаться его нетерминальными символами.
Во многих случаях язык, подвергаемый синтаксическому анализу. содержит вложенные синтаксические единицы (например, выражения и операторы), так что подпрограмма. выполняющая синтаксический анализ. часто является рекурсивной. Прелположим. что каждый нетерминальный символ содержит одно правило, возможно, с несколькими правыми частями. разделенными операторами ИЛИ. Рассмотрим следуюшее описание элементарных арифметических выражений в форме РБНФ: <выражение> -з <терм> ((+)-) <терм>) <терм> — з <множитель> ((*(/) <множитель>) <множитель> -з <идентификатор> ( ( <выражение> ) Если подпрограммам рекурсивного синтаксического аназиза требуется узнать, какое следующее входное обозначение должно быть подвергнуто анализу, то для его получения вызывается подпрограмма лексического анализатора.
Напомним, в главе 1 говорилось. что лексический анализатор служит входом синтаксического анализатора. Он объединяет входные символы в лексемы и возвращает грамматические лексемы, связанные с этими лексемами. В привеленной ниже функции рекурсивного синтаксического анализа ехрг эта функция называется соответствующим именем 1ехз са1.
Она получает следующую грамматическую лексему и помешает ее в глобальную переменную пехг с океп. 141 3.4. Рекурсивный нисходящий синтаксический анализ Ниже приведена подпрограмма рекурсивного синтаксическою анализа, написанная на языке С лля первого нз приведенных в этом разделе правил. чодс( ехрг() ( Сегщ()г /* синтаксический анализ первого терма */ иЬ11в (пехг со)<еп == р1иа со<(е () пехс сохеп = щ1пцэ сос(е) 1ехдса1(); /* ввод следующей граыматической лексемы */ "егщ(); /* синтаксический анализ следующего терма */ ) ) В представленной выше функции синтаксического анализа предполагается, что каждая рекурсивная функция синтаксического анализа сохраняет следуюшую входную грамматическую лексему в переменной пенс сокеп. Таким образом, всякий раз в начале выполнения функции синтаксического анализа гарантируется, что переменная пехс сохеп содержит крайнюю левую грамматическую лексему, которая еше не аналнзнровалась.
Разбираемая функцией ехрг часть языка состоит нз одного нлн нескольких элементов (сегщ), разделенных операторами сложения нлн вычитания. Такой язык порождается абстракцией <выраженне>. Следовательно, вначале вызывается функция синтаксического анализа термов. Затем функция ехрг продолжает вызывать эту функцию до тех пор, пока булут обнаруживаться элементарные значения оператор сложения нлн оператор вычитания (синтаксический анализ коюрых пропускается с помощью вызова функции 1ехдса1). Эта функция рекурсивного синтаксического анализа проще большинства ей подобных, поскольку ее правила содержат только одну правую сторону. Более тою, эта функция не солержнт никаких средств обнаружения нлн устранения синтаксических ошибок. Обшнй процесс создания программы нисходящего рекурсивного синтаксическою анализа для данного нетермннального символа начинается с написания кода для определения, какая именно правая часть правила лля данного нетермннального символа соответствует строке входных обозначений.
Это решение принимается на основе первого терминальною символа введенной строки, порождаемого нетермннальным снмволом. Код для каждой правой части правила относительно прост. Каждый терминальный снмвол сравнивается со следуюшнм обозначением. Если онн не совпадают, то возникает сннтакснческая ошибка, в противном случае лля перехода на следуюшее входное обозначение вызывается лексический анализатор. Вызов подпрограммы синтаксического анализа выполняется для каждого нетермннального символа.
Функция лля нетермннального символа <множнтель> должна делать выбор между двумя правыми частями его правила. Она также обнаруживает ошибки. В функции для символа <множнтель> прн обнаружении ошибки вызывается функция вгкок. В реальной программе синтаксического анализа в этом случае должно выдаваться диагностическое сообшенне. Более того, большинство компиляторов должны возобновлять свою работу прн появлении ошибки, чтобы процесс синтаксического анализа мог продолжаться. Подобные компиляторы не могут просто останавливаться прн обнаружении в программе первой синтаксической ошибки.
И2 Глава 3. Описание синтаксиса и семантики тоде( басгог() ( дг (пехс Гокеп = 1д соде) ( 1ех1са1 (); гегцгпг ) в1вв дх' (пехг годен == 1ейг рагел соде) ( 1ехдса1 (); ехрг(); (пехг годен == г19М рагел соде) ( 1ехдса1(); гвсцгю) в1вв еггог(); /* обнаружена закрывающая круглая скобка */ ) в1вв еггог(); /* не обнаружено ни идентификатора, ни открывающей круглой скобки */ Целью данного краткого обсуждения синтаксического анализа было убедить вас, что программу рекурсивного нисходящего синтаксического анализа легко написать, если для языка существует подходящая грамматика. В данном контексте слово "подходил(ал" означает, что для того, чтобы грамматику можно было использовать для рекурсивного синтаксического анализа, она должна иметь особую форму.
Обсуждение всех характеристик, позволяющих или запрещающих использование конкретной грамматики для рекурсивного нисходящего синтаксического анализа, выходит за рамки этой книги. Подробнее об этом вопросе вы можете узнать из работы (Р)зпегдпд (,еВ)апс, 1988). Одной простой характеристикой, создающей рекурсивному нисходящему грамматическому разбору катастрофические проблемы, является левосторонняя рекурсия. Рассмотрим следующее правило: <А> -з <А> ь <В> Подпрограмма рекурсивного нисходящего синтаксического анализа для символа <А> немедленно вызовет себя же. Это приведет к вызову подпрограммы синтаксического анализа символа <А> н еше одному вызову ее же, и еше раз, и еще. Понятно, что это ни к чему не приведет. По этой причине левосторонняя рекурсия не допускается в грамматиках, лля которых должна создаваться программа нисходящего рекурсивного синтаксического анализа.
Существенным фактором важности грамматик является их тесная связь с компиляторами. 3.5. Атрибутивные грамматики Атрибутивнал грамматика (ацпЬц(е 8гщпваг) более подробно описывает струкгуру языка программирования, чем контекстно-свободная грамматика, и является ее расширением.
Это расширение позволяет описать такие правила языка, как совместимость типов. Прежде чем мы формально определим форму атрибутивной грамматики, разьясним концепцию статической семантики. 3.5. Атрибутивиые грамматики 3.5.1. Статическое семантика Существуют некоторые характеристики структуры языков программирования, описать которые с помощью формы БНФ сложно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
