Парсинг грамматик с помощью OCaml

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

Вы можете начать с определения структуры результирующего абстрактного синтаксического дерева путем определения типов. Это может быть что-то вроде этого:

type expr =
    | Operation of term * binop * term
    | Term of term
and term =
    | Num of num
    | Lvalue of expr
    | Incrop of incrop * expression
and incrop = Incr | Decr
and binop = Plus | Minus
and num = int

Тогда я бы реализовал парсер рекурсивного спуска. Конечно, было бы намного лучше, если бы вы могли использовать потоки в сочетании с препроцессором camlp4of ...

Кстати, в документации OCaml есть небольшой пример арифметических выражений. здесь .

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

exception Backtrack

let parse l =
  let rules = snd awksub_grammar in
  let rec descend gram l =
    let rec loop = function 
      | [] -> raise Backtrack
      | x::xs -> try attempt x l with Backtrack -> loop xs
    in
    loop (rules gram)
  and attempt branch (path,tokens) =
    match branch, tokens with
    | T x :: branch' , h::tokens' when h = x -> 
        attempt branch' ((T x :: path),tokens')
    | N n :: branch' , _ -> 
        let (path',tokens) = descend n ((N n :: path),tokens) in 
        attempt branch' (path', tokens)
    | [], _ -> path,tokens
    | _, _ -> raise Backtrack
  in
  let (path,tail) = descend (fst awksub_grammar) ([],l) in
  tail, List.rev path

Итак, первое, что вам следует сделать, это написать лексический анализатор. Это функция, которая принимает "исходные" входные данные, например ["3"; «-»; "("; "4"; "+"; "2"; ")"] , и разбивает его на список токенов (то есть представления терминальных символов).

Вы можете определить токен как

type token =
    | TokInt of int         (* an integer *)
    | TokBinOp of binop     (* a binary operator *)
    | TokOParen             (* an opening parenthesis *) 
    | TokCParen             (* a closing parenthesis *)     
and binop = Plus | Minus 

Тип функции лексера будет список строк -> список токенов , а вывод

lexer ["3"; "-"; "("; "4"; "+"; "2"; ")"]

будет примерно таким, как

[   TokInt 3; TokBinOp Minus; TokOParen; TokInt 4;
    TBinOp Plus; TokInt 2; TokCParen   ]

. Это упростит работу по написанию парсера, потому что вам не придется беспокоиться о том, чтобы распознать, что такое целое число, что такое оператор, и т. д.

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

Когда это будет сделано, вы можете написать более реалистичный лексический анализатор типа строка -> список токенов , который принимает фактические необработанные входные данные, такие как «3- (4 + 2)» и превращает его в список токенов.