Написать код для создания синтаксического дерева

Question

Этот вопрос был задан мне в интервью вопрос:

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

a+(b+c*(e/f)+d)*g 

Answer 1

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

Answer 2

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

В этом случае я бы сказал, что это хорошее упражнение, чтобы написать все это самостоятельно.

Начните с хорошего представления для самого дерева. Это будет выводиться на ваш алгоритм. Например, это может быть коллекция объектов, где один объект может представлять собой «ярлык», например a, b и c в вашем примере. Другие могут представлять числа. Затем вы могли определить представление операторов, например + - это двоичный оператор, который имел бы два подобъекта, представляющих левое и правое подвыражение.

Следующий шаг - это синтаксический анализатор, я бы предложил классический рекурсивный порядочный парсер. Один текст, описывающий это, и обеспечивает стандартную реализацию псевдокода, - это текст Theodore Norvell

Answer 3

Простой выход - преобразовать ваше выражение в постфиксную нотацию (abcef/* ++) &, а затем обратиться к ответу на этот вопрос (http://stackoverflow.com/questions/423898/postfix-notation-to-expression-tree) для преобразования выражения postfix в дерево.

Это то, что интервьюер ожидал :)

Answer 4

Начните с определения языка. Никто не может реализовать парсер или компилятор на языке, который не очень четко определен. Вы привести пример: «а + (B + C * (е/е) + г) * г», который должен вызвать следующие вопросы:

1. Является ли язык одно выражение, или может быть несколько операторов (отделяется ';' может быть?
2. Что означают символы 'a', 'b', ... 'g'? Это переменная? Каков синтаксис переменных? Является ли это C-подобной переменной или это один буквенно-цифровой символ, который может означать ваш пример.
3. В вашем примере есть 3 двоичных выражения. Это все? Поддерживает ли язык также «-». Поддерживает ли ваш язык логические и битовые операторы?
4. Имеет ли номер поддержки языка буквальный s? целое число? удваивать? Поддерживает ли язык строковые литералы? Вы цитируете строковые литералы?
5. Синтаксис для комментариев?
6. У какого оператора есть приоритет? Имеет ли оператор «*» приоритет над «+», как в примере? Проверяются ли операнды справа налево или слева направо?
7. Любая предварительная обработка?

Как только вы получите хорошее определение синтаксиса языка, начните с реализации токенизатора. Токенизатор получает поток символов и генерирует список токенов.В приведенном выше примере каждый символ является токеном, но в var * 12 (var power 12) есть 3 жетона: 'var', ' *' и '12'. Если регулярное выражение разрешено, возможно, вы можете сделать эту часть синтаксического анализа с регулярными выражениями.

Далее, функция, которая идентифицирует каждый токен по типу: является ли он оператором, является ли это переменной, литералом числа, строковым литералом и т. Д. Пакет все в методе NextToken, который возвращает токен и его тип.

И наконец, начните синтаксический анализ. В вашем примере выше корень дерева синтаксического анализа будет узлом с оператором «+» (который имеет приоритет над «»). Левый дочерний элемент является переменным токеном «a», а правый дочерний элемент - деревом с корневым элементом «токен». Работайте рекурсивно.