Commit | Line | Data |
---|---|---|

5f2eab64 JM |
1 | This code is structured roughly as follows: |

2 | ||

3 | xmalloc.c: | |

4 | - Wrappers for the malloc() functions, for error generation and | |

5 | memory leak checking purposes. | |

6 | ||

7 | tre-mem.c: | |

8 | - A simple and efficient memory allocator. | |

9 | ||

10 | tre-stack.c: | |

11 | - Implements a simple stack data structure. | |

12 | ||

13 | tre-ast.c: | |

14 | - Abstract syntax tree (AST) definitions. | |

15 | ||

16 | tre-parse.c: | |

17 | - Regexp parser. Parses a POSIX regexp (with TRE extensions) into | |

18 | an abstract syntax tree (AST). | |

19 | ||

20 | tre-compile.c: | |

21 | - Compiles ASTs to ready-to-use regex objects. Comprised of two parts: | |

22 | * Routine to convert an AST to a tagged AST. A tagged AST has | |

23 | appropriate minimized or maximized tags added to keep track of | |

24 | submatches. | |

25 | * Routine to convert tagged ASTs to tagged nondeterministic state | |

26 | machines (TNFAs) without epsilon transitions (transitions on | |

27 | empty strings). | |

28 | ||

29 | tre-match-parallel.c: | |

30 | - Parallel TNFA matcher. | |

31 | * The matcher basically takes a string and a TNFA and finds the | |

32 | leftmost longest match and submatches in one pass over the input | |

33 | string. Only the beginning of the input string is scanned until | |

34 | a leftmost match and longest match is found. | |

35 | * The matcher cannot handle back references, but the worst case | |

36 | time consumption is O(l) where l is the length of the input | |

37 | string. The space consumption is constant. | |

38 | ||

39 | tre-match-backtrack.c: | |

40 | - A traditional backtracking matcher. | |

41 | * Like the parallel matcher, takes a string and a TNFA and finds | |

42 | the leftmost longest match and submatches. Portions of the | |

43 | input string may (and usually are) scanned multiple times. | |

44 | * Can handle back references. The worst case time consumption, | |

45 | however, is O(k^l) where k is some constant and l is the length | |

46 | of the input string. The worst case space consumption is O(l). | |

47 | ||

48 | tre-match-approx.c: | |

49 | - Approximate parallel TNFA matcher. | |

50 | * Finds the leftmost and longest match and submatches in one pass | |

51 | over the input string. The match may contain errors. Each | |

52 | missing, substituted, or extra character in the match increases | |

53 | the cost of the match. A maximum cost for the returned match | |

54 | can be given. The cost of the found match is returned. | |

55 | * Cannot handle back references. The space and time consumption | |

56 | bounds are the same as for the parallel exact matcher, but | |

57 | in general this matcher is slower than the exact matcher. | |

58 | ||

59 | regcomp.c: | |

60 | - Implementation of the regcomp() family of functions as simple | |

61 | wrappers for tre_compile(). | |

62 | ||

63 | regexec.c: | |

64 | - Implementation of the regexec() family of functions. | |

65 | * The appropriate matcher is dispatched according to the | |

66 | features used in the compiled regex object. | |

67 | ||

68 | regerror.c: | |

69 | - Implements the regerror() function. |