Какова подходящая структура данных или алгоритм для создания неизменного конкретного синтаксического дерева функционально чистым способом?
Учитывая грамматику 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
Пожалуйста, обратите внимание
Я предложу хорошую награду за лучший ответ, так что не спешите. Ответы, которые просто публикуют ссылку, будут иметь меньший вес по сравнению с ответами, которые показывают код или содержат подробные объяснения.
Последнее замечание.
Я действительно новичок в такого рода вещах, поэтому не бойтесь называть меня дурачком.
3 ответа
Вы хотите проанализировать что-то в абстрактном синтаксическом дереве.
В чисто функциональном языке программирования Haskell вы можете использовать комбинаторы синтаксического анализатора для выражения своей грамматики. Вот пример, который анализирует крошечный язык выражений:
EDIT Используйте монадический стиль для соответствия книге Грэма Хаттона
-- 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] .
Серия блогов Эрика Липперта о неизменяемых двоичных деревьях может быть полезна. Очевидно, вам нужно дерево, которое не является двоичным, но оно даст вам общее представление.
Обязательно ознакомьтесь с подходом комбинатора монадического синтаксического анализатора; Я писал об этом в C # и в F # .