Skip to content

Latest commit

 

History

History
121 lines (99 loc) · 9.07 KB

README.md

File metadata and controls

121 lines (99 loc) · 9.07 KB

Лабораторная работа №2. Ручное построение нисходящих синтаксических анализаторов.

Вариант 9. Описание массивов в Паскале

Илья Бизяев, курс «Методы трансляции», ИТМО, 2019

Формулировка задания

Массив в Pascal. Заголовок начинается ключевым словом var, далее идёт имя массива, двоеточие, ключевое слово array, далее описание диапазона индексов, затем of и имя типа. Диапазон индексов представляет собой две границы, между которыми две точки.
Используйте один терминал для всех имен переменных и имен типов. Используйте один терминал для ключевого слов var и array (не несколько v, a, r).
Пример: var x: array [1..10] of integer;

Грамматика

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

Нетерминал Описание
S -> V X : A [D] O T; Массив в Pascal состоит из V — ключевого слова var, X — имени массива, далее : и A - array, D — списка диапазонов значений индексов, заключённого в квадратные скобки, O — of, T — типа элементов в массиве, ;.
D -> D,D or R Массив может быть n-мерным, поэтому каждый список диапазонов может состоять из двух, разделённых запятой, или же являться одним диапазоном R.
R -> N..N or T Диапазон индексов состоит из двух чисел N, разделённых двумя точками, либо одного названия типа (идентификатора).
X -> X,X or id Объявление массивов может состоять из одного или нескольких имён, имя каждого — идентификатор.
T -> id По условию для имён массивов и имен типов используется один терминал — идентификатор.
N -> number У чисел свой идентификатор, чтобы отличать их от имён.

Для построения нисходящего парсера без возврата требуется LL(1)-грамматика, а выбранная грамматика в силу наличия левой рекурсии и правого ветвления таковой не является. Устраним левую рекурсию и правое ветвление в правилах для D и X, используя соответствующие алгоритмы.
Получится грамматика:

Нетерминал Описание
S -> V X : A [D] O T; Описание массива в Pascal
D -> RD'' Список диапазонов индексов
R -> N..N or T Один диапазон
D''-> D' Продолжение списка диапазонов
D''-> ε Конец списка диапазонов
D' -> ,DP Описание нового диапазона индексов
P -> D' Продолжение нового диапазона
P -> ε Конец списка
X -> idX'' Список имён массивов
X''-> X' Продолжение списка имён массивов
X''-> ε Конец списка имён массивов
X' -> ,XY Описание нового имени элемента в списке имён
Y -> X' Новый элемент списка имён
Y -> ε Конец списка имён
T -> id Тип элементов массива
N -> number Числовая граница индексов массива

Лексический анализатор

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

Терминал Токен
<id> Id
<number> Number
var Var
: Colon
array Array
[ OpenSBracket
.. DoubleDot
, Comma
] CloseSBracket
of Of
; Semicolon
ε Epsilon
$ Eof

Синтаксический анализатор

Для написания парсера нам требуется построить множества FIRST и FOLLOW для нетерминалов нашей грамматики:

FIRST FOLLOW
S var $
D n ],,
D' , ],,
D'' ε,, ],,
R n ,,]
P ε,, ],,
X <id> :,,
X' , :,,
X'' ε,, :,,
Y ε,, :,,
T <id> ;
N <number> .,,,]

Визуализация дерева разбора

Построенные деревья разбора можно представлять графически, например, сохраняя их в формате Dot (Graphviz) и конвертируя в векторные файлы SVG. Пример дерева

Набор тестов

Тесты для лексического и синтаксического анализаторов написаны с использованием встроенных средств тестирования языка Rust; краткое описание тестов обозначено в названиях тестовых функций.

Сборка и использование программы

Структура программы

  • main.rs — точка входа программы. Принимает на стандартный ввод выражение для разбора, выводит в стандартный вывод дерево разбора в формате Dot (Graphviz).
  • lexer.rs — лексический анализатор.
  • parser.rs — синтаксический анализатор.
  • lexer/tests.rs, parser/tests.rs — тесты.

Зависимости
Решение использует только стандартную библиотеку Rust и протестировано с rustc 1.39.0.

Команды

  • Пример запуска решения:
    echo "var x: array [1..10] of integer;" | cargo run | dot -Tsvg > test.svg
  • Запуск тестов:
    cargo test
  • Сборка без запуска:
    cargo build [--release]