GitHub - karimmerhom/compilers-lab-1: Task1: This task is the implementation of a deterministic finite automaton (DFA) abstract data type. Recall that a DFA is a quintuple (Q, Σ, δ, q0, F): Q is a non-empty, finite set of states; Σ is non-empty, finite set of symbols (an alphabet); δ : Q × Σ −→ Q is the transition function; q0 ∈ Q is the start state; and F ⊆ Q is the set of accept states. A DFA accepts a string w = w1w2 · · · wn ∈ Σ ∗ if there is a sequence r0, r1, . . ., rn of states such that (i) r0 = q0, (ii) rn ∈ F, and (iii) δ(ri , wi+1) = ri+1, for every 0 ≤ i < n. Task2: This task is the implementation of the classical algorithm for constructing a deterministic finite automaton (DFA) equivalent to a non-deterministic finite automaton (NFA). Recall that an NFA is a quintuple (Q, Σ, δ, q0, F): Q is a non-empty, finite set of states; Σ is non-empty, finite set of symbols (an alphabet); δ : Q × (Σ ∪ {ε}) −→ P(Q) is the transition function; q0 ∈ Q is the start state; and F ⊆ Q is the set of accept states. Given a description of an NFA, you need to construct an equivalent DFA. Task4: This task is the implementation of a fallback deterministic finite automaton with actions (FDFA) abstract data type. Recall that an FDFA is a sextuple (Q, Σ, δ, q0, F, A): Q is a nonempty, finite set of states; Σ is non-empty, finite set of symbols (an alphabet); δ : Q×Σ −→ Q is the transition function; q0 ∈ Q is the start state; F ⊆ Q is the set of accept states; and A is function that maps every state in Q to an action. Refer to the slides of Lecture 2 of CSEN1003 for more details about the operation of FDFA. Task5: This task is the implementation of the context-free grammar (CFG) left-recursion elimination algorithm introduced in Lecture 3 of CSEN1003. Recall that a CFG is a quadruple (V, Σ, R, S) where V and Σ are disjoint alphabets (respectively, containing variables and terminals), R ⊆ V × (V ∪ Σ)∗ is a set of rules, and S ∈ V is the start variable. Task6: This task is the implementation of the algorithms computing the functions First and Follow, introduced in Lecture 4 of CSEN1003, for the variables of a given context-free grammar. Recall that a CFG is a quadruple (V, Σ, R, S) where V and Σ are disjoint alphabets (respectively, containing variables and terminals), R ⊆ V ×(V ∪ Σ)∗ is a set of rules, and S ∈ V is the start variable. Task7: This task is the implementation of an LL(1) parser using pushdown automata (PDA) and predictive parsing tables. Given an input context-free grammar G = (V, Σ, R, S), along with the First and Follow sets for all rules, you need to (i) construct the predictive parsing table for G, (ii) construct the PDA equivalent to G, and (iii) implement an LL(1) parser for G which makes use of the table and the PDA to direct its decisions. Given an input string w, the parser should signal an error if w /∈ L(G) and produce a derivation of w from S if w ∈ L(G).

karimmerhom / compilers-lab-1 Public

Notifications You must be signed in to change notification settings
Fork 1
Star 1

Task1: This task is the implementation of a deterministic finite automaton (DFA) abstract data type. Recall that a DFA is a quintuple (Q, Σ, δ, q0, F): Q is a non-empty, finite set of states; Σ is non-empty, finite set of symbols (an alphabet); δ : Q × Σ −→ Q is the transition function; q0 ∈ Q is the start state; and F ⊆ Q is the set of accept s…