SkipCaptcha
265
edits
Changes
Jump to navigation
Jump to search
Line 195:
Line 195: − + + + + + + + + + + + + +
→Chomsky hierarchy: start detailing context-free grammars
Regular grammars or equivalent are widely used by [[compiler]]s in the lexical analysis of programming languages.
Regular grammars or equivalent are widely used by [[compiler]]s in the lexical analysis of programming languages.
===Level 2===
===Level 2: context-free grammar===
The transformation rules for context-free grammars don't appear that much different from those for regular grammars.
*Only a single non-terminal item can appear on the left-hand side of a rule.
*The right-hand side of any rule must be one of:
**[nothing].
**any combination of terminal items and non-terminal items.
The key difference is that in a regular grammar, any non-empty rule must effectively start with terminal item so that every rule transformation makes some immediate progress, while in a context-free grammar a rule could start with a non-terminal item which itself could be subject to arbitrary further transformations.
====Example====
This example shows how context-free grammars can cope with arithmetic expressions involving possibly nested brackets. Also an expression such as "2 + 3 * 4" could be interpreted as either "(2 + 3) * 4" or as "2 + (3 * 4)". The latter interpretation is that which is normally used - multiplication "*" is said to have a higher priority than addition "+" - so the example also needs to incorporate this priority concept into the grammar.
To avoid distracting side-issues, this example deals with numbers consisting solely of a single digit.
===Level 1===
===Level 1===