Compiler Design - Definitions
Lexical analysis
Lexical analyzer reads the source program character by character and returns the tokens of the source program. The tokens represent pattern of characters which have the same meaning such as identifiers, operators, numbers and etc.
Syntax analysis
Syntax analyzer re-combine the tokens and create a graphical representation of the syntactic structure (syntax tree). In addition to that, it rejects the invalid string by reporting the syntax error.
In syntax tree the terminals are at the leave nodes and the inner nodes are non-terminals
Context-free grammar
Context-free grammar is a set of rules for putting strings together and so correspondent to a language.
Parse tree
Parse tree is a ordered rooted tree that graphically represents the semantic of a string derived from a context free grammar.
Top-Down approach
It starts from the start symbol(root) and goes down to leaves using production rules.
Bottom-Up approach
It starts from the leave and proceeds upwards to the root which is a starting symbol.
Left most derivation
A left most derivation is obtained by applying the production to the left most variable or left most non terminal in each step.
Right most derivation
A right most derivation is obtained by applying the production to the right most variable or right most non terminal in each step.
Ambiguous grammar
A grammar is said to be ambiguous if any string generated by it has more than one parse tree or derivation tree or syntax tree or left most derivation or right most derivation.
Unambiguous grammar
A grammar is said to be unambiguous if a string generated by it has exactly one parse tree or derivation tree or syntax tree or left most derivation or right most derivation.
Left recursion
A production of a grammar is said to have left recursion if the left most variable or non-terminal of the right hand side is same as the variable or non-terminal of the left hand side.
Right recursion
A production of a grammar is said to have right recursion if the right most variable or non-terminal of the right hand side is same as the non-terminal or variable of left hand side.
Associativity
If an operand has operators on both side, then the side on which the operator takes the operand is associativity of that operator.
Precedence
Precedence determines which part operator is performed first in an expression with more than one operators with different precedence level.
Left factorization
In left factorizing, it is not clear that which of the two alternative production to use expand a non-terminal that is A -> ab/ac.
0 comments:
Post a Comment