Обзоры Обзоры 20.05.2003 в 21:00 comment

Путешествия дилетанта (не (с)только о трансляторах)

author avatar
https://secure.gravatar.com/avatar/2f8d57cddfeb455ba418faa11ee01bb0?s=96&r=g&d=https://itc.ua/wp-content/uploads/2023/06/no-avatar.png *** https://secure.gravatar.com/avatar/2f8d57cddfeb455ba418faa11ee01bb0?s=96&r=g&d=https://itc.ua/wp-content/uploads/2023/06/no-avatar.png *** https://itc.ua/wp-content/themes/ITC_6.0/images/no-avatar.svg

ITC.UA

автор

я, знаете ли, не выношу шума, возни, насилий и всяких
вещей в этом роде. В особенности ненавистен мне людской крик, будь то крик страдания,
ярости или иной какой-нибудь крик. Успокойте меня, скажите, вы не буйный?
Михаил Булгаков

Некогда, кратко привлекая внимание читателя к теме трансляции, — фундаментального
функционально-алгоритмического приема, использующегося при создании прикладного
и системного ПО разнообразных классов, автор ограничился только ссылками на
некоторые инструментальные средства, облегчающие работу программиста ("Компьютерное
Обозрение", # 23, 2001). На первый взгляд, общим у всех этих средств, вместе
со ставшей классикой "парочкой" — генераторами программ лексического
и синтаксического разбора lex и yacc (с 1975 г., с момента опубликования статей
Леска и Джонсона, эти программы стали неотъемлемыми компонентами инструментального
набора Unix и Unix-подобных ОС), является именно их Unix-прошлое, отражающееся
и в "пользовательском интерфейсе" командной строки, и в специфике
реализации. Но это только на первый взгляд… Как ни прискорбно, даже лучшие
из приведенных в давнишней статье инструментов обладают еще одним общим свойством,
связанным с историей их создания. Впрочем, столь категорическое утверждение
нуждается в детальных объяснениях — даже прописная истина "нет в мире
совершенства" иногда того требует. А сами детальные объяснения автор постарался
выстроить в виде повествования, так, чтобы одновременно и частично восполнить
недостаток информации в предыдущей статье и, собственно, не оставить без должного
внимания предмет обсуждения.

Инструмент как элемент архитектуры

…из всех искусств архитектура отважнее всех стремится
воссоздать собою миропорядок, который древние люди именовали kosmos, то есть
изукрашенный, он целокупен, как некое громадное животное, поражающее совершенством
и согласием во всех членах.
Умберто Эко

Взаимосвязь архитектуры программной системы (т. е., по сути, — тех макроархитектурных
решений, на которых строится программная среда, включающая в себя и операционную
систему, и системное/прикладное ПО) и показателей качества частных инструментальных
средств этой программной системы, без сомнения, существует. Вот только вскрыть
ее позволяют, по-видимому, исключительно или практический опыт, или безукоризненно
глубокие знания различных программных систем и инструментов. К сожалению, второй
путь для обычного (не гениального) человека сегодня фактически недостижим —
слишком велика сложность объекта познания. Остается путь эмпирический — попробовать
решить одну и ту же задачу (пусть даже и несложную) с использованием разных
инструментальных средств. Именно этот путь и подвигнул автора на написание данной
статьи.

Итак, задачка была сугубо любительской (слава Богу), можно сказать — потешной:
на досуге, сугубо для нужд, диктуемых застарелым хроническим хобби, "сваять"
элементарный транслятор, по сути, приукрашенного синтаксическими конструкциями
языка С ассемблера четырехбитного микроконтроллера (и таким устройствам находится
место в нашем мире) в машинный код. И если бы не работа над ней урывками, по
ночам, от случая к случаю, возможно, все закончилось бы вполне благополучно
— в том смысле, что эта статья так и не была бы написана…

Курс Frontend від Mate academy.
Frontend розробник може легко створити сторінки вебсайту чи вебдодаток. Тому після курсу ви станете затребуваним фахівцем у сфері, що розвивається.
Інформація про курс

Цели и средства

Винды — отстой для дурака, а если не пуста башка,
Hужна командная строка!
Плесни пивка!
Юрий Нестеренко

В выборе средств, "естественно" (до чего скуден в выразительности
инструмент журнального слова…), вопросов не возникло — так как улучшенные
легально-бесплатные версии lex и yacc неотъемлемо присутствуют в любой Unix-подобной
системе, в этих же системах есть и весь мыслимый инструментальный набор, старенький
Celeron 300A в очередной раз начал отсчитывать время по "Unix-календарю"
FreeBSD.

А вот цели… По сути, без учета нюансов, важнейший "функциональный узел"
процедуры трансляции очень прост и базируется на абстракции детерминированного
конечного автомата (ДКА).

ДКА в "трансляторном" контексте — это распознаватель так называемых
регулярных множеств — цепочек символов, соответствующих регулярным выражениям,
о чем мы уже неоднократно говорили (здесь и далее читатель может попробовать
отыскать выделенные курсивом словосочетания и фразы, например с помощью Google
для получения расширенной информации и точных определений). Обычно ДКА представляются
направленным графом, отражающим процесс распознавания цепочек символов, — каждый
путь в графе соответствует допустимому регулярному множеству и приводит к вершине
(узлу, иначе — состоянию), в которой задачу распознавания можно считать решенной.

Курс Frontend від Mate academy.
Frontend розробник може легко створити сторінки вебсайту чи вебдодаток. Тому після курсу ви станете затребуваним фахівцем у сфері, що розвивається.
Інформація про курс

Путешествия дилетанта (не (с)только о трансляторах)

Интегрированная среда GoldParser
Builder в работе: правое окно — встроенный текстовый редактор для подготовки
описания транслируемого языка (ДКА лексического разбора и грамматики), слева —
окно встроенного отладчика, в данный момент отображающее результат разбора тестового
фрагмента С-подобного языка

Простая абстракция ДКА сильна именно своей простотой и достаточной для решения
целого класса различных задач эффективностью своих "овеществлений".
Так, в общем случае и первый элемент любого транслятора (первый — в последовательности
функциональных узлов, обрабатывающих поток данных) — препроцессор, и второй
элемент — лексический анализатор, и наконец, — "сердце транслятора",
программа синтаксического разбора, строятся именно на основе реализации ДКА.
Препроцессор с помощью ДКА преобразует подаваемый на его вход текст, обычно
заменяя фрагменты текста, распознаваемые ДКА, их эквивалентами. Лексический
анализатор "отыскивает" (распознает) в тексте лексические элементы
(лексемы), в общем случае относящиеся ко множеству классов, — например,
целые, действительные и т. д. числа, имена (идентификаторы), строки, ключевые
слова языка. Обычно на этапе лексического анализа распознанные последовательности
символов, относящихся к разным классам, получают более удобную для дальнейшей
обработки компактную форму представления, отражающую и принадлежность к классу,
и уникальность лексического элемента — на последующих этапах не слишком приятно
и эффективно оперировать множеством строк переменной длины, каждый раз пытаясь
определить, "кто есть кто". В сущности, лексический анализатор трансформирует
поток символов, несущий скрытую информацию о принадлежности отдельных их подмножеств
к классам лексем, в поток описателей лексем с явно указанной этой информацией.
Третий этап трансляции выполняет синтаксический анализатор — он также фактически
использует абстракцию ДКА, но для распознавания допустимых в языке выражений
(о грамматиках и языках мы кратко говорили в давнишней, посвященной трансляторам
статье, поэтому здесь сконцентрируемся больше на "механике", обеспечивающей
овеществление теоретических построений). Результат работы синтаксического анализатора
— новая форма представления исходной (транслируемой) программы, позволяющая
автоматизировать ее трансформацию и полностью использовать априорные знания
о транслируемом языке — например, разбить более сложные выражения на элементарные
действия (вплоть до примитивных машинных команд), осуществить проверку правильности
применения данных разных типов в выражениях и многое другое — включая оптимизацию
(например, сокращение множества элементарных действий, необходимых для выполнения
выражения; нахождение и замена не зависящих от исполнения программы выражений,
т. е. выражений, результат вычисления которых не зависит от находящихся за их
пределами "факторов", предварительно вычисленными константами и т.
д.). О реализующих последние этапы трансляции функциональных узлах — генераторе
кода и оптимизаторе — достаточно сказать только, что они по сей день остаются
больше плодами искусства, чем науки. И все же есть ряд инструментальных средств,
облегчающих и их создание, и эти средства, опять же, строятся с использованием
абстракции ДКА. Но настала пора вернуться от этого экскурса к частному примеру…

"Штатная" в Unix и Unix-подобных операционных системах инструментальная
утилита lex (или flex) предназначена для избавления программиста от необходимости
написания всей программы лексического разбора "вручную". Более точно
можно сказать, что lex — это транслятор, трансформирующий описание задачи,
сформулированной на собственном языке lex, в исходные тексты программы на языке
С, реализующей решение задачи лексического распознавания. "Продукция"
lex — файл с именем lex.yy.c и находящаяся в нем самая главная функция — yylex(),
вызов которой является, по сути, единственным интерфейсом программы, реализующей
ДКА-распознаватель. В нашем повествовании, в принципе, главным будет не рассказ
о lex (об этой утилите написано море литературы — например, очень неплохая
и краткая статья В. А. Серебрякова, основанная на конспекте лекций факультета
вычислительной математики и кибернетики МГУ: www.codenet.ru/progr/compil/cons/001.php),
а принятие к сведению нескольких важных архитектурных нюансов "производимой"
lex "продукции". Во-первых, lex требует знания и использования в процессе
разработки "еще одного языка" — собственного языка описания задачи
для генерации С-кода ДКА-распознавателя. Не будем даже пытаться судить — хорошо
это или плохо (тем более, что язык lex крайне прост и для знающих синтаксис
регулярных выражений программистов никаких сложностей не представляет), просто
отметим это как факт. Во-вторых, созданный lex распознаватель имеет единственный
программный интерфейс (функция yylex()), что приводит к необходимости интенсивно
использовать глобальные переменные для передачи дополнительной информации в
вызывающую программу.

Второй элемент инструментальной архитектуры — yacc, генератор программ (с приставкой
"еще один" — Yet Another… в первых буквах аббревиатуры названия)
синтаксического разбора. С приземленной точки зрения программиста он совершенно
идентичен lex — это тоже транслятор "еще еще одного языка" в программу
на С. У этой программы также весьма скромный интерфейсный набор — фактически
только вызов функции yyparse() (скрывающий реализацию собственно механизма синтаксического
разбора) и переопределяемая программистом функция yyerror() — реакция на ошибки.
Язык, воспринимаемый yacc, сравнительно несложен, но требует знания хотя бы
основ формальных грамматик. Опять же, в тонкости реализации механизма трансляции
мы вдаваться не будем — yacc также обласкан вниманием технических писателей,
и информации, более чем пригодной для самостоятельного изучения, о нем предостаточно.
Нам же, кроме приведенных выше нюансов, остается указать еще одно свойство yacc
— взаимосвязь его входного языка с входным языком lex, так как обе инструментальные
утилиты играют роль тандема в построении транслятора и автоматизируют создание
двух его взаимозависимых функциональных узлов. Соответственно, при разработке
транслятора с некоторого языка, постановки задач для lex и yacc должны быть
согласованы. Обычно в качестве инструмента, играющего такую интегративную роль,
в Unix-подобных системах применяется утилита make, добавляющая к перечню "еще
еще еще один язык", но, при хорошем знании этого языка, действительно предоставляющая
программисту весьма серьезные возможности. Итак, в задании make (одном текстовом
файле) собираются воедино задания для lex, yacc и, наконец, — для транслятора
С, что позволяет получить исполняемый файл разрабатываемого транслятора.

Волшебные отвертки (недетская сказка)

Конечно, я вам скажу, это только игрушка. Но мыслям дает

правильное направление, а?
Джордж Оруэлл

Интересно, кто-нибудь уже слышал сказку о волшебных отвертках? Об отвертках,
которыми что ни скручивай, как ни закручивай, всегда, в конце концов, получится
табуретка. И не просто "табуретка вообще", а вполне такая себе совершенно
конкретная табуретка с четырьмя ножками, с сиденьем строго определенной формы,
с планками-распорками, соединяющими ножки. И долго многие добры молодцы пытались
сделать велосипед, а как волшебной отверткой (ну, тогда они еще не знали, что
отвертка-то волшебная) закрутят пару винтиков — так сразу табуретка и получается.
Но со временем добры молодцы задумались: "А не в отвертках ли дело?".

Несколько неожиданное отступление, естественно, не случайно, как и не случайно
упоминание в "сказке" велосипеда. И вот почему…


Путешествия дилетанта (не (с)только о трансляторах)

Расширенная отладочная информация
— сведения о действиях "сердца" транслятора — компоненты разбора

Создававшийся для развлечения транслятор (фактически — развитый макроассемблер)
— вещица совершенно игрушечная, сущая безделица. Но вот "возня" с
lex и yacc в данном случае действительно дала мыслям правильное направление.
С одной стороны, язык С, который генерируется этими утилитами, не слишком уж
удобен для обработки строк — факт общепризнанный. А даже в потешном трансляторе
потребность в мощных (и, что главное, достаточно безопасных) средствах обработки
строковых данных очень высока. Если добавить к этому очевидное соображение,
что от потешного транслятора, да еще генерирующего код для четырехбитного процессора,
быстродействия никакого не требуется (что задача трансляции будет выполняться
0,005 с, что 3 мин — совершенно все равно), логично было бы использовать возможности
созданного lex- и yacc-кода в "облатке" какого-нибудь скриптового
языка, у которого несоизмеримо более удобные механизмы работы со строками. А
не тут-то было — потому как уже созданный "как бы велосипед" под
таким углом зрения, оказывается, выглядит… да-да, именно "табуреткой".
И стоит двумя "волшебными отвертками" lex и yacc закрутить пару винтов
(т. е. сгенерировать две программки разбора), как "табуретка" обретет
форму раз и навсегда. А ведь хотелось велосипед…

Пора, наконец, от притч перейти к вещам более практического характера. Как уже
упоминалось ранее, сгенерированный lex программный модуль имеет одну интерфейсную
функцию (yylex) и задействует для передачи данных глобальные переменные. Для
того чтобы использовать ресурсы, предоставляемые этими интерфейсами из скриптового
языка, необходимо применение жутковатых по сложности и сомнительных в надежности
реализаций так называемого механизма FFI (Foreign Functions Interface) — "интерфейса
чужеродных функций". Разработка методом быстрого прототипирования (единственно
разумная в данном случае) превращается в "веселый кошмар" изучения
M вариантов (N+1)-го инструментального средства, выбора из них одного приемлемого,
и потому совершенно теряет привлекательность.

Теперь, возвращаясь к упомянутой "конкретной табуретке", можно четко
очертить ее контуры — lex и yacc жестко (или жестоко?) ограничивают перечень
архитектурных приемов, которые допустимо использовать в проектируемой программе
данного класса, оставляя разработчику фактически один-единственный вариант —
монолитная программа на С (несущественной вариацией его является "монолитная
программа на С++ с использованием С-подпрограмм). Что, опять же, в общем случае,
не хорошо и не плохо — это просто факт. Для преодоления такого ограничения
требуется использовать слишком сложные механизмы (частично или в целом — платформенно-зависимые,
как FFI). Но, что особенно неприятно, — и структурирование возвращаемых данных,
и применение "нечестных приемов" (по классике, использование глобальных
переменных в качестве интерфейсов — очень плохой стиль) — все это не
позволяет красиво и эффективно утилизировать в разработке достоинства общесистемной
архитектуры "родной" для этих утилит платформы Unix. Наверное, можно
придумать и реализовать протокол обмена, позволяющий передавать через "трубу"-pipe
содержимое и глобальных переменных, и параметры/результаты вызова интерфейсных
функций программ, сгенерированных lex и yacc, но назвать красивой реализацию
такого, мягко говоря, извращения язык не поворачивается. А вот что действительно
совсем неприятно — практически все перечисленные в предыдущей, посвященной
трансляторам, статье инструментальные средства в той или иной мере страдают
симптомом "волшебной отвертки" — все они навязывают разработчику
единственную жесткую архитектурную модель. Справедливости ради стоит сказать,
что крайний случай этого симптома, воплощенный в коде системы Gentle, является,
по крайней мере, оправданным — ведь в данном случае один инструмент применяется
для решения одной-единственной четко поставленной задачи — генерации полноценного
транслятора "от А до Я".

Проверим — а есть ли жизнь на Марсе..?

Красивая вещь, — признательно подхватил старьевщик. —
Но в наши дни мало кто ее оценит.
1984. Джордж Оруэлл

Конечно, "уткнувшись" в противоречия между навязываемыми двумя инструментами
ограничениями и требованиями, предъявляемыми к "процессу проектирования",
можно было воспользоваться каким-либо аналогом "парочки" lex и yacc,
изначально созданным на одном из скриптовых языков и… Но, во-первых, такой
подход оставил бы, по сути, ту же самую проблему нерешенной — только в ее формулировке
надо было бы заменить "монолитную программу на С" на "скрипт
на Python" или же — "скрипт на Ruby", а во-вторых, понимая "во-первых",
не хотелось тратить время на изучение "еще нескольких языков" только
для решения задачки-безделицы.

Вот так признанно "красивая вещь" — высокоуровневый транслятор, генерирующий
исходные тексты программ для класса задач, вещь, которой посвящено необъятное
количество строк высокохудожественных и высоконаучных текстов, для решения одной
конкретной потешной задачи при учете временных и прочих ограничений оказалась
очень неудобной. Возиться с С-кодированием метровых простыней-распечаток не
хотелось, да и не за чем было, учить и по ходу дела править какой-то полунедописанный
генератор кода в версии "0.07" — тоже. Могучие профессиональные инструменты
класса Gentle в этом случае явно избыточны, осталось все забросить и просто
вместо одного четырехбитного микроконтроллера баловаться с другим, для которого
есть что-то готовое. Как говорится, отрицательный результат — тоже результат,
а тема трансляторов и архитектурных "болячек" инструментальных генераторов
кода вполне заслуживает статьи. И все было бы так, опять же…


если бы не…

…третьим в этой компании оказался неизвестно откуда взявшийся
кот, громадный, как боров, черный, как сажа или грач, и с отчаянными кавалерийскими
усами.
Михаил Булгаков

В общем, охота — она пуще неволи. И пришлось немного потрудиться, поискать
такой заменитель пары lex-yacc, который бы даже на первый взгляд устранял указанное
выше ограничение. Третьим в этой компании оказался…

Вот тут-то и начинается упомянутая в начале статьи "альтернативность".
Не располагая никакими другими средствами разработки для ОС Windows, кроме бесплатной
среды скриптового языка Python (дистрибутив компании ActiveState) и встроенных
механизмов WSH (Windows Scripting Host), автор попытался отыскать аналог lex-yacc
именно для Windows — несмотря на то, что подавляющее большинство известных
инструментальных средств такого класса — выходцы из Unix-мира. "Именно
для Windows" в данном контексте означает, что разработка должна быть "родной"
для этой ОС, использующей на 100% общесистемную идеологию. Как ни "странно",
поиск длился всего минут десять—пятнадцать, и "неизвестно откуда взявшийся"
легально бесплатный GoldParser
моментально завоевал симпатии и стал одной из любимых программ для Windows.

В отличие от аналогичных, соответствующих Unix-идеологии генераторов программ,
GoldParser не формирует исходных текстов — простота программ лексического и
синтаксического разбора позволяет реализовать их в виде неизменного базового
модуля (точнее, компонента), который реконфигурируется загружаемыми табличными
описаниями автоматов, осуществляющих процедуры разбора. При этом интерфейсы
компонента фиксированы, от анализируемого языка не зависят, а их перечень богаче,
чем у lex и yacc. Кроме собственно реконфигурируемого компонента программы разбора,
в состав дистрибутива GoldParser входит интегрированная среда разработки и тестирования
ДКА и грамматик, позволяющая быстро и безболезненно "выпекать" файлы
конфигурации компонента — это, по сути, аналог входных языков lex и yacc, объединенных
языком make. GoldParser очень неплохо документирован и для освоения его требуется
буквально несколько часов (естественно, подразумеваются предварительное знакомство
с предметом и знание, например, тех же lex-yacc). Поэтому мы обойдемся без загромождающих
деталей, а остановимся на все тех же архитектурных нюансах.

Компонентный характер GoldParser (более точно — здесь идет речь об ActiveX-компоненте)
в данном случае означает устранение требования монолитности конечного продукта.
Казалось бы, это всего лишь "модные слова", но в реальной, даже потешной
разработке они сэкономили кучу времени. "Возня" с lex-yacc вынуждала
с регулярностью часового механизма проводить рекомпиляции сгенерированных программ
разбора при малейшем изменении описывающих создаваемый С-подобный ассемблер
входных файлов этих программ. Затем надо было собрать с помощью редактора связей
собственно "транслятор", погонять его через отладчик, убедиться, что
где-то в грамматике допущена ошибка, повторить весь цикл. Такой неизбежный процесс
(он — следствие той самой "табуретки", о которой говорилось ранее)
усложняется интерференцией результатов между метаошибками (ошибками в надъязыке
— описании грамматики) и просто ошибками в коде программы — за счет переноса
ошибок грамматики в код (именно он — продукт lex и yacc). GoldParser же позволил
практически полностью исключить последний фактор — здесь мухи и котлеты получились
отдельно (ну, вообще-то, мух как раз и не было благодаря интерактивному отладчику
грамматик программы GoldParser Builder), а компонентный характер самой программы
разбора позволил буквально за 20 минут набросать "облатку" на Python,
реализующую примерно 80% требуемой функциональности. Впоследствии, при более
глубоком изучении GoldParser, были выявлены и дополнительные важные преимущества,
среди которых немаловажным является изначальная пригодность компонента разбора
к "перемалыванию" Unicode-текстов.

Впрочем, довольно заслуженных дифирамбов — сочетание GoldParser, WSH JavaScript
или Python и компонентной модели ActiveX, по личному мнению автора, безоговорочно
разгромило все, чем приходилось пользоваться.


И что?

Полученный вывод можно было бы считать тривиальным, если бы не несколько
связанных с ним "но", пусть также тривиальных, но не таких явных.
Во-первых, оказалось, что неоднократно подтвержденная масштабными проектами
(например, статья Брайана Кернигана: cm.bell-labs.com/cm/cs/who/bwk/workshop.ps.gz)
высокая эффективность гибридных программных разработок с моделью "скриптовая
оболочка — быстрые критические к производительности компоненты" при увеличении
возможностей компонентной среды становится еще выше. Во-вторых, что "не
Unix единым" может жить даже непрограммирующий программист — высококлассные
разработки есть для самых разных платформ. В-третьих (это самое неприятное),
активным участникам сообщества программистов открытых Unix-подобных систем,
борющимся за расширение областей применения любимых ОС, по-видимому, пора серьезно
задуматься о существенных реформах не столько безнадежно устаревших инструментальных
средств, сколько общесистемных концепций.

Продолжается конкурс авторов ИТС. Напиши статью о развитии игр, гейминг и игровые девайсы и выигрывай профессиональный игровой руль Logitech G923 Racing Wheel, или одну из низкопрофильных игровых клавиатур Logitech G815 LIGHTSYNC RGB Mechanical Gaming Keyboard!


Loading comments...

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам: