Как реализовать регулярное выражение / cat [s]? (\ B | $) / с корректировкой ragel? - PullRequest
Новая
       41

Как реализовать регулярное выражение / cat [s]? (\ B | $) / с корректировкой ragel?

0 голосов
/ 09 января 2020

Я хочу ускорить свою программу, написанную на Go и преобразовать регулярные выражения в конечные автоматы с ragel. Я не могу понять, как правильно сопоставить конец ввода при преобразовании регулярных выражений, подобных /cat[s]?(\b|$)/ (оно соответствует границе слова или концу ввода), поэтому я сделал этот обходной путь: 

package main

import(
  "strings"
  "fmt"
  "unicode"
)

func Match(data []byte) bool {
  data = []byte(strings.ToLower(string(data)))

  %%{
    machine test;
    write data;
  }%%

  cs, p, pe, eof := 0, 0, len(data), len(data)
  _ = eof

  var matchPos int

  %%{
    main := ('cat' 's'?) @{matchPos = p};

    write init;
    write exec;
  }%%

  return checkMatch(data, matchPos+1)
}

func checkMatch(data []byte, p int) bool {
  if p == len(data) {
    return true
  }
  tail := string(data[p:])
  c := []rune(tail)[0]
  if !unicode.IsLetter(c) && !unicode.IsDigit(c) {
    return true
  }
  return false
}

func main () {
  vs := []string{
    "cat",
    "cats",
    "cat and dog",
    "cats and dogs",
    "caterpillar",
  }
  for _, v := range vs {
    fmt.Printf("'%s': %v\n", v, Match([]byte(v)))
  }
}

Finite State Machine Graph

вывод правильный: 

'cat': true
'cats': true
'cat and dog': true
'cats and dogs': true
'caterpillar': false

Я думаю, что есть лучший способ. Что такое «правильный» способ обработки конца ввода с помощью ragel?

1 Ответ

1 голос
/ 10 января 2020

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

  var matched bool

  %%{
    action setMatched {
      matched = true
    }

    main := ('cat' 's'?) %/setMatched ([ \t] >setMatched);

    write init;
    write exec;
  }%%
  // Variable generated and not used by Ragel.
  _ = _test_trans_actions

  return matched

, которая производит следующий вывод (обратите внимание на один важный добавленный тестовый пример): 

'cat': true
'cats': true
'cat and dog': true
'cats and dogs': true
'catspaw': false
'caterpillar': false

И работает как это: enter image description here

Это добавляет setMatched действие, которое запускается EOF в одном из конечных состояний (%/setMatched) первой машины (cats?) или после ввода (>setMatched) второго (который почти \b, но на самом деле может быть заменен внутренним space автоматом). И это полностью исключает необходимость checkMatch.

...