Построение абстрактного синтаксического дерева со списком токенов

Question

Я хочу построить AST из списка токенов. Я делаю язык сценариев и уже выполнил часть лексического анализа, но не знаю, как создать AST. Итак, вопрос в том, как мне взять что-то вроде этого:

WORD, int
WORD, x
SYMBOL, =
NUMBER, 5
SYMBOL, ;

и преобразовать его в абстрактное синтаксическое дерево? Предпочтительно, я хотел бы сделать это без библиотеки, такой как ANTLR или чего-то еще, я бы предпочел сделать это с нуля сам. Однако, если это действительно сложная задача, я не против использования библиотеки:) Спасибо

Answer 1

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

На каждом последующем шаге есть возможность построить часть AST, комбинируя фрагменты AST, построенные на других пошаговых этапах. Это рекурсивная идея, и она сводится к созданию конечных узлов AST для токенов по мере их сканирования. Эта основная идея встречается практически во всех AST-сборочных парсерах.

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

Чтобы построить AST с синтаксическим анализатором рекурсивного спуска, нужно спроектировать эти процедуры так, чтобы они возвращали два значения: логическое "распознанное" и, если распознано, AST, построенное (как-то) для нетерминала. (Распространенным хаком является возврат указателя, который является недействительным для "не распознан", или указывает на созданный AST, если "распознан"). Способ создания результирующего AST для одной процедуры заключается в объединении AST из подпроцедур, которые он вызывает. Это довольно тривиально для листовых процедур, которые читают входной токен и могут сразу построить дерево.

Недостатком всего этого является то, что необходимо вручную закодировать рекурсивный спуск и дополнить его шагами построения дерева. По большому счету, это на самом деле довольно легко кодировать для маленьких грамматик.

Для примера OP предположим, что у нас есть эта грамматика:

GOAL = ASSIGNMENT 
ASSIGNMENT = LHS '=' RHS ';' 
LHS = IDENTIFIER 
RHS = IDENTIFIER | NUMBER

ОК, наш парсер рекурсивного спуска:

boolean parse_Goal()
{  if parse_Assignement()
   then return true
   else return false
}

boolean parse_Assignment()
{  if not Parse_LHS()
   then return false
   if not Parse_equalsign()
   then throw SyntaxError // because there are no viable alternatives from here
   if not Parse_RHS()
   then throw SyntaxError
   if not Parse_semicolon()
   the throw SyntaxError
   return true
}

boolean parse_LHS()
{  if parse_IDENTIFIER()
   then return true
   else return false
}

boolean parse_RHS()
{  if parse_IDENTIFIER()
   then return true
   if parse_NUMBER()
   then return true
   else return false
}

boolean parse_equalsign()
{  if TestInputAndAdvance("=")  // this can check for token instead
   then return true
   else return false
}

boolean parse_semicolon()
{  if TestInputAndAdvance(";")
   then return true
   else return false
}

boolean parse_IDENTIFIER()
{  if TestInputForIdentifier()
   then return true
   else return false
}

boolean parse_NUMBER()
{  if TestInputForNumber()
   then return true
   else return false
}

Теперь давайте пересмотрим его для построения абстрактного синтаксического дерева:

AST* parse_Goal() // note: we choose to return a null pointer for "false"
{  node = parse_Assignment()
   if node != NULL
   then return node
   else return NULL
}

AST* parse_Assignment()
{  LHSnode = Parse_LHS()
   if LHSnode == NULL
   then return NULL
   EqualNode = Parse_equalsign()
   if EqualNode == NULL
   then throw SyntaxError // because there are no viable alternatives from here
   RHSnode = Parse_RHS()
   if RHSnode == NULL
   then throw SyntaxError
   SemicolonNode = Parse_semicolon()
   if SemicolonNode == NULL
   the throw SyntaxError
   return makeASTNode(ASSIGNMENT,LHSNode,RHSNode)
}

AST* parse_LHS()
{  IdentifierNode = parse_IDENTIFIER()
   if node != NULL
   then return IdentifierNode
   else return NULL
}

AST* parse_RHS()
{  RHSnode = parse_IDENTIFIER()
   if RHSnode != null
   then return RHSnode
   RHSnode = parse_NUMBER()
   if RHSnode != null
   then return RHSnode
   else return NULL
}

AST* parse_equalsign()
{  if TestInputAndAdvance("=")  // this can check for token instead
   then return makeASTNode("=")
   else return NULL
}

AST* parse_semicolon()
{  if TestInputAndAdvance(";")
   then return makeASTNode(";")
   else return NULL
}

AST* parse_IDENTIFIER()
{  text = TestInputForIdentifier()
   if text != NULL
   then return makeASTNode("IDENTIFIER",text)
   else return NULL
}

AST* parse_NUMBER()
{  text = TestInputForNumber()
   if text != NULL
   then return makeASTNode("NUMBER",text)
   else return NULL
}

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

Инструменты генератора синтаксических анализаторов, такие как JavaCC и ANTLR, в основном генерируют синтаксические анализаторы с рекурсивным спуском и имеют средства для построения деревьев, которые работают очень похоже на это.

Инструменты генератора синтаксических анализаторов, которые создают анализаторы снизу вверх (YACC, Bison, GLR, ...), также создают узлы AST в том же стиле. Тем не менее, нет набора рекурсивных функций; вместо этого эти инструменты управляют стопкой видимых и преобразованных в нетерминалы токенов. Узлы AST построены на параллельном стеке; когда происходит уменьшение, узлы AST на части стека, покрытой сокращением, объединяются, чтобы создать нетерминальный узел AST для их замены. Это происходит с сегментами стека "нулевого размера" для правил грамматики, которые тоже пусты, в результате чего узлы AST (обычно для "пустого списка" или "отсутствующей опции"), по-видимому, появляются ниоткуда.

На битовых языках написание синтаксических анализаторов с рекурсивным спуском для построения деревьев довольно практично.

Проблема с реальными языками (будь то старые и седые, такие как COBOL, или горячие и блестящие, как Scala) заключается в том, что число правил грамматики довольно велико, осложнено изощренностью языка и требованием того, чтобы языковой комитет отвечал за него. постоянно добавлять новые вкусности, предлагаемые другими языками ("зависть к языку", см. эволюционную гонку между Java, C# и C++). Теперь написание синтаксического анализатора с рекурсивным спуском выходит из-под контроля, и каждый стремится использовать генераторы синтаксического анализатора. Но даже с генератором синтаксического анализатора написание всего пользовательского кода для сборки узлов AST также является большой битвой (и мы не обсуждали, что нужно для разработки хорошего "абстрактного" синтаксиса по сравнению с первым, что приходит на ум). Поддерживать правила грамматики и строить AST Goo становится все сложнее с масштабом и продолжающейся эволюцией. (Если ваш язык успешен, в течение года вы захотите изменить его). Так что даже написание правил построения AST становится неловким.

В идеале нужно просто написать грамматику и получить синтаксический анализатор и дерево. Вы можете сделать это с некоторыми недавними генераторами синтаксических анализаторов: Наш DMS Software Reengineering Toolkit принимает полностью контекстно-свободные грамматики и автоматически создает AST, никакой работы со стороны программиста грамматики; это делается с 1995 года. Ребята из ANTLR наконец-то поняли это в 2014 году, и теперь ANTLR4 предлагает такую ​​опцию.

Последний пункт: наличие парсера (даже с AST) вряд ли является решением реальной проблемы, которую вы намеревались решить, какой бы она ни была. Это всего лишь фундаментальный элемент, и, к большому удивлению большинства новичков в парсере, это самая маленькая часть инструмента, который манипулирует кодом. Google мое эссе о жизни после разбора (или проверить мою биографию) для более подробной информации.

Answer 2

Это совсем не сложно; на самом деле, это одна из самых простых вещей, которые я сделал. Общая идея заключается в том, что каждая структура (или правила синтаксического анализа) - это просто список других структур, и когда вызывается функция parse(), они просто перебирают своих потомков и просят их проанализировать. Это не бесконечный цикл; токены являются структурами, и когда вызывается их parse(), они сканируют вывод лексера. У них также должно быть имя для идентификации, но это не обязательно. parse() обычно возвращает дерево разбора. Разобрать деревья просто как структуры - списки детей. Также хорошо иметь поле "текст" и его родительскую структуру для идентификации. Вот пример (вы бы хотели организовать его лучше и обработать ноль для реальных проектов):

public void push(ParseTree tree) { // ParseTree
    children.add(tree);
    text += tree.text;
}

public ParseTree parse() { // Structure
    ParseTree tree = new ParseTree(this);
    for(Structure st: children) {
        tree.push(st.parse());
    }
    return tree;
}

public ParseTree parse() { // Token
    if(!lexer.nextToken() || !matches(lexer.token))
        return null;
    ParseTree tree = new ParseTree(this);
    tree.text = lexer.token;
    return tree;
}

Там. Вызовите функцию parse() основной структуры, и вы получите AST. Конечно, это очень скромный пример, и он не будет работать из коробки. Также полезно иметь "модификаторы"; например, сопоставьте дочерний элемент 3 один или несколько раз, дочерний элемент 2 необязательный. Это также легко сделать; сохраните их в массиве того же размера, что и количество дочерних элементов, и при разборе проверьте его:

public void setModifier(int id, int mod) {
    mods[id] = mod;
}

public ParseTree parse() {
    ...
    ParseTree t;
    switch(mods[i]) {
        case 1: // Optional
            if((t = st.parse()) != null) tree.push(t);
        case 2: // Zero or more times
            while((t = st.parse()) != null) tree.push(t);
        ...
        default:
            tree.push(st.parse());
    }
    ...
}