Как правильно использовать whileloop для возврата значения while while

Question

Цель состоит в том, чтобы написать генератор дерева разбора, который принимает в качестве входных данных арифметическое выражение типа string и выводит дерево разбора. В приведенных ниже кодах мы видим три взаимно рекурсивных метода expr (), term (), primary (). expr () должен возвращать дерево разбора, просматривая строку входного арифметического выражения. Правила разбора определены в Exp -> Term | {+ Term}, Term -> Primary * Primary, Primary -> a | b | c ... | z | (Exp). Коды могут генерировать правильное дерево разбора, если используется только один +. Например, для входной строки типа «a + b» коды выдают Exp ('+', Var a, Var b). Код не в выражении с более чем одним +. Например, a + b + c дает Exp ('+', Var a, Var b), но в действительности это должно быть Exp ('+', Var a, Exp ('+', Var b, Var c).

exception NotImplemented
type exptree = Var of char | Expr of char * exptree * exptree
let charSet =['a'; 'b'; 'c'; 'd'; 'e'; 'f'; 'g'; 'h'; 'i'; 'j'; 'k'; 'l'; 'm'; 'n'; 'o';
   'p'; 'q'; 'r'; 's'; 't'; 'u'; 'v'; 'w'; 'x'; 'y'; 'z'] 

let rec isin charr charlist =
match charlist with
| []-> false
|q::w -> if q=charr then true else isin charr w 

let parse (inputexp: string): exptree =
  let sym = ref inputexp.[0] in
  let cursor = ref 0 in

  let getsym () =
    cursor := !cursor + 1;
    sym := inputexp.[!cursor]
  in

  let rec expr (): exptree =
    let p = term() in
    match !sym with
    | '+' -> (getsym(); Expr ('+',p,term()))
    | _ -> p

  and term (): exptree =
    let p = primary() in
    match !sym with
    | '*' -> getsym() ;Expr ('*',p,primary())
    | _ -> p

  and primary (): exptree =
    if !sym = '('
    then begin
      getsym ();
      let result = expr () in
      if !sym <> ')' then
        failwith "Mismatched parens"
      else if !cursor = (String.length inputexp) - 1  then
        result
      else begin
        getsym ();
        result
      end
    end
    else
    if isin !sym charSet then
      if !cursor = (String.length inputexp) - 1 then
        Var !sym
      else
        let result = Var !sym in
        begin
          getsym ();
          result
        end
    else
      failwith "In primary"
  in
  expr ()

Так что это показывает, что у нас есть проблема, что expr не выходит за пределы первого + во входной строке. Хотя использование цикла while кажется многообещающим. Однако рекурсивный вызов возвращает дерево разбора после того, как он видит первый +, а не ищет следующий. Поэтому, пожалуйста, помогите решить эту проблему.

Answer 1

Если вы хотите вернуть значение из цикла while, вы можете использовать исключение. Вот пример, который использует цикл while true и выходит из него с помощью исключения, которое использует возврат в качестве полезной нагрузки

exception Finished of int

let compute m =
  let n = ref 0 in
  let r = ref 1 in
  try
    while true do
      if !n < m
      then begin
        r := !r + !r;
        incr n;
      end
      else
        raise_notrace (Finished !r)
    done;
    assert false
  with Finished x -> x;;

Обратите внимание, что мы должны добавить оператор assert false, чтобы сообщить компилятору, что эта строка кода недоступна. Если ваш цикл не является циклом while true и может завершаться как в обычном, так и в исключительном порядке, он будет выглядеть следующим образом:

let compute m =
  let n = ref 0 in
  let r = ref 1 in
  try
    while !n < m do
      incr n;
      r := !r + !r;
      if !r > 4096 then raise_notrace (Finished !r)
    done;
    !r
  with Finished x -> x;;

Обратите внимание, это, конечно, неидиоматический код для OCaml, мы предпочитаем использовать рекурсию для реализации рекурсивных алгоритмов. Кроме того, в отличие от других языков, OCaml предоставляет очень дешевые исключения, поэтому вызов исключения является таким же дешевым, как использование goto в C. Мы использовали оператор raise_notrace, чтобы вызвать исключение без записи обратной трассировки, чтобы гарантировать это.