 |
CS 3723 Programming Languages |
RE Simulator | |
 RE Simulator Process .pdf, .png | 1. Parser: Unravel the syntax of the RE: what operators to apply to what operands, and in what order. The syntax is implicit in the RPN form. In a couple of weeks we'll give explicit code for a parser for REs. This code would allow us to combine steps 1 and 2, skipping the RPN. 2. Translate to NFA with ε-moves: This work is shown for a slightly more complex RE on the page: RE−−>NFA. This is shown in the diagram as a simple NFA with no ε-moves, but in this case as as with most cases, it would be more complex and have numerous ε-moves. 3. Subset Construction: Translating an arbitrary NFA to a DFA was the topic of H2: Subset Alg. (without ε-moves) and of H4: NFAs with ε-moves (with ε-moves). 4a. DFA Simulator (requires Step 3): For a specific example, this was the topic of H1: Doubles. 4b. NFA Simulator (skip Step 3): This is very similar to the subset construction, except that we handle each step separately and save only the current subset as we construct the next one. |