#2 Обзор частей интерпретатора

Этапы интерпретации исходного кода

1. Посимвольное чтение исходного кода;
2. Лексический анализ - на основе входящей последовательности символов выделяются "слова" языка;
3. Синтаксический анализ - входящая последовательность слов сопоставляется с правилами построения "предложений" на языке программирования и преобразуется в массив AST-деревьев (абстрактное синтаксическое дерево);
4. Выполнение (интерпретация) кода на основе массива AST-деревьев.

Каждому из этих этапов соответствуют определённые компоненты приложения.

Посимвольное чтение исходного кода (FileIO)

За чтение файла с исходным кодом отвечает класс FileIO , который опирается на стандартный модуль fs для работы с файловой системой. Класс реализует метод посимвольного чтения загруженного текста исходного кода.

В учебном проекте текст загружается из файла, но в действительности может быть получен "на лету" из текстовых полей, баз данных, текстового поля ввода и т.д. То есть сразу получен в виде некоторой строки, что не меняет сути дела.

Лексический анализ - выделение слов языка (LexicalAnalyzer)

Класс LexicalAnalyzer использует объект FileIO для посимвольного чтения.

LexicalAnalyzer реализует метод, сканирующий входную последовательность символов и возвращающий очередное "слово":

Cлово - неделимая с т.з. языка последовательность символов.

В случае, если встретился недопустимый символ, генерируется исключение с помощью оператора throw.

Кроме того, выполняется классификация встреченных слов по различным типам. Множество типов задаётся константным объектом SymbolsCodes:

Множество допустимых значений для каждого типа можно описать с помощью форм Бэкуса-Наура.

<Digit> ::= [0-9]
<integerConst> ::= "0" || ([1-9] <Digit>*)
<identifier> ::= [a-z]+
<plus> ::= "+"
<minus> ::= "-"
<slash> ::= "/"
<star> ::= "*"
<endOfLine> ::= #x000a

Классы Symbol и IntegerConstant

Если слово было успешно считано, то оно упаковывается в класс Symbol . Для чисел вместо Symbol используется IntegerConstant . Оба эти класса наследуются от класса SymbolBase:

Поля symbolCode и stringValue соответствуют типу слова и его представлению в виде последовательности символов. Поле value имеет смысл только для числовых констант.

Синтаксический анализ - разбор входящей последовательности слов и построение AST-деревьев (SyntaxAnalyzer)

ФБН для описания синтаксиса pascal.js-intro в стартовом состоянии приведены здесь.

За синтаксический анализ отвечает класс SyntaxAnalyzer, который использует объект LexicalAnalyzer для генерации последовательности слов языка для синтаксического разбора. В процессе синтаксического разбора входящая последовательность слов сопоставляется с набором правил синтаксиса языка программирования и преобразуется в AST-деревья, которые сохраняются в массив. Если в ходе синтаксического разбора обнаруживается, что тип очередного слова не соответствует ожидаемому типу, генерируется исключение с помощью оператора throw.

AST-Дерево

AST-дерево - это представление выражения (строки) исходного кода в виде структуры, удобной для последующей обработки.

Каждый узел дерева создаётся на основе очередного слова из входящей последовательности. Тип создаваемого узла определяетс согласно таблице 1.

Таблица 1. Тип слова -> тип узла дерева, созданного на основе слова

Перечисленные в таблице классы, описывающие узлы AST-дерева, наследуются от TreeNodeBase:

В свойстве symbol класса TreeNodeBase хранится объект класса Symbol (или IntegerConstant ), являющийся обёрткой для слова, на основе которого создан узел.

Классы Addition, Substraction, Multiplication, Division, соответствующие операциям сложения, вычитания, умножения и деления, наследуются от BinaryOperation:

То есть помимо свойства symbol, соответствующего знаку операции, объекты этих классов имеют свойства left и right - корни левого и правого поддеревьев.

Таким образом:

• Для каждой строки исходного кода строится бинарное дерево.
• Каждый узел дерева соответствует очередному слову из строки.
• Узел дерева может быть объектом одного из классов, перечисленных в таблице 1. Конкретный тип узла определяется типом соответствующего слова.
• Узлы, соответствующие числовым константам, являются листьями.
• Узлы, соответствующие бинарным операциям, имеют два потомка, соответствующие аргументам операции.

По правилам синтаксиса узлы, соответствующие операциям с более высоким приоритетом (*, /), могут быть потомками узлов, соответствующих операциям с более низким приоритетом (+, -), но не наоборот.

Алгоритм построения дерева по строке:

Тек. множитель = неопределено;
Тек. слагаемое = неопределено.

1. Читаем первое слово.
2. Текущее слово является числом?

    Нет: Ошибка.
    
    Да: 
        2.1 Создать узел, не имеющий потомков, на основе типа 'int'.
        2.2 Тек. множитель определен? 
            Нет: Тек. множитель = созданный узел.
            Да: Назначить созданный узел правым потомком текущего множителя.
        2.3 Прочитать следующее слово.
3. Текущее слово является знаком операции "*" или "/"?

    Нет: перейти к сл. пункту.

    Да: 
        3.1 Создать узел на основе типа 'star' или 'slash'.
        3.2 Назначить текущий множитель левым потомком созданного узла.
        3.3 Тек. множитель = созданный узел.
        3.4 Прочитать следующее слово.
        3.5 Перейти к п. 2
4. Текущее слово является знаком операции "+" или "-"?

    Нет: перейти к сл. пункту

    Да: 
        4.1 Создать узел на основе типа 'plus' или 'minus'.
        4.2 Текущее слагаемое определено?
            Нет: Текущее слагаемое = текущий множитель.
            Да: Назначить текущий множитель правым потомком текущего слагаемого.
        4.3. Назначить текущее слагаемое левым потомком созданного узла.
        4.4 Текущий множитель = неопределено.
        4.5 Текущее слагаемое = созданный узел.
        4.6 Прочитать следующее слово.
        4.7 Перейти к п. 2
5. Текущее слово соответствует концу строки?

    Нет: Ошибка.
 
    Да: Если текущее слагаемое определено, назначить текущий множитель правым потомком текущего слагаемого и вернуть тек. слагаемое в качетве корня результирующего AST-дерева. Иначе вернуть тек. множитель.

Пример
Дана строка:

4 + 12/4 + 11

1. ШАГ 1.
   

   Тек. множитель	Тек. слагаемое
   Неопределено	Неопределено

   Тек. слово: "4".

   Создаём узел:

   4

Текущий множитель = созданный узел.

2. Шаг 2.
   

   Тек. множитель	Тек. слагаемое
   4	Неопределено

   тек. слово: "+".

   Создаём узел:

   +

   Тек. слагаемое неопределено=> тек. слагаемое = тек. множитель = 4

   Назначаем тек. слагаемое левым потомком созданного узла:

       
       +
     /   \
    /     \
   4       ?

   тек. множитель = неопределено.
   тек. слагаемое = созданный узел.

3. Шаг 3.
   

   Тек. множитель	Тек. слагаемое
   Неопределено	+ / \ / \ 4 ?

   тек. слово: "12".

   Создаём узел:

   12

   Тек. множитель = 12.

4. Шаг 4.
   

   Тек. множитель	Тек. слагаемое
   12	+ / \ / \ 4 ?

   тек. слово: "/".

   Создаём узел:

   /

   Назначаем текущий множитель 12 левым потомком созданного узла:

    
   
        /
     /    \
    /      \
   12       ? 

   Текущий множитель = созданный узел.

5. Шаг 5.
   

   Тек. множитель	Тек. слагаемое
   / / \ / \ 12 ?	+ / \ / \ 4 ?

   тек. слово: "4"

   Создаём узел:

   4

   назначаем созданный узел правым потомком тек. множителя:

    
   
        /
     /    \
    /      \
   12       4 

6. Шаг 6.
   

   Тек. множитель	Тек. слагаемое
   / / \ / \ 12 4	+ / \ / \ 4 ?

   тек. слово: "+".

   Создаём узел:

   +

   назначаем текущий множитель правым потомком текущего слагаемого:

            +                              
          /   \                         
         /     \                       
        4       /                     
              /   \
             /     \
           12       4 
   

   .

   Назначаем текущее слагаемое левым потомком созданного узла:

                   +
                 /   \
               /       \
             /           \
            +             ?                  
          /   \                         
         /     \                       
        4       /                     
              /   \
             /     \
           12       4 
   

тек. множитель = неопределено
тек. слагаемое = созданный узел

7. Шаг 7.
   

   Тек. множитель	Тек. слагаемое
   Неопределено	+ / \ / \ / \ + ? / \ / \ 4 / / \ / \ 12 4

   тек. слово: "11"

   Создаём узел:

   11

   тек. множитель = созданный узел

8. Шаг 8.
   

   Тек. множитель	Тек. слагаемое
   11	+ / \ / \ / \ + ? / \ / \ 4 / / \ / \ 12 4

   тек. слово - конец строки.
   Назначаем тек. множитель правым потомком текущего слагаемого. Результирующее дерево:

                   +
                 /   \
               /       \
             /           \
            +            11                  
          /   \                         
         /     \                       
        4       /                     
              /   \
             /     \
           12       4 
   

Выполнение (интерпретация) кода - разбор AST-дерева (Engine)

Если на этапе синтаксического анализа не было обнаружено ошибок синтаксиса, то разобранные выражения в виде массива AST-деревьев передаются в конструктор класса Engine, который может работать с такими структурами и отвечает за выполнение программы. В данном классе реализован метод run(), который в цикле для каждого дерева вызвает методы обхода этого дерева и вычисления значения соответствующего выражения. Значения выражений записываются в массив results, который является свойством объекта Engine.

Как вычисляется значение выражения по дереву

Выполняется обратный обход дерева в глубину. Если очередной узел дерева является объектом класса NumberConstant (то есть является листом), то возвращается объект класса NumberVariable, которой представляет собой просто обёртку соответствующего числового значения.

Если же узел дерева является объектом класса, наследуемого от BinaryOperation, то сначала выполняются рекурсивные вызовы для левого, а затем для правого поддеревьев, возвращающие объекты класса NumberVariable. Выполняется соответствующая бинарная операция над распакованными значениями, и возвращется её результат, которой снова упаковывается в NumberVariable.

Класс PascalJs

является обёрткой для интерпретатора. Здесь реализован метод runFile(), который получает на вход путь к файлу с программой и реализует управление процессом интерпретации кода, выполняя последовательно шаги, описанные выше: чтение, лексический, синтаксический анализ и выполнение программы. Объект класса Enigine, выполнивший интерпретацию, сохраняется в свойстве engine класса PascalJs. Идея состоит в том, что объект PascalJs можем импортировать в другой проект для интерпретации кода.

Видео-материалы

• FileIO и общий обзор частей интерпретатора Pascal.js-intro
• Синтаксический анализатор в pascal.js-intro - пишем свой интерпретатор
• Синтаксический анализатор и построение дерева АСТ pascal.js-intro