4/15/14

Context-Free Grammars.

Context-Free Grammars can be used to check if character string belongs to context-free language. For example, if a written text is program in given programming language.

Such grammars generate a tree structure, such as AST - Abstract Syntax Tree, which has uses for example in writing parsers for compilers for programming languages.

Tree

Tree representing single production from grammar is called elementary tree. Any 'word' extension in grammar can be represented by elementary tree.

Tree representing this extension is created by joining elementary trees representing single productions that are part of word extension.

Grammar

Grammar G is G = (VN, VT, v0, P).

where:

* v0 is root node,
* vn is node from set of nonterminal symbols VN, or tree nodes that are not leaves.
* vt is node from set of terminal symbols VT, or tree nodes that are leaves.
* P is production set, production is one step of terminal symbol extension from root node v0. Production extends nonterminal symbol into an list(s) of terminal and nonterminal symbols.

Word generated by such context-free grammar is list of terminal symbols or leaf nodes that together make for example, for instruction in programming language.

for example:

if ( a == 2 ) a = 3;

is word, where terminal symbols are : if, (, ), a, ==, 2, =, 3, ;.

Extension is list of steps taken to acquire terminal symbol, starting from root node. Or a path in a tree. It consists of sequence of productions.


Example few productions that can be used as part of a single extension from a Grammar can be:


instruction -> conditional_instruction | assignment_instruction | iteration_instruction

conditional_instruction -> if ( logical_expression ) instruction ;

logical_expression -> logical_expression && logical_expression | logical_expression || logical_expression | true | false


these productions are too incomplete to form a fully working programming language.


Source: [7], BNF notation on Wikipedia.

No comments:

Post a Comment