Цели:
- Изучить и применить средство синтаксического анализа, которое поддерживает программный интерфейс, совместимый с языком Си, и параметризуется спецификацией, описывающей синтаксическую структуру разбираемого языка.
- Разработать модуль для разбора текста в соответствии с языком по варианту, используя выбранное средство синтаксического анализа.
- Построить синтаксическое дерево из исходного файла с текстом и вывести его в файл в формате, поддерживающем просмотр графического представления.
- Реализовать тестовую программу для демонстрации работоспособности созданного модуля.
- Представить результаты тестирования в виде отчета.
Задачи:
- Изучить выбранное средство синтаксического анализа, учитывая его требования к совместимости с языком Си, параметризации спецификацией синтаксической структуры разбираемого языка и возможности функционирования посредством кодогенерации и/или подключения необходимых для его работы дополнительных библиотек.
- Изучить синтаксис разбираемого по варианту языка и записать спецификацию для средства синтаксического анализа, включая конструкции подпрограмм со списком аргументов и возвращаемым значением, операции контроля потока управления, определения переменных, целочисленные, строковые и односимвольные литералы, выражения численной, битовой и логической арифметики, выражения над одномерными массивами и выражения вызова функции.
- Реализовать модуль, использующий средство синтаксического анализа для разбора языка по варианту. Этот модуль должен принимать строку с текстом и возвращать структуру, описывающую соответствующее дерево разбора и коллекцию сообщений об ошибке.
- Реализовать тестовую программу для демонстрации работоспособности созданного модуля. Программа должна принимать имя входного файла для чтения и анализа, имя выходного файла записи для дерева, описывающего синтаксическую структуру разобранного текста.
- Представить результаты тестирования в виде отчета.
Программа состоит из 3-х частей, лексера, парсера и клиентского драйвера. Реализованная программа способна воспринимать язык следующей грамматики
identifier: "[a-zA-Z_][a-zA-Z_0-9]*"; // идентификатор
str: "\"[^\"\\]*(?:\\.[^\"\\]*)*\""; // строка, окруженная двойными кавычками
char: "'[^']'";
// одиночный символ в одинарных кавычках
hex: "0[xX][0-9A-Fa-f]+";
// шестнадцатеричный литерал
bits: "0[bB][01]+";
// битовый литерал
dec: "[0-9]+";
// десятичный литерал
bool: 'true'|'false';
// булевский литерал
list<item>: (item (',' item)*)?; // список элементов, разделённых запятыми
source: sourceItem*;
typeRef: {
|builtin: 'bool'|'byte'|'int'|'uint'|'long'|'ulong'|'char'|'string';
|custom: identifier;
|array: typeRef '(' (',')* ')';
};
funcSignature: identifier '(' list<argDef> ')' ('as' typeRef)? {
argDef: identifier ('as' typeRef)?;
};
sourceItem: {
|funcDef: 'function' funcSignature (statement* 'end' 'function')?;
};
statement: {
|var: 'dim' list<identifier> 'as' typeRef;// for static typing
|if: 'if' expr 'then' statement* ('else' statement*)? 'end' 'if';
|while: 'while' expr statement* 'wend';
|do: 'do' statement* 'loop' ('while'|'until') expr;
|break: 'break';
|expression: expr ';';
};
expr: { // присваивание через '='
|binary: expr binOp expr; // где binOp - символ бинарного оператора
|unary: unOp expr; // где unOp - символ унарного оператора
|braces: '(' expr ')';
|callOrIndexer: expr '(' list<expr> ')';
|place: identifier;
|literal: bool|str|char|hex|bits|dec;
};
Результатом работы программы является построенное ast дерево, выводимое посредством символов в стандартный поток вывода, так же в случае ошибки разбора выводится сообщение об ошибке, с указанием места возникновения ошибке и причине.
function test2() as ulong
dim a,b as ulong
dim c as uint(,)
b = 0;
a = 1;
if a > b then
b = a;
end if
end function
./lab1 -f test.txt
func
func-sign
identifier [ident name: test2]
type-ref [type: ulong]
arg-def-list
statements-list
statement
ident_list
identifier [ident name: a]
type-ref [type: ulong]
ident_list
identifier [ident name: b]
type-ref [type: ulong]
statements-list
statement
ident_list
identifier [ident name: c]
type-ref [type: array]
array [dimensions: 1]
type-ref [type: uint]
statements-list
statement
binary-expression [type: =]
expression
identifier [ident name: b]
type-ref [type: none]
expression
literal [val: 0, type: dec]
statements-list
statement
binary-expression [type: =]
expression
identifier [ident name: a]
type-ref [type: none]
expression
literal [val: 1, type: dec]
statements-list
statement
branch
binary-expression [type: <]
expression
identifier [ident name: a]
type-ref [type: none]
expression
identifier [ident name: b]
type-ref [type: none]
statements-list
statement
binary-expression [type: =]
expression
identifier [ident name: b]
type-ref [type: none]
expression
identifier [ident name: a]
type-ref [type: none]
Пример выводаошибки в грамматике
syntax error, unexpected FUNCTION, expecting IF, location: linenum=8
err code=1
Flex (лексер) разбивает входной текст на набор токенов - базовых конструкций, которые передаются в Bison (парсер), который выполняет синтаксический анализ и для каждой языковой конструкции может выполнить любой прикладной код на C, в частности в ходе разбора строит AST дерево.
Стоит отметить что лексер и парсер в данной реализации генерируются функционально "чистыми" и реентерабельными, те не оперируют глобальным состоянием на этапе разбора как обычно бывает в стандартных случаях применения фреймворка flex+bison.
bison: %define api.pure full
flex: %option reentrant bison-bridge
Также было достигнуто разделение клиенского кода и кода сгенерированно лексером и парсером.
Также был реализован модуль текстового вывода полученного дерева, который обходит переданное ей дерево посредством обхода в глубину и выводит в стандартный поток вывода информацию об узлах.
Результатом лабораторной работы является программа, способная строить абстрактное синтакическое дерево по заданной вариантом грамматике.
https://docs.google.com/document/d/1QzIwLMW8o2Xe4hwct6BvpPO6aarYZ7ptjT-3fe-4ne8/edit?usp=sharing