программульки в персональной песочнице

home page compiler

© Dmitry Bodyonov, 2001.
# C++, yacc, lex. версия 0.11.2-fix2007.

Основные идеи и принципы

Изначально компилятор предназначался для трансляции XML-подобных документов в HTML-страницы, хотя реально формат итогового документа может быть практически любым, в том числе и бинарным.

Предполагается что исходные данные для компилятора представляются в некотором иерархическом виде (а так можно представить не всякие данные). Для описания данных используется SGML(XML)-подобный язык. В этом языке каждый описываемый элемент окружен специальными маркерами ‒ тегами ‒ заключенными в угловые скобки конструкциями. Один элемент данных может быть вложен в другой и таким образом задаются иерархические отношения между ними.

Рассмотрим пример:

<book>
  <title>  Красная Шапочка </title>
  <author> Ш. Перо  </author>

  <chapter>
    <title> Пирожки </title>

    шла Красная Шапочка к бабушке ...

  </chapter>

  <chapter>
    <title> У бабушки  </title>

    ....
    - А почему у тебя такие большие зубы?
    ....

  </chapter>
</book>
        

В примере задана книга (book), которая имеет: название (title), автора (author) и несколько глав (chapter). Каждая глава, в свою очередь также имеет название и содержит собственно текст книги.

Правила, по которым компилятор производит преобразования, хранятся не отдельно (как в случае с XML и XSL), а сами являются частью данных. В одном элементе могут содержаться вместе как данные так и инструкции. Более того, компилятор может на одном этапе генерации итогового документа обращаться к какому-то элементу данных именно как к данному, а на другом этапе ‒ как к инструкциям по трансляции.

В целом же процесс трансляции состоит из двух стадий:

Разбор исходных файлов и построение дерева.
Листы дерева могут содержать как просто данные так и команды (правила) по которым будет производится генерация итогового документа.
Генерация итогового документа.
Построение документа начинается с разбора некоторого "стартового" листа дерева (если не указано в опциях, то main). Если данный лист содержит команды, они будут выполнены, при этом, возможно, для получения результата будут использоваться данные с других листов этого дерева. Если эти листы, в свою очередь, также содержат в себе некоторые команды, они будут выполнены для чего могут быть использованы данные с других листов дерева и так далее ...

Рассмотрим такой исходный документ:

<main> $a + $b = $c </main>
<a> 2 </a>
<b> 3 </b>
<c> 5 </c>
        
При трансляции этого примера на первом этапе будет построено дерево:
                    
[Root] :
|
|--[main] : 
|   |--[_text] : $a + $b = $c 
|
|--[a] : 
|   |--[_text] : 2 
|
|--[b] : 
|   |--[_text] : 3 
|
|--[c] : 
|--[_text] : 5 
        

Второй этап компилятор начнет с раскрытия листа "main". В этом листе он встретит конструкции $a, $b, $c, которые являются командами. На место этих команд компилятор вставит значения листов a, b, c соответственно. Просто текст ‒ пробелы, символы '+' и '=' будут добавлены в результат как есть. В итоге документ будет таким:

2  + 3  = 5 
Листы a,b,c также могли содержать команды, и если бы лист c был определен так:
<c> $b + $a </c>
то документ получился бы таким:
2 + 3 = 3 + 2

Язык описания данных

Для описания данных используется язык похожий на SGML(XML). Для определения элементов данных используются теги, один элемент может быть вложен в другой и теоретически ограничений на уровень вложенности нет.

Существуют несколько видов тегов:

одиночные
Такие теги имеют вид:
<TagName [options] />
<TagName [options] ?>
<?TagName [options] ?>
<!TagName [options] >
          
парные

Элемент начинается открывающим тэгом, заканчивается закрывающим тэгом. Текст между двумя тэгами может содержать определения для вложенных элементов данных.

<TagName [options]>
TEXT        
</TagName>
          
парные специальные

Элемент начинается открывающим тэгом, заканчивается закрывающим тэгом.

         
<TagName [options] #>
TEXT
<#TagName>
            
Транслятор не разбирает текст между двумя такими тэгами и сохраняет его в дереве "как есть", следовательно, такой элемент не может содержать определения для вложенных элементов данных.

парные ленивые

Элемент данных также окружен открывающим и закрывающим тегами:

        
<Tagname [options] %>
TEXT
<%Tagname>
            
При разборе подобного тега будет построено такое дерево, какое было построено, если бы каждая строка TEXT'а была заключена в тег Tagname, то есть
            
<a%>
1
2
3
<%a>
            
будет эквивалентно
<a> 1 </a>
<a> 2 </a>
<a> 3 </a>
            
Подобные теги удобно использовать для задания серии элементов данных, имеющих одно имя.

Имя тега ‒ последовательность латинских букв, цифр, и знаков: + - : @ _ $. В принципе, имя тега может содержать и другие символы (в том числе и пробелы), но тогда для его записи необходимо использовать кавычки.

Опции (еще их называют атрибутами тега), указанные внутри открывающего тега имеют вид:

OptionName
определяет опцию у которой нет значения
OptionName = Value
определяет опцию со значением Value
Для имени опции можно использовать те же символы что и для имени тега. Если значение опции (Value) содержит пробелы, то нужно использовать кавычки.

Регистр символов в именах тегов и опций может учитываться, а может и не учитываться ‒ все зависит от параметров, указанных при компиляции и при запуске программы.

Комментарии в документе начинаются <!-- , и заканчиваются -->. Вложенные комментарии не допускаются.

Опции тега в дереве после разбора расположены так же как и вложенные элементы данных, то есть две следующие конструкции эквивалентны (iCV):

 <a> <b> This is b </b> </a> 
и
 <a b="This is b" /> 

В командной строке при вызове компилятора можно указать несколько входных файлов. Корневые вершины всех построенных деревьев объединяются и так формируется одно общее дерево, используемое далее.

Команды генерации документа

На втором этапе из сформированного дерева строится (генерируется) документ. Транслятор начинает генерацию документа с раскрытия стартового листа, если при этом он встретит команды, они будут исполнены, для чего возможно будут рекурсивно раскрываться и использоваться другие листы дерева.

Транслятор понимает следующие команды:

$ID

Раскрыть переменную (лист) с именем ID, например:

$a
вставить лист a.
$a.b
вставить лист b, который является потомком листа a.
$a.b{0}
вставить 1й лист с именем b, который является потомком листа a.
$a.{2}
вставить 2го потомка листа а, независимо от того как его зовут.
Можно указать параметры,которые будут использоваться при раскрытии вставляемого листа:
$ID [par1][par2][par3].....[parN]
В раскрываемом листе значения параметров можно получить используя специальные переменные: $1, $2, $3 .....

Рассмотрим пример (фрагмент дерева, $\n ‒ новая строка):

            
<b>
<a> This is a 1 ($1 $2 $3) </a>
<a> This is a 2 ($1 $2 $3) </a>
<a> This is a 3 ($1 $2 $3) </a>
</b>

<c#>
$\n $b.a{0}[x][y][z]
$\n $b.a{1}[z][x][y] 
$\n $b.a{2}[y][z][x] 
<#c>
          
При раскрытии листа c получим:
This is a 1 (x y z) 
This is a 2 (z x y) 
This is a 3 (y z x) 
          

Параметры при вызове передаются по значению, то есть при выполнении

 $a [$b] 
сначала будет раскрыт лист $b, а затем его значение будет передано в $a.

Если указанный лист не существует, то результатом раскрытия будет строка нулевой длины.

@ifdef [$ID] [Text_1] [Text_2]

Условный оператор: если лист $ID определен в дереве, то результатом команды будет Text_1, иначе ‒ Text_2. Текст может содержать как просто текст так и команды.

Данный условный оператор нельзя применять к специальным переменным используемым в трансляторе ‒ $0, $1 .... и $.

При выполнении команды всегда сначала раскрываются обе ветви (и Text_1, и Text_2), а только затем происходит проверка условия и формирование результата.

@notzero [Text] [Text_1] [Text_2]

Условный оператор: если Text имеет ненулевую длину, то результатом команды будет Text_1, иначе ‒ Text_2. Операнды могут содержать как просто текст так и любые команды.

Как и для команды @ifdef сначала раскрываются обе ветви условия (и Text_1, и Text_2), и только затем происходит проверка и формирование результата.

@each [$ID] [$oper]

Циклический оператор: для каждого листа с именем $ID будет выполнено раскрытие листа $oper. При этом, при раскрытии $oper будут определены переменные $. и $0. В $0 будет хранится имя (полное ‒ с индексами) для текущего значения $ID. Через $. можно доступ к потомкам листа $ID из $oper.

Например так можно распечатать список книг:

            
<main> 
  @each [$book] [$printbook] 
</main>

<printbook #>
  $.title
  $.author
<#printbook>

<book>
  <title> t_1 </title>
  <author> a_1 </author>
</book>

......

<book>
  <title> t_N </title>
  <author> a_N </author>
</book>
         

Возможно использование вложенных циклов, а также передача дополнительных параметров при вызове $oper.

В текущей версии программы (iCV) оба операнда @each обязательно должны быть листами дерева.

@count [$ID]
Результатом этой команды будет число листов с именем $ID, определенных в дереве. Так для предыдущего примера значение @count[$book] вероятно будет N.
@dochild [$id] [$oper]

Циклический оператор: для каждого потомка листа $ID будет выполнено раскрытие листа $oper. При этом, при раскрытии $oper будут определены переменные $. и $0. В $0 будет хранится имя (полное ‒ с индексами) для текущего значения $ID. Через $. можно доступ к потомкам листа $ID из $oper.

Возможно использование вложенных циклов, а также передача дополнительных параметров при вызове $oper.

В текущей версии программы (iCV) оба операнда @dochild обязательно должны быть листами дерева.

@for [Count] [$oper]
Циклический оператор: первый операнд будет трактоваться как число раз, которое нужно выполнить $oper. При раскрытии $oper значение специальной переменной $0 будет равно текущему значению счетчика.
@set [ $ID ] [Text2]

Установить значение для переменной (листа) ID равным Text2. Если переменная еще не определена, то она будет добавлена в корень дерева. Результат операции в документе ‒ строка нулевой длины.

Пример - присвоить листу a новое значение:

@set [$a] [ Today is @date ]

@add [Text1] [Text2] ; @minus [Text1] [Text2] ; @mply [Text1] [Text2] ; @div [Text1] [Text2]

Арифметические операции. Операнды трактуются как целые (iCV) числа над которыми производится действие. Результат операции в документе ‒ результат выполненного действия.

Примеры:

@add [1] [1]                ‒ 1+1, в документе - 2
@set [$a] [ @add[$a][1] ]   ‒ увеличить значение a на 1
@set [$c] [ @add[$a][$b] ]  ‒ значение c = a + b
          

@id [ IDNAME ]

Раскрывает лист с именем IDNAME. Имя переменной может быть сформировано "на лету", так конструкция

 @id [LIST@add[1][2]] 
раскроет лист LIST3. Если IDNAME ‒ это константная строка, то результат работы этой команды эквивалентен просто $IDNAME.

@name [$ID]
Возвращает имя листа, если параметр не указан, то возвращается имя листа на который указывает $0.
@asis [ IDNAME ]
Результатом работы данной команды в документе является значение листа IDNAME. Значение передается как есть ‒ даже если в листе имеются команды они не будут раскрываться.
@nodename [ IDNAME ]
Результатом работы данной команды в документе является имя листа IDNAME. (так как сам IDNAME может состоять и из индексов, например $a.{1}.b{2}.{3})
@eval [ TEXT ]

Выполняет код, который является результатом раскрытия TEXT.

Пример:

<a> 3 </a>
<b> 2 </b>
<c> @add[$a][$b] </c>
<d> @eval [ @asis [$c] > 4 ]  </d>
          
При раскрытии листа d будет получено:
 5 > 4 

Оператор eval можно использовать для реализации "настоящих" условных операторов: так как в операторах @ifdef и @notzero при любом иcходе _всегда_ сначала раскрываются обе ветви условия, то следующая конструкция будет бессмысленной:

@ifdef   [$a.b.c.d] 
         [ @set[$a][1] ] 
         [ @set[$a][2] ]
          
так как обе команды set будут выполнены еще до проверки условия. Выполнить же только одну команду можно применив оператор eval:
            
@eval [
  @ifdef  [$a.b.c.d] 
  [ $@set $[ $$a $] $[ 1 $] ] 
  [ $@set $[ $$a $] $[ 2 $] ]
]
          
Здесь операция @ifdef лишь генерирует текст команды, который необходимо выполнить, а выполнена команда будет уже операцией @eval. Так как генерируемый текст содержит специальные символы ($,@,[,]), то перед ними поставлен символ $.

@equal [i] [j]
Условный оператор, первые два операнда трактуются как целые числа (iCV), если они равны, то оператор вернет строку true, иначе ‒ пустую строку.
@equal [i] [j] [Then] [Else]
Второй вариант условного оператора, первые два операнда трактуются как целые числа (iCV), если они равны, то результатом будет текст Then, иначе Else.
@find [Sample] [Text]
Оператор ищет образец Sample в тексте TEXT. Если образец найден, оператор вернет строку true, иначе ‒ пустую строку.
@replace [Sample] [With] [Text]
Оператор заменяет все вхождения строки Sample в тексте TEXT на строки With. Оператор возвращает результат замены.
@print [TEXT]
Транслятор при выполнении данного оператора выведет в поток ошибок сообщение TEXT. Оператор возвращает пустую строку как результат.
@date
Вставить текущую дату.

Пример генерации документа

Рассмотрим такую задачу ‒ есть информация об оценках студентов. Необходимо сгенерировать html страницу на которой были бы все эти оценки. Также необходимо посчитать сумму оценок для каждого студента и по всей таблице целиком.

Пусть информация о студентах и их оценках описывается такой конструкцией:

<student>
  <name>  ИМЯ СТУДЕНТА </name>
  <marks> ОЦЕНКА 1 </marks>
  <marks> ОЦЕНКА 2 </marks>
  .........
  <marks> ОЦЕНКА N </marks>
</student>
    
Как было отмечено при описании языка входных файлов эту конструкцию можно переписать с использованием "ленивых" тегов:
<student>
  <name>  ИМЯ СТУДЕНТА </name>
  <marks %> 
    ОЦЕНКА 1 
    ОЦЕНКА 2 
    ...
    ОЦЕНКА N 
  <%marks>
</student>
    

Для решения поставленной задачи был написан следующий шаблон:

1:      <main> $MakePage </main>
2:
3:      <makepage #>
4:          <html>
5:          <body>
6:  
7:          <table border="1">
8:          <tr>
9:          <th> Имя </th>
10:         <th> Оценки </th>
11:         <th> Сумма </th>
12:         </tr>
13:     
14:         @each [$student] [$PrintStudent]
15:
16:         </table>
17:
18:         Итого: $Total
19:
20:         </body>
21:         </html>
22:     <#makepage>
23:
24:     <PrintStudent#>
25:
26:         @set[$Total.Local][0]
27:
28:         <tr>
29: 
30:         <td> $.Name </td>
31:
32:         <td> @each [$.marks][$PrintMarks] </td>
33:
34:         <td> $Total.Local </td>
35:         </tr>
36: 
37:     <#PrintStudent>
38:
39:     <Printmarks>
40:
41:         $.
42:         @set [$total.local] [ @add [$total.local][$.] ]
43:         @set [$total] [ @add [$total][$.] ]
44:
45:     </Printmarks>
46:
47:     <Total>
48:          0
49:         <Local> 0 </Local>
50:     </Total>
    
Необходимо дать некоторые пояснения к тексту шаблона:
строка 1
Определяется лист main, в котором есть единственная команда ‒ раскрыть лист MakePage.
строки 3‒22
Определяется элемент MakePage. Этот элемент не имеет потомков, но содержит фрагменты html кода, поэтому для определения этого элемента используются специальные парные теги, чтобы избежать разбора текста внутри этого элемента.
строки 4‒12
Вывод стандартного начала html страницы и вывод шапки у таблицы.
строка 14
Команда @each, которая для каждого листа Student раскрывает лист PrintStudent. Результат всех раскрытий будет вставлен в итоговый документ вместо команды.
строка 16‒21
Вывод стандартного окончания html таблицы и html страницы.
строки 24‒37

Определяется лист PrintStudent, который вызывается для каждого листа Student при раскрытии листа MakePage. При раскрытии этого листа должна быть определена специальная переменная $.. Через первую переменную можно получить доступ к листу для которого выполняется раскрытие, а также к потомкам этого листа.

Так же как и MakePage этот элемент не имеет потомков, но содержит фрагменты html кода (<tr>, <td> ...), поэтому чтобы не разбирать текст внутри элемента для его определения используются специальные парные теги.

строка 26
Листу Total.Local присваивается значение 0. В этом листе будет подсчитываться сумма оценок для каждого студента.
строка 30
Вывод ячейки с именем студента. Для получения доступа к потомку Name текущего листа используется специальная переменная $.
строка 32
Команда @each, которая для каждого листа Marks раскрывает лист PrintMarks. Результат всех раскрытий будет вставлен в итоговый документ вместо команды.
строка 34
Вывод ячейки с суммой оценок для данного студента. Сумма в листе $Total.Local была подсчитана при раскрытиях PrintMarks.
строки 39‒45
Определяется элемент PrintMarks.
строка 41
Вывод значения листа, для которого было вызвано раскрытие PrintMarks.
строка 42
Добавление этого значения к сумме оценок студента.
строка 43
Добавление этого значения к общей сумме оценок.
строки 47‒50
Определение элемента Total, который используется для вычисления общей суммы оценок по таблице. Этот элемент имеет потомка Local, который используется для вычисления суммы оценок для каждого студента.

Ниже приведен результат обработки некоторого исходного файла компилятором с использованием описанного шаблона:

Имя Оценки Сумма
Вася 5 5 10
Гриша 4 4 4 5 5 22
Петя 4 3 5 3 15
Миша 2 3 5
Катя 4 3 7
Аня 4 5 5 14
Таня 4 5 4 13
Итого: 86

Архитектура и программная реализация компилятора

Компилятор состоит из следующих модулей:

Tree ‒ структура дерево
Данный модуль отвечает за создание дерева, добавление новых узлов, обеспечение доступа к узлам.
x2tree ‒ парсер xml файлов
Этот модуль считывает исходные файлы в начале работы компилятора, разбирает их и заполняет дерево информацией.
tree2doc ‒ генератор документа
Данный модуль выполняет собственно генерацию документа, используя данные и инструкции из построенного дерева.

Компилятор написан на языке С++ с использованием standard template library (стандарта ANSI). Лексические и синтаксические анализаторы создавались при помощи систем yacc и lex.

Ослярик живёт здесь! [d!ë]