Г. Шилдт - Полный справочник по C++ (1109478), страница 143
Текст из файла (страница 143)
| выражение -> терм [+терм] [-терм] терм -> фактор [ "фактор! [!фякгор] фактор -> переменная,число илн выражение Квадратныс скобки содержат необязательный элемент, а символ -> интерпретируется как глагол "'паразкдае~п". Правила, указанные выше, часто называют паразкдаюи(!ини правилами (ргос1цсйоп пз!сз), или продукциями. Следователыю, определение тсрма можно было бы озвучить так: "Терм порождает фактор, умноженный на фактор, или фактор, деленный на фактор'*.
Обратите внимание на то, что порождающие правила неявно учитывают приоритет операций. Выражение й !О+5'В состоит из двух термов: 10 и 5'В, Второй терм состоит из двух факторов: 5 и В. Эти факторы состоят из одного числа и олной перел1снной. С другой стороны, выражение й 14*(7-С) состоит из двух факторов: 14 и (7 — С).
Факторы состоят из одного числа и одного выражения, заключенного в скобки. Выражение, заключенное в скобки, состоит из двух термов: одного числа и одной переменной. Этот процесс образует базис рекурсивного нисходящего анализа, представляющего собой набор взаимно рекурсивных функций, работающих по цепочке и реализующих порождающие правила.
На каждом шаге анализатор выполняет операции, последовательность которых определена алгебраическими правилами. Чтобы продемонстрировать, как порождающие правила применяются для синтаксического анализа выражений, рассмотрим следующий' пример. $9/3-(100+56) Для синтаксического анализа следует выполнить следующие действия. 1. Получить первый терм 97'3. 2. (!олучить каждый фактор и поделить цслыс числа. Результат равен 3. 3. Получить второй фактор, (100+56). В этой точке начинается рекурсивный анализ второго полвыражения.
4. Получить все факторы и сложить их. Результат: 156. 5. Вернуться из рекурсивного вызова и вычесть !56 из 3. Ответ: — 153. Если это описание вас слегка напугало, нс волнуйтесь. Ведь рекурсивный нисхоляший анализ выражений — довольно сложная концепция. Просто не забывайтс две важныс вещи. Во-первых, порожлающие правила неявно учитывают приоритет операторов. Во-вторых, этот метод анализа и вычисления выражений очень похож на способ, с помощью которого люди сами вычисляют математические выражения. В оставшейся части главы мы рассмотрим три программы синтаксического анализа выражений. Первая программа аначизирует и вычисляет выражения типа допзз1е, состоящие исключительно из констант.
Затем мы рассмотрим синтаксический анализатор, позволяющий применять переменны . И в заключение третья версия анализатора будет реализована в виде шаблонного класса, который можно применять для синтаксического анализа выражений любого типа. Часть ]!. Приложения на языке С+у 1:1 Класс рагвег В основе программы синтаксического анализа выра гений лежит класс рагввг. Первая версия этого класса приведена ниже. Последуюшие версии представляют собой модификации первой.
с1авв рагвег сиаг *ехр рсг; сцег го)сеп[ВВ); сиаг го)с суре; // Ссылается на выражение. // Хранит текужую лексему. // Хранит тил лексемы. чоЫ еча1 ехр2ЫоиЬ)е ьгееи1с); чово еча1 ехрз(йоиЬ1е агеви1с); чоЫ еча1 ехр4(г)оиЬ1е агеяи1с); чо1о еча1 ехр5(с)оиЬ1е агеви1с); чо<с) еча1 ехрб <йоиЬ1е агееи1г); чоЫ агою ЫоиЬ1е агеви1С); чоьп дег гохеп О; чоЫ аеггог(Ыс еггог]; 1пг зес)е11ы(сиаг с); риЬ11с; рагеег(); с)оиЬ1е еча1 ехр(сиаг *ехр); ) Класс рагввг содержит три закрытые переменные-члены. Вычисляемое выражение содержится в обычной строке, на которую ссылается указатель вхр рте. Таким образом, анализатор вычисляет выражения, содержашиеся в стандартных АБСИ- строках.
Например, анализатор способен вычислить следующие выражения: 1 "10 — 5" "2*33/3.1416 *3.3" Разбор выражения на составные части Чтобы вычислить выражение, необходимо разбить его на составлявшие. Поскольку эта операция является главной, ес следует рассмотреть в первую очередь. Глава 40. Синтаксичесхий анализ выражений Если анализ начинается с выражения, указатель вхр рег должен ссылаться на первый символ строки. В ходе работы анализатор считывает оставшуюся часть строки, пока не обнаружит ее конец.
Предназначение остальных переменных-членов, говею и сов туре. описано в следующем разделе. Отправной точкой анализа является функция ечв1 ввр(), которой следует передать указатель на анализирусмое выражение. Функции вча1 вхрз() — вча1 вярб() вместе с функцией веем<) образуют основу рекурсивного нисходяшего анализа. Они реализуют порождающие правила, описанные выше. В послелуюших версиях анализатора к ним булет добавлена функция вча1 вхр1() . Функция ввггог() предназначена для обработки синтаксических ошибок, содержашихся в выражении. Функции рве ео)гвп О И 3 вйв1)злю используются лля разбора выражения на составные части.
Кажлый колшопент выражения называется лексемой Во(сеп). Например, выражение В а*в т(У+[О) состоит из лексем А, ', В, —, (, %, +, 10 и ). Каждая лексема представляет собой неделимую часть выражения. Как правило, для снгпаксического анализа необходима функция, которая последовательно возвращала бы отдельные лексемы, из которых состоит выражение.
Кроме того, эта Функция должна игнорировать пробелы и знаки табуляции, а также распознавать конец выражения. Функция, которая позволяет выделить лексемы, называется нет ео)сепО. Она является членом класса ратвет. Нам необходимо знать тип лексем. В нашей программе использованы три типа лексем: уаатввпе, нпивен и пеымхтен. (К типу педтнттен относятся операторы и скобки.) Функция пес со)сеп() показана ниже. Она извлекает следующую лексему из выражения, на которос ссылается указатель ехр рст, и заносит ее в переменную ео)сеп. Тип извлеченной лексемы записывается в псремегшую ео(с суре. // Извлекает следующую лексему.
чо'й ратвет::дее Сокеп() ( тедуясет с)сат 'сещр; ток суре = Ос тещр = со)сенс *тещр = 'сО'с 1т(!*ехр рст) тегцтп/ // В конце выражения. иЫ1е(авярасе(*ехр ртт)) ++ехр ртт; // Пропуск разделителей. 11(яттс)ст("а-*/%"а[)", "ехр рст))( Со)с Суре = ()Е) 1ИХТЕР./ // Переход к следующему символу. *сещр++ = *ехр рст++; ) е1ве 11(зва1р?са[*ехр ртт)) ин11е(!1вс)е11щ[*ехр рст)) *сесар++ = *ехр рета+; тох Суре = (/ЛЕ1ЛВ~.Е/ е1ве Н (увс)191С[*ехр ртт)) ( ив11е(!1вс)е11щ(*ехр рст)) *свар++ = *ехр рте++с Со)с Суре = НОИВЕЕ; ) *сещр = 'Ю' ) // Если параметр с является разделителем, // возвращает значение ттце.
йпс ратяетссйяс)е11щ(сиад с) ( 11 [ветс)ст (" +-/*Ъ"= () ", с] ( ( с=а9 ! ! с==' Хт' ( ( с==О! тегцтп 1; тегцтп 0; Часть((. Приложения на языке С++ << А+!00 — (В*С)П Вот какие лексемы и типы возврашаст функция пвс со<сев< ) в этом примере. Лексема гвл лексемы чъахввья ввьхмхтвв мвиввл ввьхихтвв ввьхмхтма таахавг в ввьхмхтяа тлахъвьв ввьхихтвв вмьхмхтяа 100 С ) 2 пи(( Напомним, что переменная со<сев всегда храни~ строку, завсршаюшуюся н)лсвым байтом, даже если в ней записан сдинствснный символ, Глава 40. Синтаксический анализ вырываний Присмотримся к этим функциям. После первых инициализации функция пес сокев() провсряст, нс обнаружен ли консц файла. Для это~о она проверяет символ, на который ссылается указатель еяв век.
Если сто значс нив равно нулю, значит, достигнут консц выражения. Если в выражсп пи остались сшс нс извлсчснныс лексемы, функция пес со)сев<) пропускает всс всдушис разделители. Поскольку разделители игнорируются, указатель ехр рсх может ссылаться либо на число, либо на переменную„либо на оператор, либо па конец выражения (в этом случае он равен нулю). Если слсдуюшим символом является оператор, он возврашастся в видо строки и записывается в псрсмснную са(сев, а в псрсмснную сои суре записывается константа вмьхмхткя.
Если слсдуюший символ является буквой, прсдполагастся, что лскссма является псрсмсннои. Она возврашастся в виде строки и записывается в псрсмс<шую сомев, а в переменную со)с суре записывается константа зглмхдвьм. Если слслуюший символ является цифрой, считывается все число. Затсм оно прсврашастся в строку и записывается в переменную сокев, а в псрсмсппую со<с суре записывается константа мвмвмм. В заключение. соли слсдуюшии символ нс относится пи к одному из перечисленных вышс типов, считается, что функция пес сокев() достигла конца выражения.
Как указывалось выше, чтобы нс загромождать код функции, в нсй пропушсны многочисленные проверки ошибок и слслано несколько упрошаюших прсдположсний. Например. прсдгвлагастся, что выражснис нс может содсржать неопознанных символов. Кроме топь в ланной версии про|раммы псрсмснныс могут иметь произвольную длину, но значимым считается только первый символ имени. Всс нсобходимыс проверки ошибок читатели могут добавить сами, ориентируясь па трсбования своих собственных приложений.
Чтобы лучше поня~ь процссс разлслсния выражения на лексемы, рассмотрим пример. ~~~ Простая программа синтаксического анализа выражений Рассмотрим первую версию синтаксического анализатора. Он вычисляет значение выражений, состояших лишь из констант, операторов и скобок, и не допускает выражений, содсржашнх переменные.
/* Программа, выполняющая рекурсивный нисходящий анализ выражений, не содержащих переменные. */ Вапс1иое <1оветеаза> Взпс1и<)е <свео11Ь> Взпс1ис)е <сссуре> В(пс1иое <свстапд> ивзлд патеврасе ясе); епищ Гурев ( ПВЬ1Мттпл = 1, ЧЛП1ЛВЬВ, НВМВВК); с1авв ратвет ( спал *ехр рет; // Ссылается на выражение. спал сохеп[801; // Хранит текущую лексему. спат Сох Суре; // Хранит тип лексемы. чоас( еча1 ехр2 (е)оиЬ1е атеви1е); чо1е) еча1 ехрз (ооиЬ1е атеви1с); чоао еча1 ехр4 ИоиЬ1е атеяи1С); чо1<) еча1 ехр5(ооиЬ1е атеви1с); чо16 еча1 ехрб ЫоиЬ1е атеви1е); чоао асом(ооиЬ1е атеяи1с); чозс) дее сокеп(); чоа<) яеттот(1пс еттот); апс 1в<)е11щ(сЬат с); риЬ11с: ратвет()) е)оиЬ1е еча1 ехр(спат *ехр)) ); Конструктор синтаксического анализатора.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
