Как обрабатывать левую рекурсию в FParsec - PullRequest
Новая
       30

Как обрабатывать левую рекурсию в FParsec

4 голосов
/ 01 января 2012

В моих языках используются s-выражения с одной дополнительной функцией - оператором точки для доступа к элементам из массива или структуры.

В настоящее время мой анализатор работает с этим кодом с использованием оператора access - 

; Parition a sequence into a pair of sequences.
; NOTE: currently not tail-recursive.
[defRec partition [pred seq]
  (if (isDone seq)
      (pair (list) (list))
      (let (value (peek seq))
           (nextSeq (next seq))
           (nextResult (partition pred nextSeq))
           (nextResultFirst (access :m:first nextResult))
           (nextResultSecond (access :m:second nextResult))
           (if (pred value)
               (pair (cons value nextResultFirst) nextResultSecond)
               (pair nextResultFirst (cons value nextResultSecond)))))]

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

; Parition a sequence into a pair of sequences.
; NOTE: currently not tail-recursive.
[defRec partition [pred seq]
  (if (isDone seq)
      (pair (list) (list))
      (let (value (peek seq))
           (nextSeq (next seq))
           (nextResult (partition pred nextSeq))
           (nextResultFirst nextResult.first)
           (nextResultSecond nextResult.second)
           (if (pred value)
               (pair (cons value nextResultFirst) nextResultSecond)
               (pair nextResultFirst (cons value nextResultSecond)))))]

Они оба будут анализировать эквивалентный AST.Левая рекурсия здесь имеет значение, потому что выражение типа (f x).y должно анализироваться так же, как (access :m:y (f x))

Однако я не знаю, как заставить FParsec работать с этим типом леворекурсивного синтаксического анализа, или какие альтернативы япридется влево-рекурсия.

...