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

Question

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

Моя идея

symbol : either a token or a node

result : success or failure

token : a lexical token from source text
    value -> string : the value of the token
    type -> integer : the named type code of the token
    next -> token : reads the next token and keeps position of the previous token
    back -> token : moves back to the previous position and re-reads the token

node : a node in the syntax tree 
    type -> integer : the named type code of the node
    symbols -> linkedList : the symbols found at this node
    append -> symbol -> node : appends the new symbol  to a new copy of the node

Вот идея, о которой я думал. Основной проблемой здесь является обработка синтаксических ошибок. Я имею в виду, что могу остановиться на первой ошибке, но это не так.

let program token =
    sourceElements (node nodeType.program) token        

let sourceElements node token =
    let (n, r) = sourceElement (node.append (node nodeType.sourceElements)) token
    match r with
    | success -> (n, r) 
    | failure -> // ???     

let sourceElement node token =
    match token.value with
    | "function" -> 
        functionDeclaration (node.append (node nodeType.sourceElement)) token
    | _ -> 
        statement (node.append (node nodeType.sourceElement)) token 

Обратите внимание

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

Заключительная записка

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

Answer 1

Вы хотите проанализировать что-то в абстрактном синтаксическом дереве.

На чисто функциональном языке программирования Haskell вы можете использовать комбинаторы синтаксического анализатора для выражения вашей грамматики. Вот пример, который анализирует крошечный язык выражений:

РЕДАКТИРОВАТЬ Использовать монадический стиль, чтобы соответствовать книге Грэма Хаттона

    -- import a library of *parser combinators*
import Parsimony
import Parsimony.Char
import Parsimony.Error
(+++) = (<|>)

    -- abstract syntax tree
data Expr = I Int
          | Add Expr Expr
          | Mul Expr Expr
          deriving (Eq,Show)

    -- parse an expression
parseExpr :: String -> Either ParseError Expr
parseExpr = Parsimony.parse pExpr
    where

        -- grammar
    pExpr :: Parser String Expr
    pExpr = do
        a <- pNumber +++ parentheses pExpr  -- first argument
        do
            f <- pOp                        -- operation symbol
            b <- pExpr                      -- second argument
            return (f a b)
         +++ return a                       -- or just the first argument

    parentheses parser = do                 -- parse inside parentheses
        string "("
        x <- parser
        string ")"
        return x

    pNumber = do                            -- parse an integer
        digits <- many1 digit
        return . I . read $ digits

    pOp =                                   -- parse an operation symbol
         do string "+"
            return Add
        +++ 
         do string "*"
            return Mul

Вот пример запуска:

*Main> parseExpr "(5*3)+1"
Right (Add (Mul (I 5) (I 3)) (I 1))

Чтобы узнать больше о комбинаторах синтаксического анализа, см., Например, главу 8 книгу Грэма Хаттона "Программирование в Haskell" * или главу 16 из "Real World Haskell".

Многие библиотеки комбинатора синтаксического анализатора могут использоваться с разными типами токенов, как вы и собираетесь делать. Потоки токенов обычно представлены в виде списков токенов [Token].

Answer 2

Определенно проверьте подход монадического синтаксического анализатора;Я писал об этом в C # и в F # .

Answer 3

Серия блогов Эрика Липперта по неизменным двоичным деревьям может быть полезной.Очевидно, вам нужно дерево, которое не является двоичным, но оно даст вам общее представление.