Карпов - Основы построения трансляторов (2005) (943926), страница 25
Текст из файла (страница 25)
Пусть также с — стоимость короткого слова, С— стоимость длинного слова, ып1 — стоимость очередной телеграммы, Яшп— стоимость всех обработанных телеграмм, Мах — максимальная длина допустимых коротких слов в телеграмме. Семантические правила представлены следующими действиями уΠ— У7, выполняемыми конечным автоматом при распознавании им текущего потока символов (рис.
5.10). Рис. 5.10. Выполнение семантических правил Эти семантические действия описаны в табл. 5.1. Таблица 5.1. Семантические правила Х = 1: А = И = К = 1. = В =- Яшш = О; уо Все параметры принимают начальные значения ый символ телеграммы, длина а1 едной символ текущего слова раммы Е>Мах Мел И++ еЬе у3 щее слово телеграммы закончилось чилась очередная телеграмма А.+ =- й; 0+= 4 вцш = Ис~-У'С; Яыш+=- ыш: у4 ~ Печать~" Телеграмма номер" Х "Число коротких слов" "Число длинных слов" И "Стоимость" ваш) Глава 5 Таблица 5.1 (окоичаш~е) Ю++; А=1; Встретился первый символ новой телеграммы, который является знача- щим у5 Ф++; Е = О; уб Встретился первый символ новой те- леграммы, который является незнача- щим ~пробелом) Закончившаяся телеграмма была по- следней в потоке телеграмм. Нужно выдать итоговую информацию Печать~ "Всего телеграмм" Ю "Всего коротких слов" К "Всего длинных слов" 0 "Всего стоимость" Яцп1); Включение этих семантических операций в блок-схему программы распознавателя очевидно.
В результате получаем транслятор входного языка (рис. 5.11). Рис. 5.11. Блок-схема транслятора 5.3.2. Язык перечисления номеров страниц Рассмотрим теперь задачу построения программы выдачи принтеру печатаемых страниц по перечислению их номеров или интервалов, принятому в редакторах текстов, например в редакторе М1сгоюй Фогт. В этой программе приведен следующий пример такого перечисления: 1„3, 5-12, .... В строке по крайней мере один номер страницы должен быть задан, пробелы не будем учитывать. Каждое такое задание на печать — это, несомненно, цепочка языка.
Таких цепочек можно придумать бесконечное количество, например 2, 43-17, 11-28 или 15, 3, 2-7 и т. и. Искомая программа может быть построена разными способами, но наиболее простой — построить ее как транслятор языка, задающего все возможные такие цепочки. Этот язык является, конеч- Нисходящие методы синтаксического анализа но, автоматным, он может быть представлен автоматной грамматикой или, что эквивалентно, распознающим автоматом. Показанный ниже конечный автомат-распознаватель задает все цепочки этого языка.
Автомат достаточно простой, но в то же время он представляет все возможные цепочки этого языка в наглядной графической форме (рис. 5.12). Рис. 6.12. Возможные цепочки языка Искомый транслятор легко построить, добавив нужные семантические операции на переходах этого конечного автомата и затем реализовав этот автомат подобно тому, как это сделано в предыдущем примере.
Эту простую операцию мы оставляем читателю в качестве упражнения. 5.3.3. Римские числа В качестве еще одного примера рассмотрим задачу построения программы вычисления значения римских чисел. Римская система счисления оперирует со следующими римскими цифрами (табл. 5,2). Таблица 5.2. Значения римских цифр Глава 5 Каждая цифра (кроме 1) может быть также надчеркнута. при этом ее значение увеличивается в 1000 раз. В римской системе счисления используются следующие правила (табл. 5.3) синтаксиса и семантики (т. е. правила построения структуры цепочек и правила интерпретации их для подсчета значения числа). Таблица 5.3. Правила построения римских чисел Все цифры, являющиеся степенью 1О, могут повторяться до трех раз.
Цифры Ч, 1. и 0 повторяться не могут Обычно меньшие цифры следуют за большими. В этом случае их значения скла- дываются В некоторых случаях меньшие цифры могут предшествовать большим. Значение числа в этом случае получается вычитанием меньшей цифры из большей. Пред- шествование меньшей цифры большей может быть только в случае, если выполняются все следующие условия: а) меньшая цифра — степень 10; б) меньшая цифра должна быть либо одной пятой, либо одной десятой значения большей; в) меньшая цифра должна быть или первой цифрой в выражении, или же ей предшествует цифра, по крайней мере в 10 раз больше ее значения; г) если за большей цифрой следует какая-либо цифра, она должна быть меньше, чем та, которая предшествует большей цифре Примеры римских чисел: ХХХ1Х = 39, ХХИ = 24, СМ1.1Х = 959.
Непросто разработать формальный алгоритм, реализующий указанные выше правила вычисления значений римских чисел, и построить по нему программу. Но поскольку римские числа как последовательности символов (цифр) обладают структурой, мы можем использовать синтаксически-ориентированный подход, а именно построить грамматику, порождающую эти числа, после чего подобрать такие локальные семантические правила для каждого правила грамматики, которые обеспечат трансляцию любых допустимых строк, т.
е. трансляцию римских чисел. Для меньшей громоздкости мы ограничимся только четырьмя цифрами: 1, У, Х и 1. Грамматика, порождающая римские числа, является автоматной. В главе 2 было показано, что синтаксическая диаграмма и конечный автомат — это две эквивалентные модели задания множества цепочек символов. В той же главе приведена синтаксическая диаграмма, соответствующая автоматной грамматике, порождающей множество римских чисел, составленных из указанных четырех символов Дополним эту синтаксическую диаграмму семантическими операциями в нужных местах (рис.
5.13). Нисходящие методы синтаксического анализа Рис. 5.13. Синтаксическая диаграмма, дополненная семантическими операциями Семантические операции, введенные в эту синтаксическую диаграмму, имеют следующий смысл (параметр Ж накапливает значение числа) (табл. 5.4). Таблица 5.4. Смысл семантических операций Расширение этой синтаксической диаграммы на другие цифры римской системы счисления очевидно. Программу распознавания и трансляции римских чисел по этой синтаксической диаграмме легко реализовать программно. 5.4.
Лексический анализ языков программирования В реальных трансляторах первой фазой является не синтаксический анализ входной программы, а так называемый лексический анализ, т. е предварительная обработка входного текста с выделением в нем структурно значимых единиц — лексем. Лексема — это та минимальная единица языка, которая имеет смысл с точки зрения синтаксиса.
В естественном языке такими единицами являются не буквы, а слова (словоформы), в языке программирования — никак не отдельные символы, но имена, отдельные служебные слова и т. д. На входе транслятора исходная программа представлена в виде неструктурированного потока байтов, как, например, следующий: 09 бб 6Г 72 20 бА 20 ЗА 30 20 31 20 64 6Г 20 60 61 78 20 64 бГ 00 ОА 09 20 20 20 78 5В бА 50 20 ЗА ЗВ 20 30 ЗВ ОВ ОА Этот поток байтов — посимвольная кодировка в коде АЗС11 фрагмента программы: Глава 5 Для синтаксического анализа этого фрагмента удобнее оперировать такими понятиями, как "служебное слово аког", а не отдельными символами Т, 'о', 'г'; "идентификатор тах", а не отдельными символами 'т', 'а', 'х'; "опе атор присваивания:=", а не отдельными символами ' и '='.
Символ 'о' не имеет смысла для синтаксического анализа. Имеют значение (и различное!) только служебные слова Тог' или 'до', а то, что в них входит один и тот же символ 'о', значения не имеет никакого. Имеет смысл пара символов '.= ' как оператор присваивания, а вовсе не то, что в него входит символ равенства ' = '. Задача лексического анализатора — снять очевидное противоречие: входной поток представлен в виде неструктурированной последовательности байтов, в то время как алгоритмы синтаксического анализа оперируют с цепочкой синтаксически значимых единиц.
Структура транслятора с первой фазой лексического анализа приведена на рис. 5.14. Рис. 5.14. Лексический и синтаксический анализаторы в структуре трансляции Существует еще несколько других причин, по которым фаза анализа входной цепочки при трансляции разделяется на две — фазу лексического анализа и фазу синтаксического анализа. Оказывается, такое разделение упрощает фазу синтаксического анализа, позволяя построить два эффективных этапа, каждый из которых имеет свою собственную технику реализации. Например, описать с помощью контекстно-свободной грамматики язык, в котором между любыми символами может быть включен комментарий, можно, хотя очень непросто. Далее, вспомним так называемые "белые символы" — пробелы, табуляция, перевод строки — они также могут в любом количестве стоять между лексемами. Описание и языка, и включения "белых символов" в цепочки языка одной грамматикой очень громоздко.
Поэтому обычно фазу лексического анализа реализуют с помощью простейших эффективных средств— конечно-автоматного алгоритма распознавания и обработки строк, упрощая последующие фазы синтаксического и семантического анализа. Нисходящие методы синтаксического анализа Ясно, что лексический анализатор как преобразователь символьных цепочек также может быть построен на основе синтаксически-ориентированного подхода, вот только используемые здесь грамматики очень просты. А именно, все лексемы описываются регулярными выражениями — одним из способов эффективного задания автоматных языков. Затем по регулярному выражению строится конечный автомат — распознаватель, и с каждой лексемой связываются те семантические действия, которые должен выполнить автомат после распознавания этой лексемы во входном потоке байтов. Таким образом, распознавание вместе с генерацией требуемого выхода выполняется в лексическом анализаторе на основе нисходящей стратегии. Рассмотрим пример фрагмента программы: ~й Жз~апсе >= фреей * (епб~~п1е — з~аг~~ппе) ~реп Жя~апсе: = Жз~апсе— бе1~а; В этом фрагменте несколько идентификаторов: а~а~апсе, ярееа, ем~ипе и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
