1grammar::fa::dacceptorF(inn)ite automaton operations and ugsraagmemar::fa::dacceptor(n)
2______________________________________________________________________________
6
8 grammar::fa::dacceptor - Create and use deterministic acceptors
9
11 package require Tcl 8.4
12 package require snit
14 package require struct::set
16 package require grammar::fa::dacceptor ?0.1.1?
18 ::grammar::fa::dacceptor daName fa ?-any any?
20 daName option ?arg arg ...?
22 daName destroy
24 daName accept? symbols
26______________________________________________________________________________
28
30 This package provides a class for acceptors constructed from determin‐
31 istic finite automatons (DFA). Acceptors are objects which can be given
32 a string of symbols and tell if the DFA they are constructed from would
33 accept that string. For the actual creation of the DFAs the acceptors
34 are based on we have the packages grammar::fa and grammar::fa::op.
35
37 The package exports the API described here.
38 ::grammar::fa::dacceptor daName fa ?-any any?
40 Creates a new deterministic acceptor with an associated global
41 Tcl command whose name is daName. This command may be used to
42 invoke various operations on the acceptor. It has the following
43 general form:
44 daName option ?arg arg ...?
46 Option and the args determine the exact behavior of the
47 command. See section ACCEPTOR METHODS for more explana‐
48 tions.
49 The acceptor will be based on the deterministic finite
51 automaton stored in the object fa. It will keep a copy of
52 the relevant data of the FA in its own storage, in a form
53 easy to use for its purposes. This also means that
54 changes made to the fa after the construction of the
55 acceptor will not influence the acceptor.
56 If any has been specified, then the acceptor will convert
58 all symbols in the input which are unknown to the base FA
59 to that symbol before proceeding with the processing.
60
62 All acceptors provide the following methods for their manipulation:
63 daName destroy
65 Destroys the automaton, including its storage space and associ‐
66 ated command.
67 daName accept? symbols
69 Takes the list of symbols and checks if the FA the acceptor is
70 based on would accept it. The result is a boolean value. True is
71 returned if the symbols are accepted, and False otherwise. Note
72 that bogus symbols in the input are either translated to the any
73 symbol (if specified), or cause the acceptance test to simply
74 fail. No errors will be thrown. The method will process only
75 just that prefix of the input which is enough to fully determine
76 (non-)acceptance.
77
80 This document, and the package it describes, will undoubtedly contain
81 bugs and other problems. Please report such in the category grammar_fa
82 of the Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist]. Please
83 also report any ideas for enhancements you may have for either package
84 and/or documentation.
85 When proposing code changes, please provide unified diffs, i.e the out‐
87 put of diff -u.
88 Note further that attachments are strongly preferred over inlined
90 patches. Attachments can be made by going to the Edit form of the
91 ticket immediately after its creation, and then using the left-most
92 button in the secondary navigation bar.
93
95 acceptance, acceptor, automaton, finite automaton, grammar, parsing,
96 regular expression, regular grammar, regular languages, state, trans‐
97 ducer
98
100 Grammars and finite automata
101
103 Copyright (c) 2004 Andreas Kupries <andreas_kupries@users.sourceforge.net>
104tcllib 0.1.1 grammar::fa::dacceptor(n)