search

mhorod / cacophony

Repo for epic compiler project made for Compilers course on TCS, JU
7 stars 0 forks source link

Implement function for combining DFAs into one #47

Closed km1chno closed 2 weeks ago

km1chno commented 3 weeks ago

We need a function with following signature

joinAutomata<State, Atom, Result>(
    automata: List<DFA<State, Atom, Boolean, Result>
): DFA<State, Atom, Result?>

This function is supposed to take a list of automata (where is state is just accepting or not), labeled with values of type Result and combine them into one automaton with states with generalized result(). The resulting automaton accepts exactly the union of languages accepted by automata on input, but also distinguishes accepting states for each Result.

In case we detect that the grammar is ambiguous (some state in resulting DFA has at least two possible result values), then we decided to throw an error ("Ooops! It looks like cacophony has an ambiguous grammar:(").