Нисходящий парсер LL, от CST до AST - PullRequest
0 голосов
/ 15 февраля 2019

В настоящее время я изучаю синтаксический анализ и, более конкретно, синтаксический анализ сверху вниз.

Я знаю терминологию и разницу с анализаторами LR снизу вверх, и поскольку анализаторы LL сверху вниз легчереализовать вручную, я с нетерпением жду, чтобы сделать свой собственный.

Я видел два вида подхода:

Меня больше интересует последнее, его мощность и исключение вызоварекурсияОднако я не понимаю, как построить AST из неявного дерева разбора.

Этот пример кода конечного автомата на основе стека показывает анализатор, анализирующий входной буфер, только даваяответ да / нет, если синтаксис принят.

Я слышал аннотации стека для построения AST, но не могу понять, как их реализовать.Может ли кто-нибудь обеспечить практическую реализацию такой техники?

Ответы [ 2 ]

0 голосов
/ 18 февраля 2019

«Сверху вниз» и «снизу вверх» - отличные описания двух стратегий синтаксического анализа, потому что они точно описывают, как будет построено синтаксическое дерево, если оно будет построено.(Вы также можете думать об этом как о порядке обхода неявного дерева разбора, но здесь мы на самом деле заинтересованы в реальных деревьях разбора.)

Кажется очевидным, что есть преимущество в построении дерева снизу вверх.Когда пришло время добавить узел в дерево, вы уже знаете его дочерние элементы.Вы можете построить узел полностью сформированным за одно (функциональное) действие.Вся дочерняя информация тут же ждет вас, поэтому вы можете добавить семантическую информацию в узел на основе семантической информации его дочерних элементов, даже используя дочерние элементы в порядке, отличном от слева направо.

В отличие от этого, анализатор сверху вниз создает узел без дочерних элементов, а затем должен по очереди добавить каждого дочернего элемента в уже созданный узел.Это конечно возможно, но это немного некрасиво.Кроме того, инкрементная природа конструктора узла означает, что семантическая информация, присоединенная к узлу, также должна вычисляться постепенно или откладываться до тех пор, пока узел не будет полностью построен.

Во многих отношениях это похоже на разницу междуоценка выражений, написанных в обратной польской записи (RPN), из выражений, написанных в (прямой) польской записи [Примечание 1].RPN был изобретен именно для упрощения оценки, что возможно при простом стеке значений.Очевидно, что прямые польские выражения могут быть оценены: самый простой способ - использовать рекурсивный оценщик, но в средах, где на стек вызовов нельзя положиться, это можно сделать с помощью стека операторов, который эффективно превращает выражение в RPN наfly.

Так что это, вероятно, механизм выбора для построения синтаксических деревьев также из анализаторов сверху вниз.Мы добавляем маркер «сокращения» в конец каждой правой части.Так как маркер идет в конце правой части, поэтому он перемещается первым.

Нам также необходим стек значений для записи создаваемых узлов AST (или семантических значений).

В базовом алгоритме у нас теперь есть еще один случай.Мы начинаем с того, что поднимаем вершину стека анализатора, а затем исследуем этот объект:

  • Вершина стека анализатора была терминалом.Если текущим входным символом является тот же терминал, мы удаляем входной символ из ввода и помещаем его (или его семантическое значение) в стек значений.

  • Верх анализаторастек был маркером.Связанное действие сокращения запускается, что создаст новый узел AST, вытолкнув соответствующее количество значений из стека значений и объединив их в новый узел AST, который затем помещается в стек значений.(Как особый случай, действие маркера для уникального производства расширенного начального символа S' -> S $ приводит к тому, что анализ принимается, возвращая (только) значение в стеке значений как AST.)

  • Вершина стека синтаксического анализатора была нетерминальной.Затем мы определяем соответствующую правую сторону, используя текущий символ ввода, и помещаем эту правую сторону (справа налево) в стек синтаксического анализатора.

0 голосов
/ 15 февраля 2019

Вы должны понять концепцию позади.Вам необходимо понять концепцию автоматического нажатия.После того, как вы поймете, как выполнять вычисления на бумаге карандашом, вы сможете понять несколько способов реализации своей идеи, с помощью рекурсивного спуска или со стеком.Идеи те же, когда вы используете рекурсивный спуск, у вас неявно есть стек, который программа использует для выполнения, где данные выполнения объединяются с данными автомата синтаксического анализа.

Я предлагаю вам начать с преподаваемого курсаУльмана (автоматы) или Дика Груна, этот лучше всего ориентирован на разбор.(книга Груна эта ), ищите 2-е издание.

Для анализа LR необходимо понять идеи Эрли, из этих идей Дон Кнут создал метод LR,

Для анализа LL превосходна книга Груна, и Ульман представляет вычисление на бумаге, математический фон синтаксического анализа, который очень важен, чтобы знать, хотите ли вы реализовать свои собственные парсеры.

Что касается AST, это вывод парсинга.Парсер сгенерирует дерево синтаксического анализа, которое преобразуется в AST или может генерировать и выводить непосредственно AST.

...