Skip to content

Консольное приложение для построения AST по коду входной программы

Notifications You must be signed in to change notification settings

KuzmichevaKsenia/ast

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

1 Commit
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Компилятор, выполняющий построение абстрактного синтаксического дерева (AST) входной программы

БНФ реализуемого языка

<Программа> ::= <Список объявлений переменных> Begin <Список операторов> End
<Список объявлений переменных> ::= <Объявление переменных> | <Объявление переменных> <Список объявлений переменных>
<Объявление переменных> ::= Var <Список переменных> :Boolean; | Var <Список переменных> :Decimal;
<Список переменных> ::= <Идент> | <Идент>, <Список переменных>
<Идент> ::= <Буква><Идент> | <Буква>
<Список операторов> ::= <Оператор> | <Оператор> <Список операторов>
<Оператор> ::= <Присваивание> | <Цикл>
<Присваивание> ::= <Идент> = <Выражение>;
<Выражение> ::= <Выражение> <Бин.оп.> <Выражение> | ".NOT." <Выражение> | (<Выражение>) | <Идент> | <Const>
<Бин.оп.> ::= ".AND." | ".OR." | ".XOR." | "-" | "+" | "*" | "/" | ">" | "<" | "=="
<Const> ::= <BConst> | <DConst> 
<DConst>::= <Цифра> | <Цифра><DConst>
<BConst> ::= 0|1
<Цикл> ::= FOR <Идент> := <Выражение> TO <Выражение> DO <Оператор>

<Буква> – буква латинского алфавита (a...z).
<Цифра> – цифра от 0 до 9
Комментарии в стиле Паскаля:
{	Первая строка комментария.
 	Вторая строка комментария.
	Последняя строка комментария.	}

Список классов лексем реализуемого языка

  • Ключевые слова
    • Begin
    • End
    • Var
    • Boolean
    • Decimal
    • FOR
    • TO
    • DO
  • Математические операторы
    • -
    • +
    • *
    • /
  • Операторы сравнения
    • >
    • <
    • ==
  • Логические бинарные операторы
    • .AND.
    • .OR.
    • .XOR.
  • Операторы присваивания
    • :=
    • :
  • Разделители
    • ;
    • ,
  • Символы группировки
    • (
    • )
  • Логические унарные операторы
    • .NOT.
  • Идентификаторы
    • [a-zA-Z]+
  • Целочисленные константы
    • [0-9]+

Реализация

Программа написана на языке C. Функции определены в файле funcs.c, заголовочный файл – interface.h. Лексический анализатор на flex (файл lexer.l), синтаксический анализатор на bison (файл parser.y).

Для сборки проекта нужно запустить bash-скрипт ./build. При запуске программы ей в параметрах передается имя файла с текстом программы ./a.exe my_prog.

Примеры выполнения

Пример 1 - вывод AST корректно написанной программы

Var a, b: Decimal;
Var d: Boolean;
Begin
    a := 3 + 6 / 3;
    FOR b := 0 TO 5 DO a := a + b;
    {
        my
        comments
    }
    d := .NOT. (a > b);
End
prog
  |
  |-->(declars){}
  |        |
  |        |-[Decimal]->(var names){}
  |        |                  |
  |        |                  |-->(a){}
  |        |                  |
  |        |                  |-->(b){}
  |        |
  |        |-[Boolean]->(var names){}
  |                           |
  |                           |-->(d){}
  |
  |-->(stmts){}
          |
          |-->(:=){assignment}
          |     |
          |     |-[var]->(var){}
          |     |           |
          |     |           |-->(D){type}
          |     |           |
          |     |           |-->(a){name}
          |     |
          |     |-[exp]->(+){bin oper}
          |                |
          |                |-[left exp]->(3){const}
          |                |
          |                |-[right exp]->(/){bin oper}
          |                                 |
          |                                 |-[left exp]->(6){const}
          |                                 |
          |                                 |-[right exp]->(3){const}
          |
          |-->(loop){for}
          |      |
          |      |-[iter]->(){}
          |      |          |
          |      |          |-[iter var]->(var){}
          |      |          |                |
          |      |          |                |-->(D){type}
          |      |          |                |
          |      |          |                |-->(b){name}
          |      |          |
          |      |          |-[iter list]->(){}
          |      |                          |
          |      |                          |-[begin val]->(0){const}
          |      |                          |
          |      |                          |-[end val]->(5){const}
          |      |
          |      |-[stmt]->(:=){assignment}
          |                  |
          |                  |-[var]->(var){}
          |                  |           |
          |                  |           |-->(D){type}
          |                  |           |
          |                  |           |-->(a){name}
          |                  |
          |                  |-[exp]->(+){bin oper}
          |                             |
          |                             |-[left exp]->(var){}
          |                             |                |
          |                             |                |-->(D){type}
          |                             |                |
          |                             |                |-->(a){name}
          |                             |
          |                             |-[right exp]->(var){}
          |                                               |
          |                                               |-->(D){type}
          |                                               |
          |                                               |-->(b){name}
          |
          |-->(:=){assignment}
                |
                |-[var]->(var){}
                |           |
                |           |-->(B){type}
                |           |
                |           |-->(d){name}
                |
                |-[exp]->(!){un oper}
                           |
                           |-->(>){cmp oper}
                                 |
                                 |-[left exp]->(var){}
                                 |                |
                                 |                |-->(D){type}
                                 |                |
                                 |                |-->(a){name}
                                 |
                                 |-[right exp]->(var){}
                                                   |
                                                   |-->(D){type}
                                                   |
                                                   |-->(b){name}

Пример 2 - используется неправильный оператор присваивания, из-за чего сработал обработчик лексической ошибки

Var a: Boolean;
Begin
    a = 1; 
End
error in line 3: Mystery character '='

Пример 3 - пропущено присваеваемое значение, сработал обработчик синтаксической ошибки

Var a, b: Decimal;
Begin
    FOR a := TO 3 DO b := a;
End
error in line 3: iterator begin value missed

Пример 4 - не объявлена переменная, сработал обработчик синтаксической ошибки

Var a: Boolean;
Begin
    b := 0;
End
error in line 3: non declared var 'b'

About

Консольное приложение для построения AST по коду входной программы

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published