Блог

Я пытаюсь создать комбинаторы синтаксического анализа, следуя Хаттону и Мейеру, «Комбинаторам монадического синтаксического анализа». Моя реализация в PostScript, но я думаю, что моя проблема является общей для анализаторов комбинаторов, а не для моей конкретной реализации.

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

 (pc9.ps)run

/Dot         (.) char         def
/Meta        (* ?) anyof      def
/Character   (* ?.|()) noneof def

/Atom        //Dot
             //Character  plus  def
/Factor      //Atom  //Meta maybe  seq   def
/Term        //Factor  //Factor many  seq  def
/Expression  //Term  (|) char //Term xthen  many  seq  def

/regex { string-input //Expression exec ps } def

(abc|def|ghi) regex 

quit
  

Это работает, но на выходе много [] пустых массивов, которые действительно мешают, когда я пытаюсь с помощью bind обработчиков обработать значения.

 $ gsnd -q -dNOSAFER pc9re2.ps
stack:
[[[[[97 []] [[98 []] [[99 []] []]]] [[[100 []] [[101 []] [[102 []]
[]]]] [[[103 []] [[104 []] [[105 []] []]]] []]]] null]]
  

Это происходит всякий раз, когда seq комбинатор последовательности принимает результат из maybe or many (который использует maybe ), который имел нулевые вхождения.

Каков обычный способ исключения этого дополнительного шума в выходных данных с помощью комбинаторов синтаксического анализа?

репозиторий github

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

Редактировать: я снова столкнулся с той же проблемой в версии 11 (с половиной). Теперь у меня есть лучшее решение, IMO:

https://groups.google.com/g/comp.lang.functional/c/MbJxrJSk8Mw/m/MoT3Dr0IAwAJ

Тьфу. Я думаю, что это даже не было проблемой X / Y. Это было «доктор, мне больно, когда я двигаю рукой вот так; … так что не двигайте рукой, как эта » проблема.

Я хочу, чтобы «результирующая» часть структуры «reply» (используя новые термины, следующие из документа Parsec) была любого из / обычных / типов PostScript: integer, real, string, boolean, array, dictionary.

Но мне также нужен какой-то способ произвольного объединения двух объектов независимо от типа. Мой then (он же seq ) комбинатор должен это сделать. Итак, я создал взломанную функцию, которая выполняет объединение. Если у него два массива, он объединяет содержимое в более длинный массив. Если у него есть один массив и какой-либо другой объект, он расширяет массив на единицу и помещает объект спереди или сзади соответственно. Если у него есть два объекта, не являющихся массивами, он создает новый массив из двух элементов, содержащий их.

Таким образом, вместо того, чтобы xthen и thenx отключаться от then и нуждаться в cons, car и cdr, я могу записать все 3 из них как более общую параметризованную функцию.

 sequence{ p q u }{
  { /p exec  is-ok {
      next x-xs force /q exec  is-ok {
        next x-xs 3 1 roll /u exec exch consok
      }{
        x-xs 3 2 roll ( after ) exch cons exch cons cons
      } ifelse
    } if } ll }  @func
then { {append} sequence }
xthen { {exch pop} sequence }
thenx { {pop} sequence }

append { 1 index zero eq { exch pop }{
                  dup zero eq { pop }{
         1 index type /arraytype eq {
             dup type /arraytype eq { compose }{ one compose } ifelse
         }{ dup type /arraytype eq { curry }{ cons } ifelse } ifelse } ifelse } ifelse }
  

@func это мое собственное нестандартное расширение к PostScript, которое принимает
тело процедуры и список параметров и завершает процедуру с
код, который определяет аргументы в локальном словаре. ll мой
взломанный PostScript способ создания лямбд с жестко исправленными параметрами,
это сокращение от load all literals. )

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