Дерево грамматики

Question

У меня есть лаборатория в университете. Но я не понимаю, как я могу это сделать. У меня есть грамматика некоторого языка (например, грамматика арифметических выражений). Я должен построить дерево этой грамматики (я не знаю как). Тогда я должен определить, является ли входное предложение предложением этого языка? Как мне это сделать? Постскриптум Я прочитал несколько глав Книги Дракона, но я не нашел ничего, что мне нужно. P.P.S. Я не могу использовать lex / flex и yacc / bison.

---

РЕДАКТИРОВАТЬ Извините! Я должен быть более внимательным. Действительно, у меня есть грамматика, и я должен построить дерево, используя эту грамматику и входное предложение (я понимаю, как это сделать), если это возможно (в другом случае я должен показать сообщение об этом). Есть ли для этого простые для понимания алгоритмы? Я могу использовать грамматику любого простого языка, такого как арифметические выражения.

Answer 1

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

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

Для набора правил, подобного следующему:

(1) start: expression

(2) expression: expression '+' term
(3)           | expression '-' term
(4)           | term

(5) term: 'a'
(6)     | 'b'

Учитывая выражение a + b - a, вы бы пошли примерно так:

a.start (дано)
b.expression (1)
c.expression '-' term (3)
д.expression '-' 'a' (5)
e.expression '+' term '-' 'a' (2)
ф.term '+' term '-' 'a' (4)
г.'a' '+' term '-' 'a' (5)
ч.'a' '+' 'b' '-' 'a' (6)

Так вот, как вы делаете это по одному шагу за раз ... Теперь уловка в том, что вам нужно отслеживать все ваши вызовы правил.Итак, ваше настоящее дерево будет выглядеть примерно так:

                          start
                            | (b)
                        expression
                        /   |   \ (c)
               expression  '-'  term
                /  |  \ (e)       | (d)
       expression '+' term       'a'
           | (f)        | (h)
          term         'b'
           | (g)
          'a'

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

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

РЕДАКТИРОВАТЬ: Я перечислил все шаги выражения, используя строчные буквы выше, а затем показал, что каждый наборветви из дерева фактически соответствуют одному из приложений правил.Может или не может помочь.

Answer 2

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

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

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

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

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

Answer 3

Я бы хотел ответить на это, но на самом деле не хватает материала для работы - у меня остались следующие вопросы:

• Поскольку это университетская лаборатория, не так ли?сопроводительный учебный материал или занятия?Кроме того, сколько у вас есть времени?
• Что вы пробовали до сих пор?
• Можете ли вы жестко запрограммировать данную грамматику в вашу программу, или ваша программа должна быть в состоянии это сделать?читать любую грамматику из файла и строить из нее дерево разбора?
• Насколько сложны грамматики;а именно: являются ли они рекурсивными?
• Являются ли грамматические маркеры односимвольными или многосимвольными?

Редактировать: Принимая во внимание комментарий и обновленный вопрос: я думаю, что самый прямой-forward подход был бы парсером рекурсивного спуска, который строит дерево при совпадении входных данных.Ищите книгу Никлауса Вирта «Построение компилятора», которая была доступна в формате PDF в Интернете и которая описывает RDP для простого языка.

Основная идея синтаксического анализатора рекурсивного спуска заключается в том, что каждое правило вграмматика соответствует функции, и каждая функция проверяет следующий токен и вызывает соответствующую функцию анализа следующего нижнего уровня.Например, если в вашей грамматике есть правило

expression : constant '+' constant

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

void parseExpression() {
    parseConstant();
    Token token = peek_at_next_token();
    if (token == '+') {
        parseConstant();
        ... tree building code here ...
    }
    else
        throw ParseException("Expected '+', found "+token);
}

Но см. Также другие ответы на этот вопросвопрос.