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

Ответ 1

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

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

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

Чтобы построить 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
}

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

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

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

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

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

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

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

Ответ 2

Это не сложно; на самом деле, это одна из самых простых вещей, которые я сделал. Общая идея состоит в том, что каждая структура (так называемые правила парсера) является всего лишь списком других структур, и когда вызывается функция 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;
}

Там. Вызвать основной синтаксический анализ(), и вы получили 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());
    }
    ...
}