Илья Бизяев, курс «Методы трансляции», ИТМО, 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]