Есть ли более эффективный способ вычислить номер следующей строки / столбца из многострочного токена?

Question

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

module Program =            

    type Token = { value:string; line:int; column:int; }

    let lineTerminators = set ['\u000A'; '\u000D'; '\u2028'; '\u2029']

    let main () =

        let token = { value = "/*\r\n *\r\n *\r\n \n */"; line = 1; column = 1; }

        let chars = token.value.ToCharArray()

        let totalLines =
            chars
            |> Array.mapi(
                fun i c ->
                    if not (lineTerminators.Contains c)  then 
                        0 
                    else
                        if c <> '\n' || i = 0 || chars.[i - 1] <> '\r' then 
                            1 
                        else 
                            0
            )
            |> Array.sum

        let nextLine = token.line + totalLines

        let nextColumn =
            if totalLines = 0 then 
                token.column + token.value.Length 
            else
                1 + (chars 
                     |> Array.rev 
                     |> Array.findIndex lineTerminators.Contains)


        System.Console.ReadKey true |> ignore

    main()

Answer 1

Одна проблема с вашей реализацией заключается в том, что изначально кажется, что все разделители строк являются просто односимвольными символами, но на самом деле это не так - если вы рассматриваете "\ r \ n" как разделитель из одной строки (составленный из 2 символов) ), тогда ситуация должна быть более понятной. Например, я бы объявил терминаторы следующим образом:

let terminators = [ ['\r'; '\n']; ['\r']; ['\n'] ]

Порядок является существенным - если мы сначала находим "\ r \ n", то мы хотим пропустить 2 символа (чтобы мы не считали следующий символ '\ n' как следующий терминатор). К сожалению, «пропустить 2 символа» немного сложно - это невозможно сделать с помощью функции mapi, которая вызывает функцию для каждого элемента.

Прямая реализация с использованием рекурсивной функции может выглядеть следующим образом:

let input = "aaa\nbbb\r\nccc" |> List.ofSeq

// Returns Some() if input starts with token (and the returned
// value is the rest of the input with the starting token removed)
let rec equalStart input token = 
  match input, token with
  | _, [] -> Some(input) // End of recursion
  | a::input, b::token when a = b -> equalStart input token // Recursive call
  | _ -> None // Mismatch

// Counts the number of lines...
let rec countLines count input = 
  // Pick first terminator that matches with the beginning of the input (if any)
  let term = terminators |> List.tryPick (equalStart input)
  match term, input with 
  | None, _::input -> countLines count input  // Nothing found - continue
  | None, [] -> count + 1 // At the end, add the last line & return
  | Some(rest), _ -> countLines (count + 1) rest  // Found - add line & continue

Если вы использовали какую-то библиотеку комбинаторов синтаксического анализа (например, FParsec ), то вы могли бы использовать встроенные парсеры для большинства вещей. Я на самом деле не пробовал это, но вот грубый набросок - вы можете сохранить список терминаторов в виде списка строк и сгенерировать парсер для каждой строки:

let terminators = [ "\r\n"; "\r"; "\n" ]
let parsers = [ for t in terminators -> 
                  parser { let! _ = pstring t  
                           return 1 } ] // Return '1' because we found next line

Это дает вам список анализаторов, которые возвращают 1, когда в конце есть терминатор - теперь вы можете объединить их все, используя <|> (или комбинатор), а затем запустить составной синтаксический анализатор. Если это не помогло, вы можете пропустить первый символ (объединить его с другим анализатором) и продолжить рекурсивно. Единственная проблема состоит в том, что комбинаторы синтаксического анализатора обычно возвращают все возможные деривации («\ r \ n» можно интерпретировать как два переноса строки ..), поэтому вам нужно получить только первый результат ...

(Из вашего вопроса не было ясно, действительно ли вы хотите использовать какую-то библиотеку комбинаторов синтаксического анализа или нет, поэтому я не стал подробно останавливаться на этой теме - если вам интересно, вы можете попросить более подробную информацию ... .)