diff options
| author | bringert <unknown> | 2005-09-08 14:39:12 +0000 |
|---|---|---|
| committer | bringert <unknown> | 2005-09-08 14:39:12 +0000 |
| commit | 9508120dd1afa7494a6c9eb7d117a69370a933e0 (patch) | |
| tree | d912a4cda3c973a909ba99ee7338a06624d79dcd /src/GF/Speech/TransformCFG.hs | |
| parent | 982a5222726831d60f046fdeff91461ff610c6c5 (diff) | |
Defined compileAutomaton in terms of make_fa
Diffstat (limited to 'src/GF/Speech/TransformCFG.hs')
| -rw-r--r-- | src/GF/Speech/TransformCFG.hs | 23 |
1 files changed, 18 insertions, 5 deletions
diff --git a/src/GF/Speech/TransformCFG.hs b/src/GF/Speech/TransformCFG.hs index 9c3ed2c06..0b4b680f8 100644 --- a/src/GF/Speech/TransformCFG.hs +++ b/src/GF/Speech/TransformCFG.hs @@ -5,9 +5,9 @@ -- Stability : (stable) -- Portability : (portable) -- --- > CVS $Date: 2005/09/07 14:21:31 $ +-- > CVS $Date: 2005/09/08 15:39:12 $ -- > CVS $Author: bringert $ --- > CVS $Revision: 1.16 $ +-- > CVS $Revision: 1.17 $ -- -- This module does some useful transformations on CFGs. -- @@ -134,9 +134,22 @@ mutRecCats g = equivalenceClasses $ symmetricSubrelation $ transitiveClosure $ r -- Convert a strongly regular grammar to a finite automaton. compileAutomaton :: Cat_ -- ^ Start category - -> CFRules - -> FA () (Maybe Token) -compileAutomaton s g = undefined + -> CFRules + -> FA () (Maybe Token) +compileAutomaton start g = make_fa s [Cat start] f g fa'' + where fa = newFA () + s = startState fa + (fa',f) = newState () fa + fa'' = addFinalState f fa' + +-- | The make_fa algorithm from \"Regular approximation of CFLs: a grammatical view\", +-- Mark-Jan Nederhof. International Workshop on Parsing Technologies, 1997. +make_fa :: State -> [Symbol Cat_ Token] -> State + -> CFRules -> FA () (Maybe Token) -> FA () (Maybe Token) +make_fa q0 a q1 g fa = + case a of + [] -> newTrans q0 Nothing q1 fa + [Tok t] -> newTrans q0 (Just t) q1 fa -- -- * CFG rule utilities |