Compiler

Introduction to compiler

Regex - NFA - DFA

@ Regex-to-NFA (Link) - transforming a regular expression into an equivalent nondeterministic finite automaton.

@ NFA-to-DFA (Link 1 | Link 2) - converting a nondeterministic finite automaton into a equivalent deterministic finite automaton.

@ DFA minimization (Link) - transforming a given deterministic finite automaton (DFA) into an equivalent DFA that has a minimum number of states.

References

The following links can help you when dealing with regexes:

1. Regular-Expressions.info - Regex Tutorial, Examples and Reference - Regex Patterns
2. Regular Expression Library (great site with lots of regexes and an excellent regex tester) (Link 1 | Link 2)
3. DFA minimization (ITMO Link | Youtube example)

@ Graphviz - Drawing graphs with dot.

CFG

@ What is a CFG? (Read more)

@ Left recursion in CFG problem

    In the formal language theory of computer science, left recursion is a special case of recursion where a string is recognized as part of a language by the fact that it decomposes into a string from that same language (on the left) and a suffix (on the right).

@ Types of left recursion

1. Direct left recursion

       A → Aα
   

2. Indirect left recursion

       A → BC
       B → A
   

3. Hidden left recursion

       A → BA
       B → 𝜀
   

@ Elimination of Left-Recursion

• External links:

1. https://en.wikipedia.org/wiki/Left_recursion
2. https://web.cs.wpi.edu/~kal/PLT/PLT4.1.2.html
3. ELR - ITMO University

• See also

1. CYK Algorithm
2. LL Parser

@ Elimination useless symbols in CFG

• Documentation: Algorithm 2.9 (p. 171) - The theory of parsing, translation and compiling (Vol. 1, 1972 Ru-version).