(a) LEXICAL ANALYSER – (S) FINITE AUTOMATA
IN Lexical Analysis , finite automata are used to produce tokens or strings in the form of identifiers , keywords , constants from the program that will be stored in the symbol table and the lexical analyser plays a major role in their pattern recognition , as it identifies and provide token no. to the keywords in the symbol table .
(b) Code optimization – (P) DAG
at the syntax analyser, after generating the grammer in the form of syntax tree / derivation tree from the given token string and then at semantic analyser , it will create the modified parse tree with modified parse tree as input , intermediate code will be generated . That intermediate is optimized making it consume fewer resources (i.e. CPU , MEMORY ) so that faster running m/c code will result.(optimized intermediate code). DAG(DIRECTED ACYCLIC GRAPH ) gives a tree like view to identify the common strings and eliminate them thus saving up some memory and making it faster to run .
© Code generation – (Q) Syntax tree
Semantic analyser which created the modified parse tree using the grammer / tree , we generate an intermediate code which is m/c independent code which we can run on any system.
(D) Abelian Groups – (R) Push Down Automata
Abelian group consist of all those sets which should satisfy :-
Algebraic structure - which satisfy closure property
Semigroup - Associative property (a + b) + c = a + (b + c)
Monoid - Identity element property (a + e = a)
Group - inverse property with identity element as output ( a + b = b + a = e )
where a = b^-1 , b = a^-1
Abelian Group - It should satisfy the commutative property
(a + b) = (b + a)