0
$\begingroup$

I've just found the finite state transducer.

Since the FST processes two tapes: one for input, one for output,

shouldn't it be possible to use FST to "pack together" some compiler stages, such as Syntactic Analysis and Semantic Analysis.

The FST could take in tokens and output semantically analysed code.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

How useful this would be depends on the level of the Chomsky hierarchy at which the transducer operates:

  • Regular languages:

A Finite State Automaton (FSA) is represented by its transitions (e.g. via a diagram or a list of triples) and the corresponding transducer can be seen as adding an output to each of the transitions.

Hence, the output is at the same 'granularity' as the input alphabet, which may not always be what's desired for associating semantics with syntax.

The issue is not so much with the `redundant (epsilon) outputs' as the possible need to make semantic decisions at the level of sequences of syntactic elements, modeled in regular languages by a (necessarily fairly messy) nested transducer scheme.

  • Context-free grammars

More usefully than for regular languages, it is possible to use syntax-directed translation which can be seen as a `transducing' scheme associating a semantic output with a grammatical production.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I did think that but was thinking of e.g. adding "epsilons" (empty string) to the outputs that aren't required. Then possibly even filtering them out. $\endgroup$
    – mavavilj
    Dec 25, 2015 at 23:49
  • $\begingroup$ @mavavilj - is the revised answer above of any greater help? $\endgroup$
    – NietzscheanAI
    Dec 26, 2015 at 8:33
  • $\begingroup$ What's the difference between syntax-directed translation and the FST? $\endgroup$
    – mavavilj
    Dec 26, 2015 at 9:02
  • $\begingroup$ @mavavilj - answer now revised to make the distinction explicit. $\endgroup$
    – NietzscheanAI
    Dec 26, 2015 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.