Идея разбора синтаксической диаграммы символов

Question

Люди, я реализую странную вещь, я должен написать утилиту для синтаксического анализа синтаксической диаграммы в простом текстовом формате и преобразования ее в формат xml, в принципе она такая же, как в IBM (как в «СозданиеЧасть задания «без преобразования»: http://publib.boulder.ibm.com/infocenter/idshelp/v10/index.jsp?topic=/com.ibm.sqls.doc/sqls17.htm Типичный синтаксический анализатор / лексер, такой как ANTLR / yacc / bison, кажется, не может справиться с такого рода вещами, у меня есть одна идея - преобразовать синтаксическую диаграмму в битовую карту символов и определитьфункционируют как more_up, move_down, влево, вправо или около того, чтобы пройти всю диаграмму, чтобы имитировать процесс понимания невооруженным глазом человека.Хотя это звучит недостаточно умело, я не нашел другого лучшего подхода.Кто-нибудь когда-нибудь играл с подобным сценарием?Может быть, вы могли бы пролить свет на это.

Заранее спасибо!

Answer 1

Я никогда не делал ничего подобного раньше, но вот как я бы подошел к этому.

Во-первых, я бы начал с чего-то вроде этого:

class CharGrid(object):
    def __init__(self, text):
        self.lines = text.split('\n')

    def __getitem__(self, pos):
        try:
            col, row = pos
        except (TypeError, ValueError):
            raise KeyError('%r not a 2-tuple' % (pos,))
        if row >= len(self.lines):
            return ' '
        line = self.lines[row]
        if col >= len(line):
            return ' '
        return line[col]

такчто я могу получить доступ к символам в тексте через 2D-координаты:

grid = CharGrid("""Creating a No-Conversion Job

>>-onpladm create job--job--+--------------+-- -n--------------->
                            '- -p--project-'

>-- -d--device-- -D--database-- -t--table----------------------->

   .---------------------------------------------------------------------.
   V                                                                     |
>----+-----------------------------------------------------------------+-+-><
     |                                                            (1)  |
     '-+-------------+--+-------------+--| Setting the Run Mode |------'
       '- -S--server-'  '- -T--target-'
""")

print ''.join((grid[0,0], grid[1,0], grid[2,0]))
print ''.join((grid[0,2], grid[1,2]))

(уступая)

Cre
>>

После этого задача будет преобразовывать 2D-сетку символов в 1Dпоследовательность символов:

1. считывание метки с первой строки
2. сканирование по первому столбцу до тех пор, пока вы не найдете >>
3. сканирование вправо от текущей позиции довы найдете [что угодно]

... и т. д. Следуйте диаграмме в порядке следования глаз.

Если у вас есть последовательность символов в 1D, вы можете использовать обычную технику разбора начто.

Answer 2

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

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

Вероятно, проще всего найти узлы, которые, вероятно, обозначены (см. Другой ответ) символами, представляющими точки ветвления на диаграмме (например, + ). Каждая дуга будет строкой символов, ведущих к изгибу дуги или к другому узлу. Следование таким строкам символов должно быть довольно простым (:-)) и может создать строку, представляющую дугу, даже если в ней есть изгибы.

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

Вы захотите перечислить каждую дугу, покидающую узел, и собрать строку, представляющую дугу.

Я бы подал струну дуги лексеру, чтобы разорвать его; он может иметь интересный контент (например, аннотацию в виде встроенной последовательности символов).

На данный момент у вас есть узлы и дуги со связанными аннотациями. Построить соответствующий граф из них должно быть довольно легко.