Как выполнять итерацию по лесу синтаксического анализа Marpa, а не по его деревьям синтаксического анализа?

Скажем, у меня есть хорошая неоднозначная грамматика Марпа и хорошая неоднозначная входная строка.

Я могу разобрать строку с помощью Marpa и в итоге получить синтаксический лес. Я даже могу перебирать каждое дерево синтаксического анализа в лесу.

Но как я могу перебирать «вдоль» леса синтаксического анализа?

Чтобы описать, что я имею в виду:

Лес синтаксического анализа — это своего рода граф, который может иметь узлы, в которых альтернативы отделяются, и узлы, в которых альтернативы снова объединяются в «основной поток».

Скажем, это альтернативные деревья синтаксического анализа одного леса синтаксического анализа:

  • A B1 C
  • A B2 C
  • A B3 B4 C

Есть основной поток A ... C, но неоднозначный участок B.

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

Какие подходы можно использовать для итерации по цепочке однозначных и неоднозначных узлов?

На самом деле я могу вывести весь график?


ambiguity parse-tree ambiguous-grammar parse-forest marpa
person hippietrail    schedule 18.09.2014    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Этот суть показывает 2 примера (базовый и расширенный) перебора узлов ASF для получения списка сериализованные AST.

Оба основаны на коде набора тестов Marpa::R2 (cpan/t/sl_panda(1).t).

Надеюсь, поможет.

P.S. Этот суть, вероятно, послужит вам лучше — он печатает все узлы ASF в порядке посещения — вы можете использовать

$spans->{ $literal }->{ $start }

hash, чтобы увидеть, является ли узел неоднозначным или нет, и построить график оттуда на основе интервалов промежутка ($ start, $ start + $ length), чтобы построить дочерние/родительские связи.

person rns    schedule 18.09.2014
comment
rns — продвинутый пользователь новых ASF — на данный момент у него больше реального опыта их использования, чем у меня. - person Jeffrey Kegler; 18.09.2014

arrow_upward
1
arrow_downward

Интерфейс для этого только что перешел из альфа-версии в стабильную версию Marpa::R2, так что вопрос очень своевременный. Посмотрите на https://metacpan.org/pod/distribution/Marpa-R2/pod/ASF.pod и https://metacpan.org/pod/distribution/Marpa-R2/pod/Glade.pod.

Можете ли вы вывести весь график? Да, но это легко обеспечить. Сложной частью было придумать хороший способ детализировать интересующие части без экспоненциального роста.

Кстати, здесь может вмешаться еще один эксперт Marpa, у которого на данный момент больше опыта работы с моим интерфейсом, чем у меня. Возможно, вы хотели бы немного подождать его ответа, который вам может понравиться больше, чем мой. :-)

person Jeffrey Kegler    schedule 18.09.2014
comment
Я использую ASF, но приведенный здесь пример дал мне возможность итерации по каждому альтернативному синтаксическому анализу леса, а не по графу. Я не уверен, то ли я упустил ту функцию ASF, которую ищу, то ли я не смог объяснить свою проблему... - person hippietrail; 18.09.2014
comment
На самом деле похоже, что то, что мне нужно, вероятно, находится там, но требует некоторого глубокого чтения и знакомства с кучей концепций и терминологии, чтобы понять это. - person hippietrail; 18.09.2014
comment
Чтобы преодолевать двусмысленности, вы должны понимать, что они бывают разных видов. Я был удивлен, обнаружив, что это мало исследовано в литературе - обход деревьев синтаксического анализа является очень стандартной вещью во многих текстах, но леса синтаксического анализа - это новая территория. Большая часть документации ASF и Glade разработана заново. - person Jeffrey Kegler; 18.09.2014