Как анализатор саксофона проверяет соответствие dtd?

Question

У меня есть XML-файл и определен dtd. Насколько я понимаю, синтаксический анализатор обрабатывает события, а не хранит весь XML-документ (например, DOM) в памяти. Скажем, у меня есть xml-файл с объявлением вроде ... // здесь около 2 миллионов строк .. Итак, что в этом случае будет хранить саксо-парсер в памяти? Откуда он знает, что имя конечного тега будет иметь место? А теперь реальный вопрос, как парсер саксофона проверяется на dtd? Я не ищу подробное объяснение, а просто общую идею о том, как происходит проверка.

Answer 1

Обычно DTD преобразуется в набор автоматов конечного состояния - существует стандартный алгоритм для преобразования грамматики BNF в детерминированный FSA, который можно найти в учебниках по компилятору, таких как Aho и Ullmann.Это создаст один FSA для модели содержимого каждого элемента.Текущее состояние анализа / проверки, таким образом, представлено стеком, содержащим один FSA (с его текущим состоянием) для каждого открытого элемента.Когда синтаксический анализатор обнаруживает начальный тег, он проверяет, представляет ли этот начальный тег действительный переход в самом верхнем FSA, и изменяет текущее состояние в этом FSA, выполняя этот переход;он также добавляет новый FSA в стек, соответствующий FSA для модели содержимого нового элемента.Когда он видит конечный тег, он проверяет, является ли текущее состояние самого верхнего FSA конечным состоянием, и извлекает этот FSA из стека.