13-03-2017, 03:52 PM
Grammar without context
A context-free grammar (CFG) is a set of recursive rewriting rules (or productions) used to generate string patterns.
A CFG consists of the following components:
• a set of terminal symbols, which are the characters of the alphabet that appear in the strings generated by the grammar.
• a set of non-terminal symbols, which are position markers for terminal symbol patterns that can be generated by non-terminal symbols.
• a set of productions, which are rules for replacing (or rewriting) non-terminal symbols (on the left side of production) in a string with other non-terminal or terminal symbols (on the right side of production).
• a start symbol, which is a special non-terminal symbol that appears in the initial string generated by the grammar.
To generate a string of terminal symbols from a CFG, we:
• Start with a string consisting of the start symbol;
• Apply one of the productions with the start symbol in the left hand size, replacing the start symbol with the right side of the production;
• Repeat the process of selecting non-terminal symbols in the chain and replace them with the right side of a corresponding production until all non-terminal terminals have been replaced by terminal symbols.
A context-free grammar (CFG) is a set of recursive rewriting rules (or productions) used to generate string patterns.
A CFG consists of the following components:
• a set of terminal symbols, which are the characters of the alphabet that appear in the strings generated by the grammar.
• a set of non-terminal symbols, which are position markers for terminal symbol patterns that can be generated by non-terminal symbols.
• a set of productions, which are rules for replacing (or rewriting) non-terminal symbols (on the left side of production) in a string with other non-terminal or terminal symbols (on the right side of production).
• a start symbol, which is a special non-terminal symbol that appears in the initial string generated by the grammar.
To generate a string of terminal symbols from a CFG, we:
• Start with a string consisting of the start symbol;
• Apply one of the productions with the start symbol in the left hand size, replacing the start symbol with the right side of the production;
• Repeat the process of selecting non-terminal symbols in the chain and replace them with the right side of a corresponding production until all non-terminal terminals have been replaced by terminal symbols.
