Все существующие программы. Часть 9

  Мы здесь, кажется, столкнулись с некоторой проблемой с производительностью. Мы можем напустить на этот код профайлер и в обычной ситуации я бы порекомендовал именно это. Но в этом случае давайте решим эту проблему аналитически. Предположим, что мы пытаемся решить эту задачу с нашей предыдущей грамматикой, скажем, S[6]. Помимо всего прочего, это требует от нас…

0

Все существующие программы. Часть 8

  Хорошо, давайте начнем с начала. Предположим, что у нас есть строка, которая содержит грамматику, уже переписанную в нашей «удобной» форме, которая содержит в точности два терма для каждого правила подстановки. Мы можем легко написать анализатор для разбора этой строки. Я создам ассоциативный массив, который будет содержать соответствие каждого правила со списком двухсимвольной подстановки. Итак,…

0

Все существующие программы. Часть 7

  Все, вроде бы идет нормально. У нас есть каркас рекурсивного решения для перебора всех строк некоторой грамматики, и оно кажется обоснованным. Давайте рассмотрим одну более сложную грамматику из предыдущего сообщения: DECL:  MODIFIER class ID BASE { } MODIFIER: NIL | public | internal BASE:  NIL | : ID ID: a | b | c…

0

Все существующие программы. Часть 6

  Работая над механизмом перечисления результатов работы различных грамматик мы столкнулись с проблемой, связанной с тем, что рекурсия не сводит задачу к задаче меньшего объема. Нам нужно найти способ свести задачу к меньшей задаче, при этом гарантируя, что перебираем все возможные программы, определенные некоторой грамматикой. Я уже говорил ранее, что существует два типа грамматик: неоднозначная…

0

Все существующие программы. Часть 5

В прошлый раз: Мы явно уменьшили задачу размером k, к нескольким задачам размера, меньшего, чем k-1, так что эта задача является отличным кандидатом для рекурсивного решения. Так ведь? Нет, не так. (Слово «явно» было предательским.) Вспомните о трех вещах, необходимых для рекурсивного решения. Во-первых, должен быть способ свести задачу некоторого размера к похожей задаче меньшего…

0

Все существующие программы. Часть 4

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

0

Все существующие программы. Часть 3

  Предположим, мы хотим написать грамматику для упрощенного объявления классов языка C#. Давайте предположим, что наш идентификатор состоит из одного символа, класс может быть открытым (public) или внутренним (internal) и что не существует вложенных или обобщенных типов, и также не существует членов. Как насчет такого? DECL:     MODIFIER class ID : ID { } MODIFIER: public…

0

Все существующие программы. Часть 2

Предположим мы хотим найти CFG для чисел и суммирования. Рассмотрим очень простую грамматику только с одним нетерминальным символом. Можно сказать, что выражением является либо число, либо сумма двух выражений: X: 1 | 2 | 3 | X + X Мы можем сделать следующий набор замен, каждый раз заменяя оставшийся крайний слева нетерминальный символ: X X…

0

Все существующие программы. Часть 1

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

0