Синтаксический разбор
1. Разбор последовательностей диапазонов страниц
Дана строка, содержащая последовательность диапазонов страниц либо отдельных страниц, разделенную запятыми.
Например: 1, 4-6, 9 , 10-15.
Требуется преобразовать строку в массив пар $(a, b)$, где $a$-$b$ – диапазон страниц (если $a = b$, то указана одна страница).
Процедура разбора состоит из двух этапов:
- лексический разбор – строка преобразуется в последовательность лексем: чисел, дефисов, запятых;
- синтаксический разбор – последовательность лексем преобразуется в искомый массив.
Разбор строки
На этапе лексического разбора последовательность символов преобразуется в последовательность элементов таких типов: число, запятая, дефис.
Далее происходит синтаксический разбор. Считаем, что обработчик на каждом шаге разбора находится в одном из нескольких состояний. Состояние определяет поведение обработчика при считывании очередного символа, а именно, в какое состояние будет произведен переход и какая функция для преобразования символов в другие данные будет вызвана.
Выделим следующие состояния обработчика (конечного детерминированного автомата):
- S - стартовое состояние, либо после запятой
- N - число после запятой либо в начале строки
- N- - число с дефисом
- N-N - число после дефиса
Автомат работает так:
(S, число) -> N
(S, ,) -> ошибка: лишняя запятая
(S, -) -> ошибка: лишний дефис
(N, число) -> ошибка: два числа разделены пробелами
(N, -) -> N-
(N, ,) -> S + вызов процедуры добавления нового диапазона в массив
(N-, число) -> N-N
(N-, -) -> ошибка: два дефиса подряд
(N-, ,) -> ошибка: запятая после дефиса
(N-N, число) -> ошибка: ожидалась запятая
(N-N, ,) -> S + вызов процедуры добавления нового диапазона в массив
(N-N, -) -> ошибка: число между двумя дефисами
Также следует рассмотреть поведение автомата, когда ему на вход поступает лексема “конец строки”.
2. Разбор арифметических выражений
Форма Бэкуса-Наура описывает процесс генерации строки по заданному набору правил синтаксического вывода. Этот процесс происходит так: символ, стоящий в левой части правила вывода, заменяется на цепочку (последовательность) символов, стоящую в правой части правила подстановки. При этом на каждом шаге генерации может быть выбрано любое из предложенных правил. По определению, правило подстановки имеет вид ${\tt u ::= x}$, где ${\tt u}$ – символ, ${\tt x}$ – непустая цепочка символов. Как нетрудно заметить, ${\tt u}$ – это левая часть правила, ${\tt x}$ – правая. Запись ${\tt a ::= x | y | z}$ является сокращенной записью 3-х правил подстановки ${\tt a ::= x, a ::= y, a ::= z}$.
Все символы, которые встречаются в левых и правых частях правил, образуют словарь $D$. Символы словаря, которые не встречаются в левых частях правил, называются терминальными и образуют алфавит $A$.
На входе мы получим строку из символов алфавита, и нам надо будет по этой строке восстановить структуру, в которой будут присутствовать понятия более высокого порядка, стоящие в левых частях правил подстановки.
Нисходящий (рекурсивный) разбор
Сформулируем алгоритм в абстрактных терминах.
На входе – $s \in A^*$, где $A = \mathbb N_0 \cup p_1 \cup p_3 \cup p_4 \cup { (, ) }$.
На выходе – $t \in {\rm Tree}\langle e \rangle$.
Определим функцию \({\rm parse\_expr}(s \in A^*;\; @k, j \in \mathbb N) \to t \in {\rm Tree}\langle e \rangle\), которая вычисляет синтаксическое дерево выражения, прочитанного из строки $s$, начиная с символа с номером $k$, если считать, что в строке записано выражение, которое представляет собой последовательность подвыражений, разделенных операциями с приоритетом не выше $j$ – фактически это синтаксический разбор относительно начального символа \({\tt \langle выражение{}_j\rangle}\).
При $j = 1, 3, 4$ функция \({\rm parse\_expr}\) вызовет саму себя для $j \leftarrow j - 1$.
При $j = 2$ функция \({\rm parse\_expr}\) проверит условие $s[j] = -$. Если оно выполняется, то работает синтаксическое правило
<выражение2> -> - <выражение1>
Иначе работает правило
<выражение2> -> <выражение1>
В первом случае функция вызывает саму себя для $j = 1$, $k \leftarrow k + 1$ и генерирует объект типа $e_2$ с полем ${\rm arg}$, равным результату рекурсивного вызова функции \({\rm parse\_expr}(s, 1, @k)\). Во втором случае функция вызывает саму себя для $j = 1$, $k$ и возвращает результат рекурсивного вызова.
При $j = 0$ функция проверяет, является ли $s[j]$ (лексема) числом или скобкой. В зависимости от этого работает одно из двух синтаксических правил:
<выражение0> -> число
<выражение0> -> ( <выражение4> )
В первом случае функция \({\rm parse\_expr}\) возвращает объект \(\{ {\rm num} = \text{число} \} \in e_0\). Во втором случае функция \({\rm parse\_expr}\) сдвигает курсор вправо \(k \leftarrow k + 1\) и производит рекурсивный вызов \({\rm parse\_expr}(s, 4, @k)\), после чего проверяет, что \(s[k] = \text{ )}\). Если да, то $k \leftarrow k + 1$. Если нет, то ошибка.