Я очень рекомендую F # язык как ваш язык выбора для синтаксического анализа на платформе .NET. Корни в семействе языков ML означают, что он отлично поддерживает языковое программирование.
Дискриминационные союзы и сопоставление образцов позволяют получить очень сжатую и мощную спецификацию вашего АСТ. Функции более высокого порядка позволяют определять операции разбора и их состав. Первоклассная поддержка монадических типов позволяет управлять государственным управлением, неявно значительно упрощая состав парсеров. Мощный тип-вывод значительно помогает определению этих (сложных) типов. И все это можно указать и выполнить в интерактивном режиме, что позволяет быстро прототипировать.
Стефан Тольксдорф поставил это на практике его синтаксического анализа библиотеки комбинатора FParsec
Из его примеров мы видим, как естественно задана АСТ:
type expr =
| Val of string
| Int of int
| Float of float
| Decr of expr
type stmt =
| Assign of string * expr
| While of expr * stmt
| Seq of stmt list
| IfThen of expr * stmt
| IfThenElse of expr * stmt * stmt
| Print of expr
type prog = Prog of stmt list
реализация парсера (частично Опущенные) является так же, как сжатое:
let stmt, stmtRef = createParserForwardedToRef()
let stmtList = sepBy1 stmt (ch ';')
let assign =
pipe2 id (str ":=" >>. expr) (fun id e -> Assign(id, e))
let print = str "print" >>. expr |>> Print
let pwhile =
pipe2 (str "while" >>. expr) (str "do" >>. stmt) (fun e s -> While(e, s))
let seq =
str "begin" >>. stmtList .>> str "end" |>> Seq
let ifthen =
pipe3 (str "if" >>. expr) (str "then" >>. stmt) (opt (str "else" >>. stmt))
(fun e s1 optS2 ->
match optS2 with
| None -> IfThen(e, s1)
| Some s2 -> IfThenElse(e, s1, s2))
do stmtRef:= choice [ifthen; pwhile; seq; print; assign]
let prog =
ws >>. stmtList .>> eof |>> Prog
на второй линии, в качестве примера, и stmtch - синтаксические анализаторы, а sepBy1 - это комбинатор синтаксического анализатора, который принимает два простых синтаксических анализатора и возвращает парсер комбинаций. В этом случае sepBy1 p sep возвращает парсер, который анализирует один или несколько вхождений p, разделенных sep. Таким образом, вы можете увидеть, как быстро мощный синтаксический анализатор можно объединить с простыми парсерами. Поддержка F # для переопределенных операторов также допускает краткую инфиксную нотацию, например. комбинатор последовательности и комбинатор выбора могут быть указаны как >>. и <|>.
удачи,
Дэнни
Саймон, я просматриваю ваши сообщения, и вы упоминаете, что вы «решили сделать это вручную». Вы интересуетесь упражнением здесь, чтобы узнать о синтаксическом анализе, или вы после семантически правильного, поддерживаемого, быстрого парсера для использования? Если последнее, я считаю, что ваше решение было преждевременным. Вы будете так привязаны к логике синтаксического анализа, что вы скоро забудете о «немногих случаях края», которые вы решили исправить. –
Последний. Мы пошли по маршруту генератора-генератора и оказались с тем, чего мы не понимаем, и поэтому не можем исправить. Я бы предпочел, чтобы на месяцы работы было что-то, но которое можно исправить, чем что-то быстрое, чего нет. – Simon
Я немного озадачен этим. Вы недостаточно знакомы с тем, как работают генераторы парсеров? Вы не должны играть с сгенерированным кодом вообще, если вы сделали это правильно. – Eric